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

Russ Cox <rsc@swtch.com>
3 Feb 2006 18:42:22 -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: Russ Cox <rsc@swtch.com>
Newsgroups: comp.compilers
Date: 3 Feb 2006 18:42:22 -0500
Organization: Compilers Central
References: 06-01-140 06-02-005
Keywords: lex, DFA, history, question
Posted-Date: 03 Feb 2006 18:42:22 EST

> > 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, ...


I apologize for not being clearer. I have an implementation (and it does
exactly what you describe, with "not yet calculated" states). My question
is not "how can I do this?" but "who was the first and is there a reference
to a canonical paper?".


Thanks.
Russ

Post a followup to this message

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