发布时间 : 星期六 文章编译原理实验报告3-LL(1)文法构造更新完毕开始阅读
实验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; ，用@代替 S->Qc|c|cab; Q->Rb|b; R->Sa|a; 本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或
T->@|ab; //由于无法输出ε七、实验报告要求 Q->Rb|b; 实验报告应包括以下几个部分： R->bcaU|caU|cabaU|aU; 1、 满足LL（1）文法的分析条件； U->bcaU|@; 转换前要求文法中不含回路（经过推导有形如P->P之类的），也不含以ε为右部的产生式。
一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，
无左公因子。
首先需要定义一些规则：
1. 在程序运行前文法就必须输入进文本文件中，输入的文法只包含其中
的所有产生式，并且默认其为可转换的非LL（1）文法，即通过消除左递归和反复提取公共左因子，就转换成了LL（1）文法。 2. 输入的产生式为原实验1的结果，即一个非终结符只有一条产生式，
候选之间用“|”隔开。
3. 产生式与产生式之间只能以换行符或分号隔开。
4. 开始符号对应的产生式必须第一个输入，即默认输入的第一个产生式
的左部的大写字母是开始符号。
5. 输入与输出都会保存在文本文件中文件名分别是g.txt和newg.txt，本
实验测试数据时，将两个文本放在了桌面。 6. ε用@代替，输入与输出都使用@。
7. 新产生的非终结符统一使用没有在非终结符集合中出现的大写字母。 8. 规定产生式最多只有20个。
2、 构造LL（1）文法的算法；
算法：
1) 从文本文件g.txt中读入文法，存入结构体中。将第一个读到的大写字母记为开
始符号S，将读到的包括开始符号在内的所有大写字母判定为非终结符，并将第一次出现的存入文法的非终结符集合中，终结符小写字母也一样。将以换行符或分号隔开的字符串判断为一条产生式存入文法中。实现函数是scanP()。 2) 对文法中的产生式消除左递归。实现函数是remove_left_recursion()。 3) 对文法中的产生式反复提取公共左因子。实现函数是remove_left_gene ()。 4) 向newg.txt中输出文法的所有产生式。 3、 消除左递归文法和提取左因子算法实现方法；
消除左递归文法（包括其中用到其它的子函数）：
/*字符串分割函数，将产生式右部的候选返回,识别?|?，从pos位开始分割*/ string strsplit(string strTok,int pos ) {
string str; size_t position;
position = strTok.find(\,pos); if (position != string::npos) { } else {
//没找到
//找到了?|?
str = strTok.substr(pos,position - pos);
}
}
str = strTok.substr(pos, strTok.size() - pos);
return str;
/*获得一个文法中尚未定义的非终结符，即特定的大写字母*/ char GetWord(char *p) { }
/*判断非终结符是否已存在*/ bool checkWord(char ch, string Vn) { }
/*化简无用产生式*/
void simplify(struct grammar *gp) {
string str; int sVn[20]; sVn[0] = 0;
str.insert(0, 1, gp->Vn[0]); bool flag[20]; flag[0] = false; char ch; int i,j,k,l,o;
for (i = 0; i < str.size(); i++) {
for (j = 3; j < gp->P[sVn[i]].size(); j++) {
//标记哪个产生式需要删除
//初始化设置开始符号
//存储从开始符号可以到达的非终结符的序列
//标记在哪个产生式
int i;
bool flag = true;
for (i = 0; i < Vn.size(); i++) { } return flag;
if (ch == Vn[i])
flag = false;
char ch,word[] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q',
'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' }; int w,x;
for (w = 0; w < 26; w++) { } return ch;
ch = word[w];
for (x = 0; x < m; x++) { }
if (x == m) break;
if (ch == p[x]) { }
break;