实验三-算符优先分析算法的设计与实现(共17页)

1、精选优质文档-倾情为你奉上实验三 算符优先分析算法的设计与实现（8学时）一、 实验目的根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。二、 实验要求1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）： 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、数据结构char *VN=0,*VT=0;/非终结符和终结符数组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、根据文法求FIRSTVT集和LASTVT集给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的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 对每个非终结符 P和终结符 a do FP,a = false for 对每个形如 Pa或 PQa的产生式 do Insert(P,a) while stack 非空 begin 栈顶项出栈，记为(Q,a) for 对每条形如 PQ的产生式 do insert(P,a) end; end.同理，可构造计算LASTVT的算法。3、构造算符优先分析表依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。算法描述如下：for 每个形

4、如 P->X1X2Xn的产生式 do for i =1 to n-1 do begin if Xi和Xi+1都是终结符 then Xi = Xi+1 if i<= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符 then Xi = Xi+2 if Xi为终结符, Xi+1为非终结符 then for FirstVT 中的每个元素 a do Xi < a ; if Xi为非终结符, Xi+1为终结符 then for LastVT 中的每个元素 a do a > Xi+1 ; end4、构造总控程序 算法描述如下： 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 /调用出错诊察程序 until a

6、 = #5、对给定的表达式，给出准确与否的分析过程6、给出表达式的计算结果。（本步骤可选作）四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。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)    /判断是不是大写字母（非终结符）   if(ch>='A'&&ch<='Z')       return 1;   else        re

11、turn 0;/judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法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)    /两个非终结符相连，不是算符文法 

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

14、160;                  else                 j+;              

15、          if(flag=1)        /根据flag设定返回值            return 0;        else      &

16、#160;     return 1;/judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法void judge2(int n)    for(int i=0;i<=n;i+)        if(stri3=''|FLAG=1)/''代表空       &#

17、160;            cout<<"文法G不是算符优先文法!"<<endl;            FF=0;            break;   &#

18、160;                    if(i>n)            cout<<"文法G是算符优先文法!"<<endl;/search1是查看存放终结符的数组r中是否含有重复的终结符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函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体void createF(int n)    int k=0,i=1;char g;  

21、60; char t10;/t数组用来存放非终结符    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数组用来存放终结符                        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函数是将在F数组中寻找到的终结符与非终结符对的标志位值为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)    /产生式的后选式的第一个字符就是终结符的情况 

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

33、;         i+;                else if(IsLetter(a)&&b!='0'&&!IsLetter(b)        /产生式的后选式的第一个字符是非终结符的情况  

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)/构造优先表    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)/优先及等于的情况，用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)/优先及等于的情况                                         

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)/优先及小于的情况，用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)/优先及大于的情况，用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是用来返回在归约过程中两个非终结符相比较的值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<<"预备"<<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的产生式的个数n:"

131、    cin>>n;    cout<<"请输入文法产生式："<<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<<"你定义的产生式如下:"<<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);