Re: LL(*)

On Sun, 20 Mar 2022 20:05:41 +0200, Christopher F Clark
<christopher.f.clark@compiler-resources.com> wrote:


>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.


So Parr did invent a way to make fixed 'k' more practical to use. I
was not aware of that - thank you.




>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)


ANTLR also has so-called "semantic" predicates which can invoke user
supplied functions and continue with or fail the current rule based on
the results.


George

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