Regex -> DFA ->? Lex compiler

"Paul Johnston" <>
5 Feb 2000 18:46:19 -0500

          From comp.compilers

Related articles
Regex -> DFA ->? Lex compiler (Paul Johnston) (2000-02-05)
Re: Regex -> DFA ->? Lex compiler (Armel) (2000-02-10)
Re: Regex -> DFA ->? Lex compiler (Jonathan Barker) (2000-02-10)
Re: Regex -> DFA ->? Lex compiler (2000-02-10)
| List of all articles for this month |

From: "Paul Johnston" <>
Newsgroups: comp.compilers
Date: 5 Feb 2000 18:46:19 -0500
Organization: AT&T WorldNet Services
Keywords: lex, question


I'm essentially doing exercise P3.8 from the dragon book "Construct a
tool that produces a lexical analyzer from a regular expression
description of a set of tokens". No, I'm not a student but I often
feel like one given this interesting task.

Which I've done, sort of. I build up regular expressions and do the
regex to DFA construction using algorithm 3.5 on page 140. This is
going straight from regex to DFA using the first, last, and follow
sets,etc... Everything works, yea.

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). If I had built this tool going from regex to NFA
to DFA, rather than straight to a DFA, then this would be solved by
constructing a new start state s0 and linking to each NFA pattern with
an epsilon-transition, as shown on the diagram on page 130.

But how would I do this without the NFA? How is the translation done
straight from the regular expression syntax tree? Initially I was
joining each individual regex under a union, but this of course is not

Anyhow hopefully I'll have it solved soon -- even if I have to
redesign to use the intermediate NFA, but I'd be interested in your
feedback about probably basic issue.


Post a followup to this message

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