|Lazy Evaluation of a DFA firstname.lastname@example.org (1995-11-23)|
|Re: Lazy Evaluation of a DFA Martin.Jourdan@inria.fr (1995-11-28)|
|Re: Lazy Evaluation of a DFA email@example.com (1995-11-30)|
|Re: Lazy Evaluation of a DFA firstname.lastname@example.org (1995-12-09)|
|From:||email@example.com (ozan s. yigit)|
|In-Reply-To:||Martin.Jourdan@inria.fr's message of Tue, 28 Nov 1995 09:18:12 GMT|
|Organization:||The Electric Skillet|
|Date:||Thu, 30 Nov 1995 17:05:49 GMT|
|> I am looking for an algorithm that implements the lazy transition
|> evaluation technique mentioned by Aho, Sethi and Ullman in Compiler
|> Principles, Techniques and Tools. Does anyone know if one exists?
If I correctly understand your request, yes, the algorithm exists : it's
in that very book! More seriously, the "egrep" regular-expression matching
program that comes with most Unixes is an implementation of this
algorithm. This lazy-construction technique is the main reason why egrep
is generally faster than grep.
I think this is wrong. common egrep builds a complete dfa for speed.
The lazy construction technique mentioned in ASU may be available in some
other egrep [i doubt gnu egrep uses it] but a detailed discussion and
implementation may be found in "Software Tools Sampler"  which
i believe is still in print.
 Webb Miller
A Software Tools Sampler
Prentice-Hall Software Series, 1988.
Return to the
Search the comp.compilers archives again.