如何修复与语义谓词一起使用的左递归错误?

Question

我想用布尔值解析两种类型的表达式：
- 第一种是带有布尔值的初始化表达式，如：init : false
- 最后一个是带有布尔值的派生表达式，如：derive : !express or (express and (amount >= 100))

我的想法是将语义谓词放在一组规则中， 目标是当我解析以单词"init"开头的布尔表达式时，它必须只转到一个提议的替代规则，即boolExpression中的最后一个替代规则。如果它是一个以单词"derive"开头的表达式，那么它可以访问boolExpression的所有替代品。

我知道我可以制作两种类型的boolExpression，没有语义谓词，如boolExpressionInit和boolExpressionDerive...但我想尝试一下我的想法，如果它只能使用一个带有语义谓词的 boolExpression。

这是我的语法

grammar TestExpression;
@header
{
package testexpressionparser;
}
@parser::members {
int vConstraintType;
}
/* SYNTAX RULES */
textInput       : initDefinition 
| derDefinition ;
initDefinition  : t=INIT {vConstraintType = $t.type;} ':' boolExpression ;
derDefinition   : t=DERIVE {vConstraintType = $t.type;} ':' boolExpression ;
boolExpression  : {vConstraintType != INIT || vConstraintType == DERIVE}? boolExpression (boolOp|relOp) boolExpression 
| {vConstraintType != INIT || vConstraintType == DERIVE}? NOT boolExpression
| {vConstraintType != INIT || vConstraintType == DERIVE}? '(' boolExpression ')' 
| {vConstraintType != INIT || vConstraintType == DERIVE}? attributeName
| {vConstraintType != INIT || vConstraintType == DERIVE}? numliteral
| {vConstraintType == INIT || vConstraintType == DERIVE}? boolliteral
;
boolOp          : OR | AND ;
relOp           : EQ | NEQ | GT | LT | GEQT | LEQT ;
attributeName   : WORD;
numliteral      : intliteral | decliteral;
intliteral      : INT ;
decliteral      : DEC ;
boolliteral     : BOOLEAN;

/* LEXICAL RULES */
INIT            : 'init';
DERIVE          : 'derive';
BOOLEAN         : 'true' | 'false' ;
BRACKETSTART    : '(' ;
BRACKETSTOP     : ')' ;
BRACESTART      : '{' ;
BRACESTOP       : '}' ;
EQ              : '=' ;
NEQ             : '!=' ;
NOT             : '!' ;
GT              : '>' ;
LT              : '<' ;
GEQT            : '>=' ;
LEQT            : '<=' ;
OR              : 'or' ;
AND             : 'and' ;
DEC             : [0-9]* '.' [0-9]* ;
INT             : ZERO | POSITIF;
ZERO            : '0';
POSITIF         : [1-9] [0-9]* ;
WORD            : [a-zA-Z] [_0-9a-zA-Z]* ;
WS              : (SPACE | NEWLINE)+ -> skip ;
SPACE           : [ t] ;                       /* Space or tab */
NEWLINE         : 'r'? 'n' ;                  /* Carriage return and new line */

我只是语法会成功运行，但我收到的是："错误(119)：TestExpression.g4：：：以下规则集是相互左递归的 [boolExpression]
1 错误 构建失败">

Answer 1

显然，当谓词出现在左递归规则调用之前时，ANTLR4对(直接)左递归的支持不起作用。因此，您可以通过将谓词移动到左递归替代项中的第一个boolExpression之后来修复错误。

也就是说，似乎谓词首先并不是真正必要的 - 至少在您向我们展示的示例(或据我所知的编辑之前的示例)中不是必需的。由于约束类型INIT的boolExpression显然只能匹配boolLiteral，因此您可以按如下方式更改initDefinition：

initDefinition  : t=INIT ':' boolLiteral ;

然后boolExpression将始终具有约束类型DERIVE并且不再需要谓词。

通常，如果您想根据它是由y还是z调用的非终端x中允许不同的替代方案，您应该简单地拥有多个版本的x，然后从y调用一个，从z调用另一个。这通常比在代码中乱扔动作和谓词要麻烦得多。

同样，让规则匹配的超出应有的匹配度，然后在稍后阶段检测非法表达式，而不是尝试在语法级别拒绝它们，这也是有意义的。具体来说，初学者经常尝试编写只允许类型良好的表达式的语法(拒绝像1+true这样带有语法错误的东西)，并且永远不会奏效。