实 实验课程：编译原理学生姓名：学 号：专业班级：计科
验
报
告
实验3 LL（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； j< i-1；j++)
将Pj代入Pi的产生式（若可代入的话）； 消除关于Pi的直接左递归：
Pi->Piα|β，其中β不以Pi开头，则修改产生式为：
Pi—＞βPi′ Pi′—＞αPi′|ε
3）化简上述所得文法。
3、 提取左因子的算法：
A —＞δβ1|δβ2|?|δβn|γ1|γ2|?|γm
(其中,每个γ不以δ开头)
那么,可以把这些产生式改写成
A —＞δA′|γ1| γ2?|γm
A′—＞β1|β2|?|βn
4、 利用上述算法，实现构造一个LL（1）文法：
1） 从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结
构；
2） 设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和
提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子； 3） 整理得到的新文法；
4） 在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，
开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。
四、实验环境
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、实验步骤
1、学习LL（1）文法的分析条件； 2、学习构造LL（1）文法的算法；
3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法；
4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式；
5、 把实验结果写入一个新建立的文本文件。
六、测试数据
输入数据：
编辑一个文本文文件g.txt，在文件中输入如下内容：
正确结果：
选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：
S->Qc|cT; T->@|ab; //由于无法输出ε，用@代替 Q->Rb|b; R->bcaU|caU|cabaU|aU; U->bcaU|@; 本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或
S->Qc|c|cab; Q->Rb|b; R->Sa|a; 七、实验报告要求
实验报告应包括以下几个部分： 1、 满足LL（1）文法的分析条件； 2、 构造LL（1）文法的算法；
3、 消除左递归文法和提取左因子算法实现方法； 4、 整个测试程序的流程； 5、 程序的测试结果和问题； 6、 实验总结。
代码
#include
typedef struct Chomsky //定义一个产生式结构体 {
string left; //定义产生式的左部 string right; //定义产生式的右部 }Chomsky;
int n;//产生式总数 string strings;//存储产生式 char q[20];
void apart(Chomsky *p,int i) //分开产生式左右部?i代表产生式的编号 { int j;
for(j=0;j if(strings[j]=='-') { p[i].left=strings.substr(0,j);//从0开始的j长度的子串?即0~j-1 p[i].right=strings.substr(j+1,strings.length()-j);//从j+1开始的后面子串 } } int zero(Chomsky *p)//0型文法 { int flag(0),count(0); int i,j; for(i=0;i for(j=0;j<(int)p[i].left.length();j++) { if(p[i].left[j]>='A'&&p[i].left[j]<='Z') //有否非终结符 flag++;//非终结符个数加1 } if(flag>0)//说明某一个产生式左部有非终结符 { flag=0;//下个产生式判断前清零 count++;//左部存在非终结符的产生式 个数加1 } else break; //左部没有非终结符?结束 } if(count==n) return 1; //属于0型文法 else { cout< int one(Chomsky *p)//1型文法 { int flag(0); int i; if(zero(p)) {