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

[Kevin J. Cummings]

On 08/12/2009 05:45 PM, Nikolay Ognyanov wrote:
> Hi everybody,
> 
> Please have a look at a toy grammar for  language consisting of 2 
> statements :
> 
> grammar Ambiguous;
> 
> expr
>     : expr1
>     | expr2
>     ;
> expr1
>     : PREFIX_1 expr2 SUFFIX
>     ;
> expr2
>     : PREFIX_2
>     | PREFIX_2 SUFFIX
>     ;
> 
> PREFIX_1   : 'prefix_1';
> PREFIX_2   : 'prefix_2';
> SUFFIX     : 'suffix';
> WS         : (' ' | '\r' | '\n' | '\t')+ {$channel=HIDDEN;};
> 
> 
> Please do not advise how to fix it :) I know that but the question is why
> ANTLR considers rule for expr2 ambiguous?  Here is a tool run:

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.
You only have 1 token of lookahead (by default).  You might be able to
correct with syntactic predicates or a higher value of k, but your
grammar is not well defined because of the ambiguity.

-- 
Kevin J. Cummings
kjchome at rcn.com
cummings at kjchome.homeip.net
cummings at kjc386.framingham.ma.us
Registered Linux User #1232 (http://counter.li.org)