实验3 算符优先分析算法的设计与实现

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、参考数据结构char *VN=

2、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 not FP,a then

3、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 每个形如 P-X1X2Xn的产生

4、式 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 Sj a do Begi

5、n 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.写出上机调试时发现的问题，以及解决的过程；3.写出你

6、所使用的测试数据及结果；4.谈谈你的体会。5.上机8小时，完成实验报告2小时。程序代码:#include#include #include char data2020; /算符优先关系char s100; /模拟符号栈s char lable20; /文法终结符集char input100; /文法输入符号串char string2010; /用于输入串的分析int k; char a; int j; char q; int r; /文法规则个数int r1; /转化后文法规则个数char st1030; /用来存储文法规则char first1010; /文法非终结符FIRSTVT集char

7、 last1010; /文法非终结符LASTVT集int fflag10=0; /标志第i个非终结符的FIRSTVT集是否已求出int lflag10=0; /标志第i个非终结符的LASTVT集是否已求出int deal(); /对输入串的分析int zhongjie(char c); /判断字符c是否是终结符int xiabiao(char c); /求字符c在算符优先关系表中的下标void out(int j,int k,char *s); /打印s栈void firstvt(char c); /求非终结符c的FIRSTVT集void lastvt(char c); /求非终结符c的LAS

8、TVT集void table(); /创建文法优先关系表int main()int i,j,k=0; printf(请输入文法规则数：);scanf(%d,&r);printf(请输入文法规则：n);for(i=0;ir;i+) scanf(%s,sti); /存储文法规则，初始化FIRSTVT集和LASTVT集*/ firsti0=0; /*firsti0和lasti0分别表示sti0非终结符的FIRSTVT集和LASTVT集中元素的个数*/ lasti0=0;for(i=0;ir;i+) /判断文法是否合法 for(j=0;stij!=0;j+) if(sti0Z) printf(不是算符

9、文法!n); exit(-1); if(stij=A&stij=A&stij+1=Z) printf(不是算符文法!n); exit(-1); for(i=0;ir;i+) for(j=0;stij!=0;j+) if(stijZ)&stij!=-&stij!=&stij!=|) lablek+=stij; lablek=#;lablek+1=0; table();printf(每个非终结符的FIRSTVT集为：n); /输出每个非终结符的FIRSTVT集for(i=0;ir;i+) printf(%c: ,sti0); for(j=0;jfirsti0;j+) printf(%c ,firs

10、tij+1); printf(n);printf(每个非终结符的LASTVT集为：n); /输出每个非终结符的LASTVT集for(i=0;ir;i+) printf(%c: ,sti0); for(j=0;jlasti0;j+) printf(%c ,lastij+1); printf(n);printf(算符优先分析表如下:n);for(i=0;lablei!=0;i+) printf(t%c,lablei);printf(n); for(i=0;ik+1;i+) printf(%ct,lablei); for(j=0;jk+1;j+) printf(%ct,dataij); printf

11、(n);printf(请输入文法输入符号串以#结束:);scanf(%s,input); getchar(); deal();system(pause);void table()char text2010;int i,j,k,t,l,x=0,y=0;int m,n;x=0;for(i=0;ir;i+) firstvt(sti0); lastvt(sti0);for(i=0;i; else textxy=stij; y+; textxy=0; x+; y=0;r1=x;printf(转化后的文法为:n);for(i=0;ix;i+) /输出转化后的文法规则串 printf(%sn,texti);

12、for(i=0;i后的转化文法，用于最后的规约)*/ stringi0=texti0; for(j=3,l=1;textij!=0;j+,l+) stringil=textij; stringil=0;for(i=0;ix;i+) for(j=1;textij+1!=0;j+) if(zhongjie(textij)&zhongjie(textij+1) m=xiabiao(textij); n=xiabiao(textij+1); datamn=; if(textij+2!=0&zhongjie(textij)&zhongjie(textij+2)&!zhongjie(textij+1) m

13、=xiabiao(textij); n=xiabiao(textij+2); datamn=; if(zhongjie(textij)&!zhongjie(textij+1) for(k=0;kr;k+) if(stk0=textij+1) break; m=xiabiao(textij); for(t=0;tfirstk0;t+) n=xiabiao(firstkt+1); datamn=; if(!zhongjie(textij)&zhongjie(textij+1) for(k=0;kr;k+) if(stk0=textij) break; n=xiabiao(textij+1); fo

14、r(t=0;t; m=xiabiao(#);for(t=0;tfirst00;t+) n=xiabiao(first0t+1); datamn=;n=xiabiao(#);for(t=0;t;datann=;/*求FIRSTVT集*/void firstvt(char c) int i,j,k,m,n;for(i=0;ir;i+) if(sti0=c) break;if(fflagi=0) n=firsti0+1; m=0; do if(m=2|stim=|) if(zhongjie(stim+1) firstin=stim+1; n+; else if(zhongjie(stim+2) fi

15、rstin=stim+2; n+; if(stim+1!=c) firstvt(stim+1); for(j=0;jr;j+) if(stj0=stim+1) break; for(k=0;kfirstj0;k+) int t; for(t=0;tn;t+) if(firstit=firstjk+1) break; if(t=n) firstin=firstjk+1; n+; m+; while(stim!=0); firstin=0; firsti0=-n; fflagi=1;/*求LASTVT集*/void lastvt(char c) int i,j,k,m,n;for(i=0;ir;i

16、+) if(sti0=c) break;if(lflagi=0) n=lasti0+1; m=0; do if(stim+1=0|stim+1=|) if(zhongjie(stim) lastin=stim; n+; else if(zhongjie(stim-1) lastin=stim-1; n+; if(stim!=c) lastvt(stim); for(j=0;jr;j+) if(stj0=stim) break; for(k=0;klastj0;k+) int t; for(t=0;t) out(1,k,s); printf(%c,a); out(i+1,z,input); pr

17、intf(规约n); do q=sj; if(zhongjie(sj-1) j=j-1; else j=j-2; x=xiabiao(sj); y=xiabiao(q); while(dataxy!=); int m,n,N; for(m=j+1;m=k;m+) for(N=0;Nr1;N+) for(n=1;stringNn!=0;n+) if(!zhongjie(sm)&!zhongjie(stringNn) if(zhongjie(sm+1)&zhongjie(stringNn+1) &sm+1=stringNn+1) sj+1=stringN0; break; else if(zhon

18、gjie(sm) if(sm=stringNn) sj+1=stringN0; break; k=j+1; if(k=2&a=#) out(1,k,s); printf(%c,a); out(i+1,z,input); printf(结束n); printf(输入串符合文法的定义！n); return 1; /输入串符合文法的定义 else if(dataxy=|dataxy=) /移进 out(1,k,s); printf(%c,a); out(i+1,z,input); printf(移进n); k+; sk=a; i+; else return 0; printf(nflase);system(pause); return 0;void out(int j,int k,char *s) /从栈