算符优先分析方法.doc

目录1.课程设计的目的与原理11.1设计目的11.2设计原理12.课程设计环境13.课程设计内容23.1算符优先分析流程图23.2算符优先总流程图33.3算符优先文法43.4 程序调试54.总结6附录624算符优先分析方法.课程设计目的与原理1.1设计目的1. 了解利用算符优先算法进行移进规约分析的方法。2. 锻炼和提高自己的编程能力。3. 熟悉编译原理语法分析的方法，加深对算符优先基本方法的了解。4. 进一步理解编译原理，更好的的学习它的思路，掌握编译原理的理论基础。5. 了解算符优先分析和规范规约的不同以及优缺点。1.2设计原理算符优先分析方法是根据算符之间的优先关系而设计的一种自底向上的语法分析方法。算符优先分析的基本思想是只规定算符之间的优先关系，也就是只考虑终结符之间的优先关系。由于算符优先分析不考虑非终结符之间的优先关系，在归约过程中只要找到可归约串就归约，并不考虑归约到哪个非终结符，因而算符优先归约不是规范归约。.课程设计环境 1.硬件运行环境：Windows XP 2.软件运行环境：VC+ 6.0版本.课程设计内容3.1算符优先分析流程图k:=k+1sk=a置初值块：k:=1，sk:=”#”下一个输入符读入askVTYNj:=kj:=k-1sja?Q:=sjsja?sj-1 VTYNj:=j-1j:=j-1sjE+TE-TT-T*FT-FF-(E)F-i计算FIRSTVE和LASTVT集合FirstVT(E)=+,*,(,i LastVT(E)=+,*,),iFirstVT(T)=*,(,i LastVT(T)=*,),iFirstVT(F)=(,i LastVT(F)=),iFirstVT(Q)=# LastVT(Q)=#构造算符优先矩阵+*()i#+*(=i#=对于输入串i+i*i+i#的手动分析过程：步骤符号栈当前符号+剩余输入串移进或归约0#i+ i*i+i #预备1#i+i*i+i #移进2#N+i*i+i #归约3#N+i*i+i #移进4#N+i*i+i #移进5#N+N*i+i #归约6#N+N*i+i #移进7#N+N*i+i #移进8#N+N*N+i #归约9#N+N+i#归约10#N+i#归约11#N+i#移进12#N+i #移进13#N+N#归约14#N#归约15#N#接受见附录3.4程序调试例：1、输入产生式的个数：2、输入文法：3、判断文法4、生成非终结符的FIRSTVT集和LASTVT集：5、生成算符优先分析表：5、输入字符串进行分析：输出结果与自己做的结果一模一样，说明设计成功。.总结经过此次编译课程设计，使我对算符优先分析有了更深更进一步的理解，而且也锻炼了自己的程序编码能力，对自己今后的道路影响不小。当然还有不足之处以后会慢慢改进。在试验过程中，我忘记在程序最后面加上一句getchar();，导致我试验时，直接运行.exe文件，当运行到最后输入归约字符串时，执行完后界面自动关闭，导致我不能截图，经过不屑的努力，有两种解决方法，第一可以用VC软件运行，界面就不会关闭。第二种是在程序里加上getchar();，.exe文件运行到最后就不会自动关闭。附录#include#include#includetypedef structchar R;char r;int flag;array;typedef struct char E;char e;charLode;typedef struct charLode *base; int top;charstack;char str8080,arr8080,brr8080;array F20;int m,kk,p,ppp,FF=1;char r10;int crr2020,FLAG=0;char ccrr1120,ccrr2201;void Initstack(charstack &s)/定义栈s.base=new charLode20; s.top=-1;void push(charstack &s,charLode w) s.top+; s.bases.top.E=w.E; s.bases.top.e=w.e;void pop(charstack &s,charLode &w) w.E=s.bases.top.E; w.e=s.bases.top.e; s.top-;int IsEmpty(charstack s)if(s.top=-1) return 1;else return 0;int IsLetter(char ch) if(ch=A&ch=Z) return 1; else return 0;/judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法int judge1(int n)int j=3,flag=0;for(int i=0;i=n;i+) while(strij!=0) char a=strij; char b=strij+1; if(IsLetter(a)&IsLetter(b) flag=1;break;else j+; if(flag=1) return 0; else return 1;/judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法void judge2(int n)for(int i=0;i=n;i+) if(stri3=|judge1(n)=0|FLAG=1)/代表空字 cout该文法不是算符优先文法!n) cout该文法是算符优先文法!endl;/search1是查看存放终结符的数组r中是否含有重复的终结符int search1(char r,int kk,char a)for(int i=0;ikk;i+) if(ri=a) break; if(i=kk) return 0; else return 1;/createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体void createF(int n)int k=0,i=1;char g;char t10;/t数组用来存放非终结符t0=str00;while(i=n) if(tk!=stri0) k+;tk=stri0;g=tk;i+; else i+;kk=0; char c;for(i=0;i=n;i+) int j=3; while(strij!=0) c=strij; if(IsLetter(c)=0) if(!search1(r,kk,c) rkk=c;kk+;/r数组用来存放终结符 j+; m=0;for(i=0;ik;i+) for(int j=0;jkk-1;j+) Fm.R=ti; Fm.r=rj; Fm.flag=0; m+; /search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1void search(charLode w)for(int i=0;im;i+) if(Fi.R=w.E&Fi.r=w.e) Fi.flag=1;break;void FirstVT(int n)/求FirstVTcharstack sta;charLode w;int i=0;Initstack(sta);while(i=n) int k=3; w.E=stri0; char a=strik; char b=strik+1; if(!IsLetter(a)/产生式的后选式的第一个字符就是终结符的情况 w.e=a; push(sta,w); search(w); i+; else if(IsLetter(a)&b!=0&!IsLetter(b)/产生式的后选式的第一个字符是非终结符的情况 w.e=b; push(sta,w); search(w); i+; else i+;charLode ww;while(!IsEmpty(sta) pop(sta,ww); for(i=0;i=n;i+) w.E=stri0; if(stri3=ww.E&stri4=0) w.e=ww.e; push(sta,w); search(w); break; p=0;int k=1;i=1;while(im) if(Fi-1.flag=1) arrp0=Fi-1.R; arrpk=Fi-1.r; while(Fi.flag=0&im) i+; if(Fi.flag=1) if(Fi.R=arrp0) k+; else arrpk+1=0;p+;k=1; i+; void LastVT(int n)/求LastVTcharstack sta;charLode w;for(int i=0;im;i+) Fi.flag=0;i=0;Initstack(sta);while(i=n) int k=strlen(stri); w.E=stri0; char a=strik-1; char b=strik-2; if(!IsLetter(a) w.e=a; push(sta,w); search(w); i+; else if(IsLetter(a)&!IsLetter(b) w.e=b; push(sta,w); search(w); i+; else i+;charLode ee;while(!IsEmpty(sta) pop(sta,ee); for(i=0;i=n;i+) w.E=stri0; if(stri3=ee.E&stri4=0) w.e=ee.e; push(sta,w); search(w); int k=1;i=1;ppp=0;while(im) if(Fi-1.flag=1) brrppp0=Fi-1.R; brrpppk=Fi-1.r; while(Fi.flag=0&im) i+; if(Fi.flag=1) if(Fi.R=arrppp0) k+; else brrpppk+1=0;ppp+;k=1; i+; void createYXB(int n)/构造优先表int i,j; for(j=1;j=kk;j+) ccrr10j=rj-1;for( i=1;i=kk;i+) ccrr2i0=ri-1;for(i=1;i=kk;i+) for(j=1;j=kk;j+) crrij=0; int I=0,J=3; while(I=n) if(strIJ+1=0) I+;J=3; else while(strIJ+1!=0) char aa=strIJ; char bb=strIJ+1; if(!IsLetter(aa)&!IsLetter(bb)/优先及等于的情况，用1值表示等于 for(i=1;i=kk;i+) if(ccrr2i0=aa) break; for(j=1;j=kk;j+) if(ccrr10j=bb) break; if(crrij=0) crrij=1; else FLAG=1;I=n+1; J+; if(!IsLetter(aa)&IsLetter(bb)&strIJ+2!=0&!IsLetter(strIJ+2)/优先及等于的情况 for(i=1;i=kk;i+) if(ccrr2i0=aa) break; for(int j=1;j=kk;j+) if(ccrr10j=strIJ+2) break; if(crrij=0) crrij=1; else FLAG=1;I=n+1; if(!IsLetter(aa)&IsLetter(bb)/优先及小于的情况，用2值表示小于 for(i=1;i=kk;i+) if(aa=ccrr2i0) break; for(j=0;j=p;j+) if(bb=arrj0) break; for(int mm=1;arrjmm!=0;mm+) for(int pp=1;pp=kk;pp+) if(ccrr10pp=arrjmm) break; if(crripp=0) crripp=2; else FLAG=1;I=n+1; J+; if(IsLetter(aa)&!IsLetter(bb)/优先及大于的情况，用3值表示大于 for(i=1;i=kk;i+) if(ccrr10i=bb) break; for(j=0;j=ppp;j+) if(aa=brrj0) break; for(int mm=1;brrjmm!=0;mm+) for(int pp=1;pp=kk;pp+) if(ccrr2pp0=brrjmm) break; if(crrppi=0) crrppi=3; else FLAG=1;I=n+1; J+; /judge3是用来返回在归约过程中两个非终结符相比较的值int judge3(char s,char a)int i=1,j=1;while(ccrr2i0!=s) i+;while(ccrr10j!=a) j+;if(crrij=3) return 3;else if(crrij=2) return 2;else if(crrij=1) return 1;else return 0;void print(char s,char STR20,int q,int u,int ii,int k)/打印归约的过程coutu ;for(int i=0;i=k;i+) coutsi;cout ;for(i=q;i=ii;i+) coutSTR0i;cout ;void process(char STR20,int ii)/对输入的字符串进行归约的过程 cout步骤 符号栈 输入串 动作endl;int k=0,q=0,u=0,b,i,j;char s40,a;sk=#;print(s,STR,q,u,ii,k);cout预备endl;k+;u+; sk=STR0q;q+;print(s,STR,q,u,ii,k);cout移进endl;while(q=ii) a=STR0q; if(!IsLetter(sk) j=k; else j=k-1; b=judge3(sj,a); if(b=3)/大于的情况进行归约 while(IsLetter(sj-1) j-; for(i=j;i=k;i+) si=0; k=j;sk=N;u+; print(s,STR,q,u,ii,k); cout归约endl; else if(b=2|b=1)/小于或等于的情况移进 k+; sk=a; u+; q+; print(s,STR,q,u,ii,k); if(s0=#&s1=N&s2=#) cout接受endl; else cout移进endl; else cout出错endl;break;if(s0=#&s1=N&s2=#) cout归约成功endl;else cout归约失败endl;void main()int n,i,j;cout*欢迎使用算符优先分析算法模拟器* endl;coutn;for(i=0;i;stri3=#;stri4=str00;stri5=#; stri6=0;cout您定义的产生式如下:endl; for(i=0;i=n;i+) coutstriendl;if(judge1(n)=0)/判断文法G是否为算符文法 cout文法G不是算符文法!endl;if(j