Re: NFA -> DFA on-the-fly determinization

Karsten Nyblad <d148f3wg02@sneakemail.com>
2 Feb 2006 11:33:46 -0500

          From comp.compilers

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)
| List of all articles for this month |

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
Posted-Date: 02 Feb 2006 11:33:46 EST

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.