Re: Regular expressions speedup

  John Levine <johnl@iecc.com> wrote:


> > The book by Aho, Sethi & Ullman, "Compilers...", end of sec. 3.7, says
> > that best for both space and time is a "lazy transition evaluation"
> > technique.


> [I wonder if they feel differently about space tradeoffs now than they
> did 30 years ago. At that point, programs had to fit into 16 bit address
> spaces. -John]


A NFA to DFA translation may, in bad cases, result in an exponential
expansion, in which case no computer will suffice, no matter how much
memory it has. So in order to avoid that, one might use the suggestion
above. That is, translating the NFA to DFA transitions at need, caching
the partial DFA. The quote above also says that this lazy technique may be
faster than a full runtime NFA to DFA translation, in view of that unused
DFA transitions need not be computed.


--
    Hans Aberg

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