资源描述：
《编译原理实验报告3-ll文法构造》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、实验3LL（1）文法构造一、实验目的熟悉LL（1）文法的分析条件，了解LL（1）文法的构造方法。 二、实验内容1、编制一个能够将一个非LL（1）文法转换为LL（1）文法；2、消除左递归；3、消除回溯。 三、实验要求1、将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。2、提取文法左因子算法：1）对文法G的所有非终结符进行排序2）按上述顺序对每一个非终结符Pi依次执行:for(j=1；jPiα
2、β，其中β不以P
3、i开头，则修改产生式为：Pi—＞βPi′Pi′—＞αPi′
4、ε3）化简上述所得文法。3、提取左因子的算法：A—＞δβ1
5、δβ2
6、…
7、δβn
8、γ1
9、γ2
10、…
11、γm(其中,每个γ不以δ开头)那么,可以把这些产生式改写成A—＞δA′
12、γ1
13、γ2…
14、γmA′—＞β1
15、β2
16、…
17、βn4、利用上述算法，实现构造一个LL（1）文法：1）从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结构；1）设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归
18、和提出左因子；2）整理得到的新文法；3）在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“
19、”分隔的方式输出。 四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境 五、实验步骤1、学习LL（1）文法的分析条件；2、学习构造LL（1）文法的算法；3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法；4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式；2、把实验结果写入一个新
20、建立的文本文件。 六、测试数据输入数据：编辑一个文本文文件g.txt，在文件中输入如下内容：S->Qc
21、c
22、cab;Q->Rb
23、b;R->Sa
24、a; 正确结果：本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：S->Qc
25、cT;T->@
26、ab;//由于无法输出ε，用@代替Q->Rb
27、b;R->bcaU
28、caU
29、cabaU
30、aU;U->bcaU
31、@; 七、实验报告要求实验报告应包括以下几个部分：1、满足LL（1）文法的分析条件；转换前要求文法中不含回路（经过推导有形如P
32、->P之类的），也不含以ε为右部的产生式。一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。首先需要定义一些规则：1.在程序运行前文法就必须输入进文本文件中，输入的文法只包含其中的所有产生式，并且默认其为可转换的非LL（1）文法，即通过消除左递归和反复提取公共左因子，就转换成了LL（1）文法。2.输入的产生式为原实验1的结果，即一个非终结符只有一条产生式，候选之间用“
33、”隔开。3.产生式与产生式之间只能以换行符或分号隔开。4.开始符号对应的产生式必须第一个输入，即默认输入的第一个产生式的左部的大写字母是开始符号。5.输入与输
34、出都会保存在文本文件中文件名分别是g.txt和newg.txt，本实验测试数据时，将两个文本放在了桌面。6.ε用@代替，输入与输出都使用@。7.新产生的非终结符统一使用没有在非终结符集合中出现的大写字母。8.规定产生式最多只有20个。2、构造LL（1）文法的算法；算法：1)从文本文件g.txt中读入文法，存入结构体中。将第一个读到的大写字母记为开始符号S，将读到的包括开始符号在内的所有大写字母判定为非终结符，并将第一次出现的存入文法的非终结符集合中，终结符小写字母也一样。将以换行符或分号隔开的字符串判断为一条产生式存入文法中。实现函数是scanP()。2)对文
35、法中的产生式消除左递归。实现函数是remove_left_recursion()。3)对文法中的产生式反复提取公共左因子。实现函数是remove_left_gene()。4)向newg.txt中输出文法的所有产生式。3、消除左递归文法和提取左因子算法实现方法；消除左递归文法（包括其中用到其它的子函数）：/*字符串分割函数，将产生式右部的候选返回,识别‘
36、’，从pos位开始分割*/stringstrsplit(stringstrTok,intpos){stringstr;size_tposition;position=strTok.find("
37、",pos);i
38、f(position!=string:
