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

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

2、數(shù)據(jù)結(jié)構(gòu)char *VN=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 n

3、ot FP,a then begin FP,a = true; /(P,a)進棧 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 每個形

4、如 P->X1X2Xn的產(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

5、的使用深度 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+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

6、 = #5、對給定的表達式，給出準(zhǔn)確與否的分析過程6、給出表達式的計算結(jié)果。（本步驟可選作）四、實驗報告要求1.寫出編程思路、源代碼（或流程圖）；2.寫出上機調(diào)試時發(fā)現(xiàn)的問題，以及解決的過程；3.寫出你所使用的測試數(shù)據(jù)及結(jié)果；4.談?wù)勀愕捏w會。5.上機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=

8、0;char ccrr1120,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(char

9、stack &s,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;  &

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

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

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

13、60;                          flag=1;                break;     &#

14、160;                  else                 j+;              

15、          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、160;            cout<<"文法G不是算符優(yōu)先文法!"<<endl;            FF=0;            break;   &#

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

19、r r,int kk,char a)    for(int i=0;i<kk;i+)        if(ri=a)            break;        if(i=kk)        &#

20、160;    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;  

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

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

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

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

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

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

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

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

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

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

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

32、60;                  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)          &

36、#160; pop(sta,ww);        for(i=0;i<=n;i+)                    w.E=stri0;            if(stri3

37、=ww.E&&stri4='0')                            w.e=ww.e;               

38、 push(sta,w);                search(w);                break;            &#

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

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

41、160;        i+;        if(Fi.flag=1)                    if(Fi.R=arrp0)        &#

42、160;       k+;            else arrpk+1='0'p+;k=1;            i+;            &

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

44、 while(i<=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、160;      search(w);            i+;                else if(IsLetter(a)&&!IsLetter(b)      &#

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

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

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

50、.E&&stri4='0')                            w.e=ee.e;               

51、60;push(sta,w);                search(w);                            int k=1;i=1

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

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

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

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

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

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

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

59、               J=3;                        else         

60、0;                  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、160;              if(ccrr2i0=aa)                                break;

65、                                                 for(j=1;j&l

66、t;=kk;j+)                                                

67、60;   if(ccrr10j=bb)                                break;           &

68、#160;                                      if(crrij=0)         &#

69、160;                  crrij=1;                        else      &

70、#160;                      FLAG=1;                          

71、  I=n+1;                                               

72、 J+;                                        if(!IsLetter(aa)&&IsLetter(bb)&&str

73、IJ+2!='0'&&!IsLetter(strIJ+2)/優(yōu)先及等于的情況                                         

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

75、60;          if(ccrr2i0=aa)                                break;    &

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

77、#160;                                                  

78、if(ccrr10j=strIJ+2)                                break;              

79、;                                  if(crrij=0)              

80、              crrij=1;                        else           

81、;                                          FLAG=1;      

82、0;                     I=n+1;                           

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

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

85、#160;                                               if(aa=ccrr2i0)

86、0;                               break;                 

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

88、60;                                    if(bb=arrj0)            &#

89、160;                   break;                             &#

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

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

92、0;                                         if(ccrr10pp=arrjmm)     

93、60;                              break;                  

94、60;                                     if(crripp=0)          

95、60;                     crripp=2;                           

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

97、                                                  

98、            J+;                                     

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

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

101、0;           if(ccrr10i=bb)                                break;   &#

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

103、;                                                  

104、;if(aa=brrj0)                                break;               

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

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

107、160;                                                 &#

108、160;       if(ccrr2pp0=brrjmm)                                    break;  &

109、#160;                                                 &

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

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

112、0;                  J+;                               &

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

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

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

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

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

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

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

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

121、t;<<endl;    while(q<=ii)            a=STR0q;        if(!IsLetter(sk) j=k;        else j=k-1;      &#

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

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

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

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

126、60;  k+;            sk=a;            u+;            q+;         &

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

128、lt;<endl;            else cout<<"移進"<<endl;                else             

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

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

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

132、;       strij='0'        stri0='Q'        /最末行添加擴展    stri1='-'    stri2='>'    stri3='

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

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