递归下降解析 - 从LL(1)向上
-
02-07-2019 - |
题
以下简单的<!>“计算器表达式<!>”;语法(BNF)可以用一个简单的递归下降解析器轻松解析,这是一个预测LL(1):
<expr> := <term> + <term>
| <term> - <term>
| <term>
<term> := <factor> * <factor>
<factor> / <factor>
<factor>
<factor> := <number>
| <id>
| ( <expr> )
<number> := \d+
<id> := [a-zA-Z_]\w+
因为看到下一个令牌以便知道要选择的规则总是足够的。但是,假设我添加以下规则:
<command> := <expr>
| <id> = <expr>
为了在命令行上与计算器交互,使用变量,如下所示:
calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49
我不能使用简单的LL(1)预测解析器来解析<command>
规则吗?我试着为它编写解析器,但似乎我需要知道更多的令牌。是使用回溯的解决方案,还是我可以实现LL(2)并始终向前看两个令牌?
如何让RD解析器生成器处理这个问题(例如ANTLR)?
解决方案
的问题
<command> := <expr>
| <id> = <expr>
是当你<!>时看到<!>“; <id>
你无法判断它是否是分配的开始(第二条规则),或者它是<!>“<factor>
<!>”;。您只会知道何时阅读下一个令牌。
AFAIK ANTLR是LL(*)(并且如果我没有记错的话也可以生成rat-pack解析器)所以它可能会一次考虑两个令牌来处理这个语法。
如果您可以使用语法我建议为作业添加关键字(例如let x = 8
):
<command> := <expr>
| "let" <id> "=" <expr>
或使用=
表示评估:
<command> := "=" <expr>
| <id> "=" <expr>
其他提示
我认为使用递归下降解析器有两种方法可以解决这个问题:使用(更多)前瞻或回溯。
先行
command() {
if (currentToken() == id && lookaheadToken() == '=') {
return assignment();
} else {
return expr();
}
}
回溯
command() {
savedLocation = scanLocation();
if (accept( id )) {
identifier = acceptedTokenValue();
if (!accept( '=' )) {
setScanLocation( savedLocation );
return expr();
}
return new assignment( identifier, expr() );
} else {
return expr();
}
}
问题在于语法:
<command> := <expr>
| <id> = <expr>
不是一个相互递归的过程。对于递归的正确解析器,您需要确定一个非递归的等价物。
rdentato帖子显示了如何解决这个问题,假设你可以使用语法。这个powerpoint详细说明了这个问题,并展示了如何纠正它:
ANTLR 3 使用<!>“LL(*) <!> QUOT;解析器而不是LL(k)解析器,因此如果必须使用特别优化的确定性有限自动机(DFA),它必须在没有回溯的情况下直到它到达输入的末尾。
不隶属于 StackOverflow