regular expressions to direct dfas??

[magneeto]

hi,

currently i'm reading the book "compilers: principles, techniqes and tools" by AHO, SETHI & ULLMAN. the author(s) has written a technique to construct a dfa directly from a regular expression. i have read it a couple of times but still it's not clear to me. specially the function followpos() is really confusing. can anyone suggest a site where i can find a good note about this?i really need help in this. it may be difficult bcoz i'm not all that good in theory of computing.

-magneeto

[mehdi62b]

you need to be more specific,just asking something which I can't get is not the in forums' rules.
its better to post the relevant codes so we could be able to help you.

[magneeto]

sorry for not being specific.

we can convert a regular expression into a dfa by first converting it into a nfa(using thompson's construction). then we can convert the resulting nfa to a dfa using subset construction. the book i'm currently reading
(compilers: principles, techniqes and tools (the dragon book) by aho, sethi & ullman)
provides a method to directly construct a dfa from a regular expression. the method is (as stated in the book):

1.concatenate the regular expression with the unique symbol #.

2.build a syntax tree for the augmented expression (r)#.

3.construct the functions lastpos, firstpos, followpos and nullable .

if n is a node in the syntax tree then

firstpos(n) is the set of positions that can match the first symbol of a string generated by the subexpression rooted at n. likewise lastpos(n) gives the positions that can match the last symbol of such a string---here positions are the positions of symbols in the syntax tree.

next an algorithm is given to compute the states of the DFA but it does not mention how to compute the functions.

If anyone has read the book or about the topic ""From regular expression to a DFA"" then he/she will be able to understand about the functions and the method. My confusion is around these functions...especially the functions followpos(i). to be specific i will have to explain much more than this..since it is not merely a pseudocode that i can give. if there is anyother technique to convert a regular expression to a DFA directly rather than going through an NFA (like the one i'v just mentioned) than plz tell.

[mehdi62b]

what a spammer...!
I think you are H****n ? :D

[RoboTact]

what a spammer...!
I think you are H****n ? :DDon't be rude. Man don't know how to study, it's not funny.

magneeto < you just need to read it carefully, understanding every statement (not just skipping if you don't). It's explained clear enough there, only problem is many definitions all at once.