[antlr-interest] Why and how exactly does ANTLR manage to fail on non recursive grammar for finite language?

[Nikolay Ognyanov]

Actually, even backtracking does not solve this. The problem is 
apparently as you noted Jim
resolving standalone vs embedded expr2. In standalone expr2 following 
SUFFIX has to be
consumed unconditionally whereas in embedded expr2 it has to be consumed 
only if followed
by yet another SUFFIX.  To resolve between the 2 cases though procedure 
for expr2 needs
to look back, not forward, so it does not matter how far ahead it looks. 
I guess this is what
ultimately makes the grammar not LL - with LL parser expr2 has to be 
handled in a context
dependent way even though the grammar as such is context free. LALR 
should be able to
solve this I think by shifting long enough to figure out what to do 
before making a reduction.

Regards
Nikolay

Jim Idle wrote:
> David-Sarah Hopwood wrote:
>>>
>>> Because at the time it is in expr2, it is ambiguous as to whether it
>>> should match PREFIX_2 and exit, or match PREFIX_2 SUFFIX and then exit.
>>>     
>>
>> Yes.
>>
>>   
>>> You only have 1 token of lookahead (by default).
>>>     
>>
>> That's not right. The value of k is normally determined automatically
>> per rule (if not overridden). The problem here is that the grammar is
>> ambiguous *as an LL(k) grammar* for any k. Although ANTLR supports
>> backtracking (which makes it more powerful than LL(k)), that's not
>> enabled by default, and so is not taken into account by the ambiguity
>> warning.
>>
>> For example, consider input starting with "prefix_1 prefix_2 suffix".
>> A non-backtracking LL(k) parser must predict and commit to a particular
>> alternative of expr2 by looking only at tokens that would be part of that
>> alternative, here either "prefix_2" or "prefix_2 suffix". It will never
>> look further ahead than that, regardless of k.
>>
>> The default of not enabling backtracking is the right default, since the
>> ambiguity warnings are more conservative and more likely to help in
>> finding grammar errors. (To me this is more important than the loss
>> of efficiency that can result from backtracking.) In this case, the
>> left-factoring suggested by Jim Idle is a better solution than enabling
>> backtracking, even though the latter would handle this particular
>> grammar automatically.
>>
>>   
> But, you must remember that once you use backtracking, you lose the 
> inherent ability of LL parsers to pin-point the locale of errors 
> accurately. Hence backtracking is only good for prototypes, or 
> situations where you expect the input to be syntactically sound (you 
> are transforming otherwise good code and so on).
>
> Jim
>
> ------------------------------------------------------------------------
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>   


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20090813/6d2becde/attachment.html