sfyx.cpp

算符优先分析算法的实现

//
//程序名称：算符优先分析程序
//程序作者：   张焕人
//作者邮箱: [e-mail]  
//          [e-mail]
//作者QQ：27949278
//

/*   对于给定文法，进行算符优先分析
    E->E+T|E-T|T   
    T->T*F|T/F|F   
    F->(E)|i   


        算符优先关系表   
-------------------------------- 
     +   -   *   /   (   )   i   #  
 +   >   >   <   <   <   >   <   >  
 -   >   >   <   <   <   >   <   >  
 *   >   >   >   >   <   >   <   >  
 /   >   >   >   >   <   >   <   > 
 (   <   <   <   <   <   =   <   -  
 )   >   >   >   >   -   >   -   >  
 i   >   >   >   >   -   >   -   >   
 #   <   <   <   <   <   -   <   =  
*/
#include <stdio.h>
#include <iostream.h>
#include <string.h>
#define MAX 256
struct Lchar{
 char char_ch;
 struct Lchar *next;
}Lchar,*p,*h,*temp;  //p指向当前输入的字符
char table[8][8]={   //算符优先表
	{'>','>','<','<','<','>','<','>'},
    {'>','>','<','<','<','>','<','>'},
    {'>','>','>','>','<','>','<','>'},
    {'>','>','>','>','<','>','<','>'},
    {'<','<','<','<','<','=','<','?'},
    {'>','>','>','>','?','>','?','>'},
    {'>','>','>','>','?','>','?','>'},
    {'<','<','<','<','<','?','<','='}};
//存储算符优先关系表，大于为>，小于<或等于为=，其它?表示出错

char stack[MAX];
int right;  //判断是否出错的标志
int top=0,base=0; //栈顶和栈底指针

void push(char ch)  //入栈函数
{
 stack[top++]=ch;
}

char pop()  //出栈函数
{
 return stack[--top];
}


int char2int(char ch)  //将字符转为数字，以得到算符优先值
{
 int t;
 switch(ch)
 {
  case '+':t=0;break;
  case '-':t=1;break;
  case '*':t=2;break;
  case '/':t=3;break;
  case '(':t=4;break;
  case ')':t=5;break;
  case 'i':t=6;break;
  case '#':t=7;
 }
 return t;
}

void dosome(void)
{
	char curchar;
	char curcmp;
	int i,j;
	int k;  //比较字符在栈的位置

	push('#');  //将程序结束标志'#'压入堆栈
 	cout<<endl<<"\t\t     分析字符串(";
	for(temp=p;temp!=NULL;temp=temp->next) //打印待比较的字符
		cout<<temp->char_ch;
    cout<<")的过程"<<endl;
	cout<<"\t符号栈\t\t算符关系\t输入串\t\t最左素短语";
	while(true)
 {
  curchar=p->char_ch;
  k=top-1;
  
  if(stack[k]=='N')    
  	k--; //如果当前比较字符为非终结符，则指向下一个终结符
  curcmp=stack[k];
  
  i=char2int(curcmp);
  j=char2int(curchar);

  cout<<endl<<"\t";
  for(k=base;k<top;k++) //打印栈
     cout<<stack[k];
  if(top<=9)  //判断符号栈里字符大小来确定制表位，使输出显示更加整齐
	  cout<<"\t\t"<<table[i][j]<<"\t\t";  //输出优先关系表中的优先关系
  else
	  cout<<"\t"<<table[i][j]<<"\t\t";
  
  for(temp=p;temp!=NULL;temp=temp->next) //打印待比较的字符
     cout<<temp->char_ch;
  
  
  if(table[i][j]=='<'||table[i][j]=='=') //算符优先值为-1 <或=
  {
  	if(curchar=='#')/*待比较字符为空*/
    {
     if(top==2) //当前比较字符在栈的位置为两个元素
      break;
     else
     {
      cout<<"字符串未能匹配"<<endl;
      right=0;
      break;
     }
    }
    push(curchar);
    p=p->next;
  }
  else if (table[i][j]=='>') //算符优先值为 >  进行规约
  {
  	if(curcmp=='i')  //当前比较为i,出栈一次 
     cout<<"\t\t"<<pop();
    else  //当前比较不为i,出栈三次
    {
     cout<<"\t\t"<<pop()<<pop()<<pop();
    }   /*本程序在这里只有两种归约情况,
	因此采用了判断当前比较字符是否为i的办法来确定最左素短语
	--更易于推广的方法应当是按优先算符标来确定最左素短语*/
    push('N');/*归约到N*/
   
  }
  else  //不存在算符优先值
  {
  	 right=0;
     break;
  }
 } 
}

void main(void)
{
 char st[MAX],ch;
 int len,l=0;
 right=1;
 top=base=0;
 
 
 h=new struct Lchar;  //初始化输入串的队列
 h->next=NULL;
 p=h;
 
 cout<<"请输入要分析的字符串: ";
 cin>>st;
 len=strlen(st);

 do{    //输入待比较字符串，以'#'结束
  
  ch=st[l++];
  if(ch=='i'||ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
  {
   temp=new struct Lchar;
   temp->next=NULL;
   temp->char_ch=ch;
   p->next=temp;
   p=p->next;
  }
  else
  {
   temp=h->next;
   cout<<"\n字符输入错误\n";
   while(true)
   {    
    if (temp!=NULL)
     cout<<temp->char_ch;      
    else
     break;
    temp=temp->next;
   }
  }
 }while(ch!='#'&&l<len);/*输入待比较字符串，以'#'结束*/
 if (ch!='#') //如果用户未输入结束标记符，自动添加一个
 {
	 temp=new struct Lchar;
   temp->next=NULL;
   temp->char_ch='#';
   p->next=temp;
   p=p->next;
 }

 p=h->next;
 dosome();/*开始识别*/
 if(right)
  cout<<"\n输入串正确识别!\n";
 else
  cout<<"\n输入串识别错误!\n";
 
}