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

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.

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