实验3算符优先分析算法的设计与实现(优.选)

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

2、/5) 输出：错误 三、实验步骤 1 、参考数据结构 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 集。 算符描述如下： /* 求

3、 FirstVT 集的算法 */ PROCEDURE insert(P,a); IF not FP,a then begin FP,a = true; /(P,a) 进栈 end; Procedure FirstVT; Begin for 对每个非终结符 P 和终结符 a do FP,a = false for 对每个形如 Pa或P tQa的产生式 do Insert(P,a) while stack非空 begin 栈顶项出栈，记为 (Q,a) for 对每条形如 P t Q的产生式 do insert(P,a) end; end. 同理，可构造计算 LASTVT 的算法。 3 、构造算符优

4、先分析表 依据文法和求出的相应 FirstVT 和 LastVT 集生成算符优先分析表。 算法描述如下： for 每个形如 P-X 1X2Xn的产生式 do for i =1 to n-1 do begin if X i 和 Xi +1 都是终结符 then X i = X i +1 then if i= n-2, Xi 和 Xi +2 是终结符 , 但 Xi +1 为非终结符 X i = X i +2 if X i 为终结符 , X i +1 为非终结符 then for FirstVT中的每个元素 a do Xi Xi+1 ; end 4 、构造总控程序 算法描述如下： stack S;

5、k = 1; /符号栈S的使用深度 Sk =# REPEAT 把下一个输入符号读进 a 中； If Sk VT then j = k else j = k-1; While Sj a do Begin Repeat Q = Sj; if Sj-1 VT then j = j-1 else j = j-2 until Sj Q; 把Sj+1-Sk归约为某个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 =

6、# 5 、对给定的表达式，给出准确与否的分析过程 6 、给出表达式的计算结果。 （本步骤可选作） 四、实验报告要求 1. 写出编程思路、源代码（或流程图） ; 2. 写出上机调试时发现的问题，以及解决的过程; 3. 写出你所使用的测试数据及结果; 4. 谈谈你的体会。 5. 上机 8 小时，完成实验报告 2 小时。 程序代码 : #include #include #include char data2020; / 算符优先关系 char s100; / 模拟符号栈 s char lable20; / 文法终结符集 char input100; / 文法输入符号串 char string201

7、0; int k; char a; int j; char q; / 用于输入串的分析 int r; / 文法规则个数 int r1; / 转化后文法规则个数 char st1030; / 用来存储文法规则 char first1010; / 文法非终结符 FIRSTVT 集 char last1010; / 文法非终结符 LASTVT 集 int fflag10=0; 已求出 / 标志第 i 个非终结符的 FIRSTVT 集是否 int lflag10=0; 求出 / 标志第 i 个非终结符的 LASTVT 集是否已 int deal(); / 对输入串的分析 int zhongjie(ch

8、ar 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 的 LASTVT 集 void table(); int main() int i,j,k=0; / 创建文法优先关系表 printf( 请输入文法规则数： ); scanf(%d, printf( 请输入文法规则 for(i=0;ir;i

9、+) ： n); 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( 不是算符文法 !n); exit(-1); if(stij=A exit(-1); for(i=0;ir;i+) for(j=0;stij!=0;j+) if(stijZ) lab

10、lek=#; lablek+1=0; table(); FIRSTVT LASTVT 集 printf( 每个非终结符的 FIRSTVT 集为： n); / 输出每个非终结符的 集 for(i=0;ir;i+) printf(%c: ,sti0); for(j=0;jfirsti0;j+) printf(%c ,firstij+1); printf(n); printf( 每个非终结符的 LASTVT 集为： n); / 输出每个非终结符的 for(i=0;ir;i+) printf(%c: ,sti0); for(j=0;jlasti0;j+) printf(%c ,lastij+1); p

11、rintf(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(n); #结束 :); printf( 请输入文法输入符号串以 scanf(%s,input); getchar(); deal();system(pause); void table() char text2010; int i,j,k,t,l,x=0,y=0; in

12、t 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); for(i=0;ix;i+) /* 后的转化文法，用于最后的规约 )*/ stringi0=texti0; for(j=3,l=1;textij!=0;j+,l+) stringil=textij

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

14、stk0=textij) break; n=xiabiao(textij+1); for(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(zhongji

15、e(stim+1) firstin=stim+1; n+; else if(zhongjie(stim+2) firstin=stim+2; n+; if(stim+1!=c) firstvt(stim+1); for(j=0;j!.E=_=SO=IIM 宀 +E 匸+u XL+=1SU=U=1S匸 (UUILM 宀 (-兰=紅斤二巴 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+) i

16、nt t; for(t=0;t) out(1,k,s); printf(%c,a); out(i+1,z,input); printf( 规约 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) break; else if(zhongjie(sm) if(sm=stringNn) sj+1=stringN0; break; k=j+1; if(k=2 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