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

Groups > comp.compilers > #2941 > unrolled thread

Parser LL(*)

Back to article view | Back to comp.compilers

Contents

  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

#2941 — Parser LL(*)

Many language construction needs lookahead depth known in runtime, for example difference between function declarations and definitions.
LL(*) is described in https://www.antlr.org/papers/allstar-techreport.pdf.
This is only one place about LL(*) info?
If is the simplest idea make LL(1) with several conflicts and first speculative trying all paths, and backtrack?
How do speedup it with cache?
How make speculative trying in function calls?

[toc] | [next] | [standalone]

#2945

On Fri, 18 Mar 2022 11:38:48 -0700 (PDT), Andy
<borucki.andrzej@gmail.com> wrote:

>Many language construction needs lookahead depth known in runtime, for
>example difference between function declarations and definitions.
>LL(*) is described in
> https://www.antlr.org/papers/allstar-techreport.pdf.
>This is only one place about LL(*) info?

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.


>How do speedup it with cache?

??? Lookahead tokens already are cached.


>How make speculative trying in function calls?

Sorry, I'm not sure what you are asking.


George

[toc] | [prev] | [next] | [standalone]

#2947 — 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
------------------------------------------------------------------------------

[toc] | [prev] | [next] | [standalone]

#2948 — 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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web