How to avoid ambiguity in rules with optional right-hand operand?

Viewed 90

It's known that ANTLR4 does automatic left recursion optimization. But how to avoid ambiguity when the last operand is optional?

Giving the following simplified grammar as an example:

grammar Example;

root: expression EOF;

expression: binaryExpression;

binaryExpression
    : binaryExpression 'and' binaryExpression
    | binaryExpression 'or' binaryExpression
    | 'no' ID 'in' ID ('satisfies' expression)?
    | '(' expression ')'
    | OPERAND
;

OPERAND: 'true' | 'false';
ID: [a-z]+;
WS: (' ' | '\r' | '\t')+ -> channel(HIDDEN);

This grammar accepts both the expressions no x in y and no x in y satisfies condition. However, the optional subrule ('satisfies' expression)? is not considered during the left refactoring. As a result, the input no x in y satisfies true and false is reported as an ambiguity input:

2 interpretations for the input

The parser assumes two viable trees, no x in y satisfies (true and false) and (no x in y satisfies true) and false, but only the first should be considered a viable interpretation.

One could argue that I could rewrite the grammar as follows:

binaryExpression
    : binaryExpression 'and' binaryExpression
    | binaryExpression 'or' binaryExpression
    | 'no' ID 'in' ID 'satisfies' expression
    | 'no' ID 'in' ID
    | '(' expression ')'
    | OPERAND
;

Although it "works", in addition to the impact on performance, error reporting is no longer useful, as it is not possible to infer what comes next until the parser reaches the ID token.

Is there any way to refactor the grammar to explicitly specify that the expression in the RHS of the quantifier should always take precedence?

0 Answers
Related