Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2948

Re: LL(*)

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Find similar

Thread

Parser LL(*) Andy <borucki.andrzej@gmail.com> - 2022-03-18 11:38 -0700
  Re: Parser LL(*) George Neuner <gneuner2@comcast.net> - 2022-03-19 21:14 -0400
    LL(*) Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-03-20 20:05 +0200
      Re: LL(*) George Neuner <gneuner2@comcast.net> - 2022-03-21 15:47 -0400

csiph-web