ANTLR recursive ambiguity problem

Question

VARIABLE: ...

UNARYOP: 'not' Expression; // unary operation
BINARYOP: 'or' VARIABLE;

Expression : (NIL | INTEGER | UNARYOP) BINARYOP?;

In the above scenario, 'or' can either be reached through

Expression->BINARYOP

or

EXPRESSION->UNARYOP->Expression->BINARYOP

Is there a systematic way to remove ambiguities such as the above?

Answer 1

I think that removing ambiguities in grammars is a non automatically solvable task because if the choose of which of the alternatives is the right one is a 'subjective' choice.

Once you identified the problem, build the different alternative trees and add new production rules to disallow the invalid parse trees.

I am afraid there is no magic solution like for removing left recursions... Maybe I am wrong.

In your case you could define

Expression : NIL
           | INTEGER
           | VARIABLE
           | 'not' Expression
           | Expression 'or' Expression;

Or do you want to limit the right side of 'or' to variables only?