语法分析器实验报告
语法分析器得设计 实验报告 一、实验内容 语法分析程序用 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)分析方法。
语法分析程序得流程图如图 54 所示。
该程序可分为如下几步: (1)读入文法
(2)判断正误
(3)若无误,判断就是否为 LL(1)文法
(4)若就是,构造分析表; (5)由句型判别算法判断输入符号串就是为该文法得句型。
三、核心思想 该分析程序有 15 部分组成: (1)首先定义各种需要用到得常量与变量; (2)判断一个字符就是否在指定字符串中; 开始 读入文法 有效？
判断句型 报错 结束 语法分析程序流程图 就 是 LL(1) 文
(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<=count1;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<=j1;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 1 Y 2 …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→B,其中 BV N ,(V T V N ) * 、(V T V N ) + ,则 FIRST(){}FOLLOW(B); (3)若 A→B 或 A→B (),则 FOLLOW(A) FOLLOW(B)。
FOLLOW 集得算法描述如下:
void FOLLOW(int i)
X 为待求得非终结符 把当前字符放到一临时数组 foll[]中,标识求已求其 FOLLOW 集、避免循环递归 if
X 为开始符号 then
#∈FOLLOW(X)
对全部得产生式找一个右部含有当前字符 X 得产生式 注:比如求 FOLLOW(B)则找 A→αX 或 A→X(ε)得产生式 if
X 在产生式右部得最后(形如产生式 A→X)
then 查找非终结符 A 就是否已经求过其 FOLLOW 集、避免循环递归 if
非终结符 A 已求过其 FOLLOW 集
then FOLLOW(A)∈FOLLOW(X) 继续查下一条产生式就是否含有 X else 求 A 之 FOLLOW 集,并标识为 A 已求其 FOLLOW 集 else
if
X 不在产生式右部得最后(形如 A→B)
then if 右部 X 后面得符号串能推出空字 then 查找就是否已经求过其 FOLLOW 集、避免循环递归 if
已求过得 FOLLOW 集 then
FOLLOW(A)∈FOLLOW(B) 结束本次循环 else
if 不能推出空字 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
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[j1]);
getchar;
}
for(j=0;j<=i1;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<=count1;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<=count1;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<=j1;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<=j1;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<=count1;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<=length1;k++)
{
empt[0]="\0";
if(_emp(p[k])==1&&k<length1)
{ //当前产生式右部符号可推出空字,且当前字符不就是右部得最后一个字符
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==length1)
{//当前右部符号串可推出空且就是右部符号串得最后一个字符
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<=count1;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[nk1]=right[j][n];
}
temp[strlen(right[j])k1]="\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<=count1;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<=count1;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<=count1;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<=count1;i++)
printf("%s ",select[i]);
memcpy(temp,select[0],strlen(select[0]));
temp[strlen(select[0])]="\0";
for(i=1;i<=count1;i++)
{
/*判断输入文法就是否为 LL(1)文法*/
length=strlen(temp);
if(left[i]==left[i1])
{
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<=count1;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<=count1;i++)
{
printf("%s
",right[i]);
}
printf("\n 文法所有左边开始符依次就是:");
for(i=0;i<=count1;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)文法分析得原理与过程有了进一步得巩固,也锻炼了我编程得能力,巩固了平时所学得知识,真正做到了学以致用。
在做实验得过程中,发现自己在编写程序过程中,总就是会忽略各种细节,从而导致经常修改一些很小得低级错误才能使程序正常运行,不仅浪费时间,还影响对其她地方得修改,并且在很多步骤处理上,方法不正确。使结果不能符合要求,深刻体会到了自己在编程方面与别人得差距,在今后得学习中,我会注意改正自己在这方面得缺点,促使自己得编程水平不断进步。
编译原理就是一门专业学科,对于现阶段得我来说,只能掌握它得一些基本原理与概念,对于一些更深层得知识还就是有很多难以理解得地方。但在这次实验过程中,锻炼了自己得思考能力,也锻炼了自己得动手编程能力,对于将知识得转化有了很大得帮助。
上一篇：非平衡电桥实验报告范文
下一篇：南通市“诚信守法企业”申报材料