编译原理语法分析器实验
语法分析器的设计
一、实验内容
语法分析程序用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→Y1Y2…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β，其中B∈V 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
#include
#include
/*******************************************/
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];
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 continue; else if(result==1&&i 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 { //当前产生式右部符号可推出空字,且当前字符不是右部的最后一个字符 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) } 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 编译原理课程设计Course Design of Compiling （课程代码3273526） 半期题目：词法和语法分析器 实验学期：大三第二学期 学生班级：2014级软件四班 学生学号：2014112218 学生姓名：何华均 任课教师：丁光耀 信息科学与技术学院 2017.6 课程设计1-C语言词法分析器 1.题目 C语言词法分析 2.内容 选一个能正常运行的c语言程序，以该程序出现的字符作为单词符号集，不用处理c语言的所有单词符号。 将解析到的单词符号对应的二元组输出到文件中保存 可以将扫描缓冲区与输入缓冲区合成一个缓冲区，一次性输入源程序后就可以进行预处理了 3.设计目的 掌握词法分析算法，设计、编制并调试一个词法分析程序，加深对词法分析原理的理解 4.设计环境（电脑语言环境） 语言环境:C语言 CPU:i7HQ6700 内存：8G 5.概要设计（单词符号表，状态转换图） 5.1词法分析器的结构 词法分析程序的功能： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 词法分析程序可以单独为一个程序；也可以作为整个编译程序的一个子程序，当需要一个单词时，就调用此法分析子程序返回一个单词. 为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序: 1) ch 存放最新读进的源程序字符 2) strToken 存放构成单词符号的字符串 3) Buffer 字符缓冲区 4）struct keyType 存放保留字的符号和种别 5.2待分析的简单词法 （1）保留字 break、case、char、const、int、do、while… （2）运算符和界符 = 、+、-、* 、/、%、，、；、（、）、？、# 5.3各种单词符号对应的种别码 编译原理语法分析实验报告 - 班级:XXX 学号:XXX 姓名:XXX 年月日 1、摘要: 用递归子程序法实现对pascal的子集程序设计语言的分析程序 2、实验目的: 通过完成语法分析程序，了解语法分析的过程和作用 3、任务概述 实验要求:对源程序的内码流进行分析，如为文法定义的句子输出”是”否则输出”否”,根据需要处理说明语句填写写相应的符号表供以后代码生成时使用 4、实验依据的原理 递归子程序法是一种自顶向下的语法分析方法，它要求文法是LL(1)文法。通过对文法中每个非终结符编写一个递归过程，每个过程的功能是识别由该非终结符推出的串，当某非终结符的产生式有多个候选式时，程序能够按LL(1)形式唯一地确定选择某个候选式进行推导，最终识别输入串是否与文法匹配。 递归子程序法的缺点是:对文法要求高，必须满足LL(1)文法，当然在某些语言中个别产生式的推导当不满足LL(1)而满足LL(2)时，也可以采用多向前扫描一个符号的办法;它的另一个缺点是由于递归调用多，所以速度慢占用空间多，尽管这样，它还是许多高级语言，例如PASCAL，C等编译系统常常采用的语法分析方法。 为适合递归子程序法，对实验一词法分析中的文法改写成无左递归和无左共因子的,,,如下: <程序>?<程序首部><分程序>。 <程序首部>?PROGRAM标识符; <分程序>?<常量说明部分><变量说明部分><过程说明部分> <复合语句> <常量说明部分>?CONST<常量定义><常量定义后缀>;|ε <常量定义>?标识符=无符号整数 <常量定义后缀>?，<常量定义><常量定义后缀> |ε <变量说明部分>?VAR<变量定义><变量定义后缀> |ε <变量定义>?标识符<标识符后缀>:<类型>; <标识符后缀>?，标识符<标识符后缀> |ε <变量定义后缀>?<变量定义><变量定义后缀> |ε <类型>?INTEGER | LONG <过程说明部分>?<过程首部><分程序>;<过程说明部分后缀>|ε <过程首部>?PROCEDURE标识符<参数部分>; <参数部分>?(标识符: <类型>)|ε <过程说明部分后缀>?<过程首部><分程序>;<过程说明部分后缀>|ε <语句>?<赋值或调用语句>|<条件语句>|<当型循环语句>|<读语句> |<写语句>|<复合语句>|ε <赋值或调用语句>?标识符<后缀> <后缀>?:=<表达式>|(<表达式>)|ε <条件语句>?IF<条件>THEN<语句> <当型循环语句>?WHILE<条件>DO <语句> <读语句>?READ(标识符<标识符后缀>) 华北水利水电学院编译原理实验报告 2010～2011学年第二学期xxxx 级计算机专业 班级：xxxxx 学号：xxxxx 姓名：xxx 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 二、实验要求 ⑴选择最有代表性的语法分析方法，如LL（1）分析法、算符优先法或LR分析法 ⑵选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑶实习时间为6小时。 三、实验内容 选题1：使用预测分析法（LL（1）分析法）实现语法分析： （1）根据给定文法，先求出first集合、follow集合和select集合，构造预测分析表（要求预测分析表输出到屏幕或者输出到文件）； （2）根据算法和预测分析表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程） （3）给定表达式文法为： G(E): S→TE E→+TE | ε T→FK K→*FK |ε F→(S)|i (4)分析的句子为： (i+i)*i和i+i)*i 四、程序源代码 #include "stdafx.h" #include "SyntaxAnalysis.h" #include "SyntaxAnalysisDlg.h" #ifdef _DEBUG #define new DEBUG_NEW #undef THIS_FILE static char THIS_FILE[] = __FILE__; #endif /////////////////////////////////////////// // CAboutDlg dialog used for App About 编译技术 班级网络0802 学号3080610052姓名叶晨舟 指导老师朱玉全2011年 7 月 4 日 一、目的 编译技术是理论与实践并重的课程，而其实验课要综合运用一、二年级所学的多门课程的内容，用来完成一个小型编译程序。从而巩固和加强对词法分析、语法分析、语义分析、代码生成和报错处理等理论的认识和理解；培养学生对完整系统的独立分析和设计的能力，进一步培养学生的独立编程能力。 二、任务及要求 基本要求： 1．词法分析器产生下述小语言的单词序列 这个小语言的所有的单词符号，以及它们的种别编码和内部值如下表： 单词符号种别编码助记符内码值 DIM IF DO STOP END 标识符 常数（整）= + * ** ， （ ）1 2 3 4 5 6 7 8 9 10 11 12 13 14 $DIM $IF $DO $STOP $END $ID $INT $ASSIGN $PLUS $STAR $POWER $COMMA $LPAR $RPAR - - - - - - 内部字符串 标准二进形式 - - - - - - 对于这个小语言，有几点重要的限制： 首先，所有的关键字（如IF﹑WHILE等）都是“保留字”。所谓的保留字的意思是，用户不得使用它们作为自己定义的标示符。例如，下面的写法是绝对禁止的： IF（5）=x 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。 再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 学号107 成绩 编译原理上机报告 名称：编写递归下降语法分析器 学院：信息与控制工程学院 专业：计算机科学与技术 班级：计算机1401班 姓名：叶达成 2016年10月31日 一、上机目的 通过设计、编制、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握常用的语法分析方法。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、基本原理和上机步骤 递归下降分析程序实现思想简单易懂。程序结构和语法产生式有直接的对应关系。因为每个过程表示一个非终结符号的处理，添加语义加工工作比较方便。 递归下降分析程序的实现思想是：识别程序由一组子程序组成。每个子程序对应于一个非终结符号。 每一个子程序的功能是：选择正确的右部，扫描完相应的字。在右部中有非终结符号时，调用该非终结符号对应的子程序来完成。 自上向下分析过程中，如果带回溯，则分析过程是穷举所有可能的推导，看是否能推导出待检查的符号串。分析速度慢。而无回溯的自上向下分析技术，当选择某非终结符的产生时，可根据输入串的当前符号以及各产生式右部首符号而进行，效率高，且不易出错。 无回溯的自上向下分析技术可用的先决条件是：无左递归和无回溯。 无左递归：既没有直接左递归，也没有间接左递归。 无回溯：对于任一非终结符号U的产生式右部x1|x2|…|x n，其对应的字的首终结符号两两不相交。 如果一个文法不含回路（形如P?+ P的推导），也不含以ε为右部的产生式，那么可以通过执行消除文法左递归的算法消除文法的一切左递归（改写后的文法可能含有以ε为右部的产生式）。 三、上机结果 测试数据： (1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 (3)输入一符号串如i+i*#,要求输出为“非法的符号串”。 程序清单： #include 实验二LL(1)分析法 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串 进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号 以及LL（1）分析表，对输入符号串自上而下的分析过程。 三、LL（1）分析法实验设计思想及算法 ◆模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 四、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： 五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3; 实验二语法分析器 一、实验目的 通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。 二、实验内容 ◆根据某一文法编制调试LL （1 ）分析程序，以便对任意输入的符号串 进行分析。 ◆构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分 析程序。 ◆分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号 以及LL（1）分析表，对输入符号串自上而下的分析过程。 三、LL（1）分析法实验设计思想及算法 ◆模块结构： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 四、实验要求 1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析：（1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下： 五、实验源程序 LL1.java import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.table.DefaultTableModel; import java.sql.*; import java.util.Vector; public class LL1 extends JFrame implements ActionListener { /** * */ private static final long serialVersionUID = 1L; JTextField tf1; JTextField tf2; JLabel l; JButton b0; JPanel p1,p2,p3; JTextArea t1,t2,t3; JButton b1,b2,b3; 编译原理程序设计实验报告 --- 表达式语法分析器的设计 班级：计算机1306班姓名：张涛学号：20133967实验目标：用LL（1）分析法设计实现表达式语法分析器实验内容： ⑴概要设计：通过对实验一的此法分析器的程序稍加改造， 使其能够输出正确的表达式的token序列。然后利用LL（1）分析法实现语法分析。 ⑵数据结构： int op=0; //当前判断进度 char ch; //当前字符 char nowword[10]=""; // 当前单词 char operate[4]={'+','-','*','/'}; // 运算符 char bound[2]={'（','）'}; // 界符 struct Token { int code; char ch[10]; }; //Token 定义 struct Token tokenlist[50]; //Token 数组 struct Token tokentemp; //临时Token 变量struct Stack //分析栈定义{ char *base; char *top; int stacksize; }; ⑶分析表及流程图 LL(1)分析表： Begi n ⑷关键函数： int lsLetter(char ch) //判断ch 是否为字母 int IsDigit(char ch) 〃判断ch是否为数字 int lskey(char *string) 〃判断是否为关键字 int lsbound(char ch) //判断是否为界符 int lsboundnum(char ch) //给出界符所在token 值 int init(STack *s) // 栈初始化 int pop(STack *s,char *ch) // 弹栈操作 int push(STack *s,char ch) 〃压栈操作 void LL1(); //分析函数 源程序代码：(加入注释) #includevstdio.h> #includevstring.h> #includevctype.h> #includevwindows.h> #include vstdlib.h> . 编译原理实验专业：13级网络工程 语法分析器1 一、实现方法描述 所给文法为G【E】； E->TE’ E’->+TE’|空 T->FT’ T’->*FT’|空 F->i|(E) 递归子程序法： 首先计算出五个非终结符的first集合follow集，然后根据五个产生式定义了五个函数。定义字符数组vocabulary来存储输入的句子，字符指针ch指向vocabulary。从非终结符E函数出发，如果首字符属于E的first集，则依次进入T函数和E’函数，开始递归调用。在每个函数中，都要判断指针所指字符是否属于该非终结符的first集，属于则根据产生式进入下一个函数进行调用，若first集中有空字符，还要判断是否属于该非终结符的follow集。以分号作为结束符。 二、实现代码 头文件shiyan3.h #include #include int a=0; cout<<"按1结束程序"< 实验二--语法分析(算符优先)-(2) 编译原理实验报告实验名称：语法分析器设计 专业：计算机科学与技术 姓名：田莉莉 学号：201117906 语法分析—算符优先分析程序 一．实验要求 ⑴ 选择最有代表性的语法分析方法，如算符优先法、递归子程序法或LR 分析法 ⑵ 选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 ⑶ 实习时间为6 学时。 二．实验内容及要求 （ 1）根据给定文法，先求出 FirstVt 和 LastVt 集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）； （ 2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程） （3）给定表达式文法为： G（E ' ）: E'T #E# E—E+T | T T—T*F |F F—（E）|i （4）分析的句子为 : （i+i）*i 和 i+i）*i 三．程序设计思想及实现步骤 程序的设计思想： 按照编译原理教材提供的算法，本程序的设计主要实现三个主要的过程： （1） 求解 FristVT 集和 LastVT 集：利用 CString 数组存放 VT 集，利用数组 下标对应非终结符关系； （2） 输出算符优先分析表：利用 MFC 中的 ClistCtrl 控件输出显示算符表， 比 利用二维数组对应其在内存中的关系。 （3） 利用算符优先分析表进行归约：根据教材所给算法，并对其进行实现在 屏幕上输 出归约过程。 实现步骤： 1、为程序各变量设计存储形式，具体设计如下所示： CString m_strTElem[T_LEN]; CString m_strNTElem[NT_LEN]; // 非终结符 CMapStringToPtr m_mapProdu; // 存放产生式 CMapStringToPtr m_mapProduEX; // 存放 扩展产生式 CString m_strFristVT[NT_LEN]; CString m_strLastVT[NT_LEN]; int m_nPriSheet[T_LEN+1][T_LEN+1]; // 终结符 //fristVT 集 //lastVT 集 词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 扫描子程序主要部分流程图 其他 词法分析程序的C语言程序源代码： // 词法分析函数: void scan() // 数据传递: 形参fp接收指向文本文件头的文件指针； // 全局变量buffer与line对应保存源文件字符及其行号，char_num保存字符总数。 void scan() { char ch; int flag,j=0,i=-1; while(!feof(fp1)) { ch=fgetc(fp1); flag=judge(ch); printf("%c",ch);//显示打开的文件 if(flag==1||flag==2||flag==3) {i++;buffer[i]=ch;line[i]=row;} else if(flag==4) {i++;buffer[i]='?';line[i]=row;} else if(flag==5) {i++;buffer[i]='~';row++;} else if(flag==7) continue; else cout<<"\n请注意，第"< 实验二语法分析 一、实验目的： 设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。 三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。 内容：利用JavaCC生成一个MiniC的语法分析器； 要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树本次实习仅完成以下语法范畴的语法分析： 1. 写出一个源程序中仅包含if…else, else语句的语法分析。要求能分析其自身 嵌套. 其他语句可简化处理 2. 写出一个源程序中仅包含for语句的语法分析。要求能分析其自身嵌套， 其他语句可简化处理 3. 写出一个源程序中仅包含while语句的语法分析。要求能分析其自身嵌套。 其他语句可简化处理 4. 写出一个源程序中包含上面的12或者13或者23或者123语句的语法分析。 要求能分析除其自身嵌套外，还包括相互嵌套。其他语句可简化处理 具体实施步骤如下： 1.把MiniC转换为文法如下 <程序〉→ main()〈语句块〉 〈语句块〉→{〈语句串〉} 编译原理实验报告 实验名称：编写语法分析分析器实验类型： 指导教师： 专业班级： 学号： 电子邮件： 实验地点： 实验成绩： 一、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。 1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，至少选一题。 2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验过程 编写算符优先分析器。要求： （a）根据算符优先分析算法，编写一个分析对象的语法分析程序。读者可根据自己的能力选择以下三项(由易到难)之一作为分析算法中的输入： Ⅰ：通过构造算符优先关系表，设计编制并调试一个算法优先分析程序Ⅱ：输入FIRSTVT，LASTVT集合，由程序自动生成该文法的算符优先关系矩阵。 Ⅲ：输入已知文法，由程序自动生成该文法的算符优先关系矩阵。（b）程序具有通用性，即所编制的语法分析程序能够使用于不同文法以及各种输入单词串，并能判断该文法是否为算符文法和算符优先文法。 （c）有运行实例。对于输入的一个文法和一个单词串，所编制的语法分析程序应能正确地判断，此单词串是否为该文法的句子，并要求输出分析过程。 三、实验结果 算符优先分析器： 测试数据：E->E+T|T T->T*F|F F->(E)|i 实验结果：(输入串为i+i*i+i) 四、讨论与分析 自下而上分析技术－算符优先分析法： 算符文法：一个上下无关文法G，如果没有且没有P→..QR...(P ,Q ,R属于非终结符)，则G是一个算符文法。 FIRSTVT集构造 1、若有产生式P →a...或P →Qa...，则a∈FIRSTVT(P)。 2、若有产生式P→...，则FIRSTVT(R)包含在FIRSTVT(P)中。由优先性低于的定义和firstVT集合的定义可以得出：若存在某个产生式：…P…，则对所有：b∈firstVT(P)都有：a≦b。 构造优先关系表： 1、如果每个非终结符的FIRSTVT和LASTVT集均已知,则可构造优先关系表。 2、若产生式右部有...aP...的形式，则对于每个b∈FIRSTVT(P)都有 编译原理实验二语法分析器L L(1)实现 编译原理程序设计实验报告 ——表达式语法分析器的设计班级：计算机1306班姓名：张涛学号：20133967 实验目标：用LL（1）分析法设计实现表达式语法分析器实验内容： ⑴概要设计：通过对实验一的此法分析器的程序稍加改造，使其能够输出正确的表达式的token序列。然后利用LL（1）分析法实现语法分析。 ⑵数据结构： int op=0; //当前判断进度 char ch; //当前字符 char nowword[10]=""; //当前单词 char operate[4]={'+','-','*','/'}; //运算符 char bound[2]={'(',')'}; //界符 struct Token { int code; char ch[10]; }; //Token定义 struct Token tokenlist[50]; //Token数组struct Token tokentemp; //临时Token变量struct Stack //分析栈定义 { char *base; char *top; int stacksize; }; ⑶分析表及流程图 逆序压栈 int IsLetter(char ch) //判断ch是否为字母 int IsDigit(char ch) //判断ch是否为数字 int Iskey(char *string) //判断是否为关键字 int Isbound(char ch) //判断是否为界符 int Isboundnum(char ch) //给出界符所在token值int init(STack *s) //栈初始化 int pop(STack *s,char *ch) //弹栈操作 int push(STack *s,char ch) //压栈操作 void LL1(); //分析函数 源程序代码：（加入注释） 编译原理程序设计实验报告 ——表达式语法分析器的设计班级：计算机1306班姓名：张涛学号：20133967 实验目标：用LL（1）分析法设计实现表达式语法分析器 实验内容： ⑴概要设计：通过对实验一的此法分析器的程序稍加改造，使其能够输出正确的表达式的token序列。然后利用LL（1）分析法实现语法分析。 ⑵数据结构： int op=0; //当前判断进度 char ch; //当前字符 char nowword[10]=""; //当前单词 char operate[4]={'+','-','*','/'}; //运算符 char bound[2]={'(',')'}; //界符 struct Token { int code; char ch[10]; }; //Token定义 struct Token tokenlist[50]; //Token数组 struct Token tokentemp; //临时Token变量struct Stack //分析栈定义 { char *base; char *top; int stacksize; }; ⑶分析表及流程图 Begin PUSH(#),PUSH(E) POP(x) x ∈VT x ∈VN x=w end W=#n y NEXT(w) y n err 查LL （1）分析表空？ n PUSH （i ）err n y 逆序压栈 ⑷关键函数： int IsLetter(char ch) //判断ch 是否为字母 int IsDigit(char ch) //判断ch 是否为数字 int Iskey(char *string) //判断是否为关键字 int Isbound(char ch) //判断是否为界符 int Isboundnum(char ch) //给出界符所在token 值 int init(STack *s) //栈初始化 int pop(STack *s,char *ch) //弹栈操作 int push(STack *s,char ch) //压栈操作 void LL1(); //分析函数 源程序代码：（加入注释） 实验二语法分析程序设计与实现 一、实验目的 任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，通过设计、编制、调试实现一个典型的语法分析程序，对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。 二、基本实验内容与要求 选择对各种常见高级程序设计语言都较为通用的语法结构——算术表达式的一个简化子集——作为分析对象，根据如下描述其语法结构的BNF定义G2[<算术表达式>]，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。 G2[<算术表达式>]： <算术表达式> → <项> | <算术表达式>+<项> | <算术表达式>-<项> <项> → <因式> | <项>*<因式> | <项>/<因式> <因式> → <运算对象> | (<算术表达式>) 若将语法范畴<算术表达式>、<项>、<因式>和<运算对象>分别用E、T、F 和i代表，则G2可写成： G2[E]：E → T | E+T | E-T T → F | T*F | T/F F → i | (E) 输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID ······ 输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。 要求: 1、确定语法分析程序的流程图，同时考虑相应的数据结构，编写一个语法分析源程序。 2、将词法、语法分析合在一起构成一个完整的程序，并调试成功。 3、供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例。对于所输入的字符串，不论对错，都应有明确的信息输出。 昆明理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：编译原理开课实验室： 445 2011年 12 月 19日年级、专业、 班 计科093 学号200910405310 姓名孙浩川成绩 实验项目名称语法分析器指导教师严馨 教 师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强□ B.中等□ C.差□ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般□ C.没有□ 教师签名： 年月日 一、实验目的及内容 实验目的：编制一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检 查和结构分析。 实验内容：在上机(一)词法分析的基础上,采用递归子程序法或其他适合的语法分析方法,实现其语法分析程序。要求编译后能检查出语法错误。 已知待分析的C语言子集的语法，用EBNF表示如下： <程序>→main()<语句块> <语句块> →‘{’<语句串>‘}’ <语句串> → <语句> {; <语句> }; <语句> → <赋值语句> |<条件语句>|<循环语句> <赋值语句>→ID=<表达式> <条件语句>→if‘(‘条件’)’<语句块> <循环语句>→while’(‘<条件>’)‘<语句块> <条件> → <表达式><关系运算符> <表达式> <表达式> →<项>{+<项>|-<项>} <项> → <因子> {* <因子> |/ <因子>} <因子> →ID|NUM| ‘(’<表达式>‘)’ <关系运算符> →<|<=|>|>=|==|!= 二、实验原理及基本技术路线图（方框原理图或程序流程图） 实验二、语法分析 一、实验目的： 设计MiniC的上下文无关文法，利用JavaCC生成调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、语法分析器: 按照MiniC语言的语法规则检查词法分析输出的记号流是否符合这些规则，并根据这些规则所体现出的语言中的各种语法结构的层次性。把规则写入到JavaCC的.jjt文件中，可以生成树状的层次结构。 三、JavaCC: 在JavaCC的文法规范文件中，不仅可以描述语言的语法规范，而且可以描述词法规范，本次实习中，利用JavaCC以MiniC语言构造一个不含语义分析的编译器前端，包括词法分析、语法分析，并要考虑语法分析中的错误恢复问题。通过使用JavaCC, 可以体会LL(k)文法的编写特点，掌握编写JavaCC文法规范文件的方法。 内容：利用JavaCC生成一个MiniC的语法分析器； 要求： 1.用流的形式读入要分析的C语言程序，或者通过命令行输入源程序。 2.具有错误检查的能力，如果有能力可以输出错误所在的行号，并简单提示 3.如果输入的源程序符合MiniC的语法规范，输出该程序的层次结构的语法树 具体实施步骤如下： 1.把MiniC转换为文法如下 Procedure()→void main() {WhileStatement()} WhileStatement()→while(Condition()){(WhileStatement()|ass ign())} assign()→ 语法分析器的设计 一、实验内容 语法分析程序用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 华北水利水电学院编译原理实验报告 一、实验题目：语法分析（算符优先分析程序） （1）选择最有代表性的语法分析方法算符优先法； （2）选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。 二、实验内容 （1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕或者输出到文件）； （2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程） （3）给定表达式文法为： G(E’): E’→#E# E→E+T | T T→T*F |F F→(E)|i (4) 分析的句子为: (i+i)*i和i+i)*i 三、程序源代 #include编译原理课程设计-词法语法分析器
编译原理语法分析实验报告
编译原理 语法分析实验二
编译原理词法分析器语法分析器实验报告
编译原理-编写递归下降语法分析器
实验二-LL1语法分析器
编译原理 语法分析器 (java完美运行版)(精选.)
编译原理实验二语法分析器LL(1)实现
编译原理实验报告(语法分析器)
实验二--语法分析-
编译原理词法分析和语法分析报告 代码(C语言版)
编译原理实验二
编译原理-语法分析-算符优先文法分析器
编译原理实验二语法分析器LL(1)实现教学内容
编译原理实验二语法分析器LL(1)实现
实验二 语法分析程序设计与实现
昆明理工大学 编译原理 实验二 语法分析器
实验二语法分析
编译原理语法分析器实验
编译原理_实验报告实验二__语法分析(算符优先) 2
- 编译原理实验二语法分析器LL(1)实现
- 编译原理_词法分析器_实验报告
- 编译原理语法分析器
- 编译原理词法分析器语法分析器实验报告
- 编译原理词法分析器的构造
- 编译原理语法分析器实验
- 编译原理_语法分析器
- 词法分析器的设计与实现 编译原理实验报告
- 编译原理C++语法分析器
- 编译原理词法分析器实验报告
- 编译原理-语法分析器-仅供参考,不可滥用!
- 编译原理实验报告(词法分析器 语法分析器)
- 编译原理实验报告(词法分析器语法分析器)
- 编译原理课程设计-词法语法分析器
- 编译原理词法语法语义分析器设计
- 昆明理工大学 编译原理 实验二 语法分析器
- 编译原理实验二-语法分析器的设计
- 编译原理_语法分析器_(java完美运行版)
- 编译原理实验报告(词法分析器 语法分析器)
- 编译原理实验报告(语法分析器)