Re: Lazy Evaluation of a DFA

Martin.Jourdan@inria.fr (Martin Jourdan)
Tue, 28 Nov 1995 09:18:12 GMT

          From comp.compilers

Related articles
Lazy Evaluation of a DFA eborduas@microstar.com (1995-11-23)
Re: Lazy Evaluation of a DFA Martin.Jourdan@inria.fr (1995-11-28)
Re: Lazy Evaluation of a DFA oz@nexus.yorku.ca (1995-11-30)
Re: Lazy Evaluation of a DFA kanze@lts.sel.alcatel.de (1995-12-09)
| List of all articles for this month |

Newsgroups: comp.compilers
From: Martin.Jourdan@inria.fr (Martin Jourdan)
Keywords: DFA
Organization: Action Charme, INRIA, Rocquencourt, France
References: 95-11-205
Date: Tue, 28 Nov 1995 09:18:12 GMT

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


Post a followup to this message

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