Re: Lazy Evaluation of a DFA

eborduas@microstar.com (Eric Borduas) wrote (écrivait) :


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


                                                                                Martin Jourdan


Action Charme, INRIA, Rocquencourt, France
Phone +33-1-39-63-54-35, fax +33-1-39-63-56-98, Martin.Jourdan@inria.fr
--

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