// Note:Your choice is C++ IDE
#include <string.h>
#include <iostream.h>
void main(){
int g,h,i,j,l,p,y,z,count;
int a[10]; //状态栈
int ni[10]; //存放输出逆波兰式的参数
char b[10]; //符号栈
char str[10]; //放输入的表达式
char c1;
int top1,top2,top3,top,topn,m,n;
char x;
char copy[10]; //放Si,ri,看移进还是归约
char copy1[10];
char vt[6]={'+','*','i','(',')','#'}; //存放非终结符
char vn='E';//存放终结符
char *LR[4]={"E->E+E",
"E->E*E",
"E->(E)",
"E->i"
};//存放产生式
char *action[10][6]={ NULL,NULL,"S3#","S2#",NULL,NULL,//ACTION[i,a]规定了栈顶状态为i时遇到输入符号a应执行
"S4#","S5#",NULL,NULL,NULL,"acc",
NULL,NULL,"S3#","S2#",NULL,NULL,
"r4#","r4#",NULL,NULL,"r4#","r4#",
NULL,NULL,"S3#","S2#",NULL,NULL,
NULL,NULL,"S3#","S2#",NULL,NULL,
"S4#","S5#",NULL,NULL,"S9",NULL,
"r1#","S5#",NULL,NULL,"r1#","r1#",
"r2#","r2#",NULL,NULL,"r2#","r2#",
"r3#","r3#",NULL,NULL,"r3#","r3#"
};
int goto1[10]={1,//状态转换表用GOTO[i,X]=j表示,规定当栈顶状态为i,
0,//遇到当前文法符号为X时应转向状态j,X为终结符或非终结符。
6,
0,
7,
8,
0,
0,
0,
0
};
top1=0;top2=0;top3=0;top=0;topn=0;
a[0]=0;y=a[0];b[0]='#';
count=0;z=0;
cout<<"文法G[E]:"<<endl;
cout<<'\t'<<"(1) E::=E+E"<<endl;
cout<<'\t'<<"(2) E::=E*E"<<endl;
cout<<'\t'<<"(3) E::=(E)|i"<<endl;
cout<<"文法G[E]合法句子举例: i+i*i"<<endl;
cout<<"*************************************************************"<<endl;
cout<<"请输入符号串:"<<endl;
cin>>str;
l = strlen(str);
str [ l ] = '#';
for(i=l+1;i<10;i++){
str[i]=NULL;
}
cout<<endl<<'\t'<<'\t'<<"符号串"<<str<<" 分析过程如下:"<<endl;
cout<<"-----------------------------------------------------------------"<<endl;
cout<< "步骤" << '\t' << "状态栈" << '\t' << '\t' << "符号栈" << '\t' << '\t' << "输入串" << '\t' <<'\t'<< "ACTION "<<'\t'<<"GOTO"<<endl;
do{
y=z;m=0;n=0; //y,z指向状态栈栈顶
g=top;j=0;
x=str[top];
count++;
cout<<count <<'\t';
while(m<=top1)
{ //输出状态栈
cout<<a[m];
m=m+1;
}
cout<<'\t'<<'\t';
while(n<=top2)
{ //输出符号栈
cout<<b[n];
n=n+1;
}
cout<<'\t'<<'\t';
str[top-1] = ' ';
cout<<str; //输出输入串
cout<<'\t'<<'\t';
while(x!=vt[j]&&j<=6) j++; //vt[6]={'+','*','i','(',')','#'}存放终结符
if(j==6&&x!=vt[j]){
cout<<endl<<"-----------------------------------------------------------------"<<endl;
cout<<endl<<"输入字符串不是该文法的一个句子!"<<endl;
cout<<endl<<"按任意数字或字母键,回车退出!"<<endl;
cin>>i;
return;
}
if(action[y][j]==NULL){
cout<<endl<<"-----------------------------------------------------------------"<<endl;
cout<<endl<<"输入字符串不是该文法的一个句子!"<<endl;
cout<<endl<<"按任意数字或字母键,回车退出!"<<endl;
cin>>i;
return;
}
else
//cout<<"y="<<y<<"j="<<j<<" "<<action[y][j];
strcpy(copy,action[y][j]);
if(copy[0]=='S'){ //处理移进
z=copy[1]-'0';
top1=top1+1;
top2=top2+1;
a[top1]=z; //a[10]状态栈
b[top2]=x; //b[10]符号栈 x=str[top]
top=top+1;
i=0;
while(copy[i]!='#'){
cout<<copy[i];
i++;
}
cout<<endl;
}
//cout<<"y="<<y<<"j="<<j<<" "<<action[y][j];
if(copy[0]=='r'){ //处理归约
i=0;
while(copy[i]!='#'){
cout<<copy[i];
i++;
}
h=copy[1]-'0';
ni[topn]=h;
topn=topn+1;
h=h-1;
strcpy(copy1,LR[h]);//*LR[4]={"E->E+E#","E->E*E#","E->(E)#","E->i#"}存放产生式
//while(copy1[0]!=vn[0]) k++;//vn[1]={'E'}存放非终结符
l=strlen(LR[h]);
top1=top1-l+3;
y=a[top1];
//cout<<"top1="<<top1;
//y=h-1;
p=goto1[y];
top2=top2-l+4;
top1=top1+1;
a[top1]=p;
b[top2]=copy1[0];
z=p;
cout<<'\t';
cout<<p<<endl;
}
}while(action[y][j]!="acc");
cout<<"acc"<<endl;
cout<<endl<<"-------------------------------------------------------------"<<endl;
cout<<endl<<"输入字符串是该文法的一个句子!"<<endl;
cout<<"中间代码的逆波兰式如下:"<<endl;
for(i=0;i<10;i++){
if(ni[i]==1)
cout<<"EEE+="<<endl;
if(ni[i]==2)
cout<<"EEE*="<<endl;
if(ni[i]==3)
cout<<"EE()="<<endl;
if(ni[i]==4)
cout<<"iE="<<endl;
}
cout<<endl<<"按任意数字或字母键,回车退出!"<<endl;
cin>>i;
}