Xtext: Ambiguous grammar with unary minus

Question

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"

Could you translate this to simple grammar like A -> AB, B -> aB, A -> aa. I hope you're familiar with abstract grammars, otherwise this comment won't make much sense for you. I could tell you why it's ambiguous but I don't know the syntax and structure of this language. — ShellFish

Sebastian Zarnekow Sebastian Zarnekow · Accepted Answer · 2015-01-15T08:44:13

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.

Xtext: Ambiguous grammar with unary minus

1 Answers