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

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

2、0,*VT=0;/非終結(jié)符和終結(jié)符數(shù)組char firstvtNN,lastvtNN,tableNN;typedef struct /符號對(P,a)char Vn;char Vt; VN_VT;typedef struct /棧 VN_VT *top; VN_VT *bollow; int size;stack;2、根據(jù)文法求FIRSTVT集和LASTVT集給定一個上下文無關(guān)文法，根據(jù)算法設(shè)計一個程序，求文法中每個非終結(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 對每個非終結(jié)符 P和終結(jié)符 a do FP,a = false for 對每個形如 Pa或 PQa的產(chǎn)生式 do Insert(P,a) while stack 非空 begin 棧頂項出棧，記為(Q,a) for 對每條形如 PQ的產(chǎn)生式 do insert(P,a) end; end.同理，可構(gòu)造計算LASTVT的算法。3、構(gòu)造算符優(yōu)先分析表依據(jù)文法和求出的相應(yīng)FirstVT和 LastVT 集生成算符優(yōu)先分析表。算法描述如下：for 每個形如 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 中的每個元素 a do Xi < a ; if Xi為非終結(jié)符, Xi+1為終結(jié)符 then for LastVT 中的每個元素 a do a > Xi+1 ; end4、構(gòu)造總控程序 算法描述如下： stack S; k = 1; /符號棧S的使用深度 Sk = #

5、REPEAT 把下一個輸入符號讀進(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歸約為某個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 /調(diào)用出錯診察程序 until a = #5、對給定的表達(dá)式

6、，給出準(zhǔn)確與否的分析過程6、給出表達(dá)式的計算結(jié)果。（本步驟可選作）四、實驗報告要求1.寫出編程思路、源代碼（或流程圖）；2.寫出上機(jī)調(diào)試時發(fā)現(xiàn)的問題，以及解決的過程；3.寫出你所使用的測試數(shù)據(jù)及結(jié)果；4.談?wù)勀愕捏w會。5.上機(jī)8小時，完成實驗報告2小時。五、源代碼 #include<iostream.h>#include<string.h>#include<stdio.h>typedef struct    char R;    char r;   

7、 int flag;array;typedef struct     char E;    char e;charLode;typedef struct    charLode *base;    int top;charstack;char str8080,arr8080,brr8080;array F20;int m,kk,p,ppp,FF=1;char r10;int crr2020,FLAG=0;char ccrr11

8、20,ccrr2201;void Initstack(charstack &s)/定義棧    s.base=new charLode20;    s.top=-1;void push(charstack &s,charLode w)    /入棧   s.top+;   s.bases.top.E=w.E;   s.bases.top.e=w.e;void pop(charstack &s,

9、charLode &w)    /出棧   w.E=s.bases.top.E;   w.e=s.bases.top.e;   s.top-;int IsEmpty(charstack s)    /判斷是否到棧頂    if(s.top=-1)        return 1;    el

10、se         return 0;int IsLetter(char ch)    /判斷是不是大寫字母（非終結(jié)符）   if(ch>='A'&&ch<='Z')       return 1;   else        return 0;/judge

11、1是判斷是否是算符文法：若產(chǎn)生式中含有兩個相繼的非終結(jié)符則不是算符文法int judge1(int n)    int j=3,flag=0;    for(int i=0;i<=n;i+)        while(strij!='0')               

12、;     char a=strij;            char b=strij+1;            if(IsLetter(a)&&IsLetter(b)    /兩個非終結(jié)符相連，不是算符文法   

13、0;                        flag=1;                break;       

14、60;                else                 j+;                &

15、#160;       if(flag=1)        /根據(jù)flag設(shè)定返回值            return 0;        else        &#

16、160;   return 1;/judge2是判斷文法G是否為算符優(yōu)先文法：若不是算符文法或若文法中含空字或終結(jié)符的優(yōu)先級不唯一則不是算符優(yōu)先文法void judge2(int n)    for(int i=0;i<=n;i+)        if(stri3=''|FLAG=1)/''代表空         

17、60;          cout<<"文法G不是算符優(yōu)先文法!"<<endl;            FF=0;            break;     

18、60;                  if(i>n)            cout<<"文法G是算符優(yōu)先文法!"<<endl;/search1是查看存放終結(jié)符的數(shù)組r中是否含有重復(fù)的終結(jié)符int search1(char r,int kk,ch

19、ar a)    for(int i=0;i<kk;i+)        if(ri=a)            break;        if(i=kk)          

20、60;  return 0;        else             return 1;/createF函數(shù)是用F數(shù)組存放每個終結(jié)符與非終結(jié)符和組合，并且值每隊的標(biāo)志位為0;F數(shù)組是一個結(jié)構(gòu)體void createF(int n)    int k=0,i=1;char g;    char

21、 t10;/t數(shù)組用來存放非終結(jié)符    t0=str00;    while(i<=n)            if(tk!=stri0)                    k+;

22、0;           tk=stri0;            g=tk;            i+;            

23、;    else i+;        kk=0;    char c;    for(i=0;i<=n;i+)             int j=3;        while(strij

24、!='0')                    c=strij;            if(IsLetter(c)=0)           

25、60;                if(!search1(r,kk,c)                    rkk=c;         &#

26、160;      kk+;/r數(shù)組用來存放終結(jié)符                        j+;                m=

27、0;    for(i=0;i<k;i+)        for(int j=0;j<kk-1;j+)                    Fm.R=ti;         &

28、#160;  Fm.r=rj;            Fm.flag=0;            m+;        /search函數(shù)是將在F數(shù)組中尋找到的終結(jié)符與非終結(jié)符對的標(biāo)志位值為1void search(charLode w)  

29、;  for(int i=0;i<m;i+)        if(Fi.R=w.E&&Fi.r=w.e)                    Fi.flag=1;break;        voi

30、d FirstVT(int n)/求FirstVT    charstack sta;    charLode w;    int i=0;    Initstack(sta);    while(i<=n)            int k=3;  &

31、#160;     w.E=stri0;        char a=strik;        char b=strik+1;        if(!IsLetter(a)    /產(chǎn)生式的后選式的第一個字符就是終結(jié)符的情況   

32、0;                w.e=a;            push(sta,w);            search(w);     

33、       i+;                else if(IsLetter(a)&&b!='0'&&!IsLetter(b)        /產(chǎn)生式的后選式的第一個字符是非終結(jié)符的情況    

34、                w.e=b;            push(sta,w);            search(w);     &#

35、160;      i+;                else i+;    charLode ww;    while(!IsEmpty(sta)            po

36、p(sta,ww);        for(i=0;i<=n;i+)                    w.E=stri0;            if(stri3=ww.E&&am

37、p;stri4='0')                            w.e=ww.e;                push(st

38、a,w);                search(w);                break;              

39、60;             p=0;int k=1;i=1;    while(i<m)            if(Fi-1.flag=1)             &

40、#160;      arrp0=Fi-1.R;            arrpk=Fi-1.r;                while(Fi.flag=0&&i<m)     

41、60;      i+;        if(Fi.flag=1)                    if(Fi.R=arrp0)          

42、60;     k+;            else arrpk+1='0'p+;k=1;            i+;               v

43、oid LastVT(int n)/求LastVT    charstack sta;    charLode w;    for(int i=0;i<m;i+)        Fi.flag=0;    i=0;    Initstack(sta);    while(i

44、<=n)            int k=strlen(stri);        w.E=stri0;        char a=strik-1;        char b=strik-2;   

45、     if(!IsLetter(a)                    w.e=a;            push(sta,w);       

46、60;    search(w);            i+;                else if(IsLetter(a)&&!IsLetter(b)        

47、60;           w.e=b;            push(sta,w);            search(w);          

48、;  i+;                else i+;        charLode ee;    while(!IsEmpty(sta)            pop(s

49、ta,ee);        for(i=0;i<=n;i+)                    w.E=stri0;            if(stri3=ee.E&&s

50、tri4='0')                            w.e=ee.e;                push(sta,w

51、);                search(w);                            int k=1;i=1;  

52、  ppp=0;    while(i<m)            if(Fi-1.flag=1)                    brrppp0=Fi-1.R;    

53、;        brrpppk=Fi-1.r;                while(Fi.flag=0&&i<m)            i+;     

54、60;  if(Fi.flag=1)                    if(Fi.R=arrppp0)                k+;      &

55、#160;     else brrpppk+1='0'ppp+;k=1;            i+;               void createYXB(int n)/構(gòu)造優(yōu)先表    int i,j;  

56、;  for(j=1;j<=kk;j+)        ccrr10j=rj-1;    for( i=1;i<=kk;i+)        ccrr2i0=ri-1;    for(i=1;i<=kk;i+)        for(j=1;

57、j<=kk;j+)            crrij=0;        int I=0,J=3;        while(I<=n)              &#

58、160;     if(strIJ+1='0')        /掃描右部                            I+;   &

59、#160;            J=3;                        else            

60、;                while(strIJ+1!='0')                             &#

61、160;      char aa=strIJ;                    char bb=strIJ+1;                  &#

62、160; if(!IsLetter(aa)&&!IsLetter(bb)/優(yōu)先及等于的情況，用1值表示等于                                       

63、       for(i=1;i<=kk;i+)                                        

64、60;            if(ccrr2i0=aa)                                break;   

65、                                              for(j=1;j<=kk;j+)

66、0;                                                 

67、0; if(ccrr10j=bb)                                break;             &#

68、160;                                    if(crrij=0)           

69、60;                crrij=1;                        else        &#

70、160;                    FLAG=1;                            I

71、=n+1;                                                J+;

72、0;                                       if(!IsLetter(aa)&&IsLetter(bb)&&strIJ+2!='0&

73、#39;&&!IsLetter(strIJ+2)/優(yōu)先及等于的情況                                           &

74、#160;  for(i=1;i<=kk;i+)                                            

75、0;        if(ccrr2i0=aa)                                break;      &#

76、160;                                         for(int j=1;j<=kk;j+)    &#

77、160;                                                if(ccrr10j=st

78、rIJ+2)                                break;                

79、                                if(crrij=0)                &

80、#160;           crrij=1;                        else             

81、                                        FLAG=1;         

82、;                   I=n+1;                              

83、;                                  if(!IsLetter(aa)&&IsLetter(bb)/優(yōu)先及小于的情況，用2值表示小于      

84、0;                                       for(i=1;i<=kk;i+)       &#

85、160;                                             if(aa=ccrr2i0)   

86、;                             break;                    

87、;                            for(j=0;j<=p;j+)                  

88、0;                                  if(bb=arrj0)              

89、60;                 break;                               

90、60;                for(int mm=1;arrjmm!='0'mm+)                            &#

91、160;                        for(int pp=1;pp<=kk;pp+)                     

92、;                                       if(ccrr10pp=arrjmm)       

93、0;                            break;                    

94、0;                                   if(crripp=0)            

95、0;                   crripp=2;                            else &#

96、160;                               FLAG=1;I=n+1;                &

97、#160;                                                 &

98、#160;         J+;                                       

99、0;if(IsLetter(aa)&&!IsLetter(bb)/優(yōu)先及大于的情況，用3值表示大于                                         &#

100、160;   for(i=1;i<=kk;i+)                                            

101、;         if(ccrr10i=bb)                                break;     

102、60;                                          for(j=0;j<=ppp;j+)    

103、                                                if(aa=brrj0)

104、                                break;                 

105、                               for(int mm=1;brrjmm!='0'mm+)             

106、                                         for(int pp=1;pp<=kk;pp+)    

107、60;                                                 

108、60;     if(ccrr2pp0=brrjmm)                                    break;    &#

109、160;                                                 &#

110、160; if(crrppi=0)                                crrppi=3;             

111、;               else FLAG=1;I=n+1;                                

112、;                J+;                                 &#

113、160;              /judge3是用來返回在歸約過程中兩個非終結(jié)符相比較的值int judge3(char s,char a)    int i=1,j=1;    while(ccrr2i0!=s)        i+;    while(

114、ccrr10j!=a)        j+;    if(crrij=3)         return 3;    else         if(crrij=2)          &#

115、160;  return 2;        else             if(crrij=1)                return 1;     

116、0;      else                 return 0;void print(char s,char STR20,int q,int u,int ii,int k)/打印歸約的過程    cout<<u<<"      

117、60; "    for(int i=0;i<=k;i+)        cout<<si;    cout<<"         "    for(i=q;i<=ii;i+)     

118、0;  cout<<STR0i;    cout<<"        "void process(char STR20,int ii)/對輸入的字符串進(jìn)行歸約的過程     cout<<"步驟"<<"    "<<"符號棧"<<

119、"    "<<"輸入串"<<"       "<<"動作"<<endl;    int k=0,q=0,u=0,b,i,j;    char s40,a;    sk='#'    print(

120、s,STR,q,u,ii,k);    cout<<"預(yù)備"<<endl;    k+;    u+;    sk=STR0q;    q+;    print(s,STR,q,u,ii,k);    cout<<"移進(jìn)"<<end

121、l;    while(q<=ii)            a=STR0q;        if(!IsLetter(sk) j=k;        else j=k-1;        b=j

122、udge3(sj,a);        if(b=3)/大于的情況進(jìn)行歸約                    while(IsLetter(sj-1)              

123、;  j-;            for(i=j;i<=k;i+)                si='0'            k=j; &

124、#160;          sk='N'            u+;            print(s,STR,q,u,ii,k);        

125、0;   cout<<"歸約"<<endl;                else if(b=2|b=1)/小于或等于的情況移進(jìn)                   

126、0;k+;            sk=a;            u+;            q+;           &#

127、160;print(s,STR,q,u,ii,k);            if(s0='#'&&s1='N'&&s2='#')                cout<<"接受"<<endl;&

128、#160;           else cout<<"移進(jìn)"<<endl;                else               

129、      cout<<"出錯"<<endl;            break;                if(s0='#'&&s1='N'&&

130、s2='#')        cout<<"歸約成功"<<endl;    else cout<<"歸約失敗"<<endl;void main()    int n,i,j;    cout<<"請輸入你要定義的文法G的產(chǎn)生式的個數(shù)n:"  &

131、#160; cin>>n;    cout<<"請輸入文法產(chǎn)生式："<<endl;    for(i=0;i<n;i+)            gets(stri);        j=strlen(stri);   

132、     strij='0'        stri0='Q'        /最末行添加擴(kuò)展    stri1='-'    stri2='>'    stri3='#' 

133、   stri4=str00;    stri5='#'    cout<<"你定義的產(chǎn)生式如下:"<<endl;    stri6='0'    for(i=0;i<=n;i+)        cout<<stri<<en

134、dl;    if(judge1(n)=0)    /判斷文法G是否為算符文法        cout<<"文法G不是算符文法!"<<endl;    if(judge1(n)=1)            cout<<"文法G是算符文法!"<<endl;            createF(n);        FirstVT(n);        LastVT(n);