From: Eric Mahurin <eric.mahurin@...>
Date: 2008-09-29T05:53:36+09:00
Subject: Re: my ears are burning... ;)

------=_Part_23133_7800722.1222635258594
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On Sun, Sep 28, 2008 at 2:39 PM, <parrt@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.

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?

------=_Part_23133_7800722.1222635258594--