Search code examples
parsingantlrantlr3xtext

Xtext: Ambiguous grammar with unary minus


Could someone please explain why this is ambiguous grammar? I have a fairly elaborate grammar and have nailed the error which I have down to this:

Expressions:
    AdditionOrSubtraction;

AdditionOrSubtraction:
    UnaryExpression ((PLUS | MINUS) UnaryExpression)*
;
UnaryExpression:
    MINUS Expressions
    | Atom
;
Atom returns Expression:
    INT
;

I looked at the java spec which gives a similar expression: http://docs.oracle.com/javase/specs/jls/se8/html/jls-15.html#jls-MultiplicativeExpression

I have simplified it and showed it below:

MultiplicativeExpression:
    UnaryExpression 
    MultiplicativeExpression * UnaryExpression
    MultiplicativeExpression / UnaryExpression
    MultiplicativeExpression % UnaryExpression

UnaryExpression:
    + UnaryExpression 
    - UnaryExpression 
    Literal

Literal:
    IntegerLiteral 

I get the following error message when I try to run it: "Decision can match input such as "RULE_MINUS {RULE_MINUS, ......}" using multiple alternatives: 1, 2 As a result, alternative(s) 2 were disabled for that input"


Solution

  • You grammar is ambiguous since it could be parsed into two different, equally valid trees. Please consider the input 1 - 2 - 3. It would be possible to read it in two ways (parethesis added to emphasize the ambiguous precedencies:

    • 1 - ( 2 - 3 )
    • (1 - 2) - 3

    You would need to modify it to

    UnaryExpression: MINUS Primary | Primary;
    Primary: '(' Expressions ')' | Atom;
    

    to disambiguate it.