语法分析报告器实验报告材料.docx

语法分析报告器实验报告材料.docx

《语法分析报告器实验报告材料.docx》由会员分享，可在线阅读，更多相关《语法分析报告器实验报告材料.docx（39页珍藏版）》请在冰点文库上搜索。

语法分析报告器实验报告材料

语法分析器的设计实验报告

一、实验内容

语法分析程序用LL

（1）语法分析方法。

首先输入定义好的文法书写文件（所用的文法可以用LL

（1）分析），先求出所输入的文法的每个非终结符是否能推出空，再分别计算非终结符号的FIRST集合，每个非终结符号的FOLLOW集合，以及每个规则的SELECT集合，并判断任意一个非终结符号的任意两个规则的SELECT集的交集是不是都为空，如果是，则输入文法符合LL

（1）文法，可以进行分析。

对于文法：

G[E]:

E->E+T|T

T->T*F|F

F->i|（E）

分析句子i+i*i是否符合文法。

二、基本思想

1、语法分析器实现

语法分析是编译过程的核心部分，它的主要任务是按照程序的语法规则，从由词法分析输出的源程序符号串中识别出各类语法成分，同时进行词法检查，为语义分析和代码生成作准备。

这里采用自顶向下的LL

（1）分析方法。

语法分析程序的流程图如图5-4所示。

该程序可分为如下几步：

（1）读入文法

（2）判断正误

（3）若无误，判断是否为LL

（1）文法

（4）若是，构造分析表；

（5）由句型判别算法判断输入符号串是为该文法的句型。

三、核心思想

该分析程序有15部分组成：

（1）首先定义各种需要用到的常量和变量；

（2）判断一个字符是否在指定字符串中；

（3）读入一个文法；

（4）将单个符号或符号串并入另一符号串；

（5）求所有能直接推出&的符号；

（6）求某一符号能否推出‘&’；

（7）判断读入的文法是否正确；

（8）求单个符号的FIRST；

（9）求各产生式右部的FIRST；

（10）求各产生式左部的FOLLOW；

（11）判断读入文法是否为一个LL

（1）文法；

（12）构造分析表M；

（13）句型判别算法；

（14）一个用户调用函数；

（15）主函数；

下面是其中几部分程序段的算法思想：

1、求能推出空的非终结符集

Ⅰ、实例中求直接推出空的empty集的算法描述如下：

voidemp（charc）{参数c为空符号

chartemp[10];定义临时数组

inti;

for（i=0;i<=count-1;i++）从文法的第一个产生式开始查找

{

if产生式右部第一个符号是空符号并且右部长度为1,

then将该条产生式左部符号保存在临时数组temp中

将临时数组中的元素合并到记录可推出&符号的数组empty中。

}

Ⅱ、求某一符号能否推出'&'

int_emp（charc）

{//若能推出&，返回1；否则，返回0

inti,j,k,result=1,mark=0;

chartemp[20];

temp[0]=c;

temp[1]='\0';

存放到一个临时数组empt里,标识此字符已查找其是否可推出空字

如果c在可直接推出空字的empty[]中,返回1

for（i=0;;i++）

{

if（i==count）

return（0）;

找一个左部为c的产生式

j=strlen（right[i]）;//j为c所在产生式右部的长度

if右部长度为1且右部第一个字符在empty[]中.then返回1（A->B,B可推出空）

if右部长度为1但第一个字符为终结符,then返回0（A->a,a为终结符）

else

{

for（k=0;k<=j-1;k++）

{

查找临时数组empt[].并标记mark-=1（A->AB）

if找到的字符与当前字符相同（A->AB）

结束本次循环

else（mark等于0）

查找右部符号是否可推出空字,把返回值赋给result

把当前符号加入到临时数组empt[]里.

}

if当前字符不能推出空字且还没搜索完全部的产生式

then跳出本次循环继续搜索下一条产生式

elseif//当前字符可推出空字,返回1

}

}

}

2、计算每个符号的first集：

实例中求单个符号的FIRST集的算法描述如下：

voidfirst2（inti）{

参数i为符号在所有输入符号中的序号

c等于指示器i所指向的符号

在保存终结符元素的termin[]数组查找c

ifc为终结符（c∈VT），then

FIRST（c）={c}

在保存终结符元素的non_ter[]数组查找c

ifc是非终结符（c∈VN）

在所有产生式中查找c所在的产生式

if产生式右部第一个字符为终结符或空（即c→a（a∈VT）或c→&）then

把a或&加进FIRST（c）

if产生式右部第一个字符为非终结符then

if产生式右部的第一个符号等于当前字符then

跳到下一条产生式进行查找

求当前非终结符在所有字符集中的位置

if当前非终结符还没求其FIRST集then

查找它的FIRST集并标识此符号已求其FIRST集

求得结果并入到c的FIRST集.

if当前产生式右部符号可推出空字且当前字符不是右部的最后一个字符then

获取右部符号下一个字符在所有字符集中的位置

if此字符的FIRST集还未查找then

找其FIRST集,并标其查找状态为1

把求得的FIRST集并入到c的FIRST集.

if当前右部符号串可推出空且是右部符号串的最后一个字符（即产生式为c→Y1Y2…Yk,若对一切1<=i<=k，均有&∈FIRST（Yi），则将&∈符号加进FIRST（c））then

把空字加入到当前字符c的FIRST集.

else

不能推出空字则结束循环

标识当前字符c已查找其FIRST集.}

3.计算FOLLOW集

FOLLOW集的构造可用如下方法来求：

对于文法中的符号XVN，其FOLLOW（A）集合可反复应用下列规则计算，直到FOLLOW（A）集合不再增大为止。

（1）对于文法开始符号S，因为SS，故#FOLLOW（S）；

（2）若A→B，其中BVN，（VTVN）*、（VTVN）+，则

FIRST（）-{}FOLLOW（B）；

（3）若A→B或A→B（

），则

FOLLOW（A）FOLLOW（B）。

FOLLOW集的算法描述如下：

voidFOLLOW（inti）

X为待求的非终结符

把当前字符放到一临时数组foll[]中,标识求已求其FOLLOW集.避免循环递归

ifX为开始符号then#∈FOLLOW（X）

对全部的产生式找一个右部含有当前字符X的产生式

注：

比如求FOLLOW（B）则找A→αX或A→X（

ε）的产生式

ifX在产生式右部的最后（形如产生式A→X）then

查找非终结符A是否已经求过其FOLLOW集.避免循环递归

if非终结符A已求过其FOLLOW集then

FOLLOW（A）∈FOLLOW（X）

继续查下一条产生式是否含有X

else

求A之FOLLOW集，并标识为A已求其FOLLOW集

elseifX不在产生式右部的最后（形如A→B）then

if右部X后面的符号串能推出空字then

查找是否已经求过其FOLLOW集.避免循环递归

if已求过的FOLLOW集then

FOLLOW（A）∈FOLLOW（B）

结束本次循环

elseif不能推出空字then

求FIRST（）

把FIRST（）中所有非空元素加入到FOLLOW（B）中

标识当前要求的非终结符X的FOLLOW集已求过

4.计算SELECT集

SELECT集的构造算法如下：

对所有的规则产生式A→x：

（1）若x不能推出空字，则SELECT（A→x）=FIRST（x）；

（2）若x可推出空字，则SELECT（A→x）=FIRST（x）–{}FOLLOW（A）。

算法描述如下：

for（i=0;i<=产生式总数-1;i++）

先把当前产生式右部的FIRST集（一切非空元素,不包括ε）放入到当前产生式的SELECT（i）;

if产生式右部符号串可推出空字then

把i指向的当前产生式左部的非终结符号的FOLLOW集并入到SELECT（i）中

5.判断是否LL

（1）文法

要判断是否为LL

（1）文法，需要输入的文法G有如下要求：

具有相同左部的规则的SELECT集两两不相交，即：

SELECT（A→）∩SELECT（A→）=

如果输入的文法都符合以上的要求，则该文法可以用LL

（1）方法分析。

算法描述如下：

把第一条产生式的SELECT（0）集放到一个临时数组temp[]中

for（i=1;i<=产生式总数-1;i++）

求temp的长度length

ifi指向的当前产生式的左部等于上一条产生式的左部then

把SELECT（i）并入到temp数组中

Iftemp的长度小于length加上SELECT（i）的长度

返回0

else

把temp清空

把SELECT（i）存放到temp中

结果返回1；

四、算法

#include

#include

#include

/*******************************************/

intcount=0;//产生式的个数

intnumber;//所有终结符和非终结符的总数

charstart;//开始符号

chartermin[50];//终结符号

charnon_ter[50];//非终结符号

charv[50];//所有符号

charleft[50];//左部

charright[50][50];//右部

charfirst[50][50],follow[50][50];//各产生式右部的FIRST和左部的FOLLOW集合

charfirst1[50][50];//所有单个符号的FIRST集合

charselect[50][50];//各个产生式的SELECT集合

charfirstflag[50],followflag[50];//记录各符号的FIRST和FOLLOW是否已求过

charempty[20];//记录可推出&的符号

charnonempty[20];//记录不可推出&的符号

charempt[20];//求_emp（）时使用

charTEMP[50];//求FOLLOW时存放某一符号串的FIRST集合

intvalidity=1;//表示输入文法是否有效

intll=1;//表示输入文法是否为LL

（1）文法

intM[20][20];//分析表

charchoose;//用户输入时使用

charfoll[20];//求FOLLOW集合时使用

/*******************************************

判断一个字符c是否在指定字符串p中

********************************************/

intin（charc,char*p）

{

inti;

if（strlen（p）==0）

return（0）;

for（i=0;;i++）

{

if（p[i]==c）

return

（1）;//若在，返回1

if（i==（int）strlen（p））

return（0）;//若不在，返回0

}

}

/*******************************************

将单个符号或符号串并入另一符号串

********************************************/

voidmerge（char*d,char*s,inttype）

{//是目标符号串，s是源串，type＝1，源串中的'&'一并并入目串；

//type＝2，源串中的'&'不并入目串

inti,j;

for（i=0;i<=（int）strlen（s）-1;i++）

{

if（type==2&&s[i]=='&'）;

else

{

for（j=0;;j++）

{

if（j<（int）strlen（d）&&s[i]==d[j]）

break;//若已存在，则退出，继续看下一个源串字符

if（j==（int）strlen（d））//若不存在，则并入

{

d[j]=s[i];

d[j+1]='\0';

break;

}

}

}

}

}

/*******************************************

读入一个文法

********************************************/

chargrammer（char*t,char*n,char*left,charright[50][50]）

{

charvn[50],vt[50];

chars;

charp[50][50];

inti,j;

printf（"请输入文法的非终结符号串：

"）;

scanf（"%s",vn）;

getchar（）;

i=strlen（vn）;

memcpy（n,vn,i）;

n[i]='\0';

printf（"请输入文法的终结符号串：

"）;

scanf（"%s",vt）;

getchar（）;

i=strlen（vt）;

memcpy（t,vt,i）;

t[i]='\0';

printf（"请输入文法的开始符号：

"）;

scanf（"%c",&s）;

getchar（）;

printf（"请输入文法产生式的条数：

"）;

scanf（"%d",&i）;

getchar（）;

count=i;

for（j=1;j<=i;j++）

{

printf（"请输入文法的第%d条（共%d条）产生式：

",j,i）;

scanf（"%s",p[j-1]）;

getchar（）;

}

for（j=0;j<=i-1;j++）

{

if（p[j][1]!

='-'||p[j][2]!

='>'）//检测输入错误

{

printf（"\n输入错误!

"）;

validity=0;

return（'\0'）;

}

}

return（s）;

}

/*******************************************

判断读入的文法是否正确

********************************************/

intjudge（）

{

inti,j;

for（i=0;i<=count-1;i++）

{

if（in（left[i],non_ter）==0）

{//若左部不在非终结符中，报错

printf（"\n文法左部出错!

"）;

validity=0;

return（0）;

}

for（j=0;j<=（int）strlen（right[i]）-1;j++）

{

if（in（right[i][j],non_ter）==0&&in（right[i][j],termin）==0&&right[i][j]!

='&'）

{//若右部某一符号不在非终结符、终结符中且不为'&'，报错

printf（"\n文法右部出错!

"）;

validity=0;

return（0）;

}

}

}

return

（1）;

}

/*******************************************

求所有能直接推出&的符号

********************************************/

voidemp（charc）

{

chartemp[10];

inti;

for（i=0;i<=count-1;i++）

{

if（right[i][0]==c&&strlen（right[i]）==1）

{

temp[0]=left[i];

temp[1]='\0';

merge（empty,temp,1）;//求所有能直接推出'&"的符号,结果保存到empty[]中

emp（left[i]）;

}

}

}

/*******************************************

求某一符号能否推出'&'

********************************************/

int_emp（charc）

{//若能推出&，返回1；否则，返回0

inti,j,k,result=1,mark=0;

chartemp[20];

temp[0]=c;

temp[1]='\0';

merge（empt,temp,1）;//存放到一个临时数组empt里,标识此字符已查找其是否可推出空字

if（in（c,empty）==1）//如果c在可直接推出空字的empty[]中,返回1

return

（1）;

for（i=0;;i++）

{

if（i==count）

return（0）;

if（left[i]==c）//找一个左部为c的产生式

{

j=strlen（right[i]）;//j为c所在产生式右部的长度

if（j==1&&in（right[i][0],empty）==1）//右部长度为1且右部第一个字符在empty[]中.返回1（A->B,B可推出空）

return

（1）;

elseif（j==1&&in（right[i][0],termin）==1）//右部长度为1但第一个字符为终结符,返回0（A->a,a为终结符）

continue;

else

{

for（k=0;k<=j-1;k++）

{

if（in（right[i][k],empt）==1）//查找临时数组empt[].（A->AB）

mark=1;

}

if（mark==1）//找到的字符与当前字符相同（A->AB）

continue;//结束本次循环

else//（mark等于0）

{

for（k=0;k<=j-1;k++）

{

result*=_emp（right[i][k]）;//递归调用，查找右部符号是否可推出空字,把返回值赋给result

temp[0]=right[i][k];

temp[1]='\0';

merge（empt,temp,1）;//把当前符号加入到临时数组empt[]里，标记已查找

}

}

}

if（result==0&&i

continue;

elseif（result==1&&i

return

（1）;

}

}

}

/*******************************************

求单个符号的FIRST

********************************************/

voidfirst2（inti）

{//i为符号在所有输入符号中的序号

charc,temp[20];

intj,k,m;

charch='&';

c=v[i];

emp（ch）;//求所有能直接推出空字的符号,结果保存到empty[]中

if（in（c,termin）==1）//若为终结符--c∈VT，则FIRST（c）={c}

{

first1[i][0]=c;

first1[i][1]='\0';

}

elseif（in（c,non_ter）==1）//若为非终结符

{

for（j=0;j<=count-1;j++）//j为所有产生式中的序列

{

if（left[j]==c）//找一个左部为c的产生式

{

if（in（right[j][0],termin）==1||right[j][0]=='&'）

{//若产生式右部第一个字符为终结符或空.---产生式X→a（a∈VT）或X→&,则把a或&加进FIRST（X）

temp[0]=right[j][0];

temp[1]='\0';

merge（first1[i],temp,1）;

}

//------X→Y1Y2…Yk的产生式，若Y1∈VN，则把FIRST（Y1）中的一切非空符号加进FIRST（X）

elseif（in（right[j][0],non_ter）==1）//产生式右部第一个字符为非终结符

{

if（right[j][0]==c）//产生式右部的第一个符号等于当前字符,则跳到下一条产生式进行查找

continue;

for（k=0;;k++）

{

if（v[k]==right[j][0]）//求右部第一个字符在所有字符集中的位置k

break;

}

if（firstflag[k]=='0'）

{

first2（k）;//求其FIRST集

firstflag[k]='1';//标识其为查找状态

}

merge（first1[i],first1[k],2）;//求得结果并入到X的FIRST集.

for（k=0;k<（int）strlen（right[j]）;k++）

{

empt[0]='\0';//存放到一个临时数组里,标识此字符已查找其是否可推出空字

if（_emp（right[j][k]）==1&&k<（int）strlen（right[j]）-1）

{//当前产生式右部符号可推出空字,且当前字符不是右部的最后一个字符

for（m=0;;m++）

{

if（v[m]==right[j][k+1]）//获取右部符号下一个字符在所有字符集中的位置

break;