实验三-算符优先分析算法的设计与实现(共17页).doc

《实验三-算符优先分析算法的设计与实现(共17页).doc》由会员分享，可在线阅读，更多相关《实验三-算符优先分析算法的设计与实现(共17页).doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上实验三 算符优先分析算法的设计与实现（8学时）一、 实验目的根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。二、 实验要求1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）： EE+T|E-T|TTT*F|T/F|FF（E）|i2、对给定表达式进行分析，输出表达式正确与否的判断。程序输入/输出示例：输入：1+2;输出：正确输入：(1+2)/3+4-(5+6/7);输出：正确输入：(1-2)/3+4输出：错误输入：1+2-3+(*4/5)输出：错误三、实验步骤1、参考

2、数据结构char *VN=0,*VT=0;/非终结符和终结符数组char firstvtNN,lastvtNN,tableNN;typedef struct /符号对(P,a)char Vn;char Vt; VN_VT;typedef struct /栈 VN_VT *top; VN_VT *bollow; int size;stack;2、根据文法求FIRSTVT集和LASTVT集给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的FirstVT 集和LastVT 集。算符描述如下：/*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF n

3、ot FP,a then begin FP,a = true; /(P,a)进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P和终结符 a do FP,a = false for 对每个形如 Pa或 PQa的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈，记为(Q,a) for 对每条形如 PQ的产生式 do insert(P,a) end; end.同理，可构造计算LASTVT的算法。3、构造算符优先分析表依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。算法描述如下：for 每个形

4、如 P-X1X2Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi Xi+1 ; end4、构造总控程序 算法描述如下： stack S; k = 1; /符号栈S的使用深度 Sk = # REPEAT 把下一个输入符号读进a中； If Sk VT then j = k else j = k-1; While

5、 Sj a do Begin Repeat Q = Sj; if Sj-1 VT then j = j-1 else j = j-2 until Sj Q; 把Sj+1Sk归约为某个N，并输出归约为哪个符号； K = j+1; Sk = N; end of while if Sj a or Sj = a then begin k = k+1; Sk = a end else error /调用出错诊察程序 until a = #5、对给定的表达式，给出准确与否的分析过程6、给出表达式的计算结果。（本步骤可选作）四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，

6、以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。5.上机8小时，完成实验报告2小时。五、源代码 #include#include#includetypedef structchar R;char r;int flag;array;typedef struct char E;char e;charLode;typedef structcharLode *base;int top;charstack;char str8080,arr8080,brr8080;array F20;int m,kk,p,ppp,FF=1;char r10;int crr2020,FLAG=0;cha

7、r 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

8、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)

9、/根据flag设定返回值return 0;elsereturn 1;/judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法void judge2(int n)for(int i=0;i=n;i+)if(stri3=|FLAG=1)/代表空cout文法G不是算符优先文法!n)cout文法G是算符优先文法!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

10、 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数组用来存

11、放终结符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=

12、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);se

13、arch(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

14、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.fl

15、ag=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;

16、elsewhile(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(

17、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(crri

18、pp=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是用来返回在归约过程中两个非终结符相比较的值

19、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 p

20、rocess(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

21、;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;coutn;cout请输入文法产生式：endl;for(i=0;i;stri3=#;stri

22、4=str00;stri5=#;cout你定义的产生式如下:endl;stri6=0;for(i=0;i=n;i+)coutstriendl;if(judge1(n)=0)/判断文法G是否为算符文法cout文法G不是算符文法!endl;if(judge1(n)=1)cout文法G是算符文法!endl;createF(n);FirstVT(n);LastVT(n);createYXB(n);for(i=0;i=p;i+)/打印FirstVTcoutFirstVT(arri0)=;for(int l=1;arril+1!=0;l+)coutarril,;coutarrilendl;coutFirstVT(Q)=#endl; for(i=0;i=ppp;i+)/打印LastVTcoutLastVT(arri0)=;for(int l=1;brril+1!=0;l+)coutbrril,;coutbrrilendl;coutLastVT(Q)=#endl;cout优先表如下:endl;for(i=1;ikk;i+)/打印优先关系表