Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Pedro Sam)
10 Aug 2003 10:47:01 -0400

          From comp.compilers

Related articles
DFAs,NFAs,REs,CFGs,PDAs ARGH! (Anthony Webster) (2003-08-04)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (2003-08-10)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Thomas Skora) (2003-08-10)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Derk Gwen) (2003-08-10)
Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! (Joachim Durchholz) (2003-08-23)
| List of all articles for this month |

From: (Pedro Sam)
Newsgroups: comp.compilers
Date: 10 Aug 2003 10:47:01 -0400
Organization: University of Waterloo
References: 03-08-015
Keywords: lex
Posted-Date: 10 Aug 2003 10:47:01 EDT

Anthony Webster <> wrote:
> I'm writing the lexer and parser parts of a compiler. I've got a basic
> lexer working but it relies on a massive while statement and I was
> thinking of using something more intesting like a DFA built from a
> RE. I'm still a little confused as to which data structure to use for
> what part of the system. I understand the mechanics of things like
> CFGs and PDAs but fail to see exactly where they fit in the
> implementation of a lexer/parser. Some clarification would be most
> appreciated.

One simple way of making a lexer is to write a program that takes a
list of RE as input, and output a DFA. (at least that's what I did for
a course I took in school) I found it more intuitive to write a
program that does RE->NFA first, and then transform that NFA into a
DFA. Alternatly, there are a number of algorithms for doing RE->DFA
directly or even a caching approach, please see the Dragon book for
more details.

As for the DFA data structure, the DFA defines a function that maps a
current state to the nextstate. So the DFA data structure is a map
keyed by the current state, and valued by the next state. For an NFA,
a multi-map would also work.

Once you have the DFA, it is easy to write a program that takes the DFA,
and a text file, as input, and output the tokens.

Hope that helps,

Post a followup to this message

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