Re: Regex -> DFA ->? Lex compiler

torbenm@diku.dk (Torben AEgidius Mogensen)
10 Feb 2000 01:15:26 -0500

          From comp.compilers

Related articles
Regex -> DFA ->? Lex compiler johnston.p@worldnet.att.net (Paul Johnston) (2000-02-05)
Re: Regex -> DFA ->? Lex compiler webid@asi.fr (Armel) (2000-02-10)
Re: Regex -> DFA ->? Lex compiler jandk@easynet.co.uk (Jonathan Barker) (2000-02-10)
Re: Regex -> DFA ->? Lex compiler torbenm@diku.dk (2000-02-10)
| List of all articles for this month |

From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.compilers
Date: 10 Feb 2000 01:15:26 -0500
Organization: Department of Computer Science, U of Copenhagen
References: 00-02-012
Keywords: lex

"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)


Post a followup to this message

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