Re: Lazy Evaluation of a DFA (James Kanze US/ESC 60/3/141 #40763)
9 Dec 1995 19:38:51 -0500

          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 |

From: (James Kanze US/ESC 60/3/141 #40763)
Newsgroups: comp.compilers
Date: 9 Dec 1995 19:38:51 -0500
Organization: SEL
References: 95-11-205 95-11-254 95-11-261
Keywords: lex, performance, DFA (ozan s. yigit) writes:

|> I wrote:

|> I think this is wrong. common egrep builds a complete dfa for speed.

|> Well, Don Pardo tells me he knows a common egrep that uses lazy
|> construction. I am almost sure this cannot be SYSV egrep. :)

I'm going back a long time, now, but I seem to remember early Unix
manuals stating that egrep was very fast on large input, but had
significant start-up time. Somewhere along the line, this start-up
time disappeared. Could this be due to a change from building a
complete DFA to using lazy evaluation? (On all but very large input,
lazy evaluation will be a win, because of the number of states that
never get evaluated.)
James Kanze Tel.: (+33) 88 14 49 00 email:
GABI Software, Sarl., 8 rue des Francs-Bourgeois, F-67000 Strasbourg, France
Conseils, Etudes et realisations en logiciel oriente objet --
                                -- A la recherche d'une activite dans une region francophone

Post a followup to this message

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