如何修复与语义谓词一起使用的左递归错误?
How to fix the error in left-recursion used with semantic predicates?
我想用布尔值解析两种类型的表达式:
- 第一个是带有布尔值的初始化表达式,例如:init : false
- 最后一个是带有布尔值的派生表达式,例如:derive : !express or (express and (amount >= 100))
我的想法是将语义谓词放在一组规则中,
目标是当我解析一个以单词 'init' 开头的布尔表达式时,它只能转到一个提议的替代规则,即 boolliteral,最后一个替代规则 布尔表达式。如果它是以单词 '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 个错误
构建失败
显然,当谓词出现在 left-recursive 规则调用之前时,ANTLR4 对(直接)left-recursion 的支持不起作用。因此,您可以通过将谓词移动到 left-recursive 替代项中的第一个 boolExpression
之后来修复错误。
就是说,谓词似乎一开始并不是真正必需的 - 至少在您向我们展示的示例中(或者据我所知在您编辑之前的示例中)。由于具有约束类型 INIT
的 boolExpression
显然只能匹配 boolLiteral
,您可以按如下方式更改 initDefinition
:
initDefinition : t=INIT ':' boolLiteral ;
然后 boolExpression
将始终具有约束类型 DERIVE
并且不再需要谓词。
一般来说,如果您想根据 y
或 z
调用 non-terminal x
中的不同选项,您应该简单地拥有多个版本x
个,然后从 y
调用一个,从 z
调用另一个。这通常比在代码中乱扔动作和谓词要麻烦得多。
同样,拥有一个比它应该匹配的更多的规则然后在稍后阶段检测非法表达式而不是试图在语法级别拒绝它们也是有意义的。特别是初学者经常尝试编写只允许 well-typed 表达式的语法(拒绝诸如 1+true
之类的语法错误)并且永远不会奏效。
我想用布尔值解析两种类型的表达式:
- 第一个是带有布尔值的初始化表达式,例如:init : false
- 最后一个是带有布尔值的派生表达式,例如:derive : !express or (express and (amount >= 100))
我的想法是将语义谓词放在一组规则中, 目标是当我解析一个以单词 'init' 开头的布尔表达式时,它只能转到一个提议的替代规则,即 boolliteral,最后一个替代规则 布尔表达式。如果它是以单词 '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 个错误
构建失败
显然,当谓词出现在 left-recursive 规则调用之前时,ANTLR4 对(直接)left-recursion 的支持不起作用。因此,您可以通过将谓词移动到 left-recursive 替代项中的第一个 boolExpression
之后来修复错误。
就是说,谓词似乎一开始并不是真正必需的 - 至少在您向我们展示的示例中(或者据我所知在您编辑之前的示例中)。由于具有约束类型 INIT
的 boolExpression
显然只能匹配 boolLiteral
,您可以按如下方式更改 initDefinition
:
initDefinition : t=INIT ':' boolLiteral ;
然后 boolExpression
将始终具有约束类型 DERIVE
并且不再需要谓词。
一般来说,如果您想根据 y
或 z
调用 non-terminal x
中的不同选项,您应该简单地拥有多个版本x
个,然后从 y
调用一个,从 z
调用另一个。这通常比在代码中乱扔动作和谓词要麻烦得多。
同样,拥有一个比它应该匹配的更多的规则然后在稍后阶段检测非法表达式而不是试图在语法级别拒绝它们也是有意义的。特别是初学者经常尝试编写只允许 well-typed 表达式的语法(拒绝诸如 1+true
之类的语法错误)并且永远不会奏效。