Newshot 回顾：递归下降（RD）解析器
几个月前我写了一篇关于这个主题的文章。它对 RD 解析器如何构建以及能解析哪些文法做了很好的介绍。
这里我想重点讨论那篇文章中开发的 RD 解析器的几个问题，并提出解决方案。
问题 #1：运算符结合性
如果你还记得上一篇文章，解析器的 expr 规则是这样的（BNF 表示法）：
<expr> : <term> + <expr>
| <term> - <expr>
| <term>
这样构建（表达式右侧是 expr，左侧是 term），是为了避免文法中的左递归，左递归会导致 RD 解析器陷入无限循环而崩溃。
但正如我在脚注中暗示的（一些读者在评论中也发现了），这给文法注入了结合性问题。让我们看看为什么。
维基百科在解释什么是运算符结合性方面比我强得多，所以我假设你已经阅读并理解了。
简而言之，减号运算符的左结合性意味着 5 - 1 - 2 = (5 - 1) - 2 而不是 5 - (1 - 2)（后者返回不同的结果）。
但是，如果你用上述 expr 的 BNF 在解析器中运行 5 - 1 - 2，你会得到 6 而不是 2。那么哪里出错了？
问题出在文法定义（BNF）本身。expr 规则的定义方式使其本质上是右结合而不是左结合。规则的层次结构隐式地定义了它们的结合性，因为它定义了哪些部分会被组合在一起。为了更好地理解，或许实现 expr 规则的代码会有帮助：
def _expr(self):
lval = self._term()
if self.cur_token.type == '+':
self._match('+')
op = lambda a, b: a + b
elif self.cur_token.type == '-':
self._match('-')
op = lambda a, b: a - b
else:
print 'returning lval = %s' % lval
return lval
rval = self._expr()
print 'lval = %s, rval = %s, res = %s' % (
lval, rval, op(lval, rval))
return op(lval, rval)
注意，第一个 term 被解析，然后规则为下一个 term 递归调用自身。因此表达式是从右到左构建的，这导致了它的右结合性。
如你所见，我添加了几个打印输出，以更好地展示发生了什么。当对表达式 5 - 1 - 2 运行时，会打印：
returning lval = 2
lval = 1, rval = 2, res = -1
lval = 5, rval = -1, res = 6
我们在这里清楚地看到了问题。由于递归，实际的返回是从右到左进行的。
注意，这个文法以右结合的方式计算加法、乘法、减法和除法。这会导致减法和除法出现问题，但加法和乘法没有问题，因为这些操作无论从右到左还是从左到右计算，结果都相同 [1]。
结合性问题的解决方案
我想这个问题可以通过以某种复杂的方式重写 BNF 规则来解决，使它们既左结合又不是左递归 [2]，但我会选择另一种方法。
BNF 有一定的局限性，因为它在定义规则时并没有真正提供很多选项。所有规则必须具有非常严格的结构，如果你想自定义某些东西，你必须求助于定义子规则并递归引用它们。
进入 EBNF。它被开发出来是为了修复普通 BNF 的一些缺陷。其中之一是增加了子规则的重复。例如，我们可以用 EBNF 编写 expr 规则如下：
<expr> : <term> {+ <term>}
| <term> {- <term>}
注意大括号 { ... }。在 EBNF 中，这些表示“重复 0 次或多次”。这仍然是 LL(1) 文法，但现在表达得更舒适一些。这种表示非常适合编码，因为重复可以用循环自然地表达。
下面是使用这种惯用法对 expr 规则的重新实现：
def _expr(self):
lval = self._term()
while ( self.cur_token.type == '+' or
self.cur_token.type == '-'):
if self.cur_token.type == '+':
self._match('+')
lval += self._term()
elif self.cur_token.type == '-':
self._match('-')
lval -= self._term()
return lval
注意，while 循环“吃掉”了表达式中所有连续的项，并按预期的从左到右方式累积结果。现在计算 5 - 1 - 2 将正确地得到 2。
代码
这里是引用代码的好地方。在这里你会找到旧版（基于 BNF）解析器和新版（基于 EBNF）解析器的源代码，以及实现分词器的词法分析模块。每个解析器都是自包含的，可以单独使用。注意，它们是在 Python 2.5 下开发和测试的。
右结合运算符
有些运算符本质上是右结合的。例如幂运算。2^3^2 = 2^(3^2) = 512，而不是 (2^3)^2（等于 64）。
我们可以让这些运算符保持之前的定义，使用一条递归规则，自然地产生右结合性。以下是添加到基于 EBNF 的解析器中以支持幂运算的 power 规则代码：
# <power> : <factor> ** <power>
# | <factor>
#
def _power(self):
lval = self._factor()
if self.cur_token.type == '**':
self._match('**')
lval **= self._power()
return lval
幕间休息
现在我们有了一个正确的递归下降解析器，它使用基于 EBNF 的规则来解析表达式，并为每个运算符提供所需的结合性。这个解析器可以随时用于解析简单的语言——它已可用于生产环境。我接下来提出的“问题”只与解析器的效率有关，所以除非性能至关重要，否则它可能无关紧要。
问题 #2：效率
递归下降解析器在处理表达式时存在一个固有的性能问题。这个问题源于需要定义运算符优先级，而在 RD 解析器中，定义这种优先级的唯一方法就是使用递归子规则。例如（来自基于 EBNF 的代码）：
<expr> : <term> {+ <term>}
| <term> {- <term>}
<term> : <power> {* <power>}
| <power> {/ <power>}
这些规则的嵌套定义了加法和乘法的相对优先级。它告诉解析器：在加号之间，深入表达式并收集所有由乘号连接的子项。换句话说，它告诉解析器将表达式 5 + 2 2 分组为 5 + (2 2)，而不是 (5 + 2) * 2。
为了看到这种嵌套导致的问题，我在 expr、term、power 和 factor 每条规则中都插入了简单的打印输出，以显示解析期间调用了哪些函数。让我们看看解析简单表达式 42 时会发生什么：
expr called with NUMBER(42) at 0
term called with NUMBER(42) at 0
power called with NUMBER(42) at 0
factor called with NUMBER(42) at 0
天哪！！！仅仅解析单 token 输入 42 就调用了 4 次函数！不幸的是，虽然这个问题表面上看起来很简单，但其实并不简单。在 RD 解析器中，根本没有其他方式来表达优先级——你必须使用嵌套规则，而这种嵌套在解析表达式时效率低下。
这个问题的解决方案是使用混合解析器，而不是纯 RD 解析器。已经开发了一些算法来高效地解析中缀表达式。这篇文章提供了一个很好的综述。其中一种算法可以与 RD 结合，为表达式和更高级的编程语言结构提供一个通用解析器。
在未来的文章中，我将讨论这种解析器的实现。
如需评论，请给我发邮件。