语法分析器实验报告

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

一、实验内容

语法分析程序用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集的算法描述如下：

void emp(char c){ 参数c为空符号

char temp[10];定义临时数组

int i;

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

{

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

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

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

}

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

int _emp(char c)

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

int i,j,k,result=1,mark=0;

char temp[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 跳出本次循环继续搜索下一条产生式

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

}

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

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

void first2 (int i) {

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

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

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

if c为终结符(c∈V_T)，then

FIRST(c)={c}

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

if c是非终结符(c∈V_N)

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

if 产生式右部第一个字符为终结符或空(即c→a (a∈V_T)或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→Y₁Y₂…Y_k,若对一切1<=i<=k，均有&∈FIRST(Y_i)，则将&∈符号加进FIRST(c) ) then

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

else

不能推出空字则结束循环

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

3. 计算FOLLOW集

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

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

(1)对于文法开始符号S，因为SS，故#ÎFOLLOW(S)；

(2)若A→a Bb，其中BÎV_N，aÎ(V_TUV_N)^*、bÎ(V_TUV_N)⁺，则

FIRST(b)-{e}ÎFOLLOW(B)；

(3)若A→a B或A→a Bb (b e)，则

FOLLOW(A) ÎFOLLOW(B)。

FOLLOW集的算法描述如下：

void FOLLOW(int i)

X为待求的非终结符

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

if X为开始符号 then #∈FOLLOW(X)

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

注：比如求FOLLOW(B)则找A→αX或A→aXb(bε)的产生式

if X在产生式右部的最后(形如产生式A→aX) then

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

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

FOLLOW(A)∈FOLLOW(X)

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

else

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

else if X不在产生式右部的最后(形如A→aBb) then

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

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

if 已求过b的FOLLOW集 then

FOLLOW(A)∈FOLLOW(B)

结束本次循环

else if b不能推出空字 then

求FIRST(b)

把FIRST(b)中所有非空元素加入到FOLLOW(B)中

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

4.计算SELECT集

SELECT集的构造算法如下：

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

(1)若x不能推出空字e，则SELECT(A→x) = FIRST(x)；

(2)若x可推出空字e，则SELECT(A→x)=FIRST(x)–{e} U FOLLOW(A)。

算法描述如下：

for(i=0;i<=产生式总数-1;i++)

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

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

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

5.判断是否LL(1)文法

要判断是否为LL(1)文法，需要输入的文法G有如下要求：

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

SELECT(A→a)∩ SELECT(A→b)= Æ

如果输入的文法都符合以上的要求，则该文法可以用LL(1)方法分析。

算法描述如下：

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

for(i=1;i<=产生式总数-1;i++)

求temp的长度length

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

把SELECT(i)并入到temp数组中

If temp的长度小于length加上SELECT (i)的长度

返回0

else

把temp清空

把SELECT (i)存放到temp中

结果返回1；

四、算法

#include<stdlib.h>

#include<stdio.h>

#include<string.h>

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

int count=0; //产生式的个数

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

char start; //开始符号

char termin[50]; //终结符号

char non_ter[50]; //非终结符号

char v[50]; //所有符号

char left[50]; //左部

char right[50][50]; //右部

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

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

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

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

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

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

char empt[20]; //求_emp()时使用

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

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

int ll=1; //表示输入文法是否为LL(1)文法

int M[20][20]; //分析表

char choose; //用户输入时使用

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

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

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

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

int in(char c,char *p)

{

int i;

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

}

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

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

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

void merge(char *d,char *s,int type)

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

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

int i,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;

}

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

读入一个文法

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

char grammer(char *t,char *n,char *left,char right[50][50])

{

char vn[50],vt[50];

char s;

char p[50][50];

int i,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);

}

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

判断读入的文法是否正确

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

int judge()

{

int i,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);

}

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

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

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

void emp(char c)

{

char temp[10];

int i;

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(char c)

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

int i,j,k,result=1,mark=0;

char temp[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);

else if(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<count)//如果当前字符不能推出空字且还没搜索完全部的产生式,则跳出本次循环继续搜索下一条产生式

continue;

else if(result==1&&i<count)//当前字符可推出空字,返回1

return(1);

}

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

求单个符号的FIRST

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

void first2(int i)

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

char c,temp[20];

int j,k,m;

char ch='&';

c=v[i];

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

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

{

first1[i][0]=c;

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

}

else if(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)

else if(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;

}

if(firstflag[m]=='0')//如果此字符的FIRST集还未查找,则找其FIRST集,并标其查找状态为1

{

first2(m);

firstflag[m]='1';

}

merge(first1[i],first1[m],2);//把求得结果并入到X的FIRST集.

}

//----产生式为X→Y1Y2…Yk,若对一切1<=i<=k，均有&∈FIRST(Yi)，则将&∈符号加进FIRST(X)

else if(_emp(right[j][k])==1&&k==(int)strlen(right[j])-1)

{//当前右部符号串可推出空且是右部符号串的最后一个字符

temp[0]='&';

temp[1]='\0';

merge(first1[i],temp,1);//把空字加入到当前字符X的FIRST集.

}

else

break;//不能推出空字则结束循环

}

firstflag[i]='1';//标识当前字符c已查找其FIRST集

}

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

求各产生式右部的FIRST

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

void FIRST(int i,char *p)

{ //指针p指向右部符号串

int length;//标识右部符号串的长度

int j,k,m;

char temp[20];

length=strlen(p);

if(length==1) //如果右部为单个符号

{

if(p[0]=='&')//右部符号串字符为"&"空字

{

if(i>=0)//i不为-1时是产生式的序号

{

first[i][0]='&'; //把"&"加入到当前符号串的FIRST集

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

}

else//i为-1时,表示求FOLLOW时用到的产生式右部的FIRST集,保存在TEMP[]中

{

TEMP[0]='&';

TEMP[1]='\0';

}

else//右部符号串字符不为"&"空字

{

for(j=0;;j++)

{

if(v[j]==p[0])//求右部符号的第一个字符p[0]在所有字符集中的位置j

break;

}

if(i>=0)

{

memcpy(first[i],first1[j],strlen(first1[j]));//把j所指向的单个符号的FIRST集拷贝到该右部符号串的FIRST集

first[i][strlen(first1[j])]='\0';

}

else

{

memcpy(TEMP,first1[j],strlen(first1[j]));

TEMP[strlen(first1[j])]='\0';

}

else //如果右部为符号串

{

for(j=0;;j++)

{

if(v[j]==p[0])//求右部符号的第一个字符p[0]在所有字符集中的位置j

break;

}

if(i>=0)

merge(first[i],first1[j],2);

else

merge(TEMP,first1[j],2);

for(k=0;k<=length-1;k++)

{

empt[0]='\0';

if(_emp(p[k])==1&&k<length-1)

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

for(m=0;;m++)

{

if(v[m]==right[i][k+1])

break;

}

if(i>=0)

merge(first[i],first1[m],2);

else

merge(TEMP,first1[m],2);

}

else if(_emp(p[k])==1&&k==length-1)

{//当前右部符号串可推出空且是右部符号串的最后一个字符

temp[0]='&';

temp[1]='\0';

if(i>=0)

merge(first[i],temp,1);

else

merge(TEMP,temp,1);

}

else if(_emp(p[k])==0)

break;

}

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

求各产生式左部的FOLLOW

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

void FOLLOW(int i)

{ //参数i为该符号在非终结符中的位置

int j,k,m,n,result=1;

char c,temp[20];

c=non_ter[i]; //c为待求的非终结符

temp[0]=c;

temp[1]='\0';

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

if(c==start)

{ //若为开始符号-----开始符号S，则#∈FOLLOW(S)

temp[0]='#';

temp[1]='\0';

merge(follow[i],temp,1);

}

for(j=0;j<=count-1;j++)

{

if(in(c,right[j])==1) //找一个右部含有当前字符c的产生式

{//比如求FOLLOW(B)则找A→αB或A→αBβ(β=>*&)的产生式

for(k=0;;k++)

{

if(right[j][k]==c)

break; //k为c在该产生式右部的序号,如B在产生式A→αB中的位置

}

for(m=0;;m++)

{

if(v[m]==left[j])

break; //m为产生式左部非终结符在所有符号中的序号

}

//如果c在产生式右部的最后,形如产生式A→αB,则FOLLOW(A)∈FOLLOW(B)

if(k==(int)strlen(right[j])-1)

{

if(in(v[m],foll)==1)//查找该非终结符是否已经求过其FOLLOW集.避免循环递归

{//是则FOLLOW(A)∈FOLLOW(B)

merge(follow[i],follow[m],1);//把c所在产生式的左部非终结符的FOLLOW集加入到FOLLOW(c)中

continue;//结束本次循环,进入j++循环

}

if(followflag[m]=='0')

{//如果该非终结符的FOLLOW未求过

FOLLOW(m);//求之FOLLOW集

followflag[m]='1';//标识为1

}

merge(follow[i],follow[m],1);//FOLLOW(A)∈FOLLOW(B)

}

else

{ //如果c不在产生式右部的最后,形如A→αBβ

for(n=k+1;n<=(int)strlen(right[j])-1;n++)

{

empt[0]='\0';//把empt[]置空,因为求此字符是否可推出空字_emp(c)时用到

result*=_emp(right[j][n]);

}

if(result==1)

{ //如果右部c后面的符号串能推出空,A→αBβ(β=>*&)则FOLLOW(A)∈FOLLOW(B)

if(in(v[m],foll)==1)

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

merge(follow[i],follow[m],1);//FOLLOW(A)∈FOLLOW(B)

continue;

}

if(followflag[m]=='0')

{

FOLLOW(m);

followflag[m]='1';

}

merge(follow[i],follow[m],1);

}

//若A→αBβ，其中B∈VN，α∈(VT U VN)*、β∈(VT U VN)+，则FIRST(β)-{ε}∈FOLLOW(B)；

for(n=k+1;n<=(int)strlen(right[j])-1;n++)

{

temp[n-k-1]=right[j][n];

}

temp[strlen(right[j])-k-1]='\0';

FIRST(-1,temp);//求FIRST(β)

merge(follow[i],TEMP,2);//把FIRST(β)中所有非空元素加入到FOLLOW(B)中

}

followflag[i]='1';//标识当前要求的非终结符的FOLLOW集已求过

}

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

判断读入文法是否为一个LL(1)文法

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

int LL1()

{

int i,j,length,result=1;

char temp[50];

for(j=0;j<=49;j++)

{ //初始化

first[j][0]='\0';

follow[j][0]='\0';

first1[j][0]='\0';

select[j][0]='\0';

TEMP[j]='\0';

temp[j]='\0';

firstflag[j]='0';//用来记录该字符的FIRST集是否已求过.1表示已求,0表示未求

followflag[j]='0';//用来记录该字符的FOLLOW集是否已求过.1表示已求,0表示未求

}

for(j=0;j<=(int)strlen(v)-1;j++)

{

first2(j); //求单个符号的FIRST集合,结果保存在first1[]里

}

printf("\n各非终结符推出的first集:\n");

for(j=0;j<=(int)strlen(v)-1;j++)

{

printf("%c:%s ",v[j],first1[j]);

}

printf("\n能导空的非终结符集合:%s",empty);

printf("\n_emp:");

for(j=0;j<=(int)strlen(v)-1;j++)

printf("%d ",_emp(v[j]));

for(i=0;i<=count-1;i++)

FIRST(i,right[i]); //求FIRST

for(j=0;j<=(int)strlen(non_ter)-1;j++)

{ //求FOLLOW

if(foll[j]==0)

{

foll[0]='\0';

FOLLOW(j);

}

printf("\nfirst集:");

for(i=0;i<=count-1;i++)

printf("%s ",first[i]);

printf("\nfollow集合:");

for(i=0;i<=(int)strlen(non_ter)-1;i++)

printf("%s ",follow[i]);

for(i=0;i<=count-1;i++)

{ //求每一产生式的SELECT集合

memcpy(select[i],first[i],strlen(first[i]));//first[]存放的是各产生式右部的FIRST集

select[i][strlen(first[i])]='\0';

for(j=0;j<=(int)strlen(right[i])-1;j++)

result*=_emp(right[i][j]);

if(strlen(right[i])==1&&right[i][0]=='&')//形如产生式A->&

result=1;

if(result==1)

{

for(j=0;;j++)

if(v[j]==left[i])//j为左部符号在所有字符集中的位置

break;

merge(select[i],follow[j],1);

}

printf("\nselect集合顺序是:");

for(i=0;i<=count-1;i++)

printf("%s ",select[i]);

memcpy(temp,select[0],strlen(select[0]));

temp[strlen(select[0])]='\0';

for(i=1;i<=count-1;i++)

{ /*判断输入文法是否为LL(1)文法*/

length=strlen(temp);

if(left[i]==left[i-1])

{

merge(temp,select[i],1);

if(strlen(temp)<length+strlen(select[i]))//比较两个产生式的SELECT长度

return(0);

}

else

{

temp[0]='\0';

memcpy(temp,select[i],strlen(select[i]));

temp[strlen(select[i])]='\0';

}

return(1);

}

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

构造分析表M

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

void MM()

{

int i,j,k,m;

for(i=0;i<=19;i++)

{

for(j=0;j<=19;j++)//初始化分析表,全部置为空(-1)

{

M[i][j]=-1;

}

i=strlen(termin);

termin[i]='#'; //将#加入终结符数组

termin[i+1]='\0';

for(i=0;i<=count-1;i++)//查看每个产生式的SELECT集

{

for(m=0;;m++)

{

if(non_ter[m]==left[i])

break; //m为产生式左部非终结符的序号

}

for(j=0;j<=(int)strlen(select[i])-1;j++)//对每个SELECT集中的所有元素进行操作

{

if(in(select[i][j],termin)==1)

{

for(k=0;;k++)

{

if(termin[k]==select[i][j])

break; //k为产生式右部终结符的序号

}

M[m][k]=i;

}

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

判断符号串是否是该文法的句型

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

void syntax()

{

int i,j,k,m,n,p,q;

char ch;

char S[50],str[50];

printf("请输入该文法的句型：");

scanf("%s",str);

getchar();

i=strlen(str);

str[i]='#';

str[i+1]='\0';

S[0]='#';

S[1]=start;

S[2]='\0';

j=0;

ch=str[j];

while(1)

{

if(in(S[strlen(S)-1],termin)==1)

{

if(S[strlen(S)-1]!=ch)

{

printf("该符号串不是文法的句型！");

return;

}

else if(S[strlen(S)-1]=='#')

{

printf("该符号串是文法的句型.");

return;

}

else

{

S[strlen(S)-1]='\0';

j++;

ch=str[j];

}

else

{

for(i=0;;i++)

if(non_ter[i]==S[strlen(S)-1])

break;

for(k=0;;k++)

{

if(termin[k]==ch)

break;

if(k==(int)strlen(termin))

{

printf("词法错误！");

return;

}

if(M[i][k]==-1)

{

printf("语法错误！");

return;

}

else

{

m=M[i][k];

if(right[m][0]=='@')

S[strlen(S)-1]='\0';

else

{

p=strlen(S)-1;

q=p;

for(n=strlen(right[m])-1;n>=0;n--)

S[p++]=right[m][n];

S[q+strlen(right[m])]='\0';

}

printf("S:%s str:",S);

for(p=j;p<=(int)strlen(str)-1;p++)

printf("%c",str[p]);

printf(" \n");

}

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

一个用户调用函数

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

void menu()

{

syntax();

printf("\n是否继续？(y or n):");

scanf("%c",&choose);

getchar();

while(choose=='y')

{

menu();

}

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

主函数

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

void main()

{

int i,j;

start=grammer(termin,non_ter,left,right); //读入一个文法

printf("count=%d",count);

printf("\n开始符号为:%c",start);

strcpy(v,non_ter);

strcat(v,termin);

printf("\n所有符号集为:%s",v);

printf("\n非终结符集合:{%s",non_ter);

printf("}");

printf("\n终结符集合:{%s",termin);

printf("}");

printf("\n文法所有右边表达式依次是:");

for(i=0;i<=count-1;i++)

{

printf("%s ",right[i]);

}

printf("\n文法所有左边开始符依次是:");

for(i=0;i<=count-1;i++)

{

printf("%c ",left[i]);

}

if(validity==1)

validity=judge();

printf("\nvalidity=%d",validity);

if(validity==1)

{

ll=LL1();

printf("\nll=%d",ll);

if(ll==0)

printf("\n该文法不是一个LL1文法！");

else

{

printf("\n该文法是一个LL(1)文法！");

MM();

printf("\n");

for(i=0;i<=19;i++)

for(j=0;j<=19;j++)

if(M[i][j]>=0)

printf("M[%d][%d]=%d ",i,j,M[i][j]);

menu();

}

由于算法仍有很多错误，最终结果没能实现，这点很失望！

五、实验心得

通过本次实验，我收获了很多东西。首先对编译原理这门课有了进一步的深刻理解，同时对LL（1）文法分析的原理和过程有了进一步的巩固，也锻炼了我编程的能力，巩固了平时所学的知识，真正做到了学以致用。

在做实验的过程中，发现自己在编写程序过程中，总是会忽略各种细节，从而导致经常修改一些很小的低级错误才能使程序正常运行，不仅浪费时间，还影响对其他地方的修改，并且在很多步骤处理上，方法不正确。使结果不能符合要求，深刻体会到了自己在编程方面与别人的差距，在今后的学习中，我会注意改正自己在这方面的缺点，促使自己的编程水平不断进步。

编译原理是一门专业学科，对于现阶段的我来说，只能掌握它的一些基本原理和概念，对于一些更深层的知识还是有很多难以理解的地方。但在这次实验过程中，锻炼了自己的思考能力，也锻炼了自己的动手编程能力，对于将知识的转化有了很大的帮助。

相关推荐

语法分析器实验报告

专栏推荐