lr.cpp

算符优先分析法

// 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;
}