左递归
在上下文无关文法内里的说法,若一个非终结符号(non-terminal)r
有任何直接的文法规则或者透过多个文法规则,推导出的句型(sentential form)其中最左边的符号 又会出现r
,则我们说这个非终结符号r
是左递归的。
使用类似的方式我们可以定义出某文法本身是左递归的。
定义
"一个文法是左递归的,若我们可以找出其中存在某非终结符号A,最终会推导出来的句型(sentential form)里面包含以自己为最左符号(left-symbol)的句型"[1]
直接左递归
直接左递归(Immediate left recursion)以下面的句型规则出现:
这里 跟 代表不同的非终结符号跟终结符号组成的序列,并且 不一定要包含 。举例来说,以下规则
就是一个直接左递归的例子。 这规则的递归下降分析器(recursive descent parser)可能会像这样:
function Expr()
{
Expr(); match('+'); Term();
}
然后这个递归下降分析器在尝试去解析包含此规则的文法时,会陷入一个无穷的递归。
间接左递归
间接左递归(indirect left recursion)最简单的形式如下:
这规则可能产生 这种生成。
简单的说,间接左递归就是,并非在一条规则内完成左递归,而是在许多条规则之后,于产生的句子最左边出现了一开始的非终结符号。
更一般化的说法,对非终结符号 ,间接左递归被定义为以下的型态:
这里的 都是一堆终端与非终结符号的序列。
在由上而下语法分析(top-down parsing)里容纳左递归
一个包含左递归的形式文法不能以简易的 递归下降分析器进行语法分析,除非将文法转变为weakly equivalent 的右递归形式 (相对的,在LALR分析器里面则比较偏好左递归,因为比起右递归来说会使用比较少的堆叠);然而,比较复杂的由上而下(top-down)语法分析器里面可以借由使用缩减(by use of curtailment)来实做一般的上下文无关文法。 在2006年, Frost 和 Hafiz 提出一个算法,可以容纳包含直接左递归生成规则的 模糊文法(ambiguous grammers)。[2] 在2007年,Frost,Hafiz和Callaghan 将此算法延伸为一个完整的,可以适用并在多项式时间内处理直接或间接左递归,而且可以为高度模糊文法接近指数数目的分析树,产生小一些多项式空间的表示法。[3]这些人后来在Haskell编程语言里面以这个算法实做了一个的分析器组合(parser combinator)的集合。[4]
移除左递归
移除直接左递归
一个一般化后移除直接左递归的算法如下所述。 这个方法已经有过许多的改进,包括Robert C. Moore所撰写,名为"Removing Left Recursion from Context-Free Grammars"的改进。[5]
对于每个规则如下
(注意这里:
- A 是一个有左递归的非终端符号
- 是一个终端与非终端符号的序列,而且不为空字串 ( )
- 是一个不以A开头的,以终端与非终端符号组成的序列)
将A的规则改成以下规则:
然后对新创造出来非终端符号的规则
这个新创造出来的符号常被称为"尾巴"(tail),或者"rest"(剩余)
举例,考虑以下规则
我们可以改写为
然后最后一个规则可以缩短改写为
来避免掉左递归的出现
移除间接左递归
如果文法内不存在 (代表空字串)的生成 (不存在 这样的规则),而且不是循环(cyclic)的文法(对所有非终端符号A,不存在像是 这种形式的规则),以下这个一般化的算法可以用来去除文法的间接左递归:
将所有非终端符号以某个固定的顺序 排列
- 从 i = 1 到 n {
- 从 j = 1 到 i – 1 {
- 设 的生成规则为
-
- 将所有规则 换成
-
- 移除 规则中的直接左递归
- }
- 从 j = 1 到 i – 1 {
- }
陷阱
上面的转换使用右递归的文法来避免掉左递归的出现;但是这样会改变规则的结合律。左递归会创造出向左的结合律;但是右递归则会创造出向右的结合律。
范例 :
一开始我们拿到以下文法:
在我们使用上面的转换方式来移除掉左递归之后,我们取得了以下文法:
我们将字串 'a + a + a'用一个LALR分析器(这种分析器可以处理左递归的文法)使用原先的文法来分析,会得到下面的分析树(parse tree):
Expr / | \ Expr + Term / | \ \ Expr + Term Factor | | | Term Factor Int | | Factor Int | Int
整个分析树是往左边长,代表在这里的规则,'+'这个符号是左结合(left associative)的,或者说这规则代表(a + a) + a。
但是我们改变了文法之后,那这个分析树会变成:
Expr ---
/ \
Term Expr' --
| / | \
Factor + Term Expr' ------
| | | \ \
Int Factor + Term Expr'
| | |
Int Factor
|
Int
我们可以看出这棵树现在是往右边成长,意思上代表了a + ( a + a)。我们将'+'的结合律改变了, 变成是右结合的规则。 在处理加法的文法时这不是什么问题,但是如果我们现在处理的是减法,这就会变成是很严重的问题。
问题的关键在于有很多常用的算术规则要求左结合的规则。我们有几种解决办法: (a) 将规则重新改为左递归,(b) 使用更多的非终端符号来改写规则,以强迫文法合乎正确的结合(c) 如果使用YACC 或者Bison,他们有所谓算符宣告(operator declarations), %left, %right and %nonassoc,这一些算符可以告诉语法分析器产生程式(parser generator)应该遵从哪一种结合。
相关条目
- 尾部递归
参考资料
- ^ Notes on Formal Language Theory and Parsing (页面存档备份,存于互联网档案馆), James Power, Department of Computer Science National University of Ireland, Maynooth Maynooth, Co. Kildare, Ireland.JPR02
- ^ Frost, R.; R. Hafiz. A New Top-Down Parsing Algorithm to Accommodate Ambiguity and Left Recursion in Polynomial Time.. ACM SIGPLAN Notices. 2006, 41 (5): 46–54 [2010-10-11]. doi:10.1145/1149982.1149988. (原始内容存档于2020-06-28).
- ^ Frost, R.; R. Hafiz and P. Callaghan. Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars. (PDF). 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE (Prague). June 2007: 109–120 [2010-10-11]. (原始内容 (PDF)存档于2011-05-27).
- ^ Frost, R.; R. Hafiz and P. Callaghan. Parser Combinators for Ambiguous Left-Recursive Grammars. (PDF). 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN. January 2008, 4902 (2008): 167–181 [2010-10-11]. doi:10.1007/978-3-540-77442-6_12. (原始内容存档 (PDF)于2008-12-21).
- ^ Moore, Robert C. Removing Left Recursion from Context-Free Grammars (PDF). 6th Applied Natural Language Processing Conference. May 2000: 249–255. (原始内容 (PDF)存档于2006-09-16).
外部链接
- CMU lecture on left-recursion (页面存档备份,存于互联网档案馆)
- Practical Considerations for LALR(1) Grammars (页面存档备份,存于互联网档案馆)
- X-SAIGA (页面存档备份,存于互联网档案馆) - eXecutable SpecificAtIons of GrAmmars