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

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

Ter