10 Feb 2000 01:15:26 -0500

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

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.