以下简单的“计算器表达式”文法(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)?