Benjohn Barnes wrote:
> One article there [3] seems to imply that while a packrat parser's 
> memoization gives linear theoretical time, for almost all real grammars 
> (and inputs, I presume) it's actually not necessary.

There's a bit of a chicken/egg problem here.

Existing computer languages have been created to be easy to parse,
which means they require minimum lookahead- one or two tokens.

In part, that's because such languages are easier for humans to
parse as well, and in part because parser generators couldn't
produce efficient parsers for them... until now. Now that packrat
is on the scene, we're free to create more natural looking grammars.

> They suggest that for the cases where there is a an exponential time 
> problem, it's sensible to rely on user supplied memoization directives 
> in the grammar,

That requires a lot more user understanding (of where to memoize),
or a whole lot more analysis. ANTLR takes the 2nd approach, but it's
a difficult task that still causes many surprises. Treetop is slow,
but it's easily accessible to Joe Average without special skills and
without major surprises. I think it fills an important niche.

> or to add memoization selectively and automatically, 
> based on profiling information.

That would be cool. Write an exponential-time parser, run it over
your test cases in learning mode, and then regenerate it to get a
fast parser.

Clifford Heath.