Re: Lazy Evaluation of a DFA

oz@nexus.yorku.ca (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: kanze@gabi-soft.fr
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
--

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