parsing - 如何避免带有可选右手操作数的规则中的歧义？

Question

众所周知，ANTLR4 会自动进行左递归优化。但是当最后一个操作数是可选的时如何避免歧义呢？

以下面的简化语法为例：

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);

此文法接受表达式no x in y和no x in y satisfies condition。('satisfies' expression)?但是，在左重构期间不考虑可选子规则。结果，输入no x in y satisfies true and false被报告为歧义输入：

解析器假设有两棵可行的树no x in y satisfies (true and false)和(no x in y satisfies true) and false，但只有第一棵树应该被认为是可行的解释。

有人可能会争辩说我可以重写语法如下：

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

ID尽管它“有效”，但除了对性能的影响之外，错误报告不再有用，因为在解析器到达令牌之前无法推断接下来会发生什么。

有没有办法重构语法以明确指定量词的 RHS 中的表达式应始终优先？

标签： parsingantlrantlr4