消除左递归实验报告

消除⽂法的左递归实验编译原理实验报告实验名称 _____________ 消除⽂法的左递归__________________________ 实验时间_____________________________________________院系 _________________________________________班级 ______________________________________________学号 ____________________________________________姓名1. 试验⽬的掌握和理解消除左递归(包括直接左递归和间接左递归)在构建LL(1)⽂法的作⽤和⽬的掌握消除左递归(包括直接左递归和间接左递归)的⽅法和步骤。

写出对于输⼊任意的上下⽂⽆关⽂法可以输出消除了左递归的等价⽂法。

2. 实验原理直接左递归的消除消除产⽣式中的直接左递归是⽐较容易的。

例如假设⾮终结符P的规则为P—P a/ B其中，B是不以P开头的符号串。

那么，我们可以把P的规则改写为如下的⾮直接左递归形式：P—⼫’P'—P'￡考虑更⼀般的情况，假定关于⾮终结符P的规则为P—P a / P o2 / …/ P a n / [31 / [32 / …/ p m其中，a (I = 1, 2,…，n)都不为￡⽽每个p j (j = 1, 2,…，m) 都不以P开头，将上述规则改写为如下形式即可消除P的直接左递归：P— p l P'/ 32 P'/…/p m P'P' — 01P' / a P'/…/ a n P'/￡间接左递归的消除直接左递归见诸于表⾯，利⽤以上的⽅法可以很容易将其消除, 即把直接左递归改写成直接右递归。

然⽽⽂法表⾯上不存在左递归并不意味着该⽂法就不存在左递归了。

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

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

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

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

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

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

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

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

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

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

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

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

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

再说说公因子。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

编译原理实验报告实验名称消除文法的左递归实验时间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]，提高了语法分析的效率。

一、实验目的通过本次实验，加深对递归下降分析法的理解，掌握递归下降分析法的原理和应用，并能够根据给定的文法编写相应的递归下降分析程序。

二、实验原理递归下降分析法是一种自顶向下的语法分析方法，它将文法中的每个非终结符对应一个递归过程（函数），分析过程就是从文法开始符触发执行一组递归过程（函数），向下推到直到推出句子。

递归下降分析法的前提是文法应满足以下条件：1. 消除二义性：确保文法中每个产生式都只有一个确定的意义。

2. 消除左递归：避免产生式出现如A -> A...A的形式。

3. 提取左因子：将产生式中的左因子提取出来，避免出现左递归。

4. 判断是否为LL（1）文法：LL（1）文法是指文法满足左递归和右递归的文法。

三、实验内容1. 根据给定的文法编写递归下降分析程序。

2. 对输入的符号串进行分析，判断其是否属于该文法。

3. 输出分析过程和结果。

四、实验步骤1. 阅读相关资料，了解递归下降分析法的原理和应用。

2. 根据给定的文法，设计递归下降分析程序的结构。

3. 编写递归下降分析程序，实现分析过程。

4. 编写测试用例，验证递归下降分析程序的正确性。

5. 分析实验结果，总结实验经验。

五、实验结果与分析1. 实验结果根据给定的文法，编写了递归下降分析程序，并进行了测试。

以下为部分测试用例及结果：（1）输入：eBaA输出：分析成功，属于该文法。

（2）输入：abAcB输出：分析成功，属于该文法。

（3）输入：dEdaC输出：分析成功，属于该文法。

（4）输入：edc输出：分析成功，属于该文法。

2. 实验分析通过本次实验，我们深入了解了递归下降分析法的原理和应用。

在编写递归下降分析程序的过程中，我们学会了如何根据文法设计程序结构，以及如何实现分析过程。

同时，我们还掌握了如何对输入的符号串进行分析，并输出分析结果。

实验过程中，我们遇到了一些问题，如消除二义性、消除左递归、提取左因子等。

通过查阅资料和不断尝试，我们成功解决了这些问题。

递归实验报告分析总结递归是一种非常重要的编程思想和技巧，对于理解和解决问题具有非常大的帮助。

通过递归，我们可以将一个问题分解成为更小的子问题，从而简化问题的复杂度和难度。

在本次实验中，我深入学习了递归的原理和应用，并实践了一些递归算法。

通过这些实验，我对递归有了更深入和全面的理解，掌握了递归的使用方法和注意事项。

在实验中，我首先学习了递归的概念和原理。

递归是一种将大问题分解成小问题的算法思想，通过不断调用自己来解决问题。

递归算法通常包含两个部分：基本情况和递归情况。

基本情况是递归终止的条件，递归情况是递归调用自身的条件。

通过合理设置这两个条件，我们可以确保递归算法能够得到正确的结果并正常终止。

然后，我练习了递归的应用。

在实验中，我实现了一些常见的递归算法，如计算阶乘、斐波那契数列等。

通过这些实践，我更加熟悉了递归的写法和思维模式。

递归算法的核心思想是将大问题分解成小问题，然后通过递归调用解决这些小问题，最终得到整个问题的解。

这种思维模式非常灵活和高效，对于解决一些复杂和抽象的问题非常有帮助。

在实验过程中，我也遇到了一些递归算法的常见问题和注意事项。

例如，递归算法容易出现堆栈溢出的问题，因为每次递归调用都会占用一定的内存空间，如果递归层数过多，就容易导致栈溢出。

为了解决这个问题，我们可以在递归算法中加入递归深度的限制条件，或者考虑使用迭代算法等其他算法思想。

此外，递归算法的时间复杂度一般比较高，因为递归算法需要不断的调用自身，导致函数的调用次数非常多。

为了提高递归算法的效率，我们可以尝试使用尾递归优化、记忆化搜索等技巧。

尾递归优化是指在递归函数的最后一步调用中，直接返回递归函数的结果，而不再进行其他操作。

这样可以有效避免函数调用的堆栈积累，提高程序的性能。

总的来说，通过本次递归实验，我对递归算法有了更深入的理解和掌握。

递归是一种非常强大和灵活的算法思想，可以用来解决各种复杂的问题。

通过合理设置递归的基本情况和递归情况，我们可以通过递归算法简化问题的复杂度和难度，高效地解决问题。

深圳大学实验报告课程名称：编译原理实验项目名称：语法分析--递归下降法学院：计算机与软件专业：软件工程指导教师：张小建报告人：文成学号：2011150259 班级： 2 实验时间：2013-12-25实验报告提交时间：2013-12-26教务部制一、实验目的：掌握自顶向下的语法分析法——递归下降法。

二、实验内容：用递归下降法对如下所定义的逻辑表达式进行语法分析。

1 L→ L || A2 L→ A3 A→ A && R4 A→ R5 R→ [ L ]6 R→ ! L7 R→ E >= E8 R→ E > E9 R→ E <= E10 R→ E < E11 R→ E == E12 R→ E != E13 R→ E14 E→ E + T15 E→ T16 T→ T * F17 T→ F18 F→ ( E )19 F→ n // 数20 F→ i // 标识符三、实验设计：1、消除该文法的左递归（产生式1、3、14、16）；产生式(1)L→ L || A (2)L→ A消除左递归得到：L→ A L' L'→ || A L' | з产生式(3)A→ A && R (4)A→ R消除左递归得到：A→ RA' A'→ && RA' | з产生式(14)E→ E + T (15)E→ T消除左递归得到：E→ TE' E'→ + TE' | з产生式(16)T→ T * F (17)T→ F消除左递归得到：T→ FT' T'→ *FT' | з2、通过抽取公共左因子（产生式7 ~ 12），对该文法进行LL(1)改造；产生式7~127 R→ E >= E8 R→ E > E9 R→ E <= E10 R→ E < E11 R→ E == E12 R→ E != E抽取公共左因子：R→ ER'R'→ >=E | >E | <=E | <E | ==E | !=E3、证明最终得到的文法为LL(1)文法。

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

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

在以下产生式中，非终结符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
请消除该文法的左递归。

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）确定⽅向做⼀件事并不难，最难的是没有⽅向，不知道要做什么；只是感觉时光流逝⾃⼰却⼀点东西都没产出。

编译原理实验实验名称：消除文法左递归姓名：学号：教师签字：成绩：消除文法的左递归实验目的：实现消除左递归实验要求：输入任意的上下文无关文法,输出消除了左递归的等价文法。

实验原理：1.非终结符的排列为A1，A2……An2.For(i=1;i<=n;i++)For(j=1;j<=i-1;j++)If(Ai→Aj&& A→B1|B2|…|Bn) 替换为Ai=B1r|B2r|…|Bnr；3.消除Ai的左递归4.消除无用产生式消除直接左递归的方法是：将左递归改为右递归。

消除简介左递归的方法是：先通过产生式非终结符置换，将间接左递归变为直接左递归，然后消除直接左递归。

实验代码:#include<iostream>#include<string>using namespace std;//*******************************structwenfa //结构体定义{string left; //产生式左部string right; //产生式右部};//************************************void change(wenfa *p,char *q,intn,int count) //消除左递归{int count1=n;int flag=0;for(int i=0;i <n;i++)if(p[i].left[0]==q[0])if(p[i].left[0]==p[i].right[0])flag++;if(flag!=0){for(int i=0;i <n;i++)if(p[i].left[0]==q[0])if(p[i].left[0]==p[i].right[0]){stringstr;str=p[i].right.substr(1,int (p[i].right.length())); string temp=p[i].left;string temp1="'";p[i].left=temp+temp1;p[i].right=str+p[i].left;}else{string temp=p[i].left;string temp1="'";temp=temp+temp1;p[i].right=p[i].right+temp;}string str="'";p[count1].left=p[0].left[0]+str;p[count1].right="#";}for( i=0;i <= count;i++){for(int j=0;j <i;j++){for(int g=0;g <n;g++)if(q[i]==p[g].left[0])if(p[g].right[0]==q[j]){for(int h=0;h < n*n;h++)if(p[h].left[0]==q[j]&&int (p[h].left.length())==1) {stringstr;str=p[g].right.substr(1,int (p[g].right.length())); p[++count1].left=p[g].left;p[count1].right=p[h].right+str;}p[g].left="";p[g].right="";}}}for( i=0;i <= count;i++){flag=0;for(int j=0;j < n*n;j++)if(p[j].left[0]==q[i])if(p[j].left[0]==p[j].right[0])flag++;if(flag!=0){for(int j=0;j <= n*n;j++)if(p[j].left[0]==q[i])if(p[j].left[0]==p[j].right[0]){stringstr;str=p[j].right.substr(1,int (p[j].right.length()));string temp=p[j].left;string temp1="'";p[j].left=temp+temp1;p[j].right=str+p[j].left;}else{string temp=p[j].left;string temp1="'";temp=temp+temp1;p[j].right=p[j].right+temp;}string str="'";p[++count1].left=q[i]+str;p[count1].right="#";}}}//******************************************************int Delete(wenfa *p,int n){return 0;}//*********************************************************************** int main(){cout<<" ********************消除左递归*********************"<<endl<<endl;inti,j,flag=0,count=1,n;cout<<"输入产生式的数目：";wenfa *p=new wenfa[60];cout<<"请输入文法的个产生式："<<endl;for(i=0;i<n;i++) //接收产生式{cin>>p[i].left;cout<<"\b-->";cin>>p[i].right;cout<<endl;}cout<<endl;cout<<"输入的文法产生式为："<<endl;for(i=0;i <n;i++) //输出产生式{cout<<"\t";cout<<p[i].left<<"-->"<<p[i].right<<endl;}cout<<endl<<endl;char q[20];q[0]=p[0].left[0];for(i=1;i<n;i++){flag=0;for(j=0;j<i;j++)if(p[i].left==p[j].left)flag++;if(flag==0)q[count++]=p[i].left[0];}count--;change(p,q,n,count);Delete(p,n);cout<<"消除递归后的产生式为："<<endl;for(i=0;i <= count;i++){for(int j=0;j <= n*n;j++)if( (p[j].left[0]==q[i]) &&int (p[j].left.length())==1 )cout<<p[j].left<<"---->"<<p[j].right<<endl;else continue;for( j=0;j <= n*n;j++)if( (p[j].left[0]==q[i]) &&int (p[j].left.length())==2 )cout<<p[j].left<<"---->"<<p[j].right<<endl;else continue;return 0;}实验截图：。

学号：专业：姓名：实验日期：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..实验结果：。

LL(1)语法分析一，实验名称：实现LL分析。

二，实验要求：➢输入任意文法➢消除左递归➢消除左因子➢测试任意输入语句是否合法➢数据结构描述➢算法说明➢输出first集合➢输出follow集合➢输出LL(1)表三．设计原理及算法描述所谓LL（1）分析法，就是指从左到右扫描输入串（源程序），同时采用最左推导，且对每次直接推导只需向前看一个输入符号，便可确定当前所应当选择的规则。

实现LL（1）分析的程序又称为LL（1）分析程序或LL1（1）分析器。

一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。

当文法满足条件后，再分别构造文法每个非终结符的FIRST和FOLLOW集合，然后根据FIRST和FOLLOW集合构造LL（1）分析表，最后利用分析表，根据LL(1)语法分析构造一个分析器。

LL（1）的语法分析程序包含了三个部分，总控程序，预测分析表函数，先进先出的语法分析栈，本程序也是采用了同样的方法进行语法分析，该程序是采用了C语言来编写，其逻辑结构图如下：LL（1）预测分析程序的总控程序在任何时候都是按STACK栈顶符号X和当前的输入符号a做哪种过程的。

对于任何（X，a），总控程序每次都执行下述三种可能的动作之一：（１）若X = a =‘#’，则宣布分析成功，停止分析过程。

（２）若X = a ‘#’，则把X从STACK栈顶弹出，让a指向下一个输入符号。

（３）若X是一个非终结符，则查看预测分析表M。

若M[A，a]中存放着关于X的一个产生式，那么，首先把X弹出STACK 栈顶，然后，把产生式的右部符号串按反序一一弹出STACK 栈（若右部符号为ε，则不推什么东西进STACK栈）。

若M[A，a]中存放着“出错标志”，则调用出错诊断程序ERROR。

事实上，LL（1）的分析是根据文法构造的，它反映了相应文法所定义的语言的固定特征，因此在LL（1）分析器中，实际上是以LL（1）分析表代替相应方法来进行分析的。

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

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

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

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

例如，对于以下文法：```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 中。

第⼗次作业消除左递归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集。

编译原理实验报告实验名称消除文法的左递归实验时间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就显现出其左递归性了，这就是间接左递归文法。

编译原理实验报告计算机学院计算机科学与技术姓名:班号:学号:指导老师：刘远兴日期： 2007[一]消除左递归1、算法：要求：输入无回路文法G输出无左递归的等价文法G'方法将非终结符合理排序：A1，A2，...，An;for i in 2..nloop for j in 1..i-1loop 用Aj→δ1|δ2|...|δk的右部替换每个形如Ai→Ajγ产生式中的Aj,得到新产生式：Ai→δ1γ|δ2γ|...|δkγ;消除Ai产生式中的直接左递归;end loop;end loop;概述：将不是直接左递归的非终结符右部展开到其他产生式中注意：若G产生句子的过程中出现A A的推导，则无法消除左递归设计方法：如果一个文法中含有无用符号，ε产生式或单产生式，则总可将它们予以消除。

因此，不失一般性，在下面的讨论中，我们可假定所给的文法不含上述三种产生式。

由于文法的直接左递归性表现在含有形如A→Aα(α∈V+)的产生式上，所以为了消除直接左递归，只须将此种产生式进行改写，使之不含左递归的非终结符号即可。

用来进行此种改写的方法之一，是引入一对元语言符号{、}，用以表示花括号{x}中的符号串x可出现任意多次 (包括零次)，并把形如A→Aα|β的产生式 (其中，β不以A打头)等价地改写为A→β{α} (4 8)从而也就消除了此产生式的直接左递归性。

例如，对于文法中的产生式1和2，利用此种方法可分别改写为E→T{AT}及T→F{MF}用来改写产生式(4 8)的另一种方法，是对A引入一个新的非终结符号A′，并把式(4 8)等价地写成A→βA′A′→αA′|ε由于β不以A打头，α不以A′打头，故所得的两个产生式不是直接左递归的。

例如，对于文法(4 1)，经此种方法改写之后就成为1 E→TE′2 E′→ATE′|ε3 T→FT′4 T′→MFT′|ε(4 1)′5 F→(E)|i6 A→+|-7 M→*|/一般地，设文法中的全部A产生式为A→Aα1|Aα2|…|Aαn|β1|β2|…|βm其中，每个β i均不以A打头，则消除直接左递归后所得到的产生式为A→β1A′|β2A′|…|β mA′A′→α1A′|α2A′|…|αnA′|ε上述方法可消除出现在产生式中的全部直接左递归性，但却不能消除经两步或多步推导所出现的一切左递归性。

实验二递归下降语法分析一．实验目的1、按照语言的语法要求编写文法的规则2、转化文法的规则，使之具有EBCF，消除左递归和左因子3、掌握编程形式的语法分析器的实现二．实验内容在TINY计算机语言的编译程序的词法分析部分实现的基础上，采用递归下降的方法实现语法分析，形成语法树。

语法分析的输入是记号串，按照从左到右扫描，按照文法规则的要求，判断语句是否符合文法要求，如果符合要求则形成语法数，不符合则指出原因。

为了简化程序的编写，对语法有具体如下的要求：（1）只有5中语句if、repeat、read、write、assignment。

（2）read只作用一个变量，实现输入。

（3）write只作用一个表达式，实现输出。

（4）表达式只有两类：布尔表达式，只用于if和repeat语句的测试，算术表达式采用左结合和优先级的方式组成。

（5）没有变量的声明，仅仅在赋值时采用隐性的方式说明，只有整型变量；（6）每个语句序列采用‘；’的形式分开，最后一个语句没有分号（7）没有函数或过程三．实验要求要求实现语法分析程序的以下功能：（1）在实现之前首先实现EBNF，消除左递归和左因子，为递归下降程序做好准备（2）对于语句和表达式采用枚举的形式定义，形成一个统一的树结点结构（3）把正确源程序的首先经过词法分析形成二元式记号提供给语法分析程序（4）如果出现错误，指出错误的位置和类型（5）把语法树按照树的前序遍历的形式把所有的结点按照某种形式输出语法分析进行具体的要求：（1）语法分析的具体功能实现是一个函数TreeNode* parse()，分析记号串，形成一个语法数。

（2）编写一个单独的函数parseTree(TreeNode*)遍历整个语法树，把每个结点信息输出程序：头文件：#include<string>using namespace std;enum WordType {WRONG, NUMBER, IDENTIFIER, IF, THEN, ELSE, END, //7REPEAT, UNTIL, READ, WRITE, FALSE, PLUS, SUBTRACT, MULTIPLY, //16DIVIDEY, EQUAL, LESSTHAN, SEMICOLON, FINAL, ASSIGNMENT, S_BRACKET_L, S_BRACKET_R,//24LINE_FEED, SPACE, TAB, BIG_BRACKET_L, BIG_BRACKET_R}; //29void CiFa ();void Yufa2 ();string IntToStr(int n);//将数字转换成字符串int EqulStr (string s1, string s2);//比较两个字符串是否相等，相等返回1，否则返回0源文件：头文件中函数：#include<iostream>#include<string>#include<sstream>#include<stdexcept>#include"head.h"using namespace std;string IntToStr(int n){ostringstream result;result << n;return result.str();}int EqulStr (string s1, string s2){if (s1 == s2)return 1;elsereturn 0;}词法分析：#include<iostream>#include<iomanip>#include<ctype.h>#include<fstream>#include<string>#include"head.h"using namespace std;enum CharType {ALPHABET, OTHER};enum WrongType1 {ZERO, ALP_NUM, NUM_ALP, UNLEAGL_S, NO_MATCH, UNKNOW};char *Words [] = {"wrong", "number", "identifier", "if", "then", "else", "end",//7 "repeat", "until","read", "write", "false", "+", "-", "*", //16"/", "=", "<", ";", "$",":=", "(", ")",//24"\n", " ", " ", "{", "}"}; //29typedef struct{char *str;int wordtype;}Two;char ArrayChar[100], cbuffer;int i=-1, numline = 1, wordtype;string LineChar;Two T;ifstream fp("source.txt",ios::in);ofstream outfile ("cifa.txt", ios::out);void CiFa (){Two GetToken();if (!fp)cout<<"文件打开错误！！"<<endl;else{cout << setiosflags (ios::left) << setw (6) << "行数" << "(";cout << setiosflags (ios::left) << setw (10)<< "类别编码" << ", ";cout << setiosflags (ios::left) << setw (20) << "字符" << ")" << endl;fp.get (cbuffer);while (!fp.eof ()){GetToken();}outfile << numline << "," << FINAL << ",";}cout << "第" << numline << " 行所有字符：" << LineChar << endl;fp.close ();outfile.close ();}int Match(char str[], int chartype)//查找匹配的字符{int i;switch (chartype){case ALPHABET:for (i = IF; i <= FALSE; i++){if (strcmp(Words[i],str) == 0)return i;}case OTHER:for (i = PLUS; i <= S_BRACKET_R; i++){if (strcmp(Words[i],str) == 0)return i;}}return WRONG;}void TypeWrong (int wrongtype, int line){switch (wrongtype){case ZERO:break;case ALP_NUM:cout << "字母后面不能紧跟数字！";break;case NUM_ALP:cout << "数字后面不能紧跟字母！";break;case UNLEAGL_S:cout << "非法特殊符号！";break;case NO_MATCH:cout << "没有与第" << line << " 行“{”匹配的“}”！";break;default :cout << "其它类型错误！";break;}}Two ConvertTwo (char str[], int wordtype, int wrongtype, int numline, int line)//进行二元转换{Two T;T.wordtype = wordtype;T.str = str;cout << setiosflags (ios::left) << setw (6) << numline << "(";cout << setiosflags (ios::left) << setw (10) << T.wordtype << ", ";cout << setiosflags (ios::left) << setw (20) << T.str << ")";if (T.wordtype == WRONG)TypeWrong (wrongtype, line);cout << endl;outfile << numline << "," << T.wordtype << "," ;return T;}void HandleAlphabet ()//首字符为字母时的处理{bool mark = true;while(!fp.eof() && isalpha(cbuffer)){ArrayChar[++i]=cbuffer;fp.get(cbuffer);}if (isdigit (cbuffer)){mark = false;while(!fp.eof() && (isalpha(cbuffer)||isdigit(cbuffer))){ArrayChar[++i]=cbuffer;fp.get(cbuffer);}}ArrayChar[i+1]='\0';LineChar += ArrayChar;if (mark){wordtype = Match(ArrayChar, ALPHABET);T = ConvertTwo(ArrayChar,(IDENTIFIER > wordtype ? IDENTIFIER : wordtype), ZERO, numline, numline);}elseT = ConvertTwo(ArrayChar,WRONG, ALP_NUM, numline, numline);}void HandleNumber ()//首字符为数字时的处理{bool mark = true;while (!fp.eof() && isdigit(cbuffer)){ArrayChar[++i]=cbuffer;fp.get(cbuffer);}if (isalpha(cbuffer)){mark = false;while(!fp.eof() && (isalpha(cbuffer)||isdigit(cbuffer))){ArrayChar[++i]=cbuffer;fp.get(cbuffer);}}ArrayChar[i+1]='\0';LineChar += ArrayChar;if (mark)T = ConvertTwo(ArrayChar, NUMBER, ZERO, numline, numline);elseT = ConvertTwo(ArrayChar,WRONG, NUM_ALP, numline, numline);}void DeleteNote ()//删除注释{int record = numline;while (!fp.eof() && cbuffer != '}'){fp.get(cbuffer);while (!fp.eof() && cbuffer != '}'){if (cbuffer == '\n'){ArrayChar [i + 1] = '\0';LineChar += ArrayChar;cout << "第" << numline << " 行所有字符：" << LineChar << endl;LineChar = "";numline++;i = -1;fp.get(cbuffer);}ArrayChar[++i]=cbuffer;fp.get(cbuffer);}ArrayChar[i + 1]='\0';if (cbuffer == '}'){ArrayChar [++i] = '}';ArrayChar[i + 1]='\0';}else{T = ConvertTwo("", WRONG, NO_MATCH, numline, record);}}LineChar += ArrayChar;fp.get(cbuffer);}void HandleOther ()//字符为特殊字符时的处理{ArrayChar [++i] = cbuffer;if (ArrayChar [i] == '{')//删除注释{DeleteNote ();}else//其他字符{fp.get(cbuffer);ArrayChar [++i] = cbuffer;ArrayChar[i + 1] = '\0';char Temp1 [2];Temp1 [0] = ArrayChar [0];Temp1 [1] = '\0';if (!(wordtype = Match(ArrayChar, OTHER)))//当双字符没有匹配的时候，看单字符是否有匹配的{ArrayChar [i] = '\0';if (!wordtype)wordtype = Match(Temp1, OTHER);}else{fp.get(cbuffer);while (!fp.eof() && cbuffer != '\n' && cbuffer != ' ' && cbuffer != ' '&& !isalpha(cbuffer) && !isdigit(cbuffer)){ArrayChar [++i] = cbuffer;fp.get(cbuffer);}ArrayChar[i + 1]='\0';wordtype = Match(ArrayChar, OTHER);}LineChar += ArrayChar;T = ConvertTwo(ArrayChar, wordtype, (wordtype > 0 ? 0: UNLEAGL_S), numline, numline);}}Two GetToken(){if(cbuffer == '\n')//忽略换行符{cout << "第" << numline << " 行所有字符：" << LineChar << endl;numline++;LineChar = "";fp.get(cbuffer);}else if (cbuffer == ' ')//忽略空字符{LineChar += " ";fp.get(cbuffer);}else if (cbuffer == ' ')//忽略制表符{LineChar += " ";fp.get(cbuffer);}else if (isalpha(cbuffer))//判断是否是字母{HandleAlphabet ();}else if (isdigit(cbuffer))//判断是否是数字{HandleNumber ();}else//其他字符HandleOther ();i = -1;return T;}语法分析:#include <iostream>#include <iomanip>#include <ctype.h>#include <fstream>#include <string>#include <sstream>#include <stdexcept>#include "head.h"using namespace std;ifstream fp2("cifa.txt",ios::in);int SPro ();//1int SStm ();//2int SStms ();//3int SSta ();//4int SIf ();//5int SRep ();//6int SAss ();// 7int SRea ();//8int SWri ();//9int SExp ();//10int SCom ();//11int SSim ();//12int SSims ();//13int SAdd ();//14int STer ();//15int STers ();//16int SMul ();//17int SFac ();//18char lastline [4], line [4], ch2[4];bool OK = true;void GetWord (char *line, char *ch2){strcpy_s (lastline, line);fp2.getline (line, 3, ',');fp2.getline (ch2, 3, ',');}void Yufa2 (){CiFa ();if (!fp2)cout<<"文件打开错误！！"<<endl;else{cout << "文件打开成功！" << endl;GetWord (line, ch2);while (!EqulStr (ch2, IntToStr (FINAL)))SPro ();if (OK)cout << "OK 源文件符合该文法!" << endl;elsecout << "Wrong 源文件不符合该文法!" << endl;}fp2.close ();}int SPro ()//1{if (SStm ())return 1;//如果此次读入的第一个字符不是开始符号，则继续读取下一个cout << "第" << lastline << "行错误！" << endl;GetWord (line, ch2);OK = false;return 0;}int SStm ()//2{if (SSta ()){if (SStms ())return 1;elsecout << "第 " << lastline << " 行缺少语句的结束符；！" << endl;OK = false;return 1;}return 0;}int SStms ()//3{if (EqulStr (ch2, IntToStr (SEMICOLON))){GetWord (line, ch2);if (SSta ()){if (SStms ())return 1;elsecout << "第 " << lastline << " 行缺少有效的语句！" << endl;}elsecout << "第 " << lastline << " 行 ; 后面没有有效的语句！" << endl;OK = false;return 1;}else if (EqulStr (ch2, IntToStr (END)) || EqulStr (ch2, IntToStr (ELSE)) || EqulStr (ch2, IntToStr (UNTIL)) || EqulStr (ch2, IntToStr (FINAL)))return 1;return 0;}int SSta ()//4{if (SIf () || SRep () || SAss () || SRea () || SWri ())return 1;return 0;}int SIf ()//5{if (EqulStr (ch2, IntToStr (IF))){GetWord (line, ch2);if (SExp ()){if (EqulStr (ch2, IntToStr (THEN))){GetWord (line, ch2);if (SStm ()){if (EqulStr (ch2, IntToStr (END))){GetWord (line, ch2);return 1;}else if (EqulStr (ch2, IntToStr (ELSE))){GetWord (line, ch2);if (SStm ()){if (EqulStr (ch2, IntToStr (END))){GetWord (line, ch2);return 1;}else{cout << "第 " << lastline << " 行缺少语句的结束符 end！" << endl;}}else{cout << "第 " << lastline << " 行 else 后面没有有效的语句！" << endl;}}else{cout << "第 " << lastline << " 行缺少语句的结束符 end！" << endl;}}else{cout << "第 " << lastline << " 行缺少关键字 else！" << endl;}}else{cout << "第 " << lastline << " 行 then 后面没有有效的语句！" << endl;}}elsecout << "第 " << lastline << " 行 if 后面没有有效的表达式！" << endl;OK = false;return 1;}return 0;}int SRep ()//6{if (EqulStr (ch2, IntToStr (REPEAT))){GetWord (line, ch2);if (SStm ()){if (EqulStr (ch2, IntToStr (UNTIL))){GetWord (line, ch2);if (SExp ())return 1;elsecout << "第 " << lastline << " 行 until 后面没有有效的表达式！" << endl;}else{cout << "第 " << lastline << " 行缺少关键字 until！" << endl;}}elsecout << "第 " << lastline << " 行 repeat 后面没有有效的语句！" << endl;OK = false;return 1;}return 0;}int SAss ()//7{if (EqulStr (ch2, IntToStr (IDENTIFIER))){GetWord (line, ch2);if (EqulStr (ch2, IntToStr (ASSIGNMENT))){GetWord (line, ch2);if (SExp ())return 1;elsecout << "第 " << lastline << " 行 := 后面没有有效的表达式！" << endl;}else{cout << "第 " << lastline << " 行缺少关键字 :=！" << endl;}OK = false;return 1;}return 0;}int SRea ()//8{if (EqulStr (ch2, IntToStr (READ))){GetWord (line, ch2);if (EqulStr (ch2, IntToStr (IDENTIFIER))){GetWord (line, ch2);return 1;}else{cout << "第 " << lastline << " 行 read 后面没有有效的标识符！" << endl;}OK = false;return 1;}return 0;}int SWri ()//9{if (EqulStr (ch2, IntToStr (WRITE))){GetWord (line, ch2);if (SExp ())return 1;elsecout << "第 " << lastline << " 行 write 后面没有有效的表达式！" << endl;OK = false;return 1;}return 0;}int SExp ()//10{if (SSim ()){if (SCom ()){if (SSim ())return 1;elsecout << "第 " << lastline << " 行缺少（或者数字或者标识符！" << endl;OK = false;}return 1;}return 0;}int SCom ()//11{if (EqulStr (ch2, IntToStr (LESSTHAN)) || EqulStr (ch2, IntToStr (EQUAL))){GetWord (line, ch2);return 1;}return 0;}int SSim ()//12{if (STer ()){if (SSims ())return 1;elsecout << "第 " << lastline << " 行缺少有效的关键字！" << endl;OK = false;return 1;}return 0;}int SSims ()//13{if (SAdd ()){if (STer ()){if (SSims ())return 1;elsecout << "第 " << lastline << " 行缺少有效的关键字！" << endl;}elsecout << "第 " << lastline << " 行缺少（或者数字或者标识符！" << endl;OK = false;return 1;}elseif (EqulStr (ch2, IntToStr (THEN)) || EqulStr (ch2, IntToStr (END)) || EqulStr (ch2, IntToStr (ELSE))|| EqulStr (ch2, IntToStr (UNTIL)) || EqulStr (ch2, IntToStr (S_BRACKET_R)) || EqulStr (ch2, IntToStr (LESSTHAN))|| EqulStr (ch2, IntToStr (EQUAL)) || EqulStr (ch2, IntToStr (FINAL)) || EqulStr (ch2, IntToStr (SEMICOLON)))return 1;return 0;}int SAdd ()//14{if (EqulStr (ch2, IntToStr (PLUS)) || EqulStr (ch2, IntToStr (SUBTRACT))){GetWord (line, ch2);return 1;}return 0;}int STer ()//15{if (SFac ()){if (STers ())return 1;elsecout << "第 " << lastline << " 行缺少有效的关键字！" << endl;OK = false;return 1;}return 0;}int STers ()//16{if (SMul ()){if (SFac ()){if (STers ())return 1;elsecout << "第 " << lastline << " 行缺少有效的表达式！" << endl;}elsecout << "第 " << lastline << " 行缺少有效的表达式！" << endl;OK = false;return 1;}else if (EqulStr (ch2, IntToStr (THEN)) || EqulStr (ch2, IntToStr (END)) || EqulStr (ch2, IntToStr (ELSE))|| EqulStr (ch2, IntToStr (UNTIL)) || EqulStr (ch2, IntToStr (S_BRACKET_R)) || EqulStr(ch2, IntToStr (LESSTHAN))|| EqulStr (ch2, IntToStr (EQUAL)) || EqulStr (ch2, IntToStr (FINAL)) || EqulStr (ch2, IntToStr (SEMICOLON))|| EqulStr (ch2, IntToStr (PLUS)) || EqulStr (ch2, IntToStr (SUBTRACT)))return 1;return 0;}int SMul ()//17{if (EqulStr (ch2, IntToStr (MULTIPLY)) || EqulStr (ch2, IntToStr (DIVIDEY))){GetWord (line, ch2);return 1;}return 0;}int SFac ()//18{if (EqulStr (ch2, IntToStr (S_BRACKET_L))){GetWord (line, ch2);if (SExp ()){if (EqulStr (ch2, IntToStr (S_BRACKET_R))){GetWord (line, ch2);return 1;}else{cout << "第 " << lastline << " 行表达式后面缺少符号）！" << endl;}}elsecout << "第 " << lastline << " 行（后面缺少有效的表达式！" << endl;OK = false;return 1;}else if (EqulStr (ch2, IntToStr (NUMBER)) || EqulStr (ch2, IntToStr (IDENTIFIER))){GetWord (line, ch2);return 1;}return 0;}主函数：#include<iostream>#include<iomanip>#include<ctype.h>#include<fstream>#include<string>#include"head.h" using namespace std; int main (){Yufa2 ();system ("pause");return 0;}实验。