我有一个小的自定义脚本语言,我正在尝试更新它以允许 bool 表达式,例如 a > 2
和 a > 2 and (b < 3 or c > 5)
.这是我在这里遇到问题的括号表达式。
这是一个(根据@Bart Kiers 的回答从原始帖子开始编辑)展示问题的完整语法。这是我实际语法的精简版,但问题也出现在这里。
grammar test;
options {
language = 'JavaScript';
output = AST;
}
statement
: value_assignment_statement
EOF
;
value_assignment_statement
: IDENT
'='
expression
;
value_expression
: value_list_expression
| IDENT
;
value_list_expression
: value_enumerated_list
;
value_enumerated_list : '{' unary+ '}'
;
term
: LPAREN expression RPAREN
| INTEGER
| value_expression
;
unary : ( '+' | '-' )* term
;
mult : unary ( ('*' | '/') unary)*
;
expression : mult ( ('+' | '-') mult )*
;
boolean
: boolean_expression
EOF
;
boolean_expression
: boolean_or_expression
;
boolean_or_expression
: boolean_and_expression (OR boolean_and_expression)*
;
boolean_and_expression
: boolean_rel_expression (AND boolean_rel_expression)*
;
boolean_rel_expression
: boolean_neg_expression relational_operator boolean_neg_expression
;
boolean_neg_expression
: (NOT)? atom
;
atom
: LPAREN boolean_expression RPAREN
//| expression
;
relational_operator : '=' | '>' | '<';
LPAREN : '(';
RPAREN : ')';
AND : 'and';
OR : 'or';
NOT : 'not';
IDENT : LETTER LETTER+;
INTEGER : DIGIT+;
WS : (' ' | '\n' | '\r' | '\t')+ { $channel = HIDDEN; };
fragment DIGIT : '0'..'9';
fragment LETTER : ('a'..'z' | 'A'..'Z');
我尝试容纳带括号的 bool 表达式,例如
a > 2 or (b < 3)
位于 atom
中注释掉的行中规则。当我取消注释这一行并将其包含在语法中时,ANTLR 给了我这个错误:[fatal] rule atom has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
我想通过删除递归来解决这个问题,但我似乎无法从 Wikipedia description on how to remove left recursion 进行转换到我自己的东西。
在使用这个语法时,我有时想使用
statement
作为具有输入的根,例如 abc = 2 + 3
,它为名为 abc 的变量赋值。其他时候我想使用语法来评估表达式 boolean
作为输入的根,例如 abc > 3 and (xyz < 5 or xyz > 10)
.当我尝试使用@Bart 的答案作为模型时,它运行良好,直到我尝试合并 statement
使用的语法部分与 boolean
使用的零件.他们都应该能够使用 expression
,但这就是我遇到这个左递归错误的地方。那么,我怎样才能既处理括号又避免左递归问题呢?
最佳答案
bool 表达式与加法和乘法表达式相同,因此不应与它们分开。以下是解释所有类型表达式的方法:
grammar test;
parse
: expression EOF
;
expression
: or
;
or
: and (OR and)*
;
and
: rel (AND rel)*
;
rel
: add (('=' | '>' | '<') add)*
;
add
: mult (('+' | '-') mult)*
;
mult
: unary (('*' | '/') unary)*
;
unary
: '-' term
| '+' term
| NOT term
| term
;
term
: INTEGER
| IDENT
| list
| '(' expression ')'
;
list
: '{' (expression (',' expression)*)? '}'
;
AND : 'and';
OR : 'or';
NOT : 'not';
IDENT : LETTER LETTER*;
INTEGER : DIGIT+;
WS : (' ' | '\n' | '\r' | '\t')+ { $channel = HIDDEN; };
fragment DIGIT : '0'..'9';
fragment LETTER : ('a'..'z' | 'A'..'Z');
这将解析示例输入:
abc > 3 and (xyz < 5 or xyz > {1, 2, 3})
进入以下解析树:
关于antlr - 帮助对语法进行左分解以消除左递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6629397/