Regex -> DFA ->? Lex compiler

Hello-


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
correct.


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.


Thanks,
Paul

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