左递归

✍ dations ◷ 2025-06-22 14:37:13 #左递归

在计算机科学里面，左递归是一种递归的特殊状况。

在上下文无关文法内里的说法，若一个非终结符号（non-terminal）r有任何直接的文法规则或者透过多个文法规则，推导出的句型（sentential form）其中最左边的符号又会出现r，则我们说这个非终结符号r是左递归的。

使用类似的方式我们可以定义出某文法本身是左递归的。

"一个文法是左递归的，若我们可以找出其中存在某非终结符号A，最终会推导出来的句型(sentential form)里面包含以自己为最左符号(left-symbol)的句型"

直接左递归（Immediate left recursion）以下面的句型规则出现：

这里 ${displaystyle alpha }$ (recursive descent parser)可能会像这样：

function Expr(){      Expr();  match('+');  Term();}

然后这个递归下降分析器在尝试去解析包含此规则的文法时，会陷入一个无穷的递归。

间接左递归(indirect left recursion)最简单的形式如下：

这规则可能产生 ${displaystyle ARightarrow Balpha Rightarrow Abeta alpha Rightarrow ldots }$ (operator declarations)， %left, %right and %nonassoc，这一些算符可以告诉语法分析器产生程式(parser generator)应该遵从哪一种结合。

相关

互联网历史互联网历史起源于美国努力将计算机网络相互连接的过程，这个过程涉及国际合作，特别是与英国、法国研究人员的合作。互联网的主要前身为阿帕网。1974年美国国防部国防高等研究计
裂齿症候群裂齿症候群（Cracked tooth syndrome，缩写 CTS），是一种牙科症状，患者牙齿上的裂缝延伸到根部，有时候会延伸至牙髓，甚至穿越它。裂齿的种类相当多，医师往往不易正确诊断。
AZ截至2010年亚利桑那州（英语：Arizona，i/ɛərᵻˈzoʊnə, ærᵻ-/）是美国一个位于西南部的州份，同时也是西部和山区州份之一。此州是美国第6大及人口第14大的州份。首府和最大城
薇儿丹蒂薇儿丹蒂（古诺斯语：；英语：Verthandi）是北欧神话中掌管命运的诺伦三女神其中之一（排行老二）。她和姐姐乌尔德，共同在木片表面刻上如尼字母，决定命运。被认为是掌管“现在”的女神。
尼可籁·霍奇艾诺夫尼可籁·霍奇艾诺夫（俄语：Николай Хозяинов，英语：Nikolay Khozyainov, 1992年7月17日－），俄罗斯古典钢琴家，诞生于俄罗斯远东地区海兰泡（俄语名布拉戈维申斯克，Blagoves
妮可·舒辛格妮可·舒辛格（英语：Nicole Prescovia Elikolani Valiente；1978年6月29日－）又名妮可·奇亚，美国歌手及舞蹈员。是美国流行女子组合小野猫的主唱和舞蹈员。她的首张个人专辑于2010年
韩国电影列表本表列出历年来在韩国上映的韩国电影（包含与他国合拍的电影）：列表说明　　
讲道馆四天王讲道馆四天王（こうどうかんしてんのう）为柔道的讲道馆创立期至黎明期间，与其他流派比赛时的四名代表选手，之后以讲道馆的师范代之身活跃的西乡四郎、横山作次郎、山下义韶、富田
卧都河卧都河，位于中华人民共和国黑龙江省北部，是嫩江左岸的一条支流。发源于黑河市爱辉区北部滨南林场西北小兴安岭河界山，自东北向西南流，流经嫩江市北部卧都河林场，最后于多宝山镇卧
莫宁火山莫宁火山（英语：Mount Morning）是南极洲的穹形火山，位于维多利亚地，处于迪斯卡弗里火山西南面，海拔高度2,725米，该火山在1901至1904年英国探险队发现。