实验三算符优先分析算法的设计与实现（8学时）一、实验目的根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。

通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。

二、实验要求1、输入文法。

可以是如下算术表达式的文法（你可以根据需要适当改变）：E→E+T|E-T|TT→T*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、参考数据结构char *VN=0,*VT=0;//非终结符和终结符数组char firstvt[N][N],lastvt[N][N],table[N][N];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 not F[P,a] thenbeginF[P,a] = true; //(P,a)进栈end;Procedure FirstVT;Beginfor 对每个非终结符 P和终结符 a doF[P,a] = falsefor 对每个形如 P a…或 P→Qa…的产生式 doInsert(P,a)while stack 非空begin栈顶项出栈，记为(Q,a)for 对每条形如 P→Q…的产生式 doinsert(P,a)end;end.同理，可构造计算LASTVT的算法。

3、构造算符优先分析表依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。

算法描述如下：for 每个形如 P->X1X2…X n的产生式 dofor i =1 to n-1 dobeginif X i和X i+1都是终结符 thenX i = X i+1if i<= n-2, X i和X i+2 是终结符, 但X i+1 为非终结符 then X i = X i+2if X i为终结符, X i+1为非终结符 thenfor FirstVT 中的每个元素 a doX i < a ;if X i为非终结符, X i+1为终结符 thenfor LastVT 中的每个元素 a doa > X i+1 ;end4、构造总控程序算法描述如下：stack S;k = 1; //符号栈S的使用深度S[k] = ‘#’REPEAT把下一个输入符号读进a中；If S[k] ∈ VT then j = k else j = k-1;While S[j] > a doBeginRepeatQ = S[j];if S[j-1] ∈ VT then j = j-1 else j = j-2 until S[j] < Q;把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号；K = j+1;S[k] = N;end of whileif S[j] < a or S[j]= a thenbegin k = k+1; S[k] = a endelse error //调用出错诊察程序until a = ‘#’5、对给定的表达式，给出准确与否的分析过程6、给出表达式的计算结果。

（本步骤可选作）四、实验报告要求1.写出编程思路、源代码（或流程图）；2.写出上机调试时发现的问题，以及解决的过程；3.写出你所使用的测试数据及结果；4.谈谈你的体会。

5.上机8小时，完成实验报告2小时。

五、源代码#include<iostream.h>#include<string.h>#include<stdio.h>typedef struct{char R;char r;int flag;}array;typedef struct{char E;char e;}charLode;typedef struct{charLode *base;int top;}charstack;char str[80][80],arr[80][80],brr[80][80];array F[20];int m,kk,p,ppp,FF=1;char r[10];int crr[20][20],FLAG=0;char ccrr1[1][20],ccrr2[20][1];void Initstack(charstack &s)//定义栈{s.base=new charLode[20];s.top=-1;}void push(charstack &s,charLode w) //入栈{s.top++;s.base[s.top].E=w.E;s.base[s.top].e=w.e;}void pop(charstack &s,charLode &w) //出栈{w.E=s.base[s.top].E;w.e=s.base[s.top].e;s.top--;}int IsEmpty(charstack s) //判断是否到栈顶{if(s.top==-1)return 1;elsereturn 0;}int IsLetter(char ch) //判断是不是大写字母（非终结符）if(ch>='A'&&ch<='Z')return 1;elsereturn 0;}//judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法int judge1(int n){int j=3,flag=0;for(int i=0;i<=n;i++)while(str[i][j]!='\0'){char a=str[i][j];char b=str[i][j+1];if(IsLetter(a)&&IsLetter(b)) //两个非终结符相连，不是算符文法{flag=1;break;}elsej++;}if(flag==1) //根据flag设定返回值return 0;elsereturn 1;}//judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法void judge2(int n){for(int i=0;i<=n;i++)if(str[i][3]=='~'||FLAG==1)//'~'代表空{cout<<"文法G不是算符优先文法!"<<endl;FF=0;break;}if(i>n)cout<<"文法G是算符优先文法!"<<endl;}//search1是查看存放终结符的数组r中是否含有重复的终结符int search1(char r[],int kk,char a){for(int i=0;i<kk;i++)if(r[i]==a)break;if(i==kk)return 0;elsereturn 1;}//createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F 数组是一个结构体void createF(int n){int k=0,i=1;char g;char t[10];//t数组用来存放非终结符t[0]=str[0][0];while(i<=n){if(t[k]!=str[i][0]){k++;t[k]=str[i][0];g=t[k];i++;}else i++;}kk=0;char c;for(i=0;i<=n;i++){int j=3;while(str[i][j]!='\0'){c=str[i][j];if(IsLetter(c)==0){if(!search1(r,kk,c))r[kk]=c;kk++;//r数组用来存放终结符}j++;}}m=0;for(i=0;i<k;i++)for(int j=0;j<kk-1;j++){F[m].R=t[i];F[m].r=r[j];F[m].flag=0;m++;}}//search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1 void search(charLode w){for(int i=0;i<m;i++)if(F[i].R==w.E&&F[i].r==w.e){F[i].flag=1;break;}}void FirstVT(int n)//求FirstVT{charstack sta;charLode w;int i=0;Initstack(sta);while(i<=n){int k=3;w.E=str[i][0];char a=str[i][k];char b=str[i][k+1];if(!IsLetter(a)) //产生式的后选式的第一个字符就是终结符的情况 {w.e=a;push(sta,w);search(w);i++;}else if(IsLetter(a)&&b!='\0'&&!IsLetter(b)) //产生式的后选式的第一个字符是非终结符的情况{w.e=b;push(sta,w);search(w);i++;}else i++;}charLode ww;while(!IsEmpty(sta)){pop(sta,ww);for(i=0;i<=n;i++){w.E=str[i][0];if(str[i][3]==ww.E&&str[i][4]=='\0'){w.e=ww.e;push(sta,w);search(w);break;}}}p=0;int k=1;i=1;while(i<m){if(F[i-1].flag==1){arr[p][0]=F[i-1].R;arr[p][k]=F[i-1].r;}while(F[i].flag==0&&i<m)i++;if(F[i].flag==1){if(F[i].R==arr[p][0])k++;else {arr[p][k+1]='\0';p++;k=1;}i++;}}}void LastVT(int n)//求LastVT{charstack sta;charLode w;for(int i=0;i<m;i++)F[i].flag=0;i=0;Initstack(sta);while(i<=n){int k=strlen(str[i]);w.E=str[i][0];char a=str[i][k-1];char b=str[i][k-2];if(!IsLetter(a)){w.e=a;push(sta,w);search(w);i++;}else if(IsLetter(a)&&!IsLetter(b)){w.e=b;push(sta,w);search(w);i++;}else i++;}charLode ee;while(!IsEmpty(sta)){pop(sta,ee);for(i=0;i<=n;i++){w.E=str[i][0];if(str[i][3]==ee.E&&str[i][4]=='\0') {w.e=ee.e;push(sta,w);search(w);}}}int k=1;i=1;ppp=0;while(i<m){if(F[i-1].flag==1){brr[ppp][0]=F[i-1].R;brr[ppp][k]=F[i-1].r;}while(F[i].flag==0&&i<m)i++;if(F[i].flag==1){if(F[i].R==arr[ppp][0])k++;else {brr[ppp][k+1]='\0';ppp++;k=1;} i++;}}}void createYXB(int n)//构造优先表{int i,j;for(j=1;j<=kk;j++)ccrr1[0][j]=r[j-1];for( i=1;i<=kk;i++)ccrr2[i][0]=r[i-1];for(i=1;i<=kk;i++)for(j=1;j<=kk;j++)crr[i][j]=0;int I=0,J=3;while(I<=n){if(str[I][J+1]=='\0') //扫描右部{I++;J=3;}else{while(str[I][J+1]!='\0'){char aa=str[I][J];char bb=str[I][J+1];if(!IsLetter(aa)&&!IsLetter(bb))//优先及等于的情况，用1值表示等于 {for(i=1;i<=kk;i++){if(ccrr2[i][0]==aa)break;}for(j=1;j<=kk;j++){if(ccrr1[0][j]==bb)break;}if(crr[i][j]==0)crr[i][j]=1;else {FLAG=1;I=n+1;}J++;}if(!IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]!='\0'&&!IsLetter(str [I][J+2]))//优先及等于的情况{for(i=1;i<=kk;i++){if(ccrr2[i][0]==aa)break;}for(int j=1;j<=kk;j++){if(ccrr1[0][j]==str[I][J+2])break;}if(crr[i][j]==0)crr[i][j]=1;else{FLAG=1;I=n+1;}}if(!IsLetter(aa)&&IsLetter(bb))//优先及小于的情况，用2值表示小于 {for(i=1;i<=kk;i++){if(aa==ccrr2[i][0])break;}for(j=0;j<=p;j++){if(bb==arr[j][0])break;}for(int mm=1;arr[j][mm]!='\0';mm++){for(int pp=1;pp<=kk;pp++){if(ccrr1[0][pp]==arr[j][mm])break;}if(crr[i][pp]==0)crr[i][pp]=2;else {FLAG=1;I=n+1;}}J++;}if(IsLetter(aa)&&!IsLetter(bb))//优先及大于的情况，用3值表示大于 {for(i=1;i<=kk;i++){if(ccrr1[0][i]==bb)break;}for(j=0;j<=ppp;j++){if(aa==brr[j][0])break;}for(int mm=1;brr[j][mm]!='\0';mm++){for(int pp=1;pp<=kk;pp++){if(ccrr2[pp][0]==brr[j][mm])break;}if(crr[pp][i]==0)crr[pp][i]=3;else {FLAG=1;I=n+1;}}J++;}}}}}//judge3是用来返回在归约过程中两个非终结符相比较的值int judge3(char s,char a){int i=1,j=1;while(ccrr2[i][0]!=s)i++;while(ccrr1[0][j]!=a)j++;if(crr[i][j]==3)return 3;elseif(crr[i][j]==2)return 2;elseif(crr[i][j]==1)return 1;elsereturn 0;}void print(char s[],char STR[][20],int q,int u,int ii,int k)//打印归约的过程{cout<<u<<" ";for(int i=0;i<=k;i++)cout<<s[i];cout<<" ";for(i=q;i<=ii;i++)cout<<STR[0][i];cout<<" ";}void process(char STR[][20],int ii)//对输入的字符串进行归约的过程{cout<<"步骤"<<" "<<"符号栈"<<" "<<"输入串"<<" "<<"动作"<<endl;int k=0,q=0,u=0,b,i,j;char s[40],a;s[k]='#';print(s,STR,q,u,ii,k);cout<<"预备"<<endl;k++;u++;s[k]=STR[0][q];q++;print(s,STR,q,u,ii,k);cout<<"移进"<<endl;while(q<=ii){a=STR[0][q];if(!IsLetter(s[k])) j=k;else j=k-1;b=judge3(s[j],a);if(b==3)//大于的情况进行归约{while(IsLetter(s[j-1]))j--;for(i=j;i<=k;i++)s[i]='\0';k=j;s[k]='N';u++;print(s,STR,q,u,ii,k);cout<<"归约"<<endl;}else if(b==2||b==1)//小于或等于的情况移进{k++;s[k]=a;u++;q++;print(s,STR,q,u,ii,k);if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')cout<<"接受"<<endl;else cout<<"移进"<<endl;}else{cout<<"出错"<<endl;break;}}if(s[0]=='#'&&s[1]=='N'&&s[2]=='#')cout<<"归约成功"<<endl;else cout<<"归约失败"<<endl;}void main(){int n,i,j;cout<<"请输入你要定义的文法G的产生式的个数n:"; cin>>n;cout<<"请输入文法产生式："<<endl;for(i=0;i<n;i++){gets(str[i]);j=strlen(str[i]);str[i][j]='\0';}str[i][0]='Q'; //最末行添加扩展str[i][1]='-';str[i][2]='>';str[i][3]='#';str[i][4]=str[0][0];str[i][5]='#';cout<<"你定义的产生式如下:"<<endl;str[i][6]='\0';for(i=0;i<=n;i++)cout<<str[i]<<endl;if(judge1(n)==0) //判断文法G是否为算符文法cout<<"文法G不是算符文法!"<<endl;if(judge1(n)==1){cout<<"文法G是算符文法!"<<endl;}createF(n);FirstVT(n);LastVT(n);createYXB(n);for(i=0;i<=p;i++)//打印FirstVT{cout<<"FirstVT("<<arr[i][0]<<")={"; for(int l=1;arr[i][l+1]!='\0';l++)cout<<arr[i][l]<<",";cout<<arr[i][l]<<"}"<<endl;}cout<<"FirstVT(Q)={#}"<<endl;for(i=0;i<=ppp;i++)//打印LastVT{cout<<"LastVT("<<arr[i][0]<<")={"; for(int l=1;brr[i][l+1]!='\0';l++)cout<<brr[i][l]<<",";cout<<brr[i][l]<<"}"<<endl;}cout<<"LastVT(Q)={#}"<<endl;cout<<"优先表如下:"<<endl;for(i=1;i<kk;i++)//打印优先关系表{cout<<" ";cout<<ccrr1[0][i];}cout<<endl;for(i=1;i<kk;i++){cout<<ccrr2[i][0]<<" ";for(j=1;j<kk;j++){if(crr[i][j]==0)cout<<" ";else if(crr[i][j]==1)cout<<"=";else if(crr[i][j]==2)cout<<"<";else if(crr[i][j]==3)cout<<">";cout<<" ";}cout<<endl;}judge2(n);//判断文法G是否为算符优先文法 if(FF==1){char STR[1][20];cout<<"请输入要规约的字符串:"<<endl; gets(STR[0]);int ii=strlen(STR[0]);STR[0][ii]='#';cout<<"下面是规约的过程:"<<endl;process(STR,ii);}}。