Re: Lazy Evaluation of a DFA

Martin Jourdan:


      |> 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" [1] which
i believe is still in print.


oz
---
[1] Webb Miller
        A Software Tools Sampler
        Prentice-Hall Software Series, 1988.
--

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