消除左递归

（a）消除习题3⽂法的左递归3.8 （a）消除习题3.⽂法的左递归（b）为（a）的⽂法构造预测分析器答案：（a）S —> (L) | aL —>S L′L′—> ,S L′|∈(b) FIRST(S)={(,a}FIRST(L)={(,a,}FIRST(L′)={‘,’, ∈}FOLLOW(S)={ ‘,’，﹩}FOLLOW(L)={ )，﹩，‘,’}FOLLW(L′)={ ) ，﹩，‘,’}预测分析表如下：⾮终结符输⼊符号（） a , ﹩S S —> (L)S —> aL L —>S L′ L —>S L′L′ L′—> ∈ L′—> ,S L′ L′—> ∈【典型错误】：消除左递归请参考书上介绍的⽅法，有些⼈引⼊了两个⾮终结符，但不是最简的情况。

另外很多⼈没有构造FIRST和FOLLOW表，本题需要注意的是当FIRST 集合中有∈预测分析表的构造⽅法。

3.15（a）⽤习题3.1的⽂法构造（a，（a，a））的最右推导，说出每个右句型的句柄。

（b）给出对应（a）的最右推导的移进-归约分析器的步骤。

（c）对照（b）的移进-规约，给出⾃下⽽上构造分析树的步骤。

答案：(a) S => (L) => (L,S) =>(L,(L)) => (L,(L,S)) => (L,(L,a)) =>(L,(S,a)) =>(L,(a,a)) =>(S,(a,a)) =>(a,(a,a))(b)栈输⼊动作﹩（a，（a，a））﹩移进﹩（ a，（a，a））﹩移进﹩（a ，（a，a））﹩ S->a归约﹩（S ，（a，a））﹩ L->S归约﹩（L ，（a，a））﹩移进﹩（L，（a，a））﹩移进﹩（L，（ a，a））﹩移进﹩（L，（a ，a））﹩ S->a归约﹩（L，（S ，a））﹩ L->S归约﹩（L，（L ，a））﹩移进﹩（L，（L， a））﹩移进﹩（L，（L，a ））﹩ S->a归约﹩（L，（L，S ））﹩ L->L,S归约﹩（L，（L ））﹩移进﹩（L，（L））﹩ S—>(L)归约﹩（L，S ）﹩ L->L,S归约﹩（L ）﹩移进﹩（L）﹩ S—>(L)归约﹩ S ﹩ Acc（c）图见下页【典型错误】：（a）中要求的是最右推导，很多⼈没有注意到（b）⼀般没有错误，但注意a归约到S后要继续归约到L（c）这题的错误主要是没有给出构造的步骤，另外题⽬要求的是⾃下⽽上构造分析表。

编译原理第四章参考答案1.1考虑下⾯⽂法G1S->a|^|(T)T->T,S|S消去G1的左递归。

然后对每个⾮终结符，写出不带回溯的递归⼦程序。

答:：(1)消除左递归:S->a|^|(T)T-> ST’T’->,S T’|ε(2)first(S)={ a , ^ , ( } first(T)= { a , ^ , ( } first(T’)={ , ε}First(a)={a},First(^)={^},First( (T) )={ ( }S的所有候选的⾸符集不相交First(,ST’)={,} ,First(ε)={ε},T’的所有候选的⾸符集不相交Follow(T’)=Follow(T)={ )}first(T’)∩Follow(T’)={}所以改造后的⽂法为LL(1)⽂法。

不带回溯的递归⼦程序如下：S( ){if (lookahead=’a’) advance;Else if(lookahead=’^’) advance;Else if(lookahead=’(’){advance;T();if(lookahead=’)’) advance;else error();}Else error();}T( ){S( );T’( ):}T’->,S T’|εT’( ){if (lookahead=’,’){advance;T’();}Else if(lookahead=Follow(T’)) advance;Else error;}有⽂法G(S):S→S+aF|aF|+aFF→*aF|*a(1)改写⽂法为等价⽂法G[S’]，消除⽂法的左递归和回溯(2)构造G[S’]相应的FIRST和FOLLOW集合；(3)构造G[S’]的预测分析表，以此说明它是否为LL(1)⽂法。

(4)如果是LL(1)⽂法，请给出句⼦a*a+a*a*a的预测分析过程该⽂法为LL(1)⽂法，因为它的预测分析表中⽆冲突项。

编译原理消除左递归和公因子哎呀，编译原理这门课，听起来就像是一道难啃的硬骨头。

你想，编译器就像是一个聪明的翻译官，把我们写的代码翻译成计算机能理解的语言。

可在这过程中，左递归和公因子可就成了我们的“拦路虎”。

左递归，顾名思义，就是那种在规则里面，自我调用的情况。

就像是一个爱走回头路的小孩，走着走着就又回到了起点。

这玩意儿可是会让我们的解析器绊倒，真的是无处可逃。

想象一下，如果你在学习一门新技能，总是回到最开始的地方，那得多烦人啊。

所以，咱们得找办法把它给解决掉。

最常见的方式就是重写规则。

比如说，原本我们有个规则叫做A > Aα | β，哎呀，这个左递归可真让人头疼。

我们可以把它转变成A > βA'，然后再来个A' > αA' | ε。

看，没了左递归，简直像是畅通无阻的高速公路，通行无阻，速度飞快。

再说说公因子。

这个问题就像是大家一起唱歌，但总有一些人嗓音特好，想把大伙儿都带起来。

比如我们有A > αβ | αγ，哎呀，这里就能看到α 是个公因子。

于是，咱们也得给它处理一下。

我们可以把它改成A > αA'，然后A' > β | γ。

这样一来，所有人都能在同一个调子上合唱，和谐得很。

大家心情大好，编译器的效率也提升了，简直是双赢的局面。

这些概念一上来，真的会让人感觉天花乱坠。

可掌握这些小技巧，就能让你在编译原理的海洋里遨游。

左递归和公因子这两个家伙，别看它们名字听起来高大上，实际上我们可以把它们看成是学习过程中的小石头，捡起来扔掉就是了。

编译原理的学习，就像是打怪升级。

前面有大boss，你得先学会基本的技能，才能有机会挑战它。

左递归和公因子就是那些小怪，打掉它们，你才能顺利通关。

掌握这些技巧，随时随地都能应对各种问题，真的是如鱼得水。

我知道，有些同学可能一开始看这些规则就头大。

别怕，慢慢来，像吃火锅一样，先从底料开始，慢慢加入各种配菜。

消除左递归例题
左递归是编译原理中语法分析部分的一个概念，它指的是某个非终结符A通过自身直接或间接的左递归定义产生式的规则。

消除左递归是为了简化语法分析，提高解析效率。

下面以一个简单的算术表达式为例来说明如何消除左递归：
原始的带有左递归的文法：
E -> E + T | T
T -> T * F | F
F -> (E) | id
这个文法中，E到自身的转换就构成了左递归。

消除左递归后的文法：
E -> TE'
E' -> + TE' | ε
T -> FT'
T' -> * FT' | ε
F -> (E) | id
解释一下这个变换过程：
1. 对于E，我们引入一个新的非终结符E'，并将原产生式转换为`E -> TE'`和`E' -> + TE' | ε`，这里的ε表示空串，即加号后面可以没有E。

2. 同理，对于T也引入T'，并将原产生式转换为`T -> FT'`和`T' -> * FT' | ε`。

这样，新的文法就没有了左递归，同时保持了原语义不变，能够描述同样的算术表达式结构。

编译原理实验报告实验名称消除文法的左递归实验时间2013年11月12日院系计算机科学与电子技术系班级11计算机软件学号JV114001 JV114095 JP114065 姓名唐茹韩强强徐思维1.试验目的：输入：任意的上下文无关文法。

输出：消除了左递归的等价文法。

2.实验原理：1．直接左递归的消除消除产生式中的直接左递归是比较容易的。

例如假设非终结符P 的规则为：P →P α / β其中，β是不以P 开头的符号串。

那么，我们可以把P 的规则改写为如下的非直接左递归形式： P →βP ’P ’→αP ’ / ε这两条规则和原来的规则是等价的，即两种形式从P 推出的符号串是相同的。

设有简单表达式文法G[E]： E →E+T/ T T →T*F/ F F →（E ）/ I经消除直接左递归后得到如下文法： E →TE ’E ’ →+TE ’/ ε T →FT ’T ’ →*FT ’/ εF →（E ）/ I考虑更一般的情况，假定关于非终结符P 的规则为P →P α1 / P α2 /…/ P αn / β1 / β2 /…/βm其中，αi （I ＝1，2，…，n ）都不为ε，而每个βj （j ＝1，2，…，m ）都不以P 开头，将上述规则改写为如下形式即可消除P 的直接左递归：P →β1 P ’ / β2 P ’ /…/βm P ’P ’ →α1P ’ / α2 P ’ /…/ αn P ’ /ε 2．间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。

然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。

有些文法虽然表面上不存在左递归，但却隐藏着左递归。

例如，设有文法G[S]：S →Qc/ c Q →Rb/ b R →Sa/ a虽不具有左递归，但S 、Q 、R 都是左递归的，因为经过若干次推导有 S ⇒Qc ⇒Rbc ⇒SabcQ ⇒Rb ⇒Sab ⇒Qcab R ⇒Sa ⇒Qca ⇒Rbca就显现出其左递归性了，这就是间接左递归文法。

一、实验目的1. 理解左递归的概念及其对语法分析的影响。

2. 掌握消除左递归的方法，包括直接左递归和间接左递归的消除。

3. 能够运用消除左递归的方法对实际文法进行处理，提高语法分析的效率。

二、实验原理1. 左递归的定义：在上下文无关文法中，若存在产生式A→αAβ，其中α和β是符号串，且α不包含非终结符A，则称A产生式具有左递归。

2. 左递归的影响：左递归会导致语法分析过程中产生死循环，影响分析效率。

3. 消除左递归的方法：（1）直接左递归的消除：将具有直接左递归的文法转换为不具有直接左递归的文法。

（2）间接左递归的消除：将具有间接左递归的文法转换为不具有间接左递归的文法。

三、实验内容1. 实验环境：Python 3.72. 实验工具：Pylint、Jupyter Notebook3. 实验步骤：（1）定义文法：使用字符串表示文法，其中非终结符用大写字母表示，终结符用小写字母表示，产生式用“→”连接。

（2）检测左递归：编写函数检测文法中是否存在左递归，包括直接左递归和间接左递归。

（3）消除左递归：根据检测到的左递归类型，编写函数消除文法中的左递归。

（4）输出结果：将消除左递归后的文法输出。

四、实验过程1. 定义文法：G[E] = E→E+E | E-E | T | id2. 检测左递归：经过检测，发现文法G[E]中存在直接左递归。

3. 消除左递归：（1）消除直接左递归：将产生式E→E+E改写为E→T+E'，其中E'表示E的剩余部分。

（2）消除间接左递归：将产生式E→T+E'中的T进行递归消除，得到T→id+T'，其中T'表示T的剩余部分。

4. 输出结果：消除左递归后的文法为G'[E] = E→T+E' | T | id，T→id+T'，E'→+E | -E | ε。

五、实验结果分析1. 通过消除左递归，将原始文法G[E]转换为G'[E]，提高了语法分析的效率。

消除左递归的方法一、什么是左递归？在语法分析中，左递归是指产生式中左部直接或间接递归调用了自身的情况。

简单来说，就是一个非终结符的产生式中，左侧第一个符号又是该非终结符本身的情况。

在以下产生式中，非终结符A存在左递归：A -> Ab | cA的第一个符号是A本身。

左递归可能会导致递归下降解析器进入无限递归，导致程序崩溃或死循环。

在编写解析器时，需要消除所有的左递归。

二、消除左递归的方法1. 直接左递归消除方法对于直接左递归的产生式A -> Aα | β，可以通过以下步骤消除左递归：1）将产生式改写为A -> βA'，A' -> αA' | ε。

2）将产生式进行分割，得到以下两个产生式：A -> βA'A' -> αA' | εε表示空产生式。

对于以下产生式：A -> Aa | b可以通过直接左递归消除方法得到以下产生式：A -> bA'A' -> aA' | ε2. 间接左递归消除方法对于间接左递归的产生式，可以通过以下步骤消除左递归：1）将所有非直接左递归的产生式移至左边，所有直接左递归的产生式移至右边。

2）将每个非终结符的所有产生式按照首符号分成两个集合，一个集合为直接或间接以该非终结符开始的产生式，另一个集合为不以该非终结符开始的产生式。

3）对于每个集合，递归地消除左递归。

4）将消除左递归后的产生式合并到一起。

对于以下文法：A -> BcB -> Ad | e可以通过间接左递归消除方法得到以下产生式：B -> eB'B' -> dB' | εA -> eB'c | dcB'是在消除左递归后新增加的符号。

三、消除左递归的示例以下为一个简单的文法：S -> S + S | S * S | id该文法存在直接左递归S -> S + S和S -> S * S，因此需要进行消除。

直接消除左递归方法：
回溯：分析工作要部分地或全部地退回去重做。

条件：在文法中，对于某个非终结符地规则是其右部有多个选择，并且根据所面临地输入符号不能准确地确定所要地选择时，就可能出现回溯.
回溯带来地问题：
严重地影响了效率，只有在理论地层面上地意义而没有实际地意义。

影响效率地原因：1）语法分析需要重做；2）语义处理工作要倒退重新来做；3）当一个非终结符用某一后选式匹配成功是，这种成功可能仅仅是暂时的；4）当最终报告分析不成功时，难以知道输入串出错地准确位置；5）穷尽试探法，效率低下，代价之高。

假定P关于的全部产生式是
P→Pα1| Pα2|…| Pαm| β 1| β 2 |… | βn
其中，每个α都不等于ε，而每个β都不以P开头，
那么消除P地直接左递归就是把这个规则改写成：
P→ | β 1 P’| β 2 P’|…| β n P’
P’ →α1P’| α2P’| …| αmP’| ε
例4.2消去以下文法的直接左递归。

E→E+T|T
T→T*F|F
F→（E）|i
解：
E →TE´
E ´→+TE´|ε
T →FT´
T´→*FT´|ε
F→（E）|i
练习1]：
已知G[E]：
E→T*F | T/F | F
T →F | T*F | T/F
请消除该文法的左递归。

消除文法中的左递归
消除文法的左递归，就是要找到一种方法，把文法转化为不含左递归的文法，这种转换是通过重写产生式的右部分和用新的产生式来替换原有产生式来实现的。

首先，我们需要了解什么是左递归。

在文法中，如果一个产生式的右部分直接或间接引用了该产生式自身，那么这个产生式就是左递归的。

例如，在文法G[A]={A→Aα|β}中，产生式A→Aα就是左递归的。

为了消除左递归，我们需要对文法进行重写。

一种常见的方法是使用一个非终结符来代替原来的左递归，这个非终结符将出现在所有引用原始非终结符的地方。

例如，对于文法G[A]={A→Aα|β}，我们可以将其重写为G[A]={A→B α|β}和G[B]={B→Bα|Bβ|ε}，其中B是新引入的非终结符。

以下是一个具体的例子：
原始文法：
S→S(S)
S→id
这个文法是左递归的，因为产生式S→S(S)直接引用了S。

为了消除左递归，我们可以将其重写为：
S→P(Q)
P→P(Q)|ε
Q→id
在这个重写的文法中，我们引入了两个新的非终结符P和Q。

产生式S→P(Q)替换了原始的S→S(S)，P→P(Q)替换了S→S(S)的右部分S(S)，而Q→id则替换了原始的S→id。

因此，这个重写的文法没有左递归。

python实现⽂法左递归的消除⽅法前⾔继词法分析后，⼜来到语法分析范畴。

完成语法分析需要解决⼏个⼦问题，今天就完成⽂法左递归的消除。

没借鉴任何博客，完全⾃⼰造轮⼦。

开始之前⽂法左递归消除程序的核⼼是对字符串的处理，输⼊的产⽣式作为字符串，对它的拆分、替换与合并操作贯穿始终，处理过程的逻辑和思路稍有错漏便会漏洞百出。

采⽤直接改写法，不理解左递归消除⽅法很难读懂代码。

要求CFG⽂法判断左递归的类型消除直接左递归和间接左递归界⾯源码import osimport tkinter as tkimport tkinter.messageboximport tkinter.font as tfzhuizhong = ""wenfa = {"⾮左递归⽂法"}xi_ = ""huo = ""window = ()window.title('消除左递归')window.minsize(500,500)#转换坐标显⽰形式为元组def getIndex(text, pos):return tuple(map(int, str.split(text.index(pos), ".")))def zhijie(x,y):if not len(y):passelse:if x == y[0]:wenfa.discard("⾮左递归⽂法")#处理直接左递归zuobian = y.split('|')feizhongjie = []zhongjie = []for item in zuobian:if x in item:item = item[1:]textt = str(item) + str(x) + "'"feizhongjie.append(textt)else:text = str(item) + str(x) + "'"zhongjie.append(text)if not zhongjie:#处理A -> Ax的情况zhongjie.append(str(x + "'"))cheng = str(x) + " -> " + "|".join(zhongjie)zi = str(x) + "'" + " -> " + "|".join(feizhongjie) + "|є"text_output.insert('insert','直接左递归⽂法','tag1')text_output.insert('insert','\n')text_output.insert('insert',cheng,'tag2')text_output.insert('insert','\n')text_output.insert('insert',zi,'tag2')'''加上会判断输出⾮递归产⽣式，但会导致间接左递归不能删除多余产⽣式else:h ="不变： " + x + " -> " + ytext_output.insert('insert','⾮左递归⽂法','tag1')text_output.insert('insert','\n')text_output.insert('insert',h,'tag2')'''text_output.insert('insert','\n')def zhijie2(x,y):if not len(y):passelse:if x == y[0]:wenfa.discard("⾮左递归⽂法")#处理直接左递归zuobian = y.split('|')feizhongjie = []zhongjie = []for item in zuobian:if x in item:item = item[1:]textt = str(item) + str(x) + "'"feizhongjie.append(textt)else:text = str(item) + str(x) + "'"zhongjie.append(text)cheng = str(x) + " -> " + "|".join(zhongjie)zi = str(x) + "'" + " -> " + "|".join(feizhongjie) + "|є"text_output.insert('insert',"间接左递归⽂法",'tag1')text_output.insert('insert','\n')text_output.insert('insert',cheng,'tag2')text_output.insert('insert','\n')text_output.insert('insert',zi,'tag2')text_output.insert('insert','\n')def tihuan(xk,yi,yk):yi_you = []yi_wu =[]yi_he = ""yi_wuhe = ""yi_zhong = ""yi_feizhong = []if xk in yi:yk_replace = yk.split('|')yi_fenjie = yi.split('|')#将含⾮终结与不含分开for ba in yi_fenjie:if xk in ba:yi_you.append(ba)else:yi_wu.append(ba)yi_he = "|".join(yi_you)for item in yk_replace:yi_zhong = yi_he.replace(xk,item)#替换yi_feizhong.append(yi_zhong)yi_wuhe = "|".join(yi_wu)#再合并global zhuizhongzhuizhong = "|".join(yi_feizhong) + "|" + yi_wuhe#点击按钮后执⾏的函数def changeString():text_output.delete('1.0','end')text = text_input.get('1.0','end')text_list = list(text.split('\n'))#⼀⾏⼀⾏的拿⽂法text_list.pop()if not text_list[0]:print(tkinter.messagebox.showerror(title = '出错了！',message='输⼊不能为空')) else:for cfg in text_list:x,y = cfg.split('->')#将⽂法左右分开x = ''.join(x.split())#消除空格y = ''.join(y.split())if not (len(x) == 1 and x >= 'A' and x <= 'Z'):pos = text_input.search(x, '1.0', stopindex="end")result = tkinter.messagebox.showerror(title = '出错了！',message='⾮上下⽂⽆关⽂法!坐标%s'%(getIndex(text_input, pos),))# 返回值为：okprint(result)return 0else:zhijie(x,y)for i in range(len(text_list)):for k in range(i):xi,yi = text_list[i].split('->')xi = ''.join(xi.split())#消除空格yi = ''.join(yi.split())xk,yk = text_list[k].split('->')xk = ''.join(xk.split())#消除空格yk = ''.join(yk.split())tihuan(xk,yi,yk)tihuan(xk,zhuizhong,yk)global xi_xi_ = xizhijie2(xi_,zhuizhong)for item in wenfa:text_output.insert('insert',item,'tag1')#创建⽂本输⼊框和按钮text_input = tk.Text(window, width=80, height=16)text_output = tk.Text(window, width=80, height=20)#简单样式ft = tf.Font(family='微软雅⿊',size=12)text_output.tag_config("tag1",background="yellow",foreground="red",font=ft)text_output.tag_config('tag2',font = ft)#按钮button = tk.Button(window,text="消除左递归",command=changeString,padx=32,pady=4,bd=4) text_input.pack()text_output.pack()button.pack()window.mainloop()是不是很难懂，看看半吊⼦流程图主要流程直接左递归间接左递归合并运⾏截图总结（1）确定⽅向做⼀件事并不难，最难的是没有⽅向，不知道要做什么；只是感觉时光流逝⾃⼰却⼀点东西都没产出。

编译原理消除左递归例题
编译原理中消除左递归是一个重要的概念，它在文法的转换过程中起着关键作用。

让我们以一个简单的例题来说明消除左递归的过程。

假设我们有以下的文法：
A -> Aα₁ | Aα₂ | β₁ | β₂。

其中A是非终结符号，α₁、α₂、β₁、β₂是符号串。

这个文法存在左递归，因为A可以推导出A开头的符号串。

为了消除左递归，我们可以进行以下的步骤：
1. 将文法分成两部分，一部分是不含左递归的产生式，另一部分是含有左递归的产生式。

在这个例子中，我们可以将文法分成两部分：
A -> β₁ | β₂。

A -> Aα₁ | Aα₂。

2. 引入新的非终结符号。

我们为每个含有左递归的产生式引入
一个新的非终结符号，然后重写产生式。

在这个例子中，我们引入一个新的非终结符号A'，然后重写产生式：
A -> β₁A' | β₂A'。

A' -> α₁A' | α₂A' | ε。

3. 重写产生式。

我们将原来的产生式中的左递归部分替换为新引入的非终结符号。

在这个例子中，我们重写产生式为：
A -> β₁A' | β₂A'。

A' -> α₁A' | α₂A' | ε。

这样，我们就成功地消除了原文法中的左递归。

这个过程可以确保文法不会陷入无限递归的推导过程中，从而使得编译器能够准确地理解和处理文法。

消除左递归是编译原理中非常重要的一环，对于理解和设计语法分析器有着重要的意义。

编译原理消除左递归一、前言编译原理是计算机科学中的重要分支之一，它研究如何将高级语言转化成机器语言，使计算机能够理解并执行程序。

编译器是完成这一过程的关键工具之一。

编译器的核心任务是将源代码转换为目标代码，其中一个重要的步骤就是消除左递归。

二、概述在文法中，如果一个非终结符可以推导出以自身为左部的产生式，则称该文法具有左递归。

例如，对于以下文法：```A -> Aa | b```可以发现非终结符 A 可以推导出 Aa 这个产生式，而 Aa 中又包含了非终结符 A，因此该文法具有左递归。

左递归会导致递归下降分析法和 LL(1) 分析法无法正确处理该文法。

因此，在进行语法分析时需要先将文法中的左递归消除。

三、消除直接左递归直接左递归指的是形如 A -> Ab | c 的产生式中以 A 为左部且右部以A 开头的情况。

消除直接左递归需要进行以下步骤：1. 将所有以 A 开头的产生式提取出来，并将它们的右部中的 A 去掉，得到新的产生式：```A -> cA'A' -> bA' | ε```2. 将新产生式中的 A' 替换为原来的非终结符 A，得到最终结果：```A -> cA'A' -> bA' | ε```四、消除间接左递归间接左递归指的是存在一系列非终结符 A1, A2, ..., An，使得文法中存在产生式 A1 -> A2B，A2 -> A3C，..., An-1 -> AnD，An -> A1E 的情况。

消除间接左递归需要进行以下步骤：1. 将文法中所有非终结符按照拓扑排序的方式排列，并将它们编号为1, 2, ..., n。

2. 对于每个非终结符 Ai，将其可以推导出的所有非终结符按照编号从小到大排序，并将它们存储在一个集合 Bi 中。

3. 对于每个集合 Bi 中的非终结符 Bj，将其可以推导出的所有非终结符按照编号从小到大排序，并将它们存储在一个集合 Ci 中。

编译原理实验报告实验名称消除文法的左递归实验时间2013年11月12日院系计算机科学与电子技术系班级11计算机软件学号JV114001 JV114095 JP114065 姓名唐茹韩强强徐思维1.试验目的：输入：任意的上下文无关文法。

输出：消除了左递归的等价文法。

2.实验原理：1．直接左递归的消除消除产生式中的直接左递归是比较容易的。

例如假设非终结符P 的规则为：P →P α / β其中，β是不以P 开头的符号串。

那么，我们可以把P 的规则改写为如下的非直接左递归形式： P →βP ’P ’→αP ’ / ε这两条规则和原来的规则是等价的，即两种形式从P 推出的符号串是相同的。

设有简单表达式文法G[E]： E →E+T/ T T →T*F/ F F →（E ）/ I经消除直接左递归后得到如下文法： E →TE ’E ’ →+TE ’/ ε T →FT ’T ’ →*FT ’/ εF →（E ）/ I考虑更一般的情况，假定关于非终结符P 的规则为P →P α1 / P α2 /…/ P αn / β1 / β2 /…/βm其中，αi （I ＝1，2，…，n ）都不为ε，而每个βj （j ＝1，2，…，m ）都不以P 开头，将上述规则改写为如下形式即可消除P 的直接左递归：P →β1 P ’ / β2 P ’ /…/βm P ’P ’ →α1P ’ / α2 P ’ /…/ αn P ’ /ε 2．间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。

然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。

有些文法虽然表面上不存在左递归，但却隐藏着左递归。

例如，设有文法G[S]：S →Qc/ c Q →Rb/ b R →Sa/ a虽不具有左递归，但S 、Q 、R 都是左递归的，因为经过若干次推导有 S ⇒Qc ⇒Rbc ⇒SabcQ ⇒Rb ⇒Sab ⇒Qcab R ⇒Sa ⇒Qca ⇒Rbca就显现出其左递归性了，这就是间接左递归文法。

上下文无关文法规约技巧1. 使用左递归消除左递归问题：如果某个产生式的右部以同一个非终结符开头，并且它的右部不能推导出一个空串，则可以使用左递归消除技巧来转换该产生式。

例如，假设有一个文法规则 A -> Aα | β，其中α和β是任意的终结符和非终结符序列。

为了消除左递归，可以将该规则修改为 A -> βA'，A' -> αA' | ε，其中A'是一个新的非终结符。

2. 提取公因子：如果某个非终结符的多个产生式的右部具有相同的前缀，可以使用公因子提取技巧来将这个前缀提取出来，并创建一个新的非终结符来表示这个公因子。

例如，假设有一个文法规则 A -> αβ | αγ，其中α是一个非终结符或终结符，而β和γ是任意的终结符和非终结符序列。

为了提取公因子，可以将该规则修改为 A -> αA'，A' -> β | γ。

3. 消除无用的产生式和非终结符：如果某个产生式或非终结符无法通过其他产生式推导出来，或者某个非终结符无法由起始符号推导出来，则可以将其视为无用的，可以通过删除这些无用的产生式和非终结符来简化文法。

4. 消除多余的终结符：如果某个终结符在文法的其他部分没有出现过，则可以认为它是多余的，可以通过删除这个多余的终结符来简化文法。

5. 利用语义动作将一些语义信息引入到文法中：语义动作可以在语法分析过程中执行一些特定的操作，例如计算表达式的值或生成中间代码。

通过引入适当的语义动作，可以将语义信息引入到文法中，从而使文法更加强大和灵活。

这些技巧可以应用于上下文无关文法的规约过程，以使文法更加简洁、可读性更强，并消除一些潜在的歧义。

然而，对于复杂的文法，可能需要多种技巧的组合来进行规约。

Chomsky文法类型判断消除文法的左递归年级＿＿＿＿＿＿＿＿＿＿＿专业＿＿＿＿＿＿＿＿＿＿＿学号＿＿＿＿＿＿＿＿＿＿＿姓名＿＿＿＿＿＿＿＿＿＿＿1. 实验目的要求：输入：一组任意的规则。

输出：相应的Chomsky 文法的类型。

2．实验原理1．0型文法（短语文法）如果对于某文法G，P中的每个规则具有下列形式：u:: = v其中u∈V＋，v∈V*，则称该文法G为0型文法或短语文法，简写为PSG。

0型文法或短语结构文法的相应语言称为0型语言或短语结构语言L0。

这种文法由于没有其他任何限制，因此0型文法也称为无限制文法，其相应的语言称为无限制性语言。

任何0型语言都是递归可枚举的，故0型语言又称递归可枚举集。

这种语言可由图灵机（Turning）来识别。

2．1型文法（上下文有关文法）如果对于某文法G，P中的每个规则具有下列形式：xUy:: = xuy其中U∈V N；u∈V＋；x，y∈V*，则称该文法G为1型文法或上下文有关文法，也称上下文敏感文法，简写为CSG。

1型文法的规则左部的U和右部的u具有相同的上文x和下文y，利用该规则进行推导时，要用u替换U，必须在前面有x和后面有y的情况下才能进行，显示了上下文有关的特性。

1型文法所确定的语言为1型语言L1，1型语言可由线性有界自动机来识别。

3．2型文法（上下文无关文法）如果对于某文法G，P中的每个规则具有下列形式：U :: = u其中U∈V N；u∈V＋，则称该文法G为2型文法或上下文无关文法，简写为CFG。

按照这条规则，对于上下文无关文法，利用该规则进行推导时，无需考虑非终结符U所在的上下文，总能用u替换U，或者将u归约为U，显示了上下文无关的特点。

2型文法所确定的语言为2型语言L2，2型语言可由非确定的下推自动机来识别。

一般定义程序设计语言的文法是上下文无关的。

如C语言便是如此。

因此，上下文无关文法及相应语言引起了人们较大的兴趣与重视。

4．3型文法（正则文法，线性文法）如果对于某文法G，P中的每个规则具有下列形式：U :: = T 或 U :: = WT其中T∈V T；U,W∈V N，则称该文法G为左线性文法。

语法分析-消除左递归
⼀：什么是左递归?
在⼆型⽂法（上下⽂⽆关⽂法中），若⼀个⾮终极符A有任何直接⽂法规则或者通过多个⽂法规则，推导出的句型最左边符号⼜会出现A，我们说这个⾮终极符A 是左递归的。

⼆：左递归的类型
• 直接左递归：经过⼀次推导就能看出⽂法存在左递归
例如：A->Aa|b ,A∈VN ，a,b∈（VN∪VT）*
• 间接左递归：经过多次推导才能看出⽂法存在左递归
例如：A->Ba|β，B->Ar|β，A,B∈VN，a,β,r∈（VN∪VT）*
三：左递归的消除⽅法
• 直接左递归的消除：
步骤：
1) 把所有产⽣式写成下列形式：
A→Aa1｜Aa2……｜Aan｜b1｜b2……｜bm，其中每个a都不等于
ε，每个b都不以A开头。

2）变换候选式成如下形式：
A→b1A’｜b2A’……｜bmA’
A’ →a1A’｜a2A’……｜anA’｜ε
例如：
s->sb,|a可以替换为 s->as' ，s'->b,s'|ε
• 间接左递归的消除：
步骤：
1）把间接左递归化成直接左递归
2）按照直接左递归的消除⽅法进⾏消除
例如：
A->Bc∣d
B->aA∣Ab
1）转换成直接左递归
A->aAc∣Abc∣d
2）消除直接左递归
A->aAcA′∣dA′
A′->bcA′∣ε。