编译原理实验报告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;