编译原理实验报告
题目：对下面的文法对象，使用c语言构造它的预测分析程序；并任意给一算术表达式进行分析测试．
分析对象对象定义如下：
算术表达式→项｜算术表达式+项｜算术表达式－项
项→因式｜项*因式｜项／因式
因式→变量｜（算术表达式）
变量→字母
字母→A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z
一、分析
语法分析部分我们我们采用ｌｌ（１）方法实现，采用ｌｌ（１）方法实现语法发分析要求文法满足以下要求：
一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当有右部能=*=>ε时则与其左部非终结符的后跟符号集合也有关，此外在产生式中不存在左递归即经过压缩，无左递归，无回溯。它的基本思想是从左到右扫描源程序，同时从识别符号开始生成句子的最左推导，并只向前查看一个输入符号，便能唯一确定应选择的规则。
下面将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判
别并介绍如何对非LL(1)文法进行等价变换问题，也就是消除一个文法中的左递归和左公共因子。
注意：
一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。
LL(1) 文法的定义（5种定义）：
一个文法符号串的开始符号集合定义如下：
定义 1.设G=(VT，VN，S，P)是上下文无关文法,α是任意的文法符号串,FIRST(α)是从α推导出的串的开始符号的终结符集合。。。。
FIRST(α)={a|α=*=>aβ,a∈VT，α,β∈V*}若α=*=>ε,则规定ε∈FIRST(α)．当一个文法中相同左部非终结符的右部存在能=*=>ε的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。为此，我们定义一个文法非终结符的后跟符号的集合如下：
定义2.设G=(VT，VN，S，P)是上下文无关文法，A∈VN，S是开始符号
FOLLOW(A)=｛a|S=*=>μAβ,且a∈VT，a∈FIRST(β),μ∈VT* ,β∈V+｝
若S=*=>μAβ,且βε, 则#∈FOLLOW(A)。也可定义为：FOLLOW(A)={a|S=*=> …Aa…,a ∈VT}
若有S=*=> …A，则规定#∈FOLLOW(A)
这里我们用'#'作为输入串的结束符，或称为句子括号，如：#输入串#。
定义 3.给定上下文无关文法的产生式A→α, A∈VN,α∈V*, 若α==>ε,则SELECT(A→α)=FIRST(α)
如果α=*=>ε，则SELECT(A→α)=FIRST(αε)∪FOLLOW(A)。FIRST(αε)表示FIRST(α)的非{ε}元素。
更进一步可以看出能够使用自顶向下分析技术必须使文法满足如下条件，我们称满足条件的文法为LL(1)文法，其定义为：
定义4.一个上下文无关文法是LL(1)文法的充分必要条件是：
对每个非终结符A的两个不同产生式，A→α, A→β,满足SELECT(A→α)∩SELECT(A→β)=空,其中α，β不同时能ε.
定义5. LL（1）文法也可定义为:
一个文法G是LL（1）的，当且仅当对于G的每一个非终结符A的任何两个不同产生式A→α|β，下面的条件成立：
①FIRST（α）∩FIRST(β)= 空,也就是α和β推导不出以某个相同的终结符a为首的符号串；它们不应该都能推出空字ε．
②假若βε那么，FIRST（α)∩FOLLOW（A）＝空也就是，若βε则α所能推出的串的首符号不应在FOLLOW(A)中。
二、算法
（1）读入文法
（2）判断正误
（3）若无误，判断是否为LL(1)文法
（4）若是，构造分析表；
（5）由总控算法判断输入符号串是否
为该文法的句型。
根据下面LL(1)文法，对输入串w: (i+i)*(i+i)+i*i进行LL(1)分析,
1、先手工建立LL(1)分析表；
2
LL(1)文法G为：
E →TE’
E’→+TE’|ε
T →FT’
T’→*FT’|ε
F →(E)|id
分析算法：
输入：串w和文法G的分析表M。
输出：如果W属于L（G），则输出W的最左推导，否则报告错误。
方法：开始时，#S在分析栈中，其中S是文法的开始符号，在栈顶；令指针ip指向W#的
第一个符号；repeat
让X等于栈顶符号，a为ip所指向的符号；
if X 是终结符号或# then
If X=a then 把X从栈顶弹出并使ip指向下一个输入符号else error()
else /*X 是非终结符号*/
if M[x,a]=Xày1y2…yk then begin
从栈中弹出X；把yk,yk-1,…,y1压入栈，y1在栈顶；
输出产生式Xày1y2…yk；end
else error()
until X=# /*栈空*/
语法分析的流程算法
三、设计目的：
（1）理解和掌握LL(1)语法分析方法的基本原理；根据给出的LL(1)文法，掌握LL(1)分析表的构造及分析过程的实现。
（2）掌握预测分析程序如何使用分析表和栈联合控制实现LL(1)分析。
四、实现环境和要求
选择实习环境为486以上CPU,4M内存,TURBO C2.0语言. 实现程序见附录.
具体的实现要求：
（1）对输入文法，它能判断是否为LL(1)文法，若是，则转（2）；否则报错并终止；
（2）输入已知文法，由程序自动生成它的LL(1)分析表；
（3）对于给定的输入串，应能判断识别该串是否为给定文法的句型。
五、总结
上机前应做好准备．即根据实习目的、要求和分析，选择相应的数据结构，使用Ｃ语言参照算法中的流程编写词法分析的程序．将编好的程序上机进行调试．注意调试的例子应有词法正确的，也应有词法错误的或是超出所选数据结构范围的．
实验完成达到实习目的之后，若尚有余力者，可以对所选子集适当扩大或是增加相应功能如：①扩充界符和保留字数目；②允许实型常数；③进行词法错误检查；④最大范围扩充以至PASCAL语言所有字符的集合．
通过这次程序设计，更加清楚透彻的明白了ＬＬ(1)分析法的过程，从而也比较熟练掌握了自上而下语法分析的基本思想，此外，巩固了所学的数据结构的知识，自己所学的知识能够联系起来，使得知识自成系统。在实现和调试时次采取模块化的思想，使得本次课程设计比较顺利，增强了自己的信心，提高了自己的编程能力和动手能力以及独立分析问题、解决问题的能力和综合运用所学知识的能力。
附录
/*****************************************************
预测分析程序（语法分析程序），分析对象为C语言源程序文件。
该分析程序有18部分组成：
《1》首先定义各种需要用到的常量和变量；
《2》判断一个字符是否在指定字符串中；
《3》得到一个不是非终结符的符号；
《4》分解含有左递归的产生式；
《5》分解不含有左递归的产生式；
《6》读入一个文法；
《7》将单个符号或符号串并入另一符号串；
《8》求所有能直接推出^的符号；
《9》求某一符号能否推出‘^ ’；
《10》判断读入的文法是否正确；
《11》求单个符号的FIRST；
《12》求各产生式右部的FIRST；
《13》求各产生式左部的FOLLOW；
《14》判断读入文法是否为一个LL(1)文法；
《15》构造分析表M；
《16》总控算法；
《17》一个用户调用函数；
《18》主函数；
/*******************************************/
WORD ANAL YSE DEMO FOR TURBO C 2.0
Copyright (c) 2005-6-30 Author: 陈强
All rights reserved.
/*******************************************/
#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 f[50],F[50]; /*记录各符号的FIRST和FOLLOW是否已求过*/
char empty[20]; /*记录可直接推出^的符号*/
char TEMP[50]; /*求FOLLOW时存放某一符号串的FIRST集合*/
int validity=1; /*表示输入文法是否有效*/
int ll=1; /*表示输入文法是否为LL(1)文法*/
int M[20][20]; /*分析表*/
char choose; /*用户输入时使用*/
char empt[20]; /*求_emp()时使用*/
char fo[20]; /*求FOLLOW集合时使用*/
/*******************************************
判断一个字符是否在指定字符串中
********************************************/
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==strlen(p))
return(0); /*若不在，返回0*/
}
}
/*******************************************
得到一个不是非终结符的符号
********************************************/
char c()
{
char c='A';
while(in(c,non_ter)==1)
c++;
return(c);
}
/*******************************************
分解含有左递归的产生式
********************************************/
void recur(char *point)
{ /*完整的产生式在point[]中*/
int j,m=0,n=3,k;
char temp[20],ch;
ch=c(); /*得到一个非终结符*/
k=strlen(non_ter);
non_ter[k]=ch;
non_ter[k+1]='\0';
for(j=0;j<=strlen(point)-1;j++)
{
if(point[n]==point[0])
{ /*如果‘|’后的首符号和左部相同*/ for(j=n+1;j<=strlen(point)-1;j++)
{
while(point[j]!='|'&&point[j]!='\0')
temp[m++]=point[j++];
left[count]=ch;
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
m=0;
count++;
if(point[j]=='|')
{
n=j+1;
break;
}
}
}
else
{ /*如果‘|’后的首符号和左部不同*/ left[count]=ch;
right[count][0]='^';
right[count][1]='\0';
count++;
for(j=n;j<=strlen(point)-1;j++)
{
if(point[j]!='|')
temp[m++]=point[j];
else
{
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
printf(" count=%d ",count);
m=0;
count++;
}
}
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]=ch;
right[count][m+1]='\0';
count++;
m=0;
}
}
}
/*******************************************
分解不含有左递归的产生式
********************************************/
void non_re(char *point)
{
int m=0,j;
char temp[20];
for(j=3;j<=strlen(point)-1;j++)
{
if(point[j]!='|')
temp[m++]=point[j];
else
{
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]='\0';
m=0;
count++;
}
}
left[count]=point[0];
memcpy(right[count],temp,m);
right[count][m]='\0';
count++;
m=0;
}
/*******************************************
读入一个文法
********************************************/ 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,k;
printf("\n请输入文法的非终结符号串：");
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();
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("\ninput error!");
validity=0;
return('\0');
} /*检测输入错误*/
for(k=0;k<=i-1;k++)
{ /*分解输入的各产生式*/
if(p[k][3]==p[k][0])
recur(p[k]);
else
non_re(p[k]);
}
return(s);
}
/*******************************************
将单个符号或符号串并入另一符号串
********************************************/
void merge(char *d,char *s,int type)
{ /*d是目标符号串，s是源串，type＝1，源串中的‘^ ’一并并入目串；
type＝2，源串中的‘^ ’不并入目串*/
int i,j;
for(i=0;i<=strlen(s)-1;i++)
{
if(type==2&&s[i]=='^')
;
else
{
for(j=0;;j++)
{
if(j break; if(j==strlen(d)) { d[j]=s[i]; d[j+1]='\0'; break; } } } } } /******************************************* 求所有能直接推出^的符号 ********************************************/ 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); 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); if(in(c,empty)==1) return(1); for(i=0;;i++) { if(i==count) return(0); if(left[i]==c) /*找一个左部为c的产生式*/ { j=strlen(right[i]); /*j为右部的长度*/ if(j==1&&in(right[i][0],empty)==1) return(1); else if(j==1&&in(right[i][0],termin)==1) return(0); else { for(k=0;k<=j-1;k++) if(in(right[i][k],empt)==1) mark=1; if(mark==1) continue; else { for(k=0;k<=j-1;k++) { result*=_emp(right[i][k]); temp[0]=right[i][k]; temp[1]='\0'; merge(empt,temp,1); } } } if(result==0&&i continue; else if(result==1&&i return(1); } } } /******************************************* 判断读入的文法是否正确 ********************************************/ int judge() { int i,j; for(i=0;i<=count-1;i++) { if(in(left[i],non_ter)==0) { /*若左部不在非终结符中，报错*/ printf("\nerror1!"); validity=0; return(0); } for(j=0;j<=strlen(right[i])-1;j++) { if(in(right[i][j],non_ter)==0&&in(right[i][j],termin)==0&&right[i][j]!='^') { /*若右部某一符号不在非终结符、终结符中且不为‘^ ’，报错*/ printf("\nerror2!"); validity=0; return(0); } } } return(1); } /******************************************* 求单个符号的FIRST ********************************************/ void first2(int i) { /*i为符号在所有输入符号中的序号*/ char c,temp[20]; int j,k,m; c=v[i]; char ch='^'; emp(ch); if(in(c,termin)==1) /*若为终结符*/ { first1[i][0]=c; first1[i][1]='\0'; } else if(in(c,non_ter)==1) /*若为非终结符*/ { for(j=0;j<=count-1;j++) { if(left[j]==c) { if(in(right[j][0],termin)==1||right[j][0]=='^') { temp[0]=right[j][0]; temp[1]='\0'; merge(first1[i],temp,1); } 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]) break; if(f[k]=='0') { first2(k); f[k]='1'; } merge(first1[i],first1[k],2); for(k=0;k<=strlen(right[j])-1;k++) { empt[0]='\0'; if(_emp(right[j][k])==1&&k { for(m=0;;m++) if(v[m]==right[j][k+1]) break; if(f[m]=='0') { first2(m); f[m]='1'; } merge(first1[i],first1[m],2); } else if(_emp(right[j][k])==1&&k==strlen(right[j])-1) { temp[0]='^'; temp[1]='\0'; merge(first1[i],temp,1); } else break; } } } } } f[i]='1'; } /******************************************* 求各产生式右部的FIRST ********************************************/ void FIRST(int i,char *p) { int length; int j,k,m; char temp[20]; length=strlen(p); if(length==1) /*如果右部为单个符号*/ { if(p[0]=='^') { if(i>=0) { first[i][0]='^'; first[i][1]='\0'; } else { TEMP[0]='^'; TEMP[1]='\0'; } } else { for(j=0;;j++) if(v[j]==p[0]) break; if(i>=0) { memcpy(first[i],first1[j],strlen(first1[j])); 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]) 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) { int j,k,m,n,result=1; char c,temp[20]; c=non_ter[i]; /*c为待求的非终结符*/ temp[0]=c; temp[1]='\0'; merge(fo,temp,1); if(c==start) { /*若为开始符号*/ temp[0]='#'; temp[1]='\0'; merge(follow[i],temp,1); } for(j=0;j<=count-1;j++) { if(in(c,right[j])==1) /*找一个右部含有c的产生式*/ { for(k=0;;k++) if(right[j][k]==c) break; /*k为c在该产生式右部的序号*/ for(m=0;;m++) if(v[m]==left[j]) break; /*m为产生式左部非终结符在所有符号中的序号*/ if(k==strlen(right[j])-1) { /*如果c在产生式右部的最后*/ if(in(v[m],fo)==1) { merge(follow[i],follow[m],1); continue; } if(F[m]=='0') { FOLLOW(m); F[m]='1'; } merge(follow[i],follow[m],1); } else { /*如果c不在产生式右部的最后*/ for(n=k+1;n<=strlen(right[j])-1;n++) { empt[0]='\0'; result*=_emp(right[j][n]); } if(result==1) { /*如果右部c后面的符号串能推出^*/ if(in(v[m],fo)==1) { /*避免循环递归*/ merge(follow[i],follow[m],1); continue; } if(F[m]=='0') { FOLLOW(m); F[m]='1'; } merge(follow[i],follow[m],1); } for(n=k+1;n<=strlen(right[j])-1;n++) temp[n-k-1]=right[j][n]; temp[strlen(right[j])-k-1]='\0'; FIRST(-1,temp); merge(follow[i],TEMP,2); } } } F[i]='1'; } /******************************************* 判断读入文法是否为一个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'; f[j]='0'; F[j]='0'; } for(j=0;j<=strlen(v)-1;j++) first2(j); /*求单个符号的FIRST集合*/ printf("\nfirst1:"); for(j=0;j<=strlen(v)-1;j++) printf("%c:%s ",v[j],first1[j]); printf("\nempty:%s",empty); printf("\n:::\n_emp:"); for(j=0;j<=strlen(v)-1;j++) printf("%d ",_emp(v[j])); for(i=0;i<=count-1;i++) FIRST(i,right[i]); /*求FIRST*/ printf("\n"); for(j=0;j<=strlen(non_ter)-1;j++) { /*求FOLLOW*/ if(fo[j]==0) { fo[0]='\0'; FOLLOW(j); } } printf("\nfirst:"); for(i=0;i<=count-1;i++) printf("%s ",first[i]); printf("\nfollow:"); for(i=0;i<=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])); select[i][strlen(first[i])]='\0'; for(j=0;j<=strlen(right[i])-1;j++) result*=_emp(right[i][j]); if(strlen(right[i])==1&&right[i][0]=='^') result=1; if(result==1) { for(j=0;;j++) if(v[j]==left[i]) 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) 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++) M[i][j]=-1; i=strlen(termin); termin[i]='#'; /*将#加入终结符数组*/ termin[i+1]='\0'; for(i=0;i<=count-1;i++) { for(m=0;;m++) if(non_ter[m]==left[i]) break; /*m为产生式左部非终结符的序号*/ for(j=0;j<=strlen(select[i])-1;j++) { 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("\n该符号串不是文法的句型！"); return; } else if(S[strlen(S)-1]=='#') { printf("\n该符号串是文法的句型."); 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==strlen(termin)) { printf("\n词法错误！"); return; 编译技术 班级网络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 其次，由于把关键字作为保留字，故可以把关键字作为一类特殊标示符来处理。也就是说，对于关键字不专设对应的转换图。但把它们（及其种别编码）预先安排在一张表格中（此表叫作保留字表）。当转换图识别出一个标识符时，就去查对这张表，确定它是否为一个关键字。 再次，如果关键字、标识符和常数之间没有确定的运算符或界符作间隔，则必须至少用一个空白符作间隔（此时，空白符不再是完全没有意义的了）。例如，一个条件语句应写为 一、实验内容和目的 1. 已知待分析的C语言子集的语法，用EBNF表示如下： (1)<程序>→main()<语句块> (2)<语句块>→“{” <语句串>“}” (3)<语句串>→<语句>{;<语句>} ; (4)<语句>→<赋值语句>|<条件语句>|<循环语句> (5)<赋值语句>→ID=<表达式> (6)<条件语句>→if(条件)<语句块> (7)<循环语句>→while(<条件>)<语句块> (8)<条件>→<表达式><关系运算符><表达式> (9)<表达式>→<项>{+<项>}|<项>{-<项>} (10)<项>→<因子>{*<因子>}|<因子>{/<因子>} (11)<因子>→ID|NUM|(<表达式>) (12)<关系运算符>→<|<=|>|>=|==|!= 2. 实验目的、要求实现的功能 实验目的：编制一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析。 实验要求：在上机(一)词法分析的基础上，采用递归子程序法或其他适合的语法分析方法，实现其语法分析程序。要求编译后能检查出语法错误。 3. 将实验方法改写为适合预测分析法的文法如下： (1) <程序>→main()<语句块> (2)<语句块>→{ <语句串>} (3)<语句串>→<语句>; <语句串> (3_1) <语句串>→ε (4)<语句>→<赋值语句> (5)<语句>→<条件语句> (6) <语句>→<循环语句> (7)<赋值语句>→ID=<表达式> (8)<条件语句>→if(<条件>)<语句块> (9)<循环语句>→while(<条件>)<语句块> (10)<条件>→<表达式><关系运算符><表达式> (11)<表达式>→<项><表达式`> (11_1)<表达式`>→+<项><表达式`> (11_2)<表达式`>→-<项><表达式`> (11_3)<表达式`>→ε (12) <项>→<因子><项`> (12_1) <项`>→*<因子><项`> (12_2)<项`>→/<因子><项`> (12_3)<项`>→ε (13) <因子>→ID (14) <因子>→NUM (15) <因子>→(<表达式>) (16) <关系运算符>→< (17) <关系运算符>→<= 编译原理实验报告实验名称：实验一编写词法分析程序 实验类型：验证型实验 指导教师：何中胜 专业班级：13软件四 姓名：丁越 学号： 电子邮箱： 实验地点：秋白楼B720 实验成绩： 日期：2016年3 月18 日 一、实验目的 通过设计、调试词法分析程序，实现从源程序中分出各种单词的方法；熟悉词法分析 程序所用的工具自动机，进一步理解自动机理论。掌握文法转换成自动机的技术及有穷自动机实现的方法。确定词法分析器的输出形式及标识符与关键字的区分方法。加深对课堂教学的理解；提高词法分析方法的实践能力。通过本实验，应达到以下目标： 1、掌握从源程序文件中读取有效字符的方法和产生源程序的内部表示文件的方法。 2、掌握词法分析的实现方法。 3、上机调试编出的词法分析程序。 二、实验过程 以编写PASCAL子集的词法分析程序为例 1.理论部分 （1）主程序设计考虑 主程序的说明部分为各种表格和变量安排空间。 数组 k为关键字表，每个数组元素存放一个关键字。采用定长的方式，较短的关键字 后面补空格。 P数组存放分界符。为了简单起见，分界符、算术运算符和关系运算符都放在 p表中 （编程时，还应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id和ci数组分别存放标识符和常数。 instring数组为输入源程序的单词缓存。 outtoken记录为输出内部表示缓存。 还有一些为造表填表设置的变量。 主程序开始后，先以人工方式输入关键字，造 k表；再输入分界符等造p表。 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；接收键盘上 送来的一个单词；调用词法分析过程；输出每个单词的内部码。 ⑵词法分析过程考虑 将词法分析程序设计成独立一遍扫描源程序的结构。其流程图见图1-1。 图1-1 该过程取名为 lexical，它根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：以字符 k表示关键字；i表示标识符；c表示常数；p表示分界符；s表示运算符（编程时类号分别为 1，2，3，4，5）。 对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有 该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数 变为二进制形式存入数组中 ci中，并记录其在表中的位置。 lexical过程中嵌有两个小过程：一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；另一个名为error，当出现错误时，调用这个过程， 输出错误编号。 2.实践部分 语法分析程序大作业 一、作业目的和要求 通过设计、编制、调试一个典型的语法分析程序（任选有代表性的语法分析方法，如LL(1)、递归下降分析法、LR、算符优先分析法）等，作为编制语法分析程序的依据，对词法分析器所提供的单词序列进行语法检测和结构分析，实现并进一步掌握常用的语法分析方法。 二、作业内容 选择对各种常见高级程序设计语言都较为通用的语法结构作为分析对象（例如表达式、if、while、for等等），给出其文法规则描述（注意，文法规则的描述要符合所选分析方法的要求，比如用LL(1)分析法，文法必须是LL(1)文法），设计并实现一个完整的语法分析程序。 输入：源程序以文件的形式输入。 输出：对于输入的源程序，如果输入源程序是给定文法定义的合法程序，则输出”success”，如果不是，即输入源程序有错误，则输出“Error”,并且尽可能指出出错位置和原因。 三、作业要求 1、说明语法分析的源语言是什么？ 能分析的语法成分有哪些（比如if、while、表达式、switch等等）。 给出每个语法规则的文法描述。（可以自定义语法成分，设计合理的语法规则。） 2、说明选择的语法分析方法是哪种？描述总体设计思路和主要的流程图。 3、编程实现，程序中编写的各种函数，需要给出注释，说明函数的作用。 四、结果分析 1、输入正确的源程序截图： 输出结果截图： 2、输入错误的源程序截图： 输出结果截图： 3、总结（自己的心得体会、你编写的语法分析程序的优缺点） 作业分工 上交内容：将以下文件打包压缩，压缩包命名：班级学号姓名_语法分析大作业 学号姓名以组长名字命名即可 1、本报告 2、语法分析程序代码 3、编译生成可执行程序 4、用于测试的源程序代码文件。 词法分析 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 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请注意，第"< 语义分析程序的设计与实现 班号：2008211316姓名：张荣学号：08211627序号：26 实验日期：2010-11-23 一：实验内容： (2) 二：实验要求： (2) 三：实验方法： (2) ◆由LEX建立YACC的词法分析程序 (2) ◆yacc原理介绍 (3) ◆词法分析 (4) ◆解析器如何工作 (5) ◆Yacc环境 (6) ◆常用代码 (7) 第四：YACC内部名称： (7) 第五：运行结果（源代码见附录） (8) 第六：实验总结 (9) 第七：附录 (10) 附录一：yacc程序，加注释 (10) 附录二：词法分析器的工作原理 (16) 一：实验内容： 编写语法分析程序，实现对算术表达式的语法分析，要求所分析的算术表达式由如下的文法产生。 ◆E->E+T|E-T|T ◆T->T*F|T/F|F ◆F->id|(E)|num 二：实验要求： 在对表达式进行分析的同时，输出所采用的产生式。 可以采用多种方法 ◆编写递归调用程序，实现自顶向下的分析。 ◆编写LL(1)语法分析程序，要求： ◇编程实现算法4.2，为给定的文法自动构造预测分析表 ◇编程实现算法4.1，构造LL(1)预测分析程序， ◆编写语法分析程序，实现自底向上的分析，要求： ◇构造识别所有活前缀的DFA ◇构造LR分析表 ◇编程实现算法4.3，构造LR分析程序 ◆利用yacc自动生成语法分析程序，调用LEX自动生成的词法分析器程序 三：实验方法： ◆由LEX建立YACC的词法分析程序 由LEX产生的词法分析程序可用于YACC，LEX编译程序根据LEX 源程序产生词法分析程序yylex(),这个名字就是YACC所需要的词法分析程序的名字。如果YACC要调用LEX产生的词法分析程序，则在YACC源程序的第三部分用语句#include“lex.yy.c”代替函数yylex()的定义，这一yylex()就可以访问YACC中记号的名字，因为LEX的输出时候YACC输出文件的一部分，所有，每个LEX的动作都返回YACC 知道的终结符。 在UNIX的环境下，如果LEX源程序在first.l中，YACC的源程序在second.y中，可以使用以下命令得到所需要的分析程序。 Lex first.l Yacc second.y cc-o yaccdemo y.tab.c lex.yy.c ◆yacc原理介绍 Yacc 是用可移植的C 语言写成的。接受的规定类别是非常一般性的: 带有去歧义规则的LALR(1) 文法。 Yacc 提供了一个通用工具来在计算机程序的输入上施加结构。Yacc 用户准备输入处理的规定；它包括描述输入结构的规则，在识别了这些规则的时候调用的代码，和做基本输入的一个低层例程。Yacc 接着生成一个函数来控制输入处理。这个函数叫做解析器(parser)，它调用用户提供的低层输入例程(词法分析器(analyzer))来从输入流中选取基本项目(叫做记号(token))。依据叫做文法规则的输入结构规则来组织这些记号；在识别了这些规则中的某一个的时候，接着调用为这个规则提供的叫做动作的用户代码；动作有能力返回值并 《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 //将文法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)；//求符号串s=X1X2...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 编译原理实验报告 ******************************************************************************* ******************************************************************************* PL0语言功能简单、结构清晰、可读性强，而又具备了一般高级程序设计语言的必须部分，因而PL0语言的编译程序能充分体现一个高级语言编译程序实现的基本方法和技术。PL/0语言文法的EBNF表示如下： <程序>::=<分程序>. <分程序> ::=[<常量说明>][<变量说明>][<过程说明>]<语句> <常量说明> ::=CONST<常量定义>{，<常量定义>}; <常量定义> ::=<标识符>=<无符号整数> <无符号整数> ::= <数字>{<数字>} <变量说明> ::=VAR <标识符>{, <标识符>}; <标识符> ::=<字母>{<字母>|<数字>} <过程说明> ::=<过程首部><分程序>{; <过程说明> }; <过程首部> ::=PROCEDURE <标识符>; <语句> ::=<赋值语句>|<条件语句>|<当循环语句>|<过程调用语句> |<复合语句>|<读语句><写语句>|<空> <赋值语句> ::=<标识符>:=<表达式> <复合语句> ::=BEGIN <语句> {;<语句> }END <条件语句> ::= <表达式> <关系运算符> <表达式> |ODD<表达式> <表达式> ::= [+|-]<项>{<加法运算符> <项>} <项> ::= <因子>{<乘法运算符> <因子>} <因子> ::= <标识符>|<无符号整数>| ‘(’<表达式>‘)’ <加法运算符> ::= +|- <乘法运算符> ::= *|/ <关系运算符> ::= =|#|<|<=|>|>= <条件语句> ::= IF <条件> THEN <语句> <过程调用语句> ::= CALL 标识符 <当循环语句> ::= WHILE <条件> DO <语句> <读语句> ::= READ‘(’<标识符>{,<标识符>}‘)’ <写语句> ::= WRITE‘(’<表达式>{,<表达式>}‘)’ <字母> ::= a|b|…|X|Y|Z <数字> ::= 0|1|…|8|9 【预处理】 对于一个pl0文法首先应该进行一定的预处理，提取左公因式，消除左递归（直接或间接），接着就可以根据所得的文法进行编写代码。 【实验一】词法分析 【实验目的】给出PL/0文法规，要求编写PL/0语言的词法分析程序。 【实验容】已给PL/0语言文法，输出单词（关键字、专用符号以及其它标记）。 实验五LL(1)文法识别程序设计 一、实验目的 通过LL(1)文法识别程序的设计理解自顶向下的语法分析思想。 二、实验重难点 FIRST集合、FOLLOW集合、SELECT集合元素的求解，预测分析表的构造。 三、实验内容与要求 实验内容： 1．阅读并理解实验案例中LL(1)文法判别的程序实现； 2．参考实验案例，完成简单的LL(1)文法判别程序设计。 四、实验学时 4课时 五、实验设备与环境 C语言编译环境 六、实验案例 1．实验要求 参考教材93页预测分析方法，94页图5.11 预测分析程序框图，编写表达式文法的识别程序。要求对输入的LL(1)文法字符串，程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。 表达式文法为： E→E+T|T T→T*F|F F→i|(E) 2．参考代码 为了更好的理解代码，建议将图5.11做如下标注： /* 程序名称：LL(1)语法分析程序*/ /* E->E+T|T */ /* T->T*F|F */ /* F->(E)|i */ /*目的: 对输入LL(1)文法字符串，本程序能自动判断所给字符串是否为所给文法的句子，并能给出分析过程。 /********************************************/ /* 程序相关说明*/ /* A=E' B=T' */ /* 预测分析表中列号、行号*/ /* 0=E 1=E' 2=T 3=T' 4=F */ /* 0=i 1=+ 2=* 3=( 4=) 5=# */ /************************************/ #include"iostream" #include "stdio.h" #include "malloc.h" #include "conio.h" /*定义链表这种数据类型参见： https://www.doczj.com/doc/e38283192.html,/link?url=_owQzf8PRZOt9H-5oXIReh4X0ClHo6zXtRdWrdSO5YBLpKl NvkCk0qWqvFFxjgO0KzueVwEQcv9aZtVKEEH8XWSQCeVTjXvy9lxLQ_mZXeS###*/ struct Lchar{ char char_ch; struct Lchar *next; }Lchar,*p,*h,*temp,*top,*base; /*p指向终结符线性链表的头结点，h指向动态建成的终结符线性链表节点，top和base分别指向非终结符堆栈的顶和底*/ 实验1-3 《编译原理》S语言词法分析程序设计方案 一、实验目的 了解词法分析程序的两种设计方法之一：根据状态转换图直接编程的方式； 二、实验内容 1．根据状态转换图直接编程 编写一个词法分析程序，它从左到右逐个字符的对源程序进行扫描，产生一个个的单词的二元式，形成二元式（记号）流文件输出。在此，词法分析程序作为单独的一遍，如下图所示。 具体任务有： （1）组织源程序的输入 （2）拼出单词并查找其类别编号，形成二元式输出，得到单词流文件 （3）删除注释、空格和无用符号 （4）发现并定位词法错误，需要输出错误的位置在源程序中的第几行。将错误信息输出到屏幕上。 （5）对于普通标识符和常量，分别建立标识符表和常量表（使用线性表存储），当遇到一个标识符或常量时，查找标识符表或常量表，若存在，则返回位置，否则返回0并且填写符号表或常量表。 标识符表结构：变量名，类型（整型、实型、字符型），分配的数据区地址 注：词法分析阶段只填写变量名，其它部分在语法分析、语义分析、代码生成等阶段逐步填入。 常量表结构：常量名，常量值 三、实验要求 1．能对任何S语言源程序进行分析 在运行词法分析程序时，应该用问答形式输入要被分析的S源语言程序的文件名，然后对该程序完成词法分析任务。 2．能检查并处理某些词法分析错误 词法分析程序能给出的错误信息包括：总的出错个数，每个错误所在的行号，错误的编号及错误信息。 本实验要求处理以下两种错误（编号分别为1，2）： 1：非法字符：单词表中不存在的字符处理为非法字符，处理方式是删除该字符，给出错误信息，“某某字符非法”。 2：源程序文件结束而注释未结束。注释格式为：/* …… */ 四、保留字和特殊符号表 xx理工大学 《编译原理》 题目语法分析程序 姓名： 学号： 班级： 一、实验目的 编制一个递归下降分析程序，实现对词法分析程序所提供的单词序列的语法检查和结构分析。 二、实验要求 利用C语言编制递归下降分析程序，并对简单语言进行语法分析。 2.1 待分析的简单语言的语法 用扩充的BNF表示如下： ⑴<程序>：：=begin<语句串>end ⑵<语句串>：：=<语句>{；<语句>} ⑶<语句>：：=<赋值语句> ⑷<赋值语句>：：=ID：=<表达式> ⑸<表达式>：：=<项>{+<项> | -<项>} ⑹<项>：：=<因子>{*<因子> | /<因子> ⑺<因子>：：=ID | NUM | （<表达式>） 2.2 实验要求说明 输入单词串，以“#”结束，如果是文法正确的句子，则输出成功信息，打印“success”，否则输出“error”。 例如： 输入begin a:=9; x:=2*3; b:=a+x end # 输出success 输入x:=a+b*c end # 输出error 2.3 语法分析程序的酸法思想 ⑴主程序示意图如图2-1所示。 图2-1 语法分析主程序示意图 ⑵递归下降分析程序示意图如图2-2所示。 ⑶语句串分析过程示意图如图2-3所示。 图2-2 递归下降分析程序示意图 图2-3 语句串分析示意图 ⑷statement 语句分析程序流程如图2-4、2-5、2-6、2-7所示。 图2-4 statement 语句分析函数示意图 图2-5 expression 表达式分析函数示意图 图2-7 factor分析过程示意图三、语法分析程序的C语言程序源代码 #include "stdio.h" #include "string.h" char prog[100],token[8],ch; char *rwtab[6]={"begin","if","then","while","do","end"}; int syn,p,m,n,sum; int kk; factor(); expression(); yucu(); term(); statement(); lrparser(); scaner(); main() { p=kk=0; printf("\nGrade:05 Class:03 Name:Qiyubing Number:200507096 \n"); printf("\n----Please input the string end with '#':-------- \n"); do 编译原理课程设计(词法分析，语法分析，语义分析，代码 生成） #include char left;// string right;// int len;// }; ivan css[20];// 20 struct pank// action { char sr;// int state;// }; pank action[46][18];//action int go_to[46][11];// go_to struct ike// { ike *pre; int num;// int word;// ike *next; }; ike *stack_head,*stack_tail;// struct L// { int k; string op;// string op1;// string op2;// string result;// L *next;// L *Ltrue;//true L *Lfalse;//false }; LL(1)语法分析实验报告 一、实验题目 LL（1）语法分析 二、实验目的 通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，检查语法错误，进一步掌握常用的语法分析方法。 三、实验内容 构造LL(1)语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合则输出错误信息。 消除递归前的文法消除递归和提取公因子后的等价文法 S →S ∨ a T | a T | ∨ a T S→aTS’ |vaTS’ T →∧ a T | ∧a S’→vaTS’ |ε T→∧ a T’ T’→∧ aT’ |ε 根据已建立的分析表，对下列输入串：a∧ a∧ a进行语法分析，判断其是否符合文法。 四、实验要求 1.根据已由的文法规则建立LL（1）分析表； 2.输出分析过程。 请输入待分析的字符串: a∧ a∧ a 符号栈输入串所用产生式 #S a∧ a∧ a# #S’Ta a∧ a∧ a# S→aTS’ #S’T ∧ a∧ a# # S’T’a∧∧ a∧ a# T→∧ a T’ # S’T’a a∧ a# # S’T’∧ a# # S’T’a∧∧ a# T’→∧ aT’ # S’ T’a a# # S’ T’# # S’ # T’→ε # # S’→ε 五、程序思路 模块结构： 1、定义部分：定义常量、变量、数据结构。 2、初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体等）； 3、运行程序：让程序分析一个text文件，判断输入的字符串是否符合文法定义的规则； 4、利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示简单的错误提示。 六、程序源代码 /* 程序名称： LL(1)文法分析程序 */ /* S->S>aT|aT|>aT */ /* T-> 本代码只供学习参考： 词法分析源代码： #include 词法分析 一、实验目的 设计、编制并调试一个词法分析程序，加深对词法分析原理的理解。 二、实验要求 2.1 待分析的简单的词法 （1）关键字： begin if then while do end 所有的关键字都是小写。 （2）运算符和界符 ： = + - * / < <= <> > >= = ; ( ) # （3）其他单词是标识符（ID）和整型常数（SUM），通过以下正规式定义： ID = letter (letter | digit)* NUM = digit digit* （4）空格有空白、制表符和换行符组成。空格一般用来分隔ID、SUM、运算符、界符和关键字，词法分析阶段通常被忽略。 2.2 各种单词符号对应的种别码： 输入：所给文法的源程序字符串。 输出：二元组（syn,token或sum）构成的序列。 其中：syn为单词种别码； token为存放的单词自身字符串； sum为整型常数。 例如：对源程序begin x:=9: if x>9 then x:=2*x+1/3; end #的源文件，经过词法分析后输出如下序列： (1,begin)(10,x)(18,:=)(11,9)(26,;)(2,if)…… 三、词法分析程序的算法思想： 算法的基本任务是从字符串表示的源程序中识别出具有独立意义的单词符号，其基本思想是根据扫描到单词符号的第一个字符的种类，拼出相应的单词符号。 3.1 主程序示意图： 主程序示意图如图3-1所示。其中初始包括以下两个方面： ⑴关键字表的初值。 关键字作为特殊标识符处理，把它们预先安排在一张表格中（称为关键字表），当扫描程序识别出标识符时，查关键字表。如能查到匹配的单词，则该单词为关键字，否则为一般标识符。关键字表为一个字符串数组，其描述如下： Char *rwtab[6] = {“begin”, “if”, “then”, “while”, “do”, “end”,}; 图3-1 （2）程序中需要用到的主要变量为syn,token和sum 3.2 扫描子程序的算法思想： 首先设置3个变量：①token用来存放构成单词符号的字符串；②sum用来整型单词；③syn用来存放单词符号的种别码。扫描子程序主要部分流程如图3-2所示。 实验报告 班级：14 姓名： oneseven 学号： 一．题目：词法分析程序设计与实现 * 二．实验内容：设计并实现 C 语言的词法分析程序，要求如下。 (1) 可以识别出用C语言编写的源程序中的每个单词符号，并以记号的形式输出每个单词符号。 (2) 可以识别并读取源程序中的注释。 (3) 可以统计源程序中的语句行数、单词个数和字符个数，其中标点和空格不计算为单词，并输出统计结果。 (4) 检查源程序中存在的非法字符错误，并可以报告错误所在的行列位置。 三．实现要求：采用C/C++作为实现语言，手工编写词法分析程序。 ； 四．实现功能：基本完成了实验内容中要求的所有功能。(1)识别出源程序中的每个单词符号，并以记号的形式输出每个单词符号(2)识别并读取源程序中的注释(3) 统计源程序中的语句行数、单词个数和字符个数(4) 检查源程序中存在的非法字符错误，并可以报告错误所在的行列位置。 注：本程序未把注释中的单词符号，“”中的单词符号统计在单词个数中。单词个数只包括了标示符，关键字，无符号数。 五．实验原理： 1.词法分析程序的功能： 输入源程序，输出单词符号的记号形式，如图所示： > 源程序词法分析器单词符号的记号形式 词法分析器 2.处理过程：每次调用词法分析程序，它均能自动继续扫描下去，形成下一个单词，直至整个源程序全部扫描完毕，并形成相应的单词串形式的源程序。 六．代码 #include 实验内容： 可选择LL1分析法、算符优先分析法、LR分析法之一，实现如下表达式文法的语法分析器： （1）E→E+T | E-T | T （2）T→T*F | T/F | F （3）F→P^F | P （4）P→(E) | i 实验环境： Windows XP 实验分析： （1）定义部分：定义常量、变量、数据结构。 （2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； （3）控制部分：从键盘输入一个表达式符号串； （4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分 实验程序： #include {'r','r','s','r','r','r'}, {'r','r','r','r','r','r'}, {'r','r','r','r','r','r'} }; char snum[12][6]={//数字表 {5,1,1,4,2,1}, {3,6,5,3,2,0}, {2,2,7,2,2,2}, {4,4,4,4,4,4}, {5,1,1,4,2,1}, {6,6,6,6,6,6}, {5,1,1,4,2,1}, {5,1,1,4,2,1}, {3,6,5,3,11,4}, {1,1,7,1,1,1}, {3,3,3,3,3,3}, {5,5,5,5,5,5} }; int go2[12][3]={//goto表 {1,2,3}, {0,0,0}, {0,0,0}, {0,0,0}, {8,2,3}, {0,0,0}, {0,9,3}, {0,0,10}, {0,0,0}, {0,0,0}, {0,0,0}, {0,0,0} }; void action(int i,char *&a,char &how,int &num,char &A,int &b)//action函数[i,a] { int j; switch(*a) { case 'i': j=0;break; case '+': j=1;break; case '*': j=2;break; case '(': 语法分析器的设计 一、实验内容 语法分析程序用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编译原理词法分析器语法分析器实验报告
编译原理(语法分析程序设计)
编译原理实验报告实验一编写词法分析程序
语法分析程序的要求
编译原理词法分析和语法分析报告 代码(C语言版)
语义分析程序的设计与实现
编译原理实验报告《LL(1)语法分析器构造》
编译原理实验 (词法语法分析报告 附源代码
实验5 LL(1)语法分析程序的设计与实现(C语言)
实验1-3 《编译原理》词法分析程序设计方案
语法分析程序报告
编译原理课程设计(词法分析,语法分析,语义分析,代码生成)
语法分析程序实验报告及代码
编译原理实验词法分析语法分析
编译原理词法分析和语法分析报告+代码(C语言版)
北邮编译原理-词法分析文档和程序
语法分析C语言程序
编译原理语法分析器实验
相关主题
文本预览