《实验4-算符优先分析法.doc》由会员分享，可在线阅读，更多相关《实验4-算符优先分析法.doc（16页珍藏版）》请在金锄头文库上搜索。
1、实验名称：实验任务：对下述描述算符表达式的算符优先文法GE,给出算符优先分析的实验结果。实验内容：有上下无关文法如下：E-E+T|E-T|TT-T*F|T/F|FF-(E)|i说明：优先关系矩阵的构造过程：1 = 关系由产生式 F-(E) 知 = FIRSTVT 集及 LASTVT 集FIRSTVT(E)= +,-,*,/,(,i FIRSTVT(F)= (,i FIRSTVT(T)= *,/,(,i LASTVT(E)= +,-,*,/,),i LASTVT(F)= ),i LASTVT(T)= *,/,),i (2) 关系+T则有：+ FIRSTVT(T)-T则有：- FIRSTVT(T)
2、*F则有：* FIRSTVT(F)学习文档 仅供参考/F则有：/ FIRSTVT(F)(E则有：( 关系E+则有： LASTVT(E) +E-则有： LASTVT(E) -T*则有： LASTVT(T) *T/则有： LASTVT(T) /E)则有： LASTVT(E) )(4)请大家画出优先关系矩阵终结符之间的优先关系是唯一的， 所以该文法是算符优先文法。 程序的功能描述：程序由文件读入字符串以#结束 ，然后进行算符优先分析，分析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输出移近规约过程。学习文档 仅供参考(5)依据文法和求出的相应 FirstVT 和 LastVT 集生成算符优先
3、分析表。 算法描述如下：for每个形如 P-X1X2Xn 的产生式dofor i =1 to n-1 dobeginif Xi 和 Xi+1 都是终结符 thenXi = Xi+1if i= n-2, Xi 和 Xi+2 是终结符, 但 Xi+1 为非终结符thenXi = Xi+2if Xi 为终结符, Xi+1 为非终结符 thenfor FirstVT 中的每个元素 a do Xi Xi+1end(6)构造总控程序算法描述如下：stack S; k = 1; /符号栈 S 的使用深度学习文档 仅供参考Sk = #REPEAT把下一个输入符号读进 a 中；If Sk VT thenj =
4、kelsej = k-1;While Sj a doBeginRepeatQ = Sj;if Sj-1 VT thenj = j-1elsej = j-2until Sj Q;把 Sj+1Sk归约为某个N，并输出归约为哪个符号；K = j+1;Sk = N;end of whileif Sj a or Sj = a thenbegin k = k+1; Sk = a end学习文档 仅供参考else error /调用出错诊察程序until a = #(7)代码如下：#include #include #include char data2020; /算符优先关系char s100; /模拟符
5、号栈 schar lable20; /文法终极符集char input100; /文法输入符号串char string2010; /用于输入串的分析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 集是否已求出
6、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 的 LASTVT 集void table(); /创建文法优先关系表void main()int i,j,k=0; printf(请输入文法规则数：);scanf(%d,&r);print
7、f(请输入文法规则：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(不是算符文法!n); exit(-1);if(stij=A&stij=A&stij+1=Z)printf(不是算符文法!n); exit(-1); for(i
8、=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 ,firstij+1);printf(n);学习文档 仅供参考printf(每个非终结符的LASTVT 集为：n); /输出每个非终结符的 LASTVT 集for(i=0;i
9、r;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(n);printf(请输入文法输入符号串以#结束:);scanf(%s,input);deal();void table()char text2010;int
10、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;elsetextxy=stij;y+;textxy=0;x+;y=0;r1=x;printf(转化后的文法为:n);for(i=0;ix;i+) /输出转化后的文法规则串printf(%sn,texti);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
11、=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=xiabiao(textij);n=xiabiao(textij+2);datamn=;if(zhongjie(textij)&!zhongjie(textij+1)for(k=0;kr;k+)if(stk0=textij+1)bre
12、ak;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);for(t=0;t;m=xiabiao(#);for(t=0;tfirst00;t+)学习文档 仅供参考n=xiabiao(first0t+1);datamn=;n=xiabiao(#);for(t=0;t;datann=;void firstvt(char c) /in
13、t i,j,k,m,n;for(i=0;ir;i+)if(sti0=c)break;if(fflagi=0)n=firsti0+1;m=0;doif(m=2|stim=|)if(zhongjie(stim+1)firstin=stim+1;n+;elseif(zhongjie(stim+2)firstin=stim+2;n+;if(stim+1!=c)firstvt(stim+1);学习文档 仅供参考求 FIRSTVT 集for(j=0;jr;j+)if(stj0=stim+1)break;for(k=0;kfirstj0;k+)int t;for(t=0;tn;t+)if(firstit=f
14、irstjk+1)break;if(t=n)firstin=firstjk+1;n+;m+;while(stim!=0);firstin=0;firsti0=-n;fflagi=1;void lastvt(char c) /求 LASTVT 集int i,j,k,m,n;for(i=0;ir;i+)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+;elseif(zhongjie(stim-1)lastin=stim-1;n+;if(
15、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);printf(规约n);doq=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+)学习文档 仅供参考
16、输入串的长度栈置初值计算输入串的长度 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; /输入串符合文法的定义elseif(dataxy=|dataxy=) /移进out(1,k,s);printf(%c,a);out(i+1,z,input);printf(移进n);k+;sk=a;i+;elseprintf(nflase);学习文档 仅供参考if(!zhongjie(sm)&!zhongjie(stringNn)if(zhongjie(sm
17、+1)&zhongjie(stringNn+1)&sm+1=stringNn+1)sj+1=stringN0; break; elseif(zhongjie(sm)if(sm=stringNn)sj+1=stringN0; break;return 0;printf(nflase);return 0;void out(int j,int k,char *s)int n=0;int i;for(i=j;i=k;i+)printf(%c,si);n+;for(;n15;n+)printf( );int xiabiao(char c) /int i;for(i=0;lablei!=0;i+)if(c=lablei)return i;return -1;int zhongjie(char c) /int i;for(i=0;lablei!=0;i+)if(c=lablei)return 1;return 0;求字符 c 在算符优先关系表中的下标判断字符 c 是否是终极符学习文档 仅供参考实验结果：学习文档 仅供参考
