Re: Converting regex to DFA - rule diagram

Torben Mogensen <>
20 Aug 1998 13:55:31 -0400

          From comp.compilers

Related articles
Converting regex to DFA - rule diagram (1998-08-19)
Re: Converting regex to DFA - rule diagram (Torben Mogensen) (1998-08-20)
| List of all articles for this month |

From: Torben Mogensen <>
Newsgroups: comp.compilers
Date: 20 Aug 1998 13:55:31 -0400
Organization: Compilers Central
References: 98-08-139
Keywords: lex, DFA

Peter Friend wrote:

> I am working on building a regex compiler, and I am using the rules
> from the "Dragon Book" to convert the parsed regex to a DFA. To help
> with this, I have copied the diagram from page 138 and expanded it a
> bit to include lastpos and followpos. I am still working on the
> followpos entry for the '?' operator.

There should be no entry. You can think of e? as a | \epsilon. From
this you can derive that firstpos of e? is firstpos of e and there
should be no followpos rule (as there are none for | or \epsilon).

BTW, you need to replace all references to firstpos(e_1) and
firstpos(e_2) in the lastpos column by lastpos(e_1) and lastpos(e_2).

Torben Mogensen (

Post a followup to this message

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