LL(*)

George Neuner gets this right:


> Terence Parr both invented LL(*) and is the author of the ANTLR tool.
> AFAIK, Parr's own papers and books are the only sources of information
> about the method.


> >If is the simplest idea make LL(1) with several conflicts and first
> >speculative trying all paths, and backtrack?


> No, the simplest idea was LL(k) with a fixed value of 'k'. I don't
> believe Parr developed the method, but he was one of the pioneers of
> using it. Parr authored PCCTS which used LL(k), and early versions of
> ANTLR [prior to LL(*)] also used it.


> LL(*) eliminates the need for the developer to figure out what 'k' is
> optimal for the grammar: too low results in conflicts, too high may
> waste processing effort.


Terence's original paper, "Breaking the atomic k-tuple" made LL(k)
feasible, basically by doing each extra amount of lookahead 1 at a time.
Thus,LL(1) if no conflicts done, For those rules with LL(1) conflicts,
try LL(2), etc. No backtracking ever. No speculative execution either(*).
Just figure out how many tokens you need to read before you can
disambiguate which rule applies It is nearly always a fixed number.
If it isn't, the grammar is not LL(k) for any k. And, the if-then-else hack
takes care of one of the main problem cases where it isn't.


The latest version ANTLR4 does a slightly different variation on that,
by building a RTN that solves the problem. That's almost the same as
building an LR parser, but not quite. The only place one notices the
difference is when one has indirect (nested) left recursion. ANTLR4
doesn't allow that.


*) syntactic predicates are essentiaily speculative execution, but they
aren't strictly a part of LL(k)
--
******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

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