递归下降解析器的一些问题(2009年)
摘要
一篇发表于 2009 年的博客文章,探讨了递归下降解析器存在的问题,具体分析了右递归表达式文法如何导致错误的运算符结合性(例如,将 5-1-2 的计算结果算成 6),并提出通过基于 EBNF 的文法改写来解决这一问题。
<p><a href="https://lobste.rs/s/ksmkzy/some_problems_recursive_descent_parsers">评论</a></p>
查看缓存全文
缓存时间: 2026/11/16 08:59
# 递归下降解析器的一些问题 来源:https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers ### 回顾 \- 递归下降 \(RD\) 解析器 这是我几个月前写的一篇相关文章 (https://eli.thegreenplace.net/2008/09/26/recursive-descent-ll-and-predictive-parsers/)。它很好地介绍了 RD 解析器的构建方式,以及它们能够解析哪些文法。这里,我想重点讨论那篇文章中开发的 RD 解析器存在的几个问题,并提出解决方案。 ### 问题 \#1:运算符的结合性 如果你还记得上一篇文章 (https://eli.thegreenplace.net/2008/09/26/recursive-descent-ll-and-predictive-parsers/),解析器的 expr 规则如下所示 \(采用 BNF 表示法\): `` : + | - | `` 之所以这样构建 \(expr 位于表达式右侧,term 位于左侧\),是为了避免文法中的*左递归*,因为左递归可能使 RD 解析器陷入无限循环,导致崩溃。但正如我在脚注中暗示的那样 \(一些读者也在评论中发现了这一点\),这会给文法引入结合性问题。我们来看看原因。维基百科对运算符结合性 (http://en.wikipedia.org/wiki/Operator_associativity)的解释比我好得多,因此我假设你已经阅读并理解了它。不过,简单来说,减法运算符的左结合性意味着 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 '返回 lval = %s' % lval return lval rval = self._expr() print 'lval = %s, rval = %s, 结果 = %s' % ( lval, rval, op(lval, rval)) return op(lval, rval) `` 注意,解析器先解析第一个 term,然后规则递归调用自身,解析后续部分。因此,表达式是从右向左构建的,这就导致了右结合性。如你所见,我添加了几条打印语句,以便更清楚地展示执行过程。对表达式 5\-1\-2 运行这段代码时,会打印: `` 返回 lval = 2 lval = 1, rval = 2, 结果 = -1 lval = 5, rval = -1, 结果 = 6 `` 这里的问题显而易见。由于递归,实际的返回过程是从右向左进行的。注意,这个文法以右结合的方式计算加法、乘法、减法和除法。这会给减法和除法带来问题,但不会影响加法和乘法,因为后两种运算无论从右向左还是从左向右计算,结果都相同[\[1\]](https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers#id3)。 ### 结合性问题的解决方案 我想,可以通过某种巧妙的方式重写 BNF 规则,使其既具有左结合性,又不包含左递归,从而解决这个问题[\[2\]](https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers#id4),但我会选择另一种方法。BNF 有一定的局限性,因为它在定义规则时实际上没有提供太多选择。所有规则都必须遵循非常严格的结构,如果想进行某些定制,就必须定义子规则,并递归引用它们。这时就轮到 EBNF (http://en.wikipedia.org/wiki/Ebnf)登场了。它的开发目的就是弥补普通 BNF 的一些不足。其中一项改进是增加了子规则重复的表示方式。例如,我们可以用 EBNF 将 expr 规则写成: `` : {+ } | {- } `` 注意花括号 \{\.\.\.\}。在 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。 ### 代码 这里正适合介绍一下代码。在这里 (https://github.com/eliben/code-for-blog/tree/main/2009/py_rd_parser_example),你可以找到旧版 \(基于 BNF\) 和新版 \(基于 EBNF\) 解析器的源代码,以及实现词法分析器的 lexer 模块。每个解析器都是独立完整的,可以单独使用。注意,它们是在 Python 2\.5 下开发和测试的。 ### 右结合运算符 有些运算符本来就具有右结合性。例如乘方。2^3^2=2^\(3^2\)=512,而不是 \(2^3\)^2 \(后者等于 64\)。我们可以保留这些运算符原有的定义,使用自然产生右结合性的递归规则。下面是为支持乘方而添加到基于 EBNF 的解析器中的 power 规则代码: `` # : ** # | # def _power(self): lval = self._factor() if self.cur_token.type == '**': self._match('**') lval **= self._power() return lval `` ### 中场休息 现在,我们已经有了一个正确的递归下降解析器,它使用基于 EBNF 的规则来解析表达式,并为每个运算符提供所需的结合性。这个解析器可以直接用于解析简单语言,已经能够投入生产使用。接下来要介绍的“问题”只与解析器的效率有关,因此,除非性能至关重要,否则你可能无需在意。 ### 问题 \#2:效率 递归下降解析器在处理表达式时存在一个固有的性能问题。这个问题源于定义运算符优先级的需要,而在 RD 解析器中,定义这种优先级的唯一方法就是使用递归子规则。例如 \(摘自基于 EBNF 的代码\): `` : {+ } | {- } : {* } | {/ } `` 这些规则的嵌套关系定义了加法和乘法的相对优先级。它告诉解析器:在加号之间,深入表达式,收集所有由乘号连接的子项。换句话说,它告诉解析器将表达式 5\+2\*2 分组为 5\+\(2\*2\),而不是 \(5\+2\)\*2。为了展示这种嵌套带来的问题,我在 expr、term、power 和 factor 各条规则中插入了简单的打印语句,用来显示解析过程中调用了哪些函数。我们来看看解析极其简单的表达式 42 时会发生什么: `` 调用 expr,当前词法单元为 NUMBER(42),位置为 0 调用 term,当前词法单元为 NUMBER(42),位置为 0 调用 power,当前词法单元为 NUMBER(42),位置为 0 调用 factor,当前词法单元为 NUMBER(42),位置为 0 `` **天哪\!\!\!** 仅仅解析只有一个词法单元的输入 42,就需要调用 4 次函数!遗憾的是,这个问题虽然表面上看起来很简单,实际上却并非如此。在 RD 解析器中,根本没有其他方式可以表达优先级:你必须使用嵌套规则,而这种嵌套在解析表达式时效率不高。解决这个问题的方法是使用混合解析器,代替纯 RD 解析器。人们已经开发出了一些能够高效解析中缀表达式 (http://en.wikipedia.org/wiki/Infix_notation)的算法。这篇文章 (http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm)对此做了很好的综述。可以将其中一种算法与 RD 结合起来,构建一个既能解析表达式,又能解析更高层编程语言结构的通用解析器。在以后的文章中,我将讨论这种解析器的一种实现。 [\[1\]](https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers#id1)更准确地说,加法和乘法在数学意义上都是满足结合律的二元运算 (http://en.wikipedia.org/wiki/Associativity)。[\[2\]](https://eli.thegreenplace.net/2009/03/14/some-problems-of-recursive-descent-parsers#id2)不过,我现在懒得寻找这样的方法。如果你找到了,请告诉我。
相似文章
递归代理推理
本文将测试时推理方法重新诠释为递归算子——Grow、Prune 和 Branch——并对其进行评估,发现 Branch 通过从预算耗尽的输出中恢复,持续提高准确性,同时建议在比较研究中使用配对评分。
递归语言模型在域外泛化
论文表明,递归语言模型通过隔离子任务、避免标准思维链所使用的捷径,并指出经典学习理论在真正推理方面的局限性,从而提高域外泛化能力。
写下 Pratt 解析法,好让自己记住它
一篇个人博客文章,通过讲解调度场算法、一个简单的 C 语言实现,以及作者在阅读 Pratt 原始论文时所做的笔记,来解释 Pratt 解析法。作者当时正在构建一个 C 表达式解析器,未来可能会发展成一个编译器。
ReSyn: 一种广义的递归正则表达式合成框架
ReSyn是一个广义的递归框架,用于从示例中合成正则表达式,旨在改进现有的合成技术。
一种类型化的代数解析方法
一篇介绍类型化代数解析方法的论文,很可能来自剑桥大学。