编译原理语法分析程序.doc

该【编译原理语法分析程序 】是由【小城故事书屋】上传分享，文档一共【24】页，该文档可以免费在线阅读，需要了解更多关于【编译原理语法分析程序 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序编译原理实验报告题目:对下边的文法对象,使用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)文法的定义鉴识,也就是说文法中不含左递归和左公共因子,不过LL(1)文法的必需条件。LL(1)文法的定义(5种定义):编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序一个文法符号串的开始符号会集定义以下:=(VT,VN,S,P)是上下文没关文法,α是任意的文法符号串,FIRST(α)是从α推导出的串的开始符号的终结符会集。。。。FIRST(α)={a|α=*=>aβ,a∈VT,α,β∈V*}若α=*=>ε,则规定ε∈FIRST(α).当一个文法中同样左部非终结符的右部存在能=*=>ε的状况则一定知道该非终结符的后跟符号的会集中能否含有其他右部开始符号会集的元素。为此,我们定义一个文法非终结符的后跟符号的会集以下:=(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)编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序这里我们用'#'作为输入串的结束符,或称为句子括号,如:#输入串#。→α,A∈VN,α∈V*,若α==>ε,则编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序假如α=*=>ε,则SELECT(A→α)=FIRST(αε)∪FOLLOW(A)。FIRST(αε)表示编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序FIRST(α)的非{ε}元素。编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序更进一步可以看出可以使用自顶向下解析技术一定使文法满足以下条件,我们称满足条件的文法为LL(1)文法,其定义为:(1)文法的充分必需条件是:对每个非终结符A的两个不一样产生式,A→α,A→β,满足SELECT(A→α)∩SELECT(A→β)=空,此中α,(1)文法也可定义为:一个文法G是LL(1)的,当且仅当对于G的每一个非终结符A的任何两个不一样产生式A→α|β,下边的条件建立:①FIRST(α)∩FIRST(β)=空,也就是α和β推导不出以某个同样的终结符a为首的符号串;②若是βε那么,FIRST(α)∩FOLLOW(A)=空也就是,若βε则α所能推出的串的首符号不该在FOLLOW(A)中。二、算法该程序可分为以下几步:是LL(1)文法?(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),则输出方法:开始时,#S在解析栈中,此中第一个符号;repeatW的最左推导,不然报告错误。S是文法的开始符号,在栈顶;令指针ip指向W#的编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序让X等于栈顶符号,a为ip所指向的符号;ifX是终结符号或#then编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序IfX=athen把X从栈顶弹出并使ip指向下一个输入符号elseerror()else/*X是非终结符号*/ifM[x,a]=Xày1y2ykthenbegin从栈中弹出X;把yk,yk-1,,y1压入栈,y1在栈顶;输出产生式Xày1y2yk;endelseerror()untilX=#/*栈空*/语法解析的流程算法编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序三、设计目的:编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序(1)理解和掌握LL(1)语法解析方法的基根源理;依据给出的LL(1)文法,掌握LL(1)编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序解析表的构造及解析过程的实现。编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序(2)掌握展望解析程序如何使用解析表和栈联合控制实现LL(1)解析。编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序四、实现环境和要求编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序选择实****环境为486以上CPU,4M内存,语言.实现程序见附录.编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序详尽的实现要求:编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序(1)对输入文法,它能判断能否为LL(1)文法,若是,则转(2);不然报错并停止;(2)输入已知文法,由程序自动生成它的LL(1)解析表;(3)对于给定的输入串,应能判断鉴识该串能否为给定文法的句型。五、、要乞降解析,选择相应的数据构造,,,若另有余力者,可以对所选子集合适扩大或是增添相应功能如:扩大界符和保留字数量;同意实型常数;进行词法错误检查;,更加清楚透辟的理解了LL(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》主函数;*/(c)2005-6-30Author:陈强Allrightsreserved./*/#include<>#include<>#include<>intcount=0;/*分解的产生式的个数*/intnumber;/*全部终结符和非终结符的总数*/charstart;/*开始符号*/chartermin[50];/*终结符号*/charnon_ter[50];/*非终结符号*/charv[50];/*全部符号*/charleft[50];/*左部*/charright[50][50];/*右部*/charfirst[50][50],follow[50][50];/*各产生式右部的FIRST和左部的FOLLOW会集*/charfirst1[50][50];/*全部单个符号的FIRST会集*/charselect[50][50];/*各单个产生式的SELECT会集*/charf[50],F[50];/*记录各符号的FIRST和FOLLOW能否已求过*/charempty[20];/*记录可直接推出^的符号*/charTEMP[50];/*求FOLLOW时存放某一符号串的FIRST会集*/intvalidity=1;/*表示输入文法能否有效*/intll=1;/*表示输入文法能否为LL(1)文法*/intM[20][20];/*解析表*/charchoose;/*用户输入时使用*/charempt[20];/*求_emp()时使用*/charfo[20];/*求FOLLOW会集时使用*//*判断一个字符能否在指定字符串中/intin(charc,char*p){inti;if(strlen(p)==0)return(0);for(i=0;;i++){if(p[i]==c)return(1);/*若在,返回1*/编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序if(i==strlen(p))return(0);/*若不在,返回0*/}}/*获取一个不是非终结符的符号/charc(){charc='A';while(in(c,non_ter)==1)c++;return(c);}/*分解含有左递归的产生式/voidrecur(char*point){/*完好的产生式在point[]中*/intj,m=0,n=3,k;chartemp[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;}}}/*分解不含有左递归的产生式/voidnon_re(char*point){intm=0,j;chartemp[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;}/*读入一个文法/chargrammer(char*t,char*n,char*left,charright[50][50]){charvn[50],vt[50];chars;charp[50][50];inti,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("\ninputerror!");validity=0;return('\0');编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序}/*检测输入错误*/编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序for(k=0;k<=i-1;k++)编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序{/*分解输入的各产生式*/编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序if(p[k][3]==p[k][0])recur(p[k]);elsenon_re(p[k]);}return(s);}/*将单个符号或符号串并入另一符号串/voidmerge(char*d,char*s,inttype){/*d是目标符号串,s是源串,type=1,源串中的‘^’一并并入目串;type=2,源串中的‘^’不并入目串*/inti,j;for(i=0;i<=strlen(s)-1;i++){if(type==2&&s[i]=='^');else{for(j=0;;j++){if(j<strlen(d)&&s[i]==d[j])break;if(j==strlen(d)){d[j]=s[i];d[j+1]='\0';break;}}}}编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序}/*求全部能直接推出^的符号/voidemp(charc){/*即求全部由‘^’推出的符号*/chartemp[10];inti;for(i=0;i<=count-1;i++){if(right[i][0]==c&&strlen(right[i])==1){temp[0]=left[i];temp[1]='\0';merge(empty,temp,1);emp(left[i]);}}}/*求某一符号能否推出‘^’/int_emp(charc)编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序{/*若能推出,返回inti,j,k,result=1,mark=0;chartemp[20];temp[0]=c;temp[1]='\0';merge(empt,temp,1);if(in(c,empty)==1)return(1);for(i=0;;i++){1;不然,返回0*/编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序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);elseif(j==1&&in(right[i][0],termin)==1)return(0);else{编译原理语法解析程序编译原理语法解析程序编译原理语法解析程序