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

Wed, 12 Aug 2009 15:14:34 -0700

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:

java org.antlr.Tool Ambiguous.g
warning(200): Ambiguous.g:11:5: Decision can match input such as 
"PREFIX_2 {EOF, SUFFIX}" using multiple alternatives: 1, 2
As a result, alternative(s) 2 were disabled for that input
error(201): Ambiguous.g:11:5: The following alternatives can never be 
matched: 2
Clearly, this is ambiguous because you follow expr2 with SUFFIX in the expr1 rule. When parsing expr2 as part of expr1, the paths of taking PREFIX_2 the using SUFFIX in expr1 and taking PREFIX_2 then SUFFIX in expr2 followed by SUFFIX in expr1 are ambiguous as written.

You say you know how to fix it, but perhaps you do not if you cannot see the ambiguity here. Because expr2 is a stand alone path from expr, there is no way to know how to disambiguate when called from expr1. Basically, you need to left factor these rules properly:

expr
   : PREFIX_1 PREFIX_2 SUFFIX SUFFIX?
   | PREFIX_2 SUFFIX?
   ;



Jim



--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "il-antlr-interest" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [email protected]
For more options, visit this group at http://groups.google.com/group/il-antlr-interest?hl=en
-~----------~----~----~----~------~----~------~--~---

List: http://www.antlr.org/mailman/listinfo/antlr-interest
Unsubscribe: 
http://www.antlr.org/mailman/options/antlr-interest/your-email-address

Reply via email to