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 应该是贪婪的：右侧的所有内容都应该被明确地消耗直到表达式结束。

我试图重构规则以允许 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

好的，在这里来回反复之后，我想我终于明白你要找的是关联性。尝试：

grammar Example;

root: expression EOF;

expression
    : '(' expression ')'                            # parenExpr
    | <assoc=right>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: (' ' | '\r' | '\t')+ -> channel(HIDDEN);

（我冒昧地为您的备选方案添加了标签并简化了表达式规则。）。这些标签将在您的代码中派上用场，因为您需要单独处理每个备选方案。标签将为您提供单独的功能以在您的 listeners/visitors 中覆盖（以及特定于该替代方案的上下文类）

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

Answer 2

我就是这样做的，使用 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);

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

出于显而易见的原因，我无法使用 (1 进行尝试（我想输入对应于另一个版本，其中整数是操作数），但是使用 (true 它给了我看起来像您正在寻找的错误报告。我不是真正的 ANTLR4 专家，所以我不知道如何预测错误恢复的细节。

ANTLR4 中的贪心子规则

Greedy subrules in ANTLR4

grammar

parsing

antlr

antlr4