Greedy subrules in ANTLR4

Question

I'm working on a parser grammar that should allow trailing expressions without enclosing symbols. The following is a simplified version that evidences the issue:

grammar Example;

root: expression EOF;

expression: binaryExpression;

binaryExpression
    : binaryExpression 'and' binaryExpression
    | binaryExpression 'or' binaryExpression
    | quantifier
    | '(' expression ')'
    | OPERAND
;

quantifier
    : 'no' ID 'in' ID 'satisfies' expression
;

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

If you try to parse the following expression, you'll notice that, although the parse correctly recognizes the input, it reports an ambiguity:

true or false and no x in y satisfies true or false

The error reporting works as expected (more about this later):

line 1:1 token recognition error at: '1'
line 1:2 mismatched input '' expecting {'(', 'no', OPERAND}

I'm looking for some way to explicitly tell the parser that the quantifier should be greedy: everything on the right-hand side should be consumed unambiguously until the end of the expression.

I tried to refactor the rules to allow the quantifier only on the RHS of binary expressions. Although it worked, the error recovery mechanism becomes unable to recognize most expressions:

grammar Example;

root: expression EOF;

expression: quantifier | booleanExpression;

quantifier
    : 'no' ID 'in' ID 'satisfies' expression
;

booleanExpression
    : orExpression ('or' (quantifier | andQuantifier))?
    | andQuantifier
;

andQuantifier: andExpression 'and' quantifier;

orExpression
    : orExpression 'or' orExpression
    | andExpression
;

andExpression
    : andExpression 'and' andExpression
    | '(' expression ')'
    | OPERAND
;

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

As you can see, the problem is gone:

But it came at the cost of more complex grammar and unable to recognize wrong inputs like (1:

line 1:1 token recognition error at: '1'
line 1:2 no viable alternative at input '('

Does anyone else have any other idea on how to fix it?

user_1566221 · Answer

This is the way I'd do it, using Antlr4's built-in algorithm for resolving ambiguity with precedence (since the grammar is certainly ambiguous). In order to get the precedence algorithm to work, it's useful to think of a qualification as a unary operator with low precedence, which is why quantifier below is just the "operator" and not the full expression. Presumably in a real grammar you would have other quantifiers, and very likely unary operators with higher precedence like not.

grammar Example;

root: expression EOF;

expression
    : expression 'and' expression
    | expression 'or' expression
    | quantifier expression
    | operand
    | '(' expression ')'
;

quantifier
    : 'no' ID 'in' ID 'satisfies'
;

operand: BOOLEAN | ID;

BOOLEAN: 'true' | 'false';
ID: [a-zA-Z]+;
WHITE_SPACE: (' ' | '
' | '
' | '	')+ -> channel(HIDDEN);

This isn't quite the same as the example in your post because you modified a few minor details from the first version of the question. But I think it's indicative.

For obvious reasons I couldn't try it with (1 (I suppose that input corresponds to yet a different version where integers are OPERANDs), but with (true it gave me what looks like the error report you are seeking. I'm not really an ANTLR4 expert so I don't know how to predict the details of error recovery.

user_73764 · Answer

OK, after a lot of back and forth here, I think I finally get that what you're looking for is associativity. Try:

grammar Example;

root: expression EOF;

expression
    : '(' expression ')'                            # parenExpr
    | expression (AND | OR) quantifier # quantifierExpr
    | expression AND expression                     # andExpr
    | expression OR expression                      # orExpr
    | OPERAND                                       # operandExpr
;

quantifier
    :  'no' ID 'in' ID 'satisfies' expression
;

AND: 'and';
OR: 'or';
OPERAND: 'true' | 'false';
ID: [a-z]+;
WS: (' ' | '
' | '	')+ -> channel(HIDDEN);

(I took the liberty of adding labels to your alternatives and simplifying the expression rule.). The labels will come in very handy in your code as you need to deal with each alternative individually. Labels will give you separate functions to override in your listeners/visitors (along with Context classes specific to that alternative)

true and false or false and no x in y satisfies true or false

true and false or false or no x in y satisfies true or false

true and false or false and no x in y satisfies true or false

Greedy subrules in ANTLR4

2 Answers