From: parrt@...
Date: 2008-09-30T04:39:07+09:00
Subject: Re: my ears are burning... ;)

On Sep 28, 1:53 pm, Eric Mahurin <eric.mahu...@gmail.com> wrote:
> [Note:  parts of this message were removed to make it a legal post.]
>
>
>
> On Sun, Sep 28, 2008 at 2:39 PM, <pa...@antlr.org> wrote:
> >  > > My parser
> > > > > generator does LL(1) and LL(*) where directed.
>
> > > > Just to prevent confusion in the namespace, I assume you mean LL(k)
> > > > not LL(*). LL(k) does more than a single symbol of lookahead but with
> > > > a finite maximum determined at parser generation time.  LL(*), on the
> > > > other hand, can generate cyclic DFA that can look arbitrarily ahead to
> > > > distinguish alternatives. As long as the lookahead language is
> > > > regular, LL(*) can handle it. If you have a left common prefix that is
> > > > recursive, naturally that means the lookahead language is not regular.
> > > > At that point, we must backtrack. That is where we get into predicated
> > > > LL(*), which knows how to backtrack and incorporate semantic
> > > > predicates its own. In fact I implement syntactic predicates,
> > > > backtracking, as a special form of semantic predicate.  this has
> > > > advantages as you'll see  next.
>
> > > I do mean LL(*).  I decided up front to make my parser mainly LL(1) for
> > > speed and clarity but give a backdoor to accomplish LL(*) via
> > backtacking.
>
> > Howdy.  Well, that's my point.  LL(*) is not backtracking.
> > Backtracking is backtracking; it's done in conjunction with LL(*) in
> > ANTLR.  I invented LL(*) (though my friend Sriram suggested the term
> > LL(*)).  I'm asking that people don't pollute the name space with
> > improper usage.  LL(k) does regular lookahead with acyclic DFA and
> > LL(*) does it with cyclic DFA.  Backtracking as used in PEGs is a
> > totally different strategy which effectively allows CFG lookahead
> > languages using syntactic predicates (something I also pioneered).
>
> > Sounds like you're doing LL(1) + backtracking.  Nice but not LL(*) +
> > backtracking.
>
> I didn't realize the special meaning of LL(*).  I'm really doing something
> very similar to what parsec does:
>
> http://legacy.cs.uu.nl/daan/download/parsec/parsec.html#try
>
> which they call "infinite lookahead" and wikipedia uses the term
> LL(infinity) with it.  Looks about like backtracking to me though.

Yep, combinators are essentially syntactic predicates.  The amount of
lookahead is arbitrary; the key difference between backtracking and
LL(*) his how it uses the arbitrary lookahead. syntactic predicates
and I presume combinators test context free lookahead languages
whereas LL(*) (ala * in regular expressions) uses only a regular
lookahead language to predict alternatives. This means no method calls
to rules and so on whereas the backtracker is looking ahead with the
full parser.

>
> It sounds like your LL(*) parsing allows arbitrary, but finite lookahead.
> Kind of like LL(k) where k is automatically determined for each set of
> alternatives?

LL(*) is arbitrarily large without a fixed number computed at static
grammar analysis time. The similarity to LL(k) is that both use
regular lookahead languages to predict alternatives.  Here is a simple
non-LL(k) decision that is trivially LL(*):

a : x B
  | x C
  ;
x : A+ ;

Note that we do not have to backtrack to solve this problem. we never
have to call x to predict alternatives of rule 'a'.

:)  Cool, eh?

Ter

Ter