Re: DFAs,NFAs,REs,CFGs,PDAs ARGH!

Anthony Webster <tony@transcendenz.co.uk> 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,
Pedro

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