编译原理之OPG实验报告

1、编译原理之算符优先文法分析*学院1105班安雨雅 班级：11* 学号：11*20实验 语法分析实验报告1、 实验题目 算符优先文法分析程序2、 实验内容及要求（1）根据给定文法，先求出FirstVt和LastVt集合，构造算符优先关系表（要求算符优先关系表输出到屏幕和文件）；（2）根据算法和优先关系表分析给定表达式是否是该文法识别的正确的算术表达式（要求输出归约过程）（3）给定表达式文法为：(OPG文件中还有其他文法可作为测试)BBoT|TTTaF|FFnF|(B)|t|f（4）分析的句子为: ntofat#3、 设计思想之重点：v 构造算符优先表：求FirstVT集和LastVT集判断是否是

2、算符文法判断是否是算符优先文法v 算符优先分析： I、求最左素短语II、根据算符优先分析表分析 （“”时归约）stack4、 程序源代码（C语言）#include stdio.h#include string.h#include stdlib.h#define STR_MAX 80/串的最大长度#define MAX_NUM 100 /符号的最大个数#define MAX 32767/文件中符号的最大个数#define N 20 /栈的长度class stack/符号栈private:char sN;int top;public:stack();void push(char);void pop

3、();int TOP();/返回top的值char *S();/返回s的值;stack:stack()top=-1; void stack:push(char ch)/进栈操作s+top=ch;stop+1=0;void stack:pop()/出栈操作top-; int stack:TOP()/返回top的值return top; char * stack:S()/返回s的值return s; OG & OPGchar MMAX_NUMMAX_NUM;struct PRO/产生式类型char left;char rightSTR_MAX;struct VNstruchar vn;char f

4、irstVTMAX_NUM;char lastVTMAX_NUM;char SOURSTR_MAX;/源文件名char OBJSTR_MAX;/目标文件名char ERRSTR_MAX;/错误信息文件名FILE *INF;/源程序文件指针FILE *OUTF;/分析结果文件指针FILE *ERRF;/错误信息文件指针char OGMAX;/存放上下文无关文法int OGlen;/上下文无关文法长度VNstru VNMAX_NUM;/非终结符数组int VN_CNT;/非终结符个数char VTMAX_NUM;/终结符数组int VT_CNT;/终结符个数char S0;/开始符号PRO PMA

5、X_NUM;/产生式数组int P_CNT;/产生式个数bool isIN(char ch,VNstru arr);/判别符号ch是否在arr数组中int isVN(char ch);/判别符号ch是否在VN数组中,存在则返回下标,否则返回-1int isVT(char ch);/判别符号ch是否在VT数组中,存在则返回下标,否则返回-1void getOG();/从源文件取得OG文法串void getVN_VT_S_P();/从OG文法提取VN,VT,S,Pvoid FirstVT(char ch,char firstVT);/求FirstVT集firstVTvoid LastVT(char

6、 ch,char lastVT);/求LastVT集lastVTbool O_G();/判别是否是OG文法bool O_P_G();/判别是否是OPG文法void leftphase(char str,char substr,char a);/求最左素短语substrvoid left_str(char w,char subw,int ip);/求剩余输入串subwOG & OPGbool isIN(char ch,VNstru arr)/判别符号ch是否在arr数组中for(int i=0;iVN_CNT;i+)if(ch=arri.vn) return 1;return 0;int isV

7、N(char ch)/判别符号ch是否在VN数组中,存在则返回下标,否则返回-1for(int i=0;iVN_CNT;i+)if(ch=VNi.vn)return i;return -1;int isVT(char ch)/判别符号ch是否在VT数组中,存在则返回下标,否则返回-1for(int i=0;iVT_CNT;i+)if(ch=VTi) return i;return -1;void getOG()/从源文件取得OG文法串OGlen=0;char ch;while(!feof(INF)ch=fgetc(INF);OG & OPGif(ch!=)OGOGlen+=ch;OGOGlen

8、=0;printf(The Grammar is :n);/将文法输出到屏幕puts(OG);fprintf(OUTF,The Grammar is :n);fputs(OG,OUTF);/将文法输出到文件void getVN_VT_S_P()/从OG文法提取VN,VT,S,PVN_CNT=0;VT_CNT=0;P_CNT=0;int newPF=0;/是否进入新产生式的标志int rightLen=0;char prech,ch,nextch;for(int i=0;iOGlen;i+)if(i!=0) prech=OGi-1;/取文法文件中的前一个符号ch=OGi;/取文法文件中的当前符号

9、nextch=OGi+1;/取文法文件中的下一个符号if(nextch=)/下一个符号是，代表箭头if(isVN(ch)=-1)/当前符号不是已经识别到的VNVNVN_CNT.vn=ch;/加入VNVN_CNT+;PP_CNT.left=ch;/记入新产生式的左部if(P_CNT=0)S0=ch;/第一条产生式的左部是开始符号i+;/跳过if(prech=|prech=|)newPF=1;/进入新的产生式rightLen=0;OG & OPGif(newPF=1)PP_CNT.rightrightLen+=ch;if(nextch=n|nextch=|)newPF=0;/一条产生式结束P_CN

10、T+;/产生式个数加1PP_CNT.left=PP_CNT-1.left;i+;/跳过回车和 |for(int j=0;jOGlen;j+)ch=OGj;if(ch!=&ch!=|&ch!=n&isVN(ch)=-1&isVT(ch)=-1&ch!= )VTVT_CNT+=ch;VTVT_CNT+=#;VTVT_CNT=0;/输出VNprintf(nVN:t);fprintf(OUTF,nVN:t);for(int x=0;xVN_CNT;x+)printf(%c,VNx.vn);fprintf(OUTF,%c,VNx.vn);/输出VTprintf(nVT:t%sn,VT);fprintf(

11、OUTF,nVT:t%sn,VT);/输出Sprintf(S0:t%cnn,S0);fprintf(OUTF,S0:%cnn,S0);/输出Pfor(int k=0;k%sn,k,Pk.left,Pk.right);OG & OPGfprintf(OUTF,P%d:t%c-%sn,k,Pk.left,Pk.right);printf(n);fprintf(OUTF,n);/（）或int f=0;void FirstVT(char ch,char firstVT)/求非终结符的FirstVT集,存至firstVT中if(isIN(ch,VN)for(int i=0;ib.if(isVT(a)!=

12、-1)firstVTf+=a;firstVTf=0;/B-Cb.if(isVN(a)!=-1 & isVT(Pi.rightj+1)!=-1)firstVTf+=Pi.rightj+1;firstVTf=0;/B-C,C-b.|Db.if(isVN(a)!=-1 & strlen(Pi.right)=1)FirstVT(a,firstVT);f=0;/f清零,便于重复调用此函数/（）或int l=0;void LastVT(char ch,char lastVT)/求非终结符的LastVT集，存放至lastVT中OG & OPGif(isIN(ch,VN)for(int i=0;i.a;if(

13、isVT(a)!=-1)lastVTl+=a;lastVTl=0;/B-.aC;if(isVN(a)!=-1 & isVT(Pi.rightj-1)!=-1)lastVTl+=Pi.rightj-1;lastVTl=0;/B-C,C-.a|.aD;if(isVN(a)!=-1 & j=0)LastVT(a,lastVT);l=0;/l清零,便于重复调用此函数bool O_G()/判别是否是OG文法没有两个连续的非终结符,即形如A-.BC.的产生式/求所有非终结符的firstVT集for(int i=0;iVN_CNT;i+)char fvtSTR_MAX;FirstVT(VNi.vn,fvt)

14、;strcpy(VNi.firstVT,fvt);printf(FirstVT(%c)= ,VNi);fprintf(OUTF,FirstVT(%c)= ,VNi);for(int j=0;j(int)strlen(fvt);j+)printf(%c ,fvtj);OG & OPGfprintf(OUTF,%c ,fvtj);printf(n);fprintf(OUTF,n);printf(n);fprintf(OUTF,n);/求所有非终结符的lastVT集for(i=0;iVN_CNT;i+)char lvtSTR_MAX;LastVT(VNi.vn,lvt);strcpy(VNi.las

15、tVT,lvt);printf(LastVT(%c)= ,VNi);fprintf(OUTF,LastVT(%c)= ,VNi);for(int j=0;j(int)strlen(lvt);j+)printf(%c ,lvtj);fprintf(OUTF,%c ,lvtj);printf(n);fprintf(OUTF,n);/判别是否是OG文法for(i=0;iP_CNT;i+)int j=0;while(Pi.rightj+1!=0)char ch=Pi.rightj;char nextch=Pi.rightj+1;if(isVN(ch)!=-1 & isVN(nextch)!=-1)re

16、turn 0;elsej+;return 1;bool O_P_G()/判别是否是OPG文法不含空产生式或任意两个终结符a,b之间至多有一种(,=)关系for(int m=0;mMAX_NUM;m+)/初始化M数组for(int n=0;nMAX_NUM;n+)Mmn= ;for(int i=0;i.ab.(a=b)if(MisVT(ch)isVT(nextch)= )/当M为空时赋号MisVT(ch)isVT(nextch)=;j+;continue;else/当有a,b有两种关系时返回printf(n%c,%c有两种关系！,ch,nextch);fprintf(ERRF,n%c,%c有两种

17、关系！,ch,nextch);return 0;if(isVT(ch)!=-1 & isVN(nextch)!=-1)/A-.aB. (aFirstVTB)FirstVT(nextch,VNisVN(nextch).firstVT);for(int m=0;VNisVN(nextch).firstVTm!=0;m+)if(MisVT(ch)isVT(VNisVN(nextch).firstVTm)= )MisVT(ch)isVT(VNisVN(nextch).firstVTm)=.aBb. (a=b)if(MisVT(prech)isVT(nextch)= )MisVT(prech)isVT(

18、nextch)=;elseprintf(n%c,%c有两种关系！,prech,nextch);fprintf(ERRF,n%c,%c有两种关系！,prech,nextch);return 0;if(isVN(ch)!=-1 & isVT(nextch)!=-1)/A-.Bb.(LastVTBb)LastVT(ch,VNisVN(ch).lastVT);for(int m=0;VNisVN(ch).lastVTm!=0;m+)if(MisVT(VNisVN(ch).lastVTm)isVT(nextch)= )MisVT(VNisVN(ch).lastVTm)isVT(nextch)=;else

19、/当有a,b有两种关系时返回printf(n%c,%c有两种关系！,VNisVN(ch).lastVTm,nextch);fprintf(ERRF,n%c,%c有两种关系！,VNisVN(ch).lastVTm,nextch);return 0;j+;continue;else j+;/(while)/(for)MVT_CNT-1VT_CNT-1=;/#=#for(int x=0;x(int)strlen(VNisVN(S0).firstVT);x+)/# FirstVT(S0)；MVT_CNT-1isVT(VNisVN(S0).firstVTx)=;for(x=0;x #MisVT(VNis

20、VN(S0).lastVTx)VT_CNT-1=;return 1;void leftphase(char str,char substr,char a) /求最左素短语，用substr储存int slen=strlen(str);int begin,end=slen-1;for(int i=slen-1;i0;i-)if(MisVT(stri)isVT(a)=)if(MisVT(stri-1)isVT(stri)=)begin=i;elsebegin=i-1;continue;if(isVN(stri)continue;int j=0;int b=begin;/必须将begin的值记录，因为

21、while的循环条件与begin有关，否则会影响素短语的取值。while(jend-begin+1)/将素短语存放至substr中substrj+=strb+;substrj=0;void left_str(char w,char subw,int ip)/求剩余输入串subwint j=0,begin;for(begin=ip+1;begin(int)strlen(w);begin+)OPG_analysissubwj=wbegin;j+;subwj=0;#include OG & OPG.cpp#include stack.cppvoid create_opg_table();bool O

22、PG_analysis(char);void create_opg_table()/构造预测分析表printf(nThe OG is OPG!nnt);fprintf(OUTF,nThe OG is OPG!nnt);for(int i=0;iVT_CNT;i+)/输出行printf(t%c,VTi);fprintf(OUTF,t%c,VTi);printf(n);fprintf(OUTF,n);for(int m=0;mVT_CNT;m+)/输出剩余部分printf(nt%c,VTm);fprintf(OUTF,nt%c,VTm);for(int n=0;nVT_CNT;n+)printf(

23、t%c,Mmn);fprintf(OUTF,t%c,Mmn);printf(n);fprintf(OUTF,n);OPG_analysisbool OPG_analysis(char w)stack st;int ip=0;/ip指向第一个字符串的字符char a=wip;/记录当前符号st.push(#);printf(n步骤tt符号栈tt当前符号t剩余输入串t移进或归约n);fprintf(OUTF,n步骤tt符号栈tt当前符号t剩余输入串t移进或归约n);int step=1;while(1)char *s=st.S();/存放栈中的数据int TOP=strlen(s)-1;char

24、subwSTR_MAX;left_str(w,subw,ip);/求剩余输入串printf(n(%d)tt%stt %ctt%6s,step+,s,a,subw); /中间的空格(3个)是为了输出效果美观的fprintf(OUTF,n(%d)tt%stt %ctt%6s,step+,s,a,subw);if(a=# & isVN(sTOP) & sTOP-1=#)/分析成功的标志printf(tt分析成功!nn);fprintf(OUTF,tt分析成功!nn);fprintf(ERRF,目标串的分析出错！n);break;while(1)/M为“或=”的时候移进if(MisVT(sTOP)is

25、VT(a)=”时，找到最左素短语，然后归约OPG_analysisif(MisVT(sTOP)isVT(a)=)char substrSTR_MAX;leftphase(s,substr,a);/substr中放最左素短语for(int m=0;m(int)strlen(substr);m+)/出栈“substr的长度”次st.pop();st.push(N);/随便一个“非终结符”进栈printf(tt 归约);fprintf(OUTF,tt 归约);break;if(isVN(sTOP)/当遇到栈顶符号为非终结符时，要考虑前一个字符的情况TOP-;if(MisVT(sTOP)isVT(a)

26、= | TOP=-1)/出错情况printf(tt出错啦！n);fprintf(OUTF,tt出错啦！n);return 0;/(while)/(while)return 1;/(end)void main()strcpy(SOUR,OPGOPG2opg2.txt);strcpy(OBJ,OPGOPG2obj2.txt);strcpy(ERR,OPGOPG2err2.txt);/程序中指定文件名if(ERRF=fopen(ERR,w)=0)printf(Cant open FILE %s!n,ERR);exit(0);OPG_analysisif(INF=fopen(SOUR,r)=0)printf(Cant open FILE %s!n,SOUR);fprintf(ERRF,Cant open FILE %s!n,SOUR);ex