实验4算符优先分析法..

1、实验名称：实验任务： 对下述描述算符表达式的算符优先文法GE,给出算符优先分析的实验结果。 实验内容：有上下无关文法如下：E->E+T|E-T|T T->T*F|T/F|F F->(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

2、 则有：+ < FIRSTVT(T) -T 则有：- < FIRSTVT(T) *F 则有：* < FIRSTVT(F) /F 则有：/ < FIRSTVT(F) (E 则有：( < FIRSTVT(E)(3) > 关系 E+ 则有： LASTVT(E) > + E- 则有： LASTVT(E) > - T* 则有： LASTVT(T) > * T/ 则有： LASTVT(T) > / E) 则有： LASTVT(E) > ) (4)请大家画出优先关系矩阵 终结符之间的优先关系是唯一的，所以该文法是算符优先文法。 程序的功能描述

3、： 程序由文件读入字符串（以#结束），然后进行算符优先分析，分析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输出移近规约过程。(5)依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。 算法描述如下： for 每个形如 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 中的每个元

4、素 a do Xi < a if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a > Xi+1 end(6)构造总控程序 算法描述如下： stack S; 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

5、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 = #(7)代码如下：#include "stdio.h"#include "stdlib.h"#include "iostream.h"char data2020; /算符优先关系char s100; /模拟符号栈s char lable20; /文法终极符集char

6、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集是否已求出int deal(); /对输入串的分析int zhongjie(ch

7、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(); /创建文法优先关系表void main()int i,j,k=0; printf("请输入文法规则数：");scanf("%d",&r);printf("请输入文法规则：n&quo

8、t;);for(i=0;i<r;i+)scanf("%s",sti); /存储文法规则，初始化FIRSTVT集和LASTVT集*/ firsti0=0; /*firsti0和lasti0分别表示sti0非终极符的FIRSTVT集和LASTVT集中元素的个数*/lasti0=0;for(i=0;i<r;i+) /判断文法是否合法for(j=0;stij!='0'j+)if(sti0<'A'|sti0>'Z')printf("不是算符文法!n"); exit(-1);if(stij>

9、;='A'&&stij<='Z') if(stij+1>='A'&&stij+1<='Z')printf("不是算符文法!n"); exit(-1); for(i=0;i<r;i+)for(j=0;stij!='0'j+)if(stij<'A'|stij>'Z')&&stij!='-'&&stij!='>'&&s

10、tij!='|')lablek+=stij;lablek='#'lablek+1='0' table();printf("每个非终结符的FIRSTVT集为：n"); /输出每个非终结符的FIRSTVT集for(i=0;i<r;i+)printf("%c: ",sti0);for(j=0;j<firsti0;j+)printf("%c ",firstij+1);printf("n");printf("每个非终结符的LASTVT集为：n")

11、; /输出每个非终结符的LASTVT集for(i=0;i<r;i+)printf("%c: ",sti0);for(j=0;j<lasti0;j+)printf("%c ",lastij+1);printf("n");printf("算符优先分析表如下:n");for(i=0;lablei!='0'i+) printf("t%c",lablei);printf("n"); for(i=0;i<k+1;i+)printf("%ct&q

12、uot;,lablei);for(j=0;j<k+1;j+)printf("%ct",dataij);printf("n");printf("请输入文法输入符号串以#结束:");scanf("%s",input); deal();void table()char text2010;int i,j,k,t,l,x=0,y=0;int m,n;x=0;for(i=0;i<r;i+)firstvt(sti0);lastvt(sti0);for(i=0;i<r;i+)textxy=sti0;y+;for(

13、j=1;stij!='0'j+)if(stij='|')textxy='0'x+;y=0;textxy=sti0;y+;textxy+='-'textxy+='>'elsetextxy=stij;y+;textxy='0'x+;y=0;r1=x;printf("转化后的文法为:n");for(i=0;i<x;i+) /输出转化后的文法规则串printf("%sn",texti);for(i=0;i<x;i+) /*求每个终结符的推导结果(去掉

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

15、&&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;k<r;k+)if(stk0=textij+1)break;m=xiabiao(textij);for(t=0;t<firstk0;t+)n=xiabiao(firstkt+1);datamn=&#

16、39;<'if(!zhongjie(textij)&&zhongjie(textij+1)for(k=0;k<r;k+)if(stk0=textij)break;n=xiabiao(textij+1);for(t=0;t<lastk0;t+)m=xiabiao(lastkt+1);datamn='>'m=xiabiao('#');for(t=0;t<first00;t+)n=xiabiao(first0t+1);datamn='<'n=xiabiao('#');for(t

17、=0;t<last00;t+)m=xiabiao(last0t+1);datamn='>'datann='='void firstvt(char c) /求FIRSTVT集int i,j,k,m,n;for(i=0;i<r;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

18、)firstvt(stim+1);for(j=0;j<r;j+)if(stj0=stim+1)break;for(k=0;k<firstj0;k+)int t;for(t=0;t<n;t+)if(firstit=firstjk+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;i<r;i+)if(sti0=c)bre

19、ak;if(lflagi=0)n=lasti0+1;m=0;doif(stim+1='0'|stim+1='|')if(zhongjie(stim)lastin=stim;n+;elseif(zhongjie(stim-1)lastin=stim-1;n+;if(stim!=c)lastvt(stim);for(j=0;j<r;j+)if(stj0=stim)break;for(k=0;k<lastj0;k+)int t;for(t=0;t<n;t+)if(lastit=lastjk+1)break;if(t=n)lastin=lastjk+1

20、;n+;m+;while(stim!='0');lastin='0'lasti0=-n;lflagi=1;int deal()int i,j;int x,y;int z; /输入串的长度k=1;sk='#' /栈置初值for(i=0;inputi!='0'i+); /计算输入串的长度z=i-;i=0;while(a=inputi)!='0')if(zhongjie(sk)j=k;elsej=k-1;x=xiabiao(sj);y=xiabiao(a);if(dataxy='>')out(1,k

21、,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;N<r1;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; elseif(zhongjie(sm)if(sm=stringNn)sj+1=stringN0; break; k=j+