25 Jan 2003 01:03:14 -0500

Related articles |
---|

NFA to DFA question unmesh_joshi@hotmail.com (Unmesh joshi) (2003-01-12) |

Re: NFA to DFA question clint@0lsen.net (Clint Olsen) (2003-01-17) |

Re: NFA to DFA question thp@cs.ucr.edu (2003-01-17) |

Re: NFA to DFA question mchristoff@sympatico.ca (Michael N. Christoff) (2003-01-17) |

Re: NFA to DFA question lord@emf.emf.net (2003-01-21) |

Re: NFA to DFA question joachim_d@gmx.de (Joachim Durchholz) (2003-01-25) |

Re: NFA to DFA question rafe@cs.mu.oz.au (Ralph Becket) (2003-01-30) |

From: | Joachim Durchholz <joachim_d@gmx.de> |

Newsgroups: | comp.compilers |

Date: | 25 Jan 2003 01:03:14 -0500 |

Organization: | Compilers Central |

References: | 03-01-051 |

Keywords: | DFA, lex |

Posted-Date: | 25 Jan 2003 01:03:12 EST |

Let me give it another try from Tom Lord's perspective: offering an

intuitive view of what's happening during the NFA->DFA conversion.

The basic idea is not to run the NFA as it is, but to build an NFA

simulator that traces all possible execution histories of the NFA in

parallel.

The simulator is just like the NFA, but instead of a single state, it

uses a set of states. Initially, the simulator set-of-states consists of

the start states of the NFA; whenever it gets an input C, it constructs

the new set of states by following all arrows from states in its

stateset that are labelled with C.

The DFA is just a precomputed version of the simulator. It's again

just a single state at a time, but every state in its graph

corresponds to a set of state from the NFA. The construction process

just traces out all possible execution histories of the NFA.

Hope this clarifies things a bit further.

Regards,

Joachim

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.