有几件事是不正确的:
1
您已将WS
令牌放在HIDDEN
通道上,这使得它们无法用于解析器规则。因此WS
,您的规则中的所有标记body
都不正确。
2
_(您的最新编辑删除了左递归问题,但我仍然会指出,抱歉,您的另一个问题有左递归规则(expr
),所以我会在此处留下此信息)_
ANTLR 是一个LL 解析器生成器,因此您可以创建左递归语法。以下是左递归的:
expr
: term term operator
;
term
: INT
| ID
| expr
;
因为规则中的第term
一个expr
可能匹配expr
规则本身。与任何 LL 解析器一样,ANTLR 生成的解析器无法处理左递归。
3
如果您解决WS
问题,您的body
规则将产生以下错误消息:
(1/7) 决策可以使用多种选择来匹配诸如“INT”之类的输入
这意味着解析器无法“看到”INT
令牌属于哪个规则。这是因为您的所有body
选择都可以重复零次或多次,expr
并且nested
也可以重复。而且它们都可以匹配一个INT
,这就是ANTLR所抱怨的。如果您*
像这样删除 's:
body
: nested
| var
| get
;
// ...
expr
: term (term operator)
;
nested
: expr (expr operator)
;
错误会消失(尽管这仍然不会导致您的输入被正确解析!)。
我意识到这听起来可能仍然含糊不清,但解释起来并非易事(如果您不熟悉这一切,也可以理解)。
4
要正确考虑递归expr
inside expr
,您需要避免左递归,正如我在#2中解释的那样。你可以这样做:
expr
: term (expr operator | term operator)*
;
这仍然是模棱两可的,但这是在使用 LL 语法描述后缀表达式的情况下,不可避免的 AFAIK。options { ... }
要解决此问题,您可以在语法部分中启用全局回溯:
options {
language=Python;
output=AST;
backtrack=true;
}
演示
如何解析递归表达式的小演示可能如下所示:
grammar star;
options {
language=Python;
output=AST;
backtrack=true;
}
parse
: expr EOF -> expr
;
expr
: (term -> term) ( expr2 operator -> ^(operator $expr expr2)
| term operator -> ^(operator term term)
)*
;
expr2
: expr
;
term
: INT
| ID
;
operator
: ('*' | '+' | '/' | '%' | '-')
;
ID
: ('a'..'z' | 'A'..'Z') ('a..z' | '0'..'9' | 'A'..'Z')*
;
INT
: '0'..'9'+
;
WS
: (' ' | '\n' | '\t' | '\r') {$channel=HIDDEN;}
;
测试脚本:
#!/usr/bin/env python
import antlr3
from antlr3 import *
from antlr3.tree import *
from starLexer import *
from starParser import *
def print_level_order(tree, indent):
print '{0}{1}'.format(' '*indent, tree.text)
for child in tree.getChildren():
print_level_order(child, indent+1)
input = "5 1 2 + 4 * + 3 -"
char_stream = antlr3.ANTLRStringStream(input)
lexer = starLexer(char_stream)
tokens = antlr3.CommonTokenStream(lexer)
parser = starParser(tokens)
tree = parser.parse().tree
print_level_order(tree, 0)
产生以下输出:
-
+
5
*
+
1
2
4
3
对应于以下 AST:
