LL(*)

From	Christopher F Clark <christopher.f.clark@compiler-resources.com>
Newsgroups	comp.compilers
Subject	LL(*)
Date	2022-03-20 20:05 +0200
Organization	Compilers Central
Message-ID	<22-03-045@comp.compilers> (permalink)
References	<22-03-039@comp.compilers> <22-03-043@comp.compilers>

Show all headers | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next 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