編譯原理之OPG實(shí)驗(yàn)報告

1、編譯原理之算符優(yōu)先文法分析 * 學(xué)院 1105班安雨雅班級： 11*學(xué)號： 11*實(shí)驗(yàn)語法分析實(shí)驗(yàn)報告一、實(shí)驗(yàn)題目算符優(yōu)先文法分析程序二、實(shí)驗(yàn)內(nèi)容及要求（ 1）根據(jù)給定文法，先求出 FirstVt 和 LastVt 集合，構(gòu)造算符優(yōu)先關(guān)系表（要求算符優(yōu)先關(guān)系表輸出到屏幕和文件） ；（ 2）根據(jù)算法和優(yōu)先關(guān)系表分析給定表達(dá)式是否是該文法識別的正確的算術(shù)表達(dá)式（要求輸出歸約過程）（ 3）給定表達(dá)式文法為： (OPG文件中還有其他文法可作為測試 ) BBoT|TTTaF|FFnF|(B)|t|f（ 4）分析的句子為 :ntofat#三、設(shè)計(jì)思想之重點(diǎn)：構(gòu)造算符優(yōu)先表：求FirstVT 集和 Last

2、VT 集判斷是否是算符文法判斷是否是算符優(yōu)先文法算符優(yōu)先分析：I 、求最左素短語II 、根據(jù)算符優(yōu)先分析表分析（“ <”或” =”時移進(jìn)；“>”時歸約）四、程序源代碼（C 語言）#include "stdio.h"#include "string.h"#include "stdlib.h"#define STR_MAX 80/串的最大長度#define MAX_NUM 100/符號的最大個數(shù)#define MAX 32767 #define N 20/文件中符號的最大個數(shù)/棧的長度classstack/符號棧private

3、:char sN;int top;public:stack();void push(char);void pop();int TOP();/返回top 的值char *S();/返回s 的值;stack:stack()top=-1;void stack:push(char ch)s+top=ch;stop+1='0'/進(jìn)棧操作void stack:pop()top-;/出棧操作int stack:TOP()/返回top 的值 return top; char * stack:S()/返回s 的值return s;char MMAX_NUMMAX_NUM;struct PRO/產(chǎn)

4、生式類型char left;char rightSTR_MAX;structVNstruchar vn;char firstVTMAX_NUM;char lastVTMAX_NUM;char SOURSTR_MAX;/源文件名char OBJSTR_MAX;/目標(biāo)文件名char ERRSTR_MAX;/錯誤信息文件名FILE *INF;/源程序文件指針FILE *OUTF;/分析結(jié)果文件指針FILE *ERRF;/錯誤信息文件指針char OGMAX;/存放上下文無關(guān)文法intOGlen;/上下文無關(guān)文法長度VNstru VNMAX_NUM;/非終結(jié)符數(shù)組intVN_CNT;/非終結(jié)符個數(shù)ch

5、ar VTMAX_NUM;/終結(jié)符數(shù)組intVT_CNT;/終結(jié)符個數(shù)char S0;/開始符號PROPMAX_NUM;/產(chǎn)生式數(shù)組intP_CNT;/產(chǎn)生式個數(shù)bool isIN(char ch,VNstru arr);/判別符號 ch 是否在 arr 數(shù)組中int isVN(char ch);/判別符號 ch 是否在 VN 數(shù)組中 ,存在則返回下標(biāo) ,否則返回 -1int isVT(char ch);/判別符號 ch 是否在 VT 數(shù)組中 ,存在則返回下標(biāo) ,否則返回 -1void getOG();/從源文件取得 OG 文法串void getVN_VT_S_P();/從 OG 文法提取 V

6、N,VT,S,Pvoid FirstVT( char ch,char firstVT);/求 FirstVT 集 firstVTvoid LastVT( char 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);/求剩余輸入串 subwbool isIN( char ch,VNstru

7、arr)/判別符號 ch 是否在 arr 數(shù)組中for(int i=0;i<VN_CNT;i+)if(ch=arri.vn)return 1;return 0;int isVN(char ch)/判別符號 ch 是否在 VN 數(shù)組中 ,存在則返回下標(biāo) ,否則返回 -1for(int i=0;i<VN_CNT;i+)if(ch=VNi.vn)return i;return -1;int isVT( char ch) /判別符號 ch 是否在 VT 數(shù)組中 ,存在則返回下標(biāo) ,否則返回 -1for(int i=0;i<VT_CNT;i+)if(ch=VTi)return i;re

8、turn -1;void getOG() /從源文件取得 OG 文法串OGlen=0;char ch;while(!feof(INF)ch=fgetc(INF);if(ch!='')OGOGlen+=ch;OGOGlen='0'printf("The Grammar is :n");/將文法輸出到屏幕puts(OG);fprintf(OUTF,"The Grammaris :n");fputs(OG,OUTF);/將文法輸出到文件void getVN_VT_S_P()/從 OG 文法提取 VN,VT,S,PVN_CNT=0

9、;VT_CNT=0;P_CNT=0;int newPF=0;int rightLen=0;/是否進(jìn)入新產(chǎn)生式的標(biāo)志char prech,ch,nextch;for(int i=0;i<OGlen;i+)if(i!=0) prech=OGi-1;ch=OGi;nextch=OGi+1;if(nextch='')/取文法文件中的前一個符號/取文法文件中的當(dāng)前符號/取文法文件中的下一個符號/下一個符號是 ，代表箭頭if(isVN(ch)=-1) /當(dāng)前符號不是已經(jīng)識別到的 VN VNVN_CNT.vn=ch; /加入 VNVN_CNT+;PP_CNT.left=ch;/記入新產(chǎn)

10、生式的左部if(P_CNT=0)i+;S0=ch;/第一條產(chǎn)生式的左部是開始符號/跳過if(prech=''|prech='|')newPF=1;/進(jìn)入新的產(chǎn)生式rightLen=0;if(newPF=1)PP_CNT.rightrightLen+=ch;if(nextch='n'|nextch='|')newPF=0;/一條產(chǎn)生式結(jié)束P_CNT+;/產(chǎn)生式個數(shù)加PP_CNT.left=PP_CNT-1.left;i+;/跳過回車和|1for(int j=0;j<OGlen;j+)ch=OGj;if(ch!='

11、9;&&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;x<VN_CNT;x+)printf("%c",VNx.vn);fprin

12、tf(OUTF,"%c",VNx.vn);/輸出 VTprintf("nVT:t%sn",VT);fprintf(OUTF,"nVT:t%sn",VT);/輸出 Sprintf("S0:t%cnn",S0);fprintf(OUTF,"S0:%cnn",S0);/輸出 Pfor(int k=0;k<P_CNT;k+)printf("P%d:t%c->%sn",k,Pk.left,Pk.right);fprintf(OUTF,"P%d:t%c->%s

13、n",k,Pk.left,Pk.right);printf("n");fprintf(OUTF,"n");/（）或int f=0;void FirstVT( char ch,char firstVT) /求非終結(jié)符的 FirstVT 集,存至 firstVT 中if(isIN(ch,VN)for(int i=0;i<P_CNT;i+)if(ch=Pi.left)int j=0;char a=Pi.rightj;/B->b.if(isVT(a)!=-1)firstVTf+=a;firstVTf='0'/B->Cb

14、.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 清零 ,便于重復(fù)調(diào)用此函數(shù)/（） 或int l=0;void LastVT( char ch,char lastVT) /求非終結(jié)符的 LastVT 集，存放至 lastVT 中if(isIN(ch,VN)for(int i=0;i

15、<P_CNT;i+)if(ch=Pi.left)int j=strlen(Pi.right)-1; /'j' 記錄右部的最后一個字符位置 char a=Pi.rightj;/B->.a;if(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

16、=0)LastVT(a,lastVT);l=0; /l 清零 ,便于重復(fù)調(diào)用此函數(shù)bool O_G()/ 判別是否是 OG 文法 沒有兩個連續(xù)的非終結(jié)符,即形如 A->.BC.的產(chǎn)生式 /求所有非終結(jié)符的firstVT 集for(int i=0;i<VN_CNT;i+)char fvtSTR_MAX;FirstVT(VNi.vn,fvt);strcpy(VNi.firstVT,fvt);printf("FirstVT(%c)= ",VNi);fprintf(OUTF,"FirstVT(%c)= ",VNi);for(int j=0;j<

17、( int)strlen(fvt);j+)printf("%c ",fvtj);fprintf(OUTF,"%c ",fvtj);printf("n");fprintf(OUTF,"n");printf("n");fprintf(OUTF,"n");/求所有非終結(jié)符的lastVT 集for(i=0;i<VN_CNT;i+)char lvtSTR_MAX;LastVT(VNi.vn,lvt);strcpy(VNi.lastVT,lvt);printf("Last

18、VT(%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;i<P_CNT;i+)int j=0;while(Pi.rightj+1!='0')char ch=Pi.r

19、ightj;char nextch=Pi.rightj+1;if(isVN(ch)!=-1 && isVN(nextch)!=-1)return 0;elsej+;return 1;bool O_P_G()/判別是否是 OPG 文法 不含空產(chǎn)生式或任意兩個終結(jié)符a,b 之間至多有一種 (<,>,=)關(guān)系 for(int m=0;m<MAX_NUM;m+)/初始化 M 數(shù)組for(int n=0;n<MAX_NUM;n+)Mmn=' 'for(int i=0;i<P_CNT;i+)int j=0;char prech=' &#

20、39;,ch=' ',nextch=' ' /當(dāng)進(jìn)入新的產(chǎn)生式時，要清空三字符的值；while(Pi.rightj!='0')if(j!=0)prech=ch;ch=Pi.rightj;nextch=Pi.rightj+1;if(isVT(ch)!=-1 && isVT(nextch)!=-1)/A->.ab.(a=b)if(MisVT(ch)isVT(nextch)=' ')/當(dāng) M 為空時賦號MisVT(ch)isVT(nextch)='='j+;continue;else/當(dāng)有 a,b

21、有兩種關(guān)系時返回printf("n%c,%c 有兩種關(guān)系！ ",ch,nextch); fprintf(ERRF,"n%c,%c 有兩種關(guān)系！ ",ch,nextch); return 0;if(isVT(ch)!=-1 && isVN(nextch)!=-1)/A->.aB. (a<FirstVTB)FirstVT(nextch,VNisVN(nextch).firstVT);for(int m=0;VNisVN(nextch).firstVTm!='0'm+)if(MisVT(ch)isVT(VNisVN(

22、nextch).firstVTm)=' ') MisVT(ch)isVT(VNisVN(nextch).firstVTm)='<'else/當(dāng)有 a,b 有兩種關(guān)系時返回printf("n%c,%c 有兩種關(guān)系！ ",ch,VNisVN(nextch).firstVTm); fprintf(ERRF,"n%c,%c 有兩種關(guān)系！ ",ch,VNisVN(nextch).firstVTm);return 0;j+;continue;if(isVT(prech)!=-1 && isVN(ch)!=-1 &

23、amp;& isVT(nextch)!=-1)/A->.aBb. (a=b)if(MisVT(prech)isVT(nextch)=' ')MisVT(prech)isVT(nextch)='='elseprintf("n%c,%c 有兩種關(guān)系！ ",prech,nextch); fprintf(ERRF,"n%c,%c 有兩種關(guān)系！ ",prech,nextch); return 0;if(isVN(ch)!=-1 && isVT(nextch)!=-1)/A->.Bb.(LastVT

24、B>b)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/當(dāng)有 a,b 有兩種關(guān)系時返回printf("n%c,%c 有兩種關(guān)系！ ",VNisVN(ch).lastVTm,nextch); fprintf(ERRF,"n%c,%c 有兩種關(guān)

25、系！ ",VNisVN(ch).lastVTm,nextch);return 0;j+;continue;elsej+;/(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<(int)strlen(VNisVN(S0).lastVT);x+)MisVT(VNisVN(S0).la

26、stVTx)VT_CNT-1='>'/LastVT(S0) > #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;i>0;i-)if(MisVT(stri)isVT(a)='>')if(MisVT(stri-1)isVT(stri)='<')begin=i;elsebegin=i-1;continue;if

27、(isVN(stri)continue;int j=0; int b=begin; /必須將 begin 的值記錄，因?yàn)?while 的循環(huán)條件與begin 有關(guān)，否則會影響素短語的取值。while(j<end-begin+1)/將素短語存放至 substr中substrj+=strb+;substrj='0'void left_str(char w,char subw,int ip) /求剩余輸入串 subw int j=0,begin;for(begin=ip+1;begin<(int)strlen(w);begin+)subwj=wbegin;j+;subwj

28、='0'#include "OG & OPG .cpp"#include "stack.cpp"void create_opg_table();bool OPG_analysis(char);void create_opg_table()/構(gòu)造預(yù)測分析表printf("nThe OG is OPG!nnt");fprintf(OUTF,"nThe OG is OPG!nnt");for(int i=0;i<VT_CNT;i+)/輸出行printf("t%c",VTi

29、);fprintf(OUTF,"t%c",VTi);printf("n");fprintf(OUTF,"n");for(int m=0;m<VT_CNT;m+)/輸出剩余部分printf("nt%c",VTm);fprintf(OUTF,"nt%c",VTm);for(int n=0;n<VT_CNT;n+)printf("t%c",Mmn);fprintf(OUTF,"t%c",Mmn);printf("n");fprin

30、tf(OUTF,"n");bool OPG_analysis(char w)stack st;int ip=0;/ip 指向第一個字符串的字符char a=wip;/記錄當(dāng)前符號st.push('#');printf("n 步驟 tt 符號棧 tt 當(dāng)前符號 t 剩余輸入串 t 移進(jìn)或歸約 n"); fprintf(OUTF,"n 步驟 tt 符號棧 tt 當(dāng)前符號 t 剩余輸入串 t 移進(jìn)或歸約 n"); int step=1;while(1)char *s=st.S();/存放棧中的數(shù)據(jù)int TOP=strlen

31、(s)-1;char 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='#')/分析成功的標(biāo)志printf("tt 分析成功 !nn");fprin

32、tf(OUTF,"tt分析成功 !nn");fprintf(ERRF," 目標(biāo)串的分析出錯！ n");break;while(1)/M 為“ <或=”的時候移進(jìn) if(MisVT(sTOP)isVT(a)='<' | MisVT(sTOP)isVT(a)='=')st.push(a);a=w+ip; printf("tt 移進(jìn) "); fprintf(OUTF,"tt 移進(jìn) ");break;/m為“ >”時，找到最左素短語，然后歸約if(MisVT(sTOP)is

33、VT(a)='>')char substrSTR_MAX;leftphase(s,substr,a);/substr 中放最左素短語for(int m=0;m<(int)strlen(substr);m+) /出棧“ substr的長度”次 st.pop();st.push('N'); /隨便一個“非終結(jié)符”進(jìn)棧 printf("tt 歸約 ");fprintf(OUTF,"tt歸約 ");break;if(isVN(sTOP) /當(dāng)遇到棧頂符號為非終結(jié)符時，要考慮前一個字符的情況TOP-;if(MisVT(s

34、TOP)isVT(a)=' ' | 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("Can't open FILE %s!n",ERR);exit(0);if(INF=fopen(SOUR,"r")=0)printf("