實(shí)驗(yàn)3算符優(yōu)先分析算法的設(shè)計(jì)與實(shí)現(xiàn)

1、實(shí)驗(yàn)三 算符優(yōu)先分析算法的設(shè)計(jì)與實(shí)現(xiàn)（8學(xué)時(shí)）一、 實(shí)驗(yàn)?zāi)康母鶕?jù)算符優(yōu)先分析法，對(duì)表達(dá)式進(jìn)行語法分析，使其能夠判斷一個(gè)表達(dá)式是否正確。通過算符優(yōu)先分析方法的實(shí)現(xiàn)，加深對(duì)自下而上語法分析方法的理解。二、 實(shí)驗(yàn)要求1、輸入文法?？梢允侨缦滤阈g(shù)表達(dá)式的文法（你可以根據(jù)需要適當(dāng)改變）： EE+T|E-T|TTT*F|T/F|FF（E）|i2、對(duì)給定表達(dá)式進(jìn)行分析，輸出表達(dá)式正確與否的判斷。程序輸入/輸出示例：輸入：1+2;輸出：正確輸入：(1+2)/3+4-(5+6/7);輸出：正確輸入：(1-2)/3+4輸出：錯(cuò)誤輸入：1+2-3+(*4/5)輸出：錯(cuò)誤三、實(shí)驗(yàn)步驟1、參考數(shù)據(jù)結(jié)構(gòu)char *VN=

2、0,*VT=0;/非終結(jié)符和終結(jié)符數(shù)組char firstvtNN,lastvtNN,tableNN;typedef struct /符號(hào)對(duì)(P,a)char Vn;char Vt; VN_VT;typedef struct /棧 VN_VT *top; VN_VT *bollow; int size;stack;2、根據(jù)文法求FIRSTVT集和LASTVT集給定一個(gè)上下文無關(guān)文法，根據(jù)算法設(shè)計(jì)一個(gè)程序，求文法中每個(gè)非終結(jié)符的FirstVT 集和LastVT 集。算符描述如下：/*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF not FP,a then

3、begin FP,a = true; /(P,a)進(jìn)棧 end; Procedure FirstVT; Begin for 對(duì)每個(gè)非終結(jié)符 P和終結(jié)符 a do FP,a = false for 對(duì)每個(gè)形如 Pa或 PQa的產(chǎn)生式 do Insert(P,a) while stack 非空 begin 棧頂項(xiàng)出棧，記為(Q,a) for 對(duì)每條形如 PQ的產(chǎn)生式 do insert(P,a) end; end.同理，可構(gòu)造計(jì)算LASTVT的算法。3、構(gòu)造算符優(yōu)先分析表依據(jù)文法和求出的相應(yīng)FirstVT和 LastVT 集生成算符優(yōu)先分析表。算法描述如下：for 每個(gè)形如 P->X1X2X

4、n的產(chǎn)生式 do for i =1 to n-1 do begin if Xi和Xi+1都是終結(jié)符 then Xi = Xi+1 if i<= n-2, Xi和Xi+2 是終結(jié)符, 但Xi+1 為非終結(jié)符 then Xi = Xi+2 if Xi為終結(jié)符, Xi+1為非終結(jié)符 then for FirstVT 中的每個(gè)元素 a do Xi < a ; if Xi為非終結(jié)符, Xi+1為終結(jié)符 then for LastVT 中的每個(gè)元素 a do a > Xi+1 ; end4、構(gòu)造總控程序 算法描述如下： stack S; k = 1; /符號(hào)棧S的使用深度 Sk = #

5、REPEAT 把下一個(gè)輸入符號(hào)讀進(jìn)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+1Sk歸約為某個(gè)N，并輸出歸約為哪個(gè)符號(hào)； K = j+1; Sk = N; end of while if Sj < a or Sj = a then begin k = k+1; Sk = a end else error /調(diào)用出錯(cuò)診察程序 until a = #5、對(duì)給定的表達(dá)式

6、，給出準(zhǔn)確與否的分析過程6、給出表達(dá)式的計(jì)算結(jié)果。（本步驟可選作）四、實(shí)驗(yàn)報(bào)告要求1.寫出編程思路、源代碼（或流程圖）；2.寫出上機(jī)調(diào)試時(shí)發(fā)現(xiàn)的問題，以及解決的過程；3.寫出你所使用的測試數(shù)據(jù)及結(jié)果；4.談?wù)勀愕捏w會(huì)。5.上機(jī)8小時(shí)，完成實(shí)驗(yàn)報(bào)告2小時(shí)。程序代碼:#include<stdio.h>#include <stdlib.h>#include <iostream.h>char data2020; /算符優(yōu)先關(guān)系char s100; /模擬符號(hào)棧s char lable20; /文法終結(jié)符集char input100; /文法輸入符號(hào)串char str

7、ing2010; /用于輸入串的分析int k; char a; int j; char q; int r; /文法規(guī)則個(gè)數(shù)int r1; /轉(zhuǎn)化后文法規(guī)則個(gè)數(shù)char st1030; /用來存儲(chǔ)文法規(guī)則char first1010; /文法非終結(jié)符FIRSTVT集char last1010; /文法非終結(jié)符LASTVT集int fflag10=0; /標(biāo)志第i個(gè)非終結(jié)符的FIRSTVT集是否已求出int lflag10=0; /標(biāo)志第i個(gè)非終結(jié)符的LASTVT集是否已求出int deal(); /對(duì)輸入串的分析int zhongjie(char c); /判斷字符c是否是終結(jié)符int xia

8、biao(char c); /求字符c在算符優(yōu)先關(guān)系表中的下標(biāo)void out(int j,int k,char *s); /打印s棧void firstvt(char c); /求非終結(jié)符c的FIRSTVT集void lastvt(char c); /求非終結(jié)符c的LASTVT集void table(); /創(chuàng)建文法優(yōu)先關(guān)系表int main()int i,j,k=0; printf("請(qǐng)輸入文法規(guī)則數(shù)：");scanf("%d",&r);printf("請(qǐng)輸入文法規(guī)則：n");for(i=0;i<r;i+) scan

9、f("%s",sti); /存儲(chǔ)文法規(guī)則，初始化FIRSTVT集和LASTVT集*/ firsti0=0; /*firsti0和lasti0分別表示sti0非終結(jié)符的FIRSTVT集和LASTVT集中元素的個(gè)數(shù)*/ 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>='A'&&am

10、p;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!='>'&&stij!='|')

11、lablek+=stij; lablek='#'lablek+1='0' table();printf("每個(gè)非終結(jié)符的FIRSTVT集為：n"); /輸出每個(gè)非終結(jié)符的FIRSTVT集for(i=0;i<r;i+) printf("%c: ",sti0); for(j=0;j<firsti0;j+) printf("%c ",firstij+1); printf("n");printf("每個(gè)非終結(jié)符的LASTVT集為：n"); /輸出每個(gè)非終結(jié)符的

12、LASTVT集for(i=0;i<r;i+) printf("%c: ",sti0); for(j=0;j<lasti0;j+) printf("%c ",lastij+1); printf("n");printf("算符優(yōu)先分析表如下:n");for(i=0;lablei!='0'i+) printf("t%c",lablei);printf("n"); for(i=0;i<k+1;i+) printf("%ct",la

13、blei); for(j=0;j<k+1;j+) printf("%ct",dataij); printf("n");printf("請(qǐng)輸入文法輸入符號(hào)串以#結(jié)束:");scanf("%s",input); getchar(); deal();system("pause");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);fo

14、r(i=0;i<r;i+) textxy=sti0; y+; for(j=1;stij!='0'j+) if(stij='|') textxy='0' x+; y=0; textxy=sti0; y+; textxy+='-' textxy+='>' else textxy=stij; y+; textxy='0' x+; y=0;r1=x;printf("轉(zhuǎn)化后的文法為:n");for(i=0;i<x;i+) /輸出轉(zhuǎn)化后的文法規(guī)則串 printf("

15、;%sn",texti);for(i=0;i<x;i+) /*求每個(gè)終結(jié)符的推導(dǎo)結(jié)果(去掉"->"后的轉(zhuǎn)化文法，用于最后的規(guī)約)*/ 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

16、=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;k<r;k+) if(stk0=textij+1) break; m

17、=xiabiao(textij); for(t=0;t<firstk0;t+) n=xiabiao(firstkt+1); datamn='<' 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&l

18、t;first00;t+) n=xiabiao(first0t+1); datamn='<'n=xiabiao('#');for(t=0;t<last00;t+) m=xiabiao(last0t+1); datamn='>'datann='='/*求FIRSTVT集*/void firstvt(char c) int i,j,k,m,n;for(i=0;i<r;i+) if(sti0=c) break;if(fflagi=0) n=firsti0+1; m=0; do if(m=2|stim='|

19、') if(zhongjie(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<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&#

20、39;); firstin='0' firsti0=-n; fflagi=1;/*求LASTVT集*/void lastvt(char c) int i,j,k,m,n;for(i=0;i<r;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+; else if(zhongjie(stim-1) lastin=stim-1; n+; if(stim!=c) lastv

21、t(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; 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=

22、0;inputi!='0'i+); /計(jì)算輸入串的長度 z=i-; i=0; while(a=inputi)!='0') if(zhongjie(sk) j=k; else j=k-1; x=xiabiao(sj); y=xiabiao(a); if(dataxy='>') out(1,k,s); printf("%c",a); out(i+1,z,input); printf("規(guī)約n"); do q=sj; if(zhongjie(sj-1) j=j-1; else j=j-2; x=xiabia

23、o(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; else if(zhongjie(sm) if(sm=stringNn) sj+1=stringN0; break; k