《LL（1）分析器的构造》实验报告
一、实验名称
LL(1)分析器的构造
二、实验目的
设计、编制、调试一个LL(1)语法分析器，利用语法分析器对符号串的识别，加深对语法分析原理的理解。
三、实验内容和要求
设计并实现一个LL(1)语法分析器，实现对算术文法:
G[E]:E->E+T|T
T->T*F|F
F->(E)|i
所定义的符号串进行识别，例如符号串i+i*i为文法所定义的句子，符号串ii+++*i+不是文法所定义的句子。
实验要求:
1、检测左递归，如果有则进行消除；
2、求解FIRST集和FOLLOW集；
3、构建LL(1)分析表；
4、构建LL分析程序，对于用户输入的句子，能够利用所构造的分析程序进行分析，并显示出分析过程。
四、主要仪器设备
硬件：微型计算机。
软件： Code blocks（也可以是其它集成开发环境）。
五、实验过程描述
1、程序主要框架
程序中编写了以下函数，各个函数实现的作用如下：
void input_grammer(string *G);//输入文法G
void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k);
//将文法G预处理得到产生式集合P，非终结符、终结符集合U、u，
int eliminate_1(string *G,string *P,string U,string *GG);//消除文法G中所有直接左递归得到文法GG
int* ifempty(string* P,string U,int k,int n);//判断各非终结符是否能推导为空
string* FIRST_X(string* P,string U,string u,int* empty,int k,int n)；求所有非终结符的FIRST
集
string FIRST(string U,string u,string* first,string s)；//求符号串Xn的FIRST集
string** create_table(string *P,string U,string u,int n,int t,int k,string* first)；//构造分析表
void analyse(string **table,string U,string u,int t,string s)；//分析符号串s
2、编写的源程序
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
void input_grammer(string *G)//输入文法G,n个非终结符
{
int i=0;//计数
char ch='y';
while(ch=='y'){
cin>>G[i++];
cout<<"继续输入?(y/n)\n";
cin>>ch;
}
}
void preprocess(string *G,string *P,string &U,string &u,int &n,int &t,int &k)//将文法G预处理产生式集合P，非终结符、终结符集合U、u，
{
int i,j,r,temp;//计数
char C;//记录规则中（）后的符号
int flag;//检测到（）
n=t=k=0;
for( i=0;i<50;i++) P[i]=" ";//字符串如果不初始化，在使用P[i][j]=a时将不能改变，可以用P[i].append(1,a)
U=u=" ";//字符串如果不初始化，无法使用U[i]=a赋值，可以用U.append(1,a)
for(n=0;!G[n].empty();n++)
{ U[n]=G[n][0];
}//非终结符集合，n为非终结符个数
for(i=0;i<n;i++)
{
for(j=4;j<G[i].length();j++)
{
if(U.find(G[i][j])==string::npos&&u.find(G[i][j])==string::npos)
if(G[i][j]!='|'&&G[i][j]!='^')
//if(G[i][j]!='('&&G[i][j]!=')'&&G[i][j]!='|'&&G[i][j]!='^')
u[t++]=G[i][j];
}
}//终结符集合，t为终结符个数
for(i=0;i<n;i++)
{
flag=0;r=4;
for(j=4;j<G[i].length();j++)
{
P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';
/* if(G[i][j]=='(')
{ j++;flag=1;
for(temp=j;G[i][temp]!=')';temp++);
C=G[i][temp+1];
//C记录（）后跟的字符，将C添加到（）中所有字符串后面
}
if(G[i][j]==')') {j++;flag=0;}
*/
l1正则化的作用 if(G[i][j]=='|')
{
//if(flag==1) P[k][r++]=C;
k++;j++;
P[k][0]=U[i];P[k][1]=':';P[k][2]=':';P[k][3]='=';
r=4;
P[k][r++]=G[i][j];
}
else
{
P[k][r++]=G[i][j];
}
}
k++;
}//获得产生式集合P，k为产生式个数
}
int eliminate_1(string *G,string *P,string U,string *GG)
//消除文法G1中所有直接左递归得到文法G2，要能够消除含有多个左递归的情况）
{
string arfa,beta;//所有形如A::=Aα|β中的α、β连接起来形成的字符串arfa、beta
int i,j,temp,m=0;//计数
int flag=0;//flag=1表示文法有左递归
int flagg=0;//flagg=1表示某条规则有左递归
char C='A';//由于消除左递归新增的非终结符，从A开始增加，只要不在原来问法的非终结符中即可加入
for(i=0;i<20&&U[i]!=' ';i++)
{ flagg=0;
arfa=beta="";
for(j=0;j<100&&P[j][0]!=' ';j++)
{
if(P[j][0]==U[i])
{
if(P[j][4]==U[i])//产生式j有左递归
{
flagg=1;
for(temp=5;P[j][temp]!=' ';temp++) arfa.append(1,P[j][temp]);
if(P[j+1][4]==U[i]) arfa.append("|");//不止一个产生式含有左递归
}
else
{
for(temp=4;P[j][temp]!=' ';temp++) beta.append(1,P[j][temp]);
if(P[j+1][0]==U[i]&&P[j+1][4]!=U[i]) beta.append("|");
}
}
}
if(flagg==0)//对于不含左递归的文法规则不重写
{GG[m]=G[i]; m++;}
else
{
flag=1;//文法存在左递归
GG[m].append(1,U[i]);GG[m].append("::=");
if(beta.find('|')!=string::npos) GG[m].append("("+beta+")");
else GG[m].append(beta);
while(U.find(C)!=string::npos){C++;}
GG[m].append(1,C);
m++;
GG[m].append(1,C);GG[m].append("::=");
if(arfa.find('|')!=string::npos) GG[m].append("("+arfa+")");
else GG[m].append(arfa);
GG[m].append(1,C);GG[m].append("|^");
m++;
C++;
}//A::=Aα|β改写成A::=βA‘，A’=αA'|β，
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论