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

## p2sam@uwaterloo.ca (Pedro Sam)

10 Aug 2003 10:47:01 -0400

*From comp.compilers*

Related articles |

DFAs,NFAs,REs,CFGs,PDAs ARGH! *tony@transCendenZ.co.uk (Anthony Webster)* (2003-08-04) |

**Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! ***p2sam@uwaterloo.ca* (2003-08-10) |

Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! *usenet0@skora.net (Thomas Skora)* (2003-08-10) |

Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! *derkgwen@HotPOP.com (Derk Gwen)* (2003-08-10) |

Re: DFAs,NFAs,REs,CFGs,PDAs ARGH! *joachim.durchholz@web.de (Joachim Durchholz)* (2003-08-23) |

| List of all articles for this month |

**From: ** | p2sam@uwaterloo.ca (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 <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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.