Re: [Boost-users] Comparison boost spirit and ANTLR

Subject: Re: [Boost-users] Comparison boost spirit and ANTLR
From: Evan Driscoll (driscoll_at_[hidden])
Date: 2013-05-29 12:05:40

On 05/29/2013 09:51 AM, Larry Evans wrote:
> On 05/29/13 07:59, salvatore dario minonne wrote:
>> ATLR is LL as well
> More specifically, ANTLR is LL(k) for some k>0:
> 
> http://en.wikipedia.org/wiki/LL_parser

Actually *that's* not true either. Antlr generates LL(*) parsers. With
some restrictions, the generated parsers have infinite lookahead.

For instance,

  nonterm1 : (term1)* term2
             (term1)* term3

is not LL(k) for any k as if you give me a k I give you the string
"term1^k term2" and you can't decide between those alternatives, but
that grammar is is LL(*).

I'm not sure how much this actually affects real usage, just trying to
be accurate. There is at least one example of something you may want to
do which is LL(*) but not LL(k)

   classMember: modifier* type ident SEMI
              | modifier* type ident LPAREN arglist RPAREN body

   modifier: PUBLIC | PRIVATE | PROTECTED | STATIC | ...

(The description of what makes a grammar LL(*) requires more than I feel
like explaining now.)

Evan