实验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; 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 #include using namespace std;

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)) {

for(i=0;i

if(p[i].right.length()

else //即不是0型文法 flag--;//flag=-1 if(flag>0) {

cout<

return 1; //属于1型文法 else return 0; }

int two(Chomsky *p)//2型文法 {

int flag(0); int i; if(one(p)) {

for(i=0;i

if((p[i].left.length()!=1)||!(p[i].left[0]>='A'&&p[i].left[0]<='Z')) //左部不属于一个字符或不属于非终结符 {

flag++;//则不为2型 break; } }

else//不为1型flag=-1 flag--; if(flag>0) {

cout<

return 1; //属于2型文法 } else return 0; }

int remove(Chomsky *p,int n)//消除左递归

{//把文法的所有非终结符按某一顺序排序

int i,j,count=1,count1=n,flag=0,m,x; q[0]=p[0].left[0];

for(i=1;i

for(j=0;j

if(p[i].left==p[j].left)break; }

if(j==i)q[count++]=p[i].left[0]; }

count--;

for(i=0;i

if(p[i].left[0]==q[0]&&p[i].left[0]==p[i].right[0]) flag++;

if(flag!=0)//消除第一个非终结符的直接左递归 {

for(i=0;i

if(p[i].left[0]==q[0]) {

if(p[i].left[0]==p[i].right[0]) {

p[i].left=p[i].left+\

p[i].right=p[i].right.substr(1,p[i].right.length())+p[i].left; }

else

p[i].right=p[i].right+p[i].left+\ } }

p[count1].left=p[0].left;

p[count1++].right=\用#代替空产生式 }

//消一切左递归 for(m=0;m<=count;m++) {

for(i=0;i

if(p[i].left[0]==q[m]) {

for(j=0;j

{ for(x=m+1;x<=count;x++)

if(p[j].left[0]==q[x]&&p[j].right[0]==q[m]) {

p[count1].left=p[j].left;

p[count1].right=p[i].right+p[j].right.substr(1,p[j].right.length());

count1=count1+1; } } } }

for(j=0;j

{

for(x=m+1;x<=count;x++)

if(p[j].right[0]==q[m]&&p[j].left[0]==q[x]) {

p[j].right=\ p[j].left=\ } }

for(x=0,flag=0;x

if(p[x].left[0]==q[m]&&p[x].left[0]==p[x].right[0])

flag++;

//消直接左递归

if(flag!=0) {

for(i=0;i

if(p[i].left[0]==q[m]) {

if(p[i].left[0]==p[i].right[0])

{

p[i].left=p[i].left+\

p[i].right=p[i].right.substr(1,p[i].right.length())+p[i].left;

p[count1].left=p[i].left;

p[count1].right=\用#代替空产生式 } else

p[i].right=p[i].right+p[i].left+\ } }

count1=count1+1; } }

count1--; return count1; }

void main( ) {

int i,j,count1;

cout<<\编译原理实验非LL(1)文法到LL(1)文法的转换................\

cout<<\请输入产生式总数及各产生式\其中左右部之间用'-'表示空用'#'表示\ cin>>n;

Chomsky *p=new Chomsky[50]; // 初始化产生式数组

for(i=0;i

cin>>strings; apart(p,i); }

if(two(p)) {

cout<<\该文法属于二型文法实验继续...\ count1=remove(p,n);

cout<<\转换后的文法输出如下\ for(i=0;i<=count1;i++) {

if(p[i].left[0]!=NULL)

cout<

cout<<\该文法不是2型文法无需进行LL(1)的转换实验结束\ system(\ }

八、思考题

1、 是不是所有的文法都可以通过上述程序构造LL（1）文法？ 2、 LL（1）文法在整个语法分析中的作用？

3、 实验1中设计的文法数据结构对本实验的影响？ 4、 如何更好地组合实验1和实验3，使之具有更高的效率？

本文来源：https://www.bwwdw.com/article/7d13.html