2 Feb 2006 11:33:46 -0500

Related articles |
---|

NFA -> DFA on-the-fly determinization rsc@swtch.com (Russ Cox) (2006-01-31) |

Re: NFA -> DFA on-the-fly determinization d148f3wg02@sneakemail.com (Karsten Nyblad) (2006-02-02) |

Re: NFA -> DFA on-the-fly determinization rsc@swtch.com (Russ Cox) (2006-02-03) |

From: | Karsten Nyblad <d148f3wg02@sneakemail.com> |

Newsgroups: | comp.compilers |

Date: | 2 Feb 2006 11:33:46 -0500 |

Organization: | Compilers Central |

References: | 06-01-140 |

Keywords: | lex, DFA |

Russ Cox wrote:

*> I am trying to find a reference for the technique of converting an NFA*

*> to a DFA as needed during NFA execution and caching the result to*

*> avoid repeating the conversion at each step. ...*

The normal implementation of an DFA is to have a map in each state,

which maps symbols to the next state or if the look up fails then the

string is not recognized. Why don't you extend that map so that a

symbol may also be mapped to a value meaning uncalculated. Each time

you look up that value, you calculate the next DFA state from the NFA

and change the map so that the symbol now maps to the new state. Of

course the map of the new state should be initialized to map any symbol

to the uncalculated value.

A variation could be not to have the uncalculated value, but then the

next state would have to recalculate at least one next state each time

the DFA is used to try to recognize a string not in the language of the

NFA/DFA.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.