ANTLR unclear multiple alternatives

Question

I have this grammar to match simple logical predicates in ANTLR.

exp :   or
    ;

or  :   and ('|' or)*
    ;

and :   unit ('&' and)*
    ;

unit    :   '(' or ')' |
        STRING
    ;

WS  :   ( ' '
        | '\t'
        | '\r'
        | '\n'
        ) {$channel=HIDDEN;}
    ;

STRING
    :  '\'' ( ESC_SEQ | ~('\\'|'\'') )* '\''
    ;

fragment
HEX_DIGIT : ('0'..'9'|'a'..'f'|'A'..'F') ;

fragment
ESC_SEQ
    :   '\\' ('b'|'t'|'n'|'f'|'r'|'\"'|'\''|'\\')
    |   UNICODE_ESC
    |   OCTAL_ESC
    ;

fragment
OCTAL_ESC
    :   '\\' ('0'..'3') ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7') ('0'..'7')
    |   '\\' ('0'..'7')
    ;

fragment
UNICODE_ESC
    :   '\\' 'u' HEX_DIGIT HEX_DIGIT HEX_DIGIT HEX_DIGIT
    ;

I'm getting the warning Decision can match input such as "'&'" using multiple alternatives: 1, 2, as well as one for the or rule. I know that this warning comes up when there ambiguities in the grammar, but I really can't see what the ambiguity is. I also don't understand the warning message because it says the input '&' has multiple alternatives, but '&' by itself shouldn't be a valid input. Can anyone point out the ambiguity? I'm worried that it will mess me up later on when the grammar does become more complex.

Did you edit your code or the error message? Your error says "Decision", but I think this referring to and in your grammar. — Laurence Gonsalves

Laurence Gonsalves Laurence Gonsalves · Accepted Answer · 2011-11-03T05:46:47

I think that instead of this:

or  :   and ('|' or)*
    ;

and :   unit ('&' and)*
    ;

you want this:

or  :   and ('|' and)*
    ;

and :   unit ('&' unit)*
    ;

The form you've got is ambiguous because when it's processing that nested or (or and) it doesn't know if that one should continue repeating, swallowing up the next | (or &) or if it should return to the outer one and let it process it.

ANTLR unclear multiple alternatives

1 Answers