Re: Lazy Evaluation of a DFA (ozan s. yigit)
Thu, 30 Nov 1995 17:05:49 GMT

          From comp.compilers

Related articles
Lazy Evaluation of a DFA (1995-11-23)
Re: Lazy Evaluation of a DFA (1995-11-28)
Re: Lazy Evaluation of a DFA (1995-11-30)
Re: Lazy Evaluation of a DFA (1995-12-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (ozan s. yigit)
In-Reply-To:'s message of Tue, 28 Nov 1995 09:18:12 GMT
Keywords: DFA, lex
Organization: The Electric Skillet
References: 95-11-205 95-11-219
Date: Thu, 30 Nov 1995 17:05:49 GMT

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.

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

Post a followup to this message

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