Re: Regex -> DFA ->? Lex compiler

"Paul Johnston" <johnston.p@worldnet.att.net> writes:


>I build up regular expressions and do the regex to DFA construction
>using algorithm 3.5 on page 140.


>The problem I have now is that I am failing to translate a *set* of
>regular expression into a lexical analyzer (rather than just one
>regular expression).


Algorithm 3.5 introduces an endmarker (#). What you need to do is to
introduce one endmarker for each regexp, i.e., #1, #2 #2 etc. You then
create the combined regular expression


  regexp1 #1 | regexp2 #2 | ... | regexpn #n


You then do the usual calculations of firstpos, followpos etc. When
you have the DFA you look for the states containing the positions of
each of the endmarkers. These states accept the corresponding regular
expressions. If a state contains several different endmarkers, accept
the regexp that corresponds to the token with highest priority (as in
the regexp->NFA->DFA construction).


Torben Mogensen (torbenm@diku.dk)

Return to the comp.compilers page.
Search the comp.compilers archives again.