算符优先分析.cpp

算符优先文法的一个实现

/*****************************************
算符优先文法  计算机04-1 王润 2004031124
******************************************/
#include<iostream>
using namespace std;

int position( char c)         // 查询c在字符串"+*^i()#"中的位置并返回位置的值
{
  char chars[ 8 ] = "+*^i()#";
  for( int i = 0; i < 8; i++ )
  if( chars[ i ] == c )
  {
	return i;
	break;
  }
  return -1;
}

int relation( char c1, char c2 )   //返回值为-1 : <.   0 : =.   1 : >
{
	int f[ 7 ] = { 3, 5, 5, 7, 1, 7, 1 };
	int g[ 7 ] = { 2, 4, 6, 6, 6, 1, 1 };//定义+*^i()#的优先函数的值
	if( f[ position( c1 ) ] < g[ position( c2 ) ] )
	return -1;
    
	else if( f[ position( c1 ) ] == g[ position( c2 ) ] )
	return 0;

	else if( f[ position( c1 ) ] > g[ position( c2 ) ] )
	return 1;
	
	else return -2;
}

int isTerminate( char c )//获得字符c是否在字符串"+*^i()#"中
{
	char chars[ 8 ] = "+*^i()#";
	for( int i = 0; i < 7; i++ )
	if( chars[ i ] == c )
	return 1;
    return 0;
}

char getChar( int& N, char *c )//返回c数组中下标为N的字符
{
	N++;
	return c[ N ];
}

void error()//输出错误
{
	cout << " oh! error! " << endl;
}

int main()
{
	int k=0;                                       
    int	Q;
    int	j;                                      //栈标
	int	count;                                  //循环计数器
	int	flag = 1;                               //主循环标记
	char a;                                     //记录当前符号
    char *analysis = "i+i*i#";                  //初始化**********************
	char s[ 10 ] = { '\0' };
	int N = -1; 
	cout<<"***********************************************************"<<endl;
	cout<<"\n****　　　　　对输入串i+i*i的算符优先规约过程　　　 　****"<<endl;
    cout<<"\n***********************************************************"<<endl;
	s[ k ] = '#';
	a = getChar( N, analysis );
    while( flag )
	{
		for( count = 0; count <= k; count++ )
			cout << s[ count ] ;
		for( count = k; count < 10 ; count++ )
			cout << " ";
		cout << "          " << a << "    ";
		for( count = 0; count < N; count++ )
			cout << " ";
		for( count = N + 1; analysis[ count ] != '\0'; count++ )
			cout << analysis[ count ];
		//a = getChar();

		if( isTerminate( s[k] ) )
			j = k;
		else
			j = k - 1;

		if( relation( s[j], a ) == 1 )
		{
			cout << "   >.  ";
			do
			{
				Q = s[ j ];
				if( isTerminate( s[j - 1] ) )
					j--;
				else 
					j = j - 2;
			}while( !( relation( s[j], Q ) ) );
            k = j + 1;                          //归约              
			s[ k ] = 'N';
			cout << "     归约"; 
		}
		else
		{
			if( relation( s[j], a ) == -1 )
			{
				cout << "   <.  ";
				k++;
				s[ k ] = a;
				a = getChar( N, analysis );
				cout << "     移进";
			}// if
			else
			{
				cout << "   =.  ";
				if( relation( s[j], a ) == 0 )
				{
					if( relation( s[j], '#' ) == 0 )
					{
						cout << "     接受" << endl;
						cout << "***********************************************************"<<endl;
						cout << "RIGHT! " << endl;
						flag = 0;
					}
					else
					{
						k++;
						s[k] = a;
						//cout << "     移进";
					}
				}
				else
				{
					error();
					flag = 0;
				}
			}		
		}
		cout << endl;
	}

	return 0;
}