下载文档原格式
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通过自身直接或间接的左递归定义产生式的规则。
消除左递归是为了简化语法分析，提高解析效率。
下面以一个简单的算术表达式为例来说明如何消除左递归：
原始的带有左递归的文法：
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）当一个非终结符用某一后选式匹配成功是，这种成功可能仅仅是暂时的；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
请消除该文法的左递归。
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）确定⽅向做⼀件事并不难，最难的是没有⽅向，不知道要做什么；只是感觉时光流逝⾃⼰却⼀点东西都没产出。
学号：专业：姓名：实验日期：2012.4.13 教师签字：成绩：实验名称：实验二：消除文法的左递归实验目的：１. 掌握上下文无关文法类型的定义，及与其他类型文法的区别；２.熟悉上下文无关文法类型的判断，能够快速按照要求写出对应文法类型的文法用例；３.给出一个上下文无关文法类型，能够正确判断其是否存在左递归，若存在则消除直接、间接左递归。
实验原理：1.文法中如果存在左递归，会产生循环递归，故需要将文法中的左递归给删除掉。
2.删除左递归需要删除直接左递归与间接左递归。
3.在删除左递归是，使用循环消元法，将左线性递归修改为又递归。
4.最后删除无用产生式。
实验内容：１.实验要求：输入任意的一个上下文无关文法,判断其是否存在左递归，若存在左递归则输出消除了左递归的等价文法。
２.实验代码：#include <iostream>#include <fstream>#include <string>#include <algorithm>#include <vector>using namespace std;struct relation{string _left;string _right;}; //关系最大为MAXN条vector<relation> rel;string VN;void print(){cout<<"[CFG消除左递归COPYRIGHT FROM NINGYU 2012/4/13]"<<endl; }bool cmp(const relation &r1,const relation &r2){if(r1._left>r2._left) return true;else if(r1._left==r2._left&&r1._right >r2._right) return true;return false;}relation get_realation(string str){ //将一个字符串生成式分为左右部输入格式为->，返回生成式结构体int t=str.find('-');relation r;r._left=str.substr(0,t);r._right=str.substr(t+2,str.length()-t);return r;}bool isUpper(char c){if(c>='A'&&c<='Z') return true;else return false;}vector<relation> find_firstVn(char c_left,char c_right){ //查找所有c为左部的产生式，c_right 为右部产生式vector<relation> v;for(int i=0;i<rel.size();i++){if(rel[i]._left[0]==c_left&&rel[i]._right[0]==c_right){v.push_back(rel[i]);rel.erase(rel.begin()+i);}return v;}vector<relation> find_Vn(char c){ //查找左部为c的产生式vector<relation> v;for(int i=0;i<rel.size();i++)if(rel[i]._left[0]==c){v.push_back(rel[i]);//rel.erase(rel.begin()+i);}return v;}bool is_exist(relation r){int i;for(i=0;i<rel.size();i++){if(r._left==rel[i]._left&&r._right==rel[i]._right)break;}if(i==rel.size()) return true;return false;}void releft(){ //消除一切左递归vector<relation> v1,v2,v3;relation r;for(int i=0;i<VN.length();i++)for (int j=0;j<=i-1;j++){v1=find_firstVn(VN[i],VN[j]);for(int t=0;t<v1.size();t++){r._left=v1[t]._left;r._right=v1[t]._right.substr(1,v1[t]._right.length()-1);if(is_exist(r)) rel.push_back(r);v2=find_Vn(VN[j]);for(int q=0;q<v2.size();q++){r._right=v2[q]._right+v1[t]._right.substr(1,v1[t]._right.length()-1); //得到替换Ai->br;if(is_exist(r)) rel.push_back(r);}}}void init(){cout<<"请输入文法，以Ctrl+Z结束"<<endl;string strPath;relation r;int p;while(cin>>strPath){rel.push_back(get_realation(strPath));//得到左部与右部;if(rel[rel.size()-1]._left.length()==1){ //得到左部的非终结符char c=rel[rel.size()-1]._left[0];if(c<='Z'&&c>='A'){int t=VN.find(c);if(t==string::npos)VN+=c;}}}}vector<relation> find_1(char c){ //查找c的直接左递归vector<relation> v;for(int i=0;i<rel.size();i++)if(rel[i]._left[0]==c&&rel[i]._right[0]==c){v.push_back(rel[i]);rel.erase(rel.begin()+i);}return v;}vector<relation> find_2(char c){//查找c的非左递归vector<relation> v;for(int i=0;i<rel.size();i++)if(rel[i]._left[0]==c&&rel[i]._right[0]!=c&&*(rel[i]._right.end()-1)!='.'){ v.push_back(rel[i]);rel.erase(rel.begin()+i);}return v;}void re_dir_left(int i){//删除有问题生成式！！！char c=VN[i];vector<relation> v1,v2;v1=find_1(c);relation r;string ch;ch.push_back(c);ch.push_back('.');bool p=false;////////////if(v1.size()>=1)p=true;/////////////////if(p){v2=find_2(c);r._left="";r._left.push_back(c);r._right="";r._right.push_back('#');if(is_exist(r)) rel.push_back(r);}for (int q=0;q<v1.size();q++){r._left=v1[q]._left;r._right=v1[q]._right.substr(1,v1[q]._right.length()-1)+ch;if(is_exist(r)) rel.push_back(r);for(int k=0;k<v2.size();k++){r._right=v2[k]._right+ch;if(is_exist(r)) rel.push_back(r);}}}int main(){print();init();sort(rel.begin(),rel.end(),cmp);releft();//消除左递归函数for(int i=0;i<VN.size();i++)re_dir_left(i);cout<<endl<<"消除左递归之后的文法为："<<endl;sort(rel.begin(),rel.end(),cmp);for(int i=0;i<rel.size();i++)//测试读入关系是否正确cout<<rel[i]._left<<"->"<<rel[i]._right<<endl;print();}3..实验结果：。
编译原理消除左递归一、前言编译原理是计算机科学中的重要分支之一，它研究如何将高级语言转化成机器语言，使计算机能够理解并执行程序。
编译器是完成这一过程的关键工具之一。
编译器的核心任务是将源代码转换为目标代码，其中一个重要的步骤就是消除左递归。
二、概述在文法中，如果一个非终结符可以推导出以自身为左部的产生式，则称该文法具有左递归。
例如，对于以下文法：```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 中。
数学与软件科学学院实验报告学期：2015至2016第2学期2016年3月21日课程名称：编译原理专业：信息与计算科学2013级5班实验编号：2实验名称：递归下降分析器指导教师：王开端姓名：李丹学号：2013060510实验成绩：实验二递归下降分析器实验目的：通过设计、编制、调试递归下降语法分析程序，对输入的符号串进行分析匹配，观察输入符号串是否为给定文法的句子。
实验内容：根据文法G[E]设计递归下降分析器并分析输入串)(*321i i i +是否为文法的句子。
G[E]：E→E+T|TT→T*F|F F→(E)|i实验步骤：在进行递归下降分析法之前，必须对文法进行左递归和回溯的消除。
1消除左递归直接消除见诸于产生式中的左递归比较容易，其方法是引入一个新的非终结符，把含有左递归的产生式改为右递归。
文法G[E]经过消去直接左递归后得到文法G’[E]为：G’[E]：iE F FT T FT T TE E TE E |)(|'*''|'''→→→+→→εε2消除回溯回溯发生的原因在于候选式存在公共的左因子。
一般情况下，设文法中关于A 的产生式为ji i A ββδβδβδβ|...|||...||121+→，那么，可以把这些产生式改写为⎩⎨⎧→→+ij i A A A ββββδ|...|'|...||'11经过反复提取左因子，就能把每个非终结符（包括新引进者）的所有候选首字符集变为两两不相交（既不含有公共左因子）。
3什么是递归下降分析法递归下降分析法是一种自顶向下的分析方法，文法的每个非终结符对应一个递归过程（函数）。
分析过程就是从文法开始符出发执行一组递归过程（函数），这样向下推导直到推出句子；或者说从根节点出发，自顶向下为输入串寻找一个最左匹配序列，建立一棵语法树。
在不含左递归和每个非终结符的所有候选终结首字符集都两两不相交条件下，我们就可能构造出一个不带回溯的自顶向下的分析程序，这个分析程序是由一组递归过程（或函数）组成的，每个过程（或函数）对应文法的而一个非终结符。
编译原理实验报告实验名称消除文法的左递归实验时间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就显现出其左递归性了，这就是间接左递归文法。
编译原理实验报告实验名称:消除文法的左递归实验时间:2015/5/28院系：管理与信息工程学院班级:12级计算机科学与技术学号：0124姓名:刘杨凡1.实验目的：输入：任意的上下文无关文法。
输出：消除了左递归的等价文法。
2.实验原理：1．直接左递归的消除假设非终结符P 的规则为：P—P a/ B其中，B是不以P开头的符号串。
那么，我们可以把P的规则改写为如下的非直接左递归形式：P—B P'P'—oP' / £这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。
设有简单表达式文法G[E]：E—E+T/ TT—T*F/ FF—（E）/ I 经消除直接左递归后得到如下文法：E—TE'E' —+TE'/ £T—FT'T' —*FT'/ £F—（E）/ I考虑更一般的情况，假定关于非终结符P的规则为P—P al / P o2 /••/ P a n / B i/ B /••/ 和其中，a （1 = 1，2，…，n）都不为£而每个B （j= 1，2，…，m）都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P— B i P'/ B P'/••/ B m P'P'— a1 P' / a2 P' /…/ a n P' /£2．间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。
然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。
有些文法虽然表面上不存在左递归，但却隐藏着左递归。
例如，设有文法G[S]：S—Qc/ cQ—Rb/ bR—Sa/ a虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有S Qc Rbc SabcQ Rb Sab QcabR 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α的规则，其中A为非终结符。
左递归可能导致文法无法被LL(1)分析器处理或导致分析器出现无限循环的情况。
因此，消除左递归是文法优化的重要一步。
下面以一个简单的例子来说明如何消除左递归。
假设有以下文法：
1. A -> Aα | β
我们可以按照以下步骤来消除左递归：
步骤1：将文法分解为两部分，一部分是不含左递归的规则，另一部分是只包含左递归的规则。
A -> βA'
A' -> αA' | ε
步骤2：消除左递归。
对于A' -> αA' | ε这条规则，我们可以进行如下改写：
A' -> ε | αA'
最终得到消除左递归后的文法如下：
A -> βA'
A' -> ε | αA'
通过以上步骤，我们成功消除了左递归。
需要注意的是，对于复杂的文法，消除左递归可能需要更多的步骤和技巧。
在实际应用中，可以借助自动化工具或算法来辅助完成左递归的消除。
编译原理消除左递归例题
编译原理中消除左递归是一个重要的概念，它在文法的转换过程中起着关键作用。
让我们以一个简单的例题来说明消除左递归的过程。
假设我们有以下的文法：
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 > Aα | β，哎呀，这个左递归可真让人头疼。
我们可以把它转变成A > βA'，然后再来个A' > αA' | ε。
看，没了左递归，简直像是畅通无阻的高速公路，通行无阻，速度飞快。
再说说公因子。
这个问题就像是大家一起唱歌，但总有一些人嗓音特好，想把大伙儿都带起来。
比如我们有A > αβ | αγ，哎呀，这里就能看到α 是个公因子。
于是，咱们也得给它处理一下。
我们可以把它改成A > αA'，然后A' > β | γ。
这样一来，所有人都能在同一个调子上合唱，和谐得很。
大家心情大好，编译器的效率也提升了，简直是双赢的局面。
这些概念一上来，真的会让人感觉天花乱坠。
可掌握这些小技巧，就能让你在编译原理的海洋里遨游。
左递归和公因子这两个家伙，别看它们名字听起来高大上，实际上我们可以把它们看成是学习过程中的小石头，捡起来扔掉就是了。
编译原理的学习，就像是打怪升级。
前面有大boss，你得先学会基本的技能，才能有机会挑战它。
左递归和公因子就是那些小怪，打掉它们，你才能顺利通关。
掌握这些技巧，随时随地都能应对各种问题，真的是如鱼得水。
我知道，有些同学可能一开始看这些规则就头大。
别怕，慢慢来，像吃火锅一样，先从底料开始，慢慢加入各种配菜。
编译原理实验报告实验名称消除文法的左递归实验时间院系计算机科学与技术学院班级学号姓名1.试验目的输入：任意的上下文无关文法。
输出：消除了左递归的等价文法。
2.实验原理1．直接左递归的消除消除产生式中的直接左递归是比较容易的。
例如假设非终结符P的规则为P→Pα / β其中，β是不以P开头的符号串。
那么，我们可以把P的规则改写为如下的非直接左递归形式： P→βP’P’→αP’ / ε这两条规则和原来的规则是等价的，即两种形式从P推出的符号串是相同的。
设有简单表达式文法G[E]：E→E+T/ TT→T*F/ FF→（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’/ β2P’/…/βmP’P’→α1P’ / α2P’ /…/ αnP’ /ε2．间接左递归的消除直接左递归见诸于表面，利用以上的方法可以很容易将其消除，即把直接左递归改写成直接右递归。
然而文法表面上不存在左递归并不意味着该文法就不存在左递归了。
有些文法虽然表面上不存在左递归，但却隐藏着左递归。
例如，设有文法G[S]：S→Qc/ cQ→Rb/ bR→Sa/ a虽不具有左递归，但S、Q、R都是左递归的，因为经过若干次推导有S⇒Qc⇒Rbc⇒SabcQ ⇒Rb ⇒Sab ⇒Qcab R ⇒Sa ⇒Qca ⇒Rbca就显现出其左递归性了，这就是间接左递归文法。
消除间接左递归的方法是，把间接左递归文法改写为直接左递归文法，然后用消除直接左递归的方法改写文法。
如果一个文法不含有回路，即形如P ⇒+P 的推导，也不含有以ε为右部的产生式，那么就可以采用下述算法消除文法的所有左递归。
第⼗次作业消除左递归1.将以下⽂法消除左递归，分析符号串 i*i+i 。
并分别求FIRST集、FOLLOW集，和SELECT集E -> E+T | TT -> T*F | FF -> (E) | i解：消除左递归：(1) E->TE'E'->+TE'|ε(2) T->FT'T'->*FT'|ε(3) F->(E)|i① FIRST集：First(TE') = {T}First(+TE') = {+}First(ε) = {ε}First(FT') = {F}First(*FT') = {*}First(ε) = {ε}First((E)) = {( }First(i) = {i}② FOLLOW集：Follow(E) = {)}Follow(E') = {#}Follow(T) = {E'}Follow(T') = {#}Follow(F) = {#}③ SELECT集：Select(E->TE') = First(TE') = {T}Select(E'->+TE') = First(+TE') = {+}Select(E'->ε) = (First(ε) = {ε})∪Follow(E') = {)}Select(T->FT') = First(FT') = {F}Select(T'->*FT') = First(+TE') = {*}Select(T'->ε) = (First(ε) = {ε})∪Follow(T') = {#}Select( F->(E)) = First((E)) = {( }Select( F->i) = First(i) = {i}2.P101练习7（2）（3）⽂法改写，并分别求FIRST集、FOLLOW集，和SELECT集 (2) A->aABe|aB->Bb|d提取左公因⼦：A->aA' A'->ABe|ε消除左递归：B->dB' B'->bB'|ε① FIRST集：First(aA') = {a}First(ABe) = {A}First(ε) = {ε}First(dB') = {d}First(bB') = {b}First(ε) = {ε}② FOLLOW集：Follow(A) = {Be}Follow(A') = {#}Follow(B) = {e}Follow(B') = {#}③ SELECT集：Select(A->aA') = First(aA') = {a}Select(A'->ABe) = First(ABe) = {A}Select(A'->ε) = First(ε) = {ε}∪Follow(A') = {#}Select(B->dB') = First(dB') = {d}Select(B'->bB') = First(bB') = {b}Select(B'->ε) = First(ε) = {ε}∪Follow(B') = {#}(3) S->Aa|bA->SBB->ab将A->SB代⼊S->Aa|b可得：S->SBa|b消除左递归：S->bS' S'->BaS'|ε B->ab① FIRST集：First(SBa) = {S}First(b) = {b}First(bS') = {b}First(BaS') = {B}First(ε) = {ε}First(ab) = {a}② FOLLOW集：Follow(S) = {B}Follow(S') = {#}Follow(B) = {a}③ SELECT集：Select(S->SBa) = First(SBa) = {S}Select(S->b) = First(b) = {b}Select(S->bS') = First(bS') = {b}Select(S'->BaS') = First(BaS') = {B}Select(S->ε) = First(ε) = {ε}∪Follow(S') = {#} Select(B->ab) = First(ab) = {a}3.课堂练习：求以下⽂法的FIRST集、FOLLOW集和SELECT集。
