parsing - ANTLR4 中的贪心子规则

Question

我正在研究一个解析器语法，它应该允许尾随表达式而不包含符号。以下是证明该问题的简化版本:

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: (' ' | '\r' | '\t')+ -> channel(HIDDEN);

如果您尝试解析以下表达式，您会注意到，虽然解析正确地识别了输入，但它报告了一个歧义:

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

错误报告按预期工作(稍后会详细介绍):

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

我正在寻找一些方法来明确地告诉解析器 量词 应该是贪婪的:在表达式结束之前应该明确地使用右侧的所有内容。

我试图重构规则以允许 quantifier 仅在二进制表达式的 RHS 上。虽然它有效，但错误恢复机制变得无法识别大多数表达式:

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: (' ' | '\r' | '\t')+ -> channel(HIDDEN);

如您所见，问题解决了:

但它是以更复杂的语法为代价的，并且无法识别像 (1:

这样的错误输入

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

还有其他人对如何修复它有任何其他想法吗？

Answer 1

我就是这样做的，使用 Antlr4 的内置算法优先解决歧义(因为语法肯定是歧义的)。为了使优先级算法起作用，将限定条件视为具有低优先级的一元运算符是很有用的，这就是为什么下面的 quantifier 只是“运算符”而不是完整的表达式。据推测，在真正的语法中，您会有其他量词，并且很可能具有更高优先级的一元运算符，例如 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: (' ' | '\r' | '\n' | '\t')+ -> channel(HIDDEN);

这与您帖子中的示例不太一样，因为您修改了问题的第一个版本中的一些小细节。但我认为这是指示性的。

出于显而易见的原因，我无法使用 (1(我想输入对应于整数是操作数的不同版本)尝试它，但使用 (true它给了我你正在寻找的错误报告。我不是真正的 ANTLR4 专家，所以我不知道如何预测错误恢复的细节。