c语言文法规则左递归变右递归

A. 什么是左递归

左递归在计算机科学里面，左递归是一种递归的特殊状况。在上下文无关文法内里的说法，，若一个非终端符号(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 {
设的生成规则为将所有规则 换成移除规则中的直接左递归}}[编辑]陷阱上面的转换使用右递归的文法来避免掉左递归的出现；但是这样会改变规则的结合律。左递归会创造出向左的结合律；但是右递归则会创造出向右的结合律。范例 :一开始我们拿到以下文法：在我们使用上面的转换方式来移除掉左递归之后，我们取得了以下文法：我们将字串 '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)应该遵从哪一种结合。

B. 已知文法G[S]: S->(L)|a L->L，S|S (1)消除文法G的左递归,并为每个非终结符构造不带回溯的递归子程序；

（1）S→(L)|aS’ S’→S|ε L→SL’ L’→SL’|ε (2) FIRST 和 FOLLOW FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S’)＝{，a,ε} FOLLOW(S’)＝{#，，，)} FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L’)＝{，，ε} FOLLOW(L’〕＝{ )}

C. 什么是语法规则的递归性，请举例说明

递归性，也可相近地理解为层次性或有机性。是机体或系统的共性，是系统得以存在，运作和发展的基本手段。递归性不仅是转换生成语法中的一种语法属性，而且它与任意性、 线性一样是语言的根本性质之一。

语言结构层次和言语生成中相同结构成分的重复或相套。反复地使用构成句法关系的有限的几种句法规则，不断地进行同功能替换，以构成复杂的短语或句子。

在句法组合中，递归性有两种表现，一种是从初始结构开始，自始至终重复运用同一条语法规则。

例如"计算机/我//喜欢"这个句子是主谓结构，它们的谓语( / 以后的部分)本身又是主谓结构，这里，"主语+谓语"这条语法规则不间断地使用了两次；另外一种表现是，同一条语法规则可以在一个结构上间隔地重复使用。

(3)c语言文法规则左递归变右递归扩展阅读：

递归性是语言的根本性质之一，语言的递归性赋予语言无限的创造性，说话者可以创造出自己从未听过或者讲过的话语。递归性是语言结构层次和言语生成中相同结构成分的重复或相套 。句子能够很好地体现语言的递归性，而通常我们认为，句子是语言中最大的句法单位，所以句法成为人们研究的核心。

人有限的记忆和无限的思维之间的矛盾促生了词的递归性，递归性在所有语言里都有表现，印欧语系的词根，词缀，缩写等即是递归性的表现。递归的最终目的是形成词素，汉语的通常意义的"字"是较完善的递归的结果。

它应称为"词素"较合适，汉语的"字"有时做词用(例"会")，即人们常说的单字词。有时做词素用(例"协会")，汉语"字"由词向词素的过渡是汉语的一场革命。

D. 关于LL(1)文法的编译原理题目

判断是不是LL(1)，首先看候选式的首字符有没有相同的，第二判断首字符迭代进去是否会构成左递归。
如果首字符不相同，也没用左递归就说明此文法是LL(1)
M→MaH｜H
H→(M)｜b(M)｜b
第一个产生式中存在左递归:M->MaH
第二个产生式中存在首字符相同:H->b(M) ,
H->b
怎么改呢？
对第一个产生式，消除左递归就是要变成右递归，把右边剩下的符号提到前面:
M->aHM'

M'->aHM'
对第二个产生式，提出公共因子
H->b( (M)|ε)
=>
H->bH'

H'->(M)|ε

E. 消除文法的左递归性

为了消除那些经多步推导所出现的左递归性，可首先查出那些具有左递归性的非终结符号，然后对以这些非终结符号为左部的产生式，通过逐步代入有关产生式的方式将它们化为直接左递归的产生式，最后再消除其中的全部直接左递归即可。显然，这是一个十分繁琐的过程。下面，我们再介绍一种一次消去文法的一切左递归性的方法，为此，先引入文法的一种矩阵表示。
设G是一前后文无关文法，它的VN中含有n个非终结符号：X1,X2,…,Xn，对于G的每一产生式
Xi→γ1|γ2|…|γm，
我们可将它的各候选式γ1,γ2,…,γm分为两类： 把以非终结符号打头的γi归为一类；而将以终结符号打头的归为另一类。例如，若某个γk以Xj打头，就把γk写成Xjαji (αji∈V+)。此时，若将元语言符号→及|形式地用“=”及“+”表示，即可将此产生式写成
Xi=X1α1i+X2α2i+…+Xnαni+β i
其中，β i是那些以终结符号打头的诸候选式之“和”。此外，若此产生式不含以某一非终结符号Xj打头的候选式，则相应的αji为。这样，我们就可将G的诸产生式写成如下的矩阵方程
(X1 X2 … Xn)=(X1 X2 … Xn)·α11[]α12[]…[]α1n
α21[]α22[]…[]α2n
…[]…[]…[]…
αn1[]αn2[]…[]αnn+(β1 β2 … βn)(411)
或
X=XA+B(412)
式(411)或式(412)即为文法G的一种矩阵表示。不过，需要注意的是，对上面各式中所出现的运算符应作如下的理解： 乘法运算表示字符串的连接，加法运算表示选择。仿342中的讨论可知，矩阵方程(412)有形如
X=BA*(413)
的解。显然，要计算矩阵A的闭包A*一般是很困难的，但可设法予以回避。事实上，由于
A*=I+A+A2+…=I+AA*
其中
I=ε[][][]…[]
[]ε[][]…[]
…[]…[]…[]…[]…
[][][]…[]ε
若设
A*=Z=z11[]z12[]…[]z1n
z21[]z22[]…[]z2n
…[]…[]…[]…
zn1[]zn2[]…[]znn
则可得如下两个矩阵式
X=BZ(414)
Z=I+AZ(415)
由于列矩阵B的各元素的每一项均以终结符号开始，故矩阵式(414)相应的诸产生式的右部符号串也以终结符号开始，也就是说它们都不是左递归的。至于由式(415)新引入的产生式，由于它们的左部为zij，显然也不会有任何的左递归性。此外，从式(412)推演到式(414)和式(415)的过程中，实际上只进行了一些等价的代换演算，故由式(414)和式(415)所表示的文法将与原文法G等价。但若新文法中含有无用的产生式 (它们可能由式(415)引入)，则应予以剔除。
例41考虑文法
S→Sa|Ab|a(416)
A→Sc
显然，其中S，A都是左递归的非终结符号。首先写出此文法的矩阵表示
(S A)=(S A)a[]c
b[]+(a )
令
a[]c
b[]*=Z=z11[]z12
z21[]z22
则有
(S A)=(a ) z11[]z12
z21[]z22
z11[]z12
z21[]z22=ε[]
[]ε+a[]c
b[]z11[]z12
z21[]z22
于是，我们就得到了与文法(416)等价的文法
S→az11A→az12
z11→az11|cz21|ε
z12→az12|cz22
z21→bz11z22→bz12|ε
删除其中的无用产生式，我们有
S→az11
z11→az11|cz21|ε
z21→bz11

F. 编译中左递归与右递归的差异在哪里，为什么要把左

采纳我告诉你答案
-”接线柱出；被测电压不要超过电压表的量程；

G. 具有左递归的文法对递归下降分析有何影响

你说的应该是编译原理吧。
递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。
每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。

所以，当有左递归出现时，递归下降分析程序就会出现回朔，将可能产生无限的循环，所以递归下降分析的前提条件之一就是消除左递归。

H. 编译原理一个文法的EBNF表示

首先
lexp-seq->lexp-seq lexp|lexp
消除左递归 得
lexp-seq->lexp q'
q'->lexp q'|空

解的ebnf为

lexp->NUMBER|(+|-|*)lexp{lexp}
就得
S->{NUMBER(+|-|*)}NUMBER
{}中间表示0次或以上

I. 编译原理文法问题，急急急

第一题
S->AB

A->aA'b
A'->aA'b|ε
B->B'
B'->dB'|ε
----------------------
第二题
S->aS'b

S'->aS'b|D
D->dD|ε
----------------------
第三题
最左推导的话，我认为要先消除左递归才行（把左递归转成右递归），消除之后:
N->DN'
N'->DN'|ε
D->0|1|2|...|9
最左推导为 N->DN'->2N'->2DN'->25N'->25DN'->258N'->258
规范推导(最右推导)为N->ND->N8->ND8->N58->D58->258
----------------------
第四题
构造一下语法树就知道了。直接短语是深度为2的节点（根节点是深度0）。短语是深度为2的节点代入深度为1的产生式中。句柄是所有直接短语中最左的那个。
1.baaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
_______|
______a
直接短语为 Aa、a
短语为 Aaa
句柄为 Aa
2.bBaa
>>>
_________S
_______/___\
______A_____B
_____/__\____|
____A___a___a
___/__\
__b___B
直接短语为 Aa、a
短语为 Aaa
句柄为 Aa

J. 编译原理中的左递归

1.A->Aa
2.A->Ba
B->Ab (A和B属于非终结符，a和b属于终结符)

通俗点讲：左递归就是情况1所说的“->”两边都含有同一个非终结符；
情况2所说的A->Ba中“->”后面的B 与 B->Ab中“->”前面的B是相同的非终结符
这两种情况就叫作左递归。