www.cpp

编译原理的一个题目：算符优先分析

#include<iostream>
#include<fstream>
#include<string>
#include<fstream>	
#include<iomanip>
using namespace std;
/*文法的定义
标号所代表的式子
1: s->a=E
2: E->TM   (M代表e1)
3: M->+TM
4: M->ξ   
5: T->FN
6: N->*FN
7: N->ξ
8: F->(E)
9: F->i
*/

//下面是主函数
//本程序中的FIRST和FOLLOW集合元素没用程序自动生成,而是先自己算好,然后构建出预测分析表
//并且预测分析表中的元素用表达式的序号表示
void main()
{
	int n=0,m=0,i,j,top,k; //top为字幅栈栈顶指针，j指示输入流中的下标
	int  LL1[6][8];   //LL1数组用来表示LL1分析表
	int  h=0,l=0;     //LL1数组的行和列
	ifstream infile("LL1b.txt");//导入LL1分析表
	
	for(i=0;i<6;i++)     //从行开始一行行导入
		for(k=0;k<8;k++)
			infile>>LL1[i][k];
	
		char stack[50];     //符号栈的初始化大小

	char in[30]; //输入串的初始化大小
	char x;  //输入字符

	cout<<"请输入字符串（以#结束且长度不超过30）:   ";

	for(i=0;i<30;i++)//按不大于30个字符大小进行输入
	{
		cin>>in[i];
		n=n+1;
		if(in[i]=='#')i=30;  //以＃结束字符的输入
	}
	j=0,top=1;         //输入流第一个字符指示下标为j=0，top指向栈顶元素

	stack[0]='#',stack[1]='S';   //符号栈栈底为＃，栈顶初始化为S
	
	char wjm[256];	  //输入目的文件名
	cout<<"输入目的文件名:";
	cin>>wjm;
	
	ofstream out(wjm);   //将输出结果输出到目的文件中
	out<<"符号栈"<<'\t'<<'\t'<<"  输入流"<<'\t'<<'\t'<<"  所用规则式"<<endl;
	
	for( i=0;i<=top;i++)     //输出符号栈里的符号
		out<<stack[i];  //从符号栈栈底到栈顶依次输出符号
	out<<'\t'<<'\t';    
	for(i=0;i<n;i++)         //输出输入流中的字符
	{
		if(i<j)out<<" "; //依次输出输入字符串
		else if(i>=i)
			out<<in[i];
	}
	out<<endl;   //输出结束

	
	for(;j<n;)       
	{ 
		x=in[j];   //x为输入流的首字符
		if(j==0)x='$';        //非终结符
		else if(x>='a'&&x<='z')   //小写字母终结符
			x='i';
	
		else if(x=='-')x='+';   //运算符“－”与“＋”一样
		else if(x=='/')x='*';   //运算符“/”与“×”一样

		else if(x>='0'&&x<='9')  //数字也属于终结符
			x='i';

	    if(stack[top]==in[j])   //如果字符栈中栈顶符号与输入流首字符相同，
		{
			top=top-1;j=j+1;   //则将相同元素去掉
			
			for( i=0;i<=top;i++)  //按新的栈内元素和输入流重新输出一遍
				out<<stack[i];

			out<<'\t'<<'\t';
			for(i=0;i<n;i++)
			{
				if(i<j)out<<" ";
				else if(i>=i)
					out<<in[i];
			}
			out<<endl;
		}		
		else 
		{
			switch(stack[top])      //栈顶元素对应预测分析表的行
			{
			case 'S': h=0;break;
			case 'E': h=1;break;
			case 'M': h=2;break;
			case 'T': h=3;break;
			case 'N': h=4;break;
			case 'F': h=5;break;
			}
			switch(x)              //输入流首字符对应预测分析表的列
			{
			case 'i': l=0;break;
			case '(': l=1;break;
			case ')': l=2;break;
			case '+': l=3;break;
			case '*': l=4;break;
			case '$': l=5;break;
			case '=': l=6;break;
			case '#': l=7;break;
			}
			
			m=LL1[h][l];                 //m为预测分析表中的矩阵元素
							        
	     	//m所对应的终结符x和非终结符U，有如下方法构建分析表：
			//(1) U－>x,则置M[U,FIRST(x)]=(U->x)序号；
			//(2) U－>ε,则置M[U,FOLLOW(U)]=(U->ε)序号。
			//否则,m=0
			if(m==0)					 
			{
				cout<<"输入的表达式或赋值语句不正确!匹配出错!"<<endl;
				out<<"匹配出错!!!"<<endl;
				j=n;
			}
			else if(m>0)
			{
				switch(m)                   //
				{
				case 1:  					//s->a=E
					stack[top++]='E';
					stack[top++]='=';
					stack[top]=in[j];
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
						else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					out<<"S->a=E"<<endl;break;
				case 2:
					stack[top++]='M';     //E->TM
					stack[top]='T';
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
						else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					out<<"E->TM"<<endl;break;
				case 3:
					stack[top++]='M';    //M->+TM
					stack[top++]='T';
					if(in[j]=='+')
						stack[top]='+';
					else stack[top]='-';
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
						else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					if(stack[top]=='-')
						out<<"M->-TM"<<endl;
					else out<<"M->+TM"<<endl;break;
			
				case 4:							//M->ξ
					top=top-1;
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=j;i<n;i++)
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
						else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					out<<"M->ξ"<<endl;break;
				case 5:                            //T->FN
					stack[top++]='N';
					stack[top]='F';
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
					    else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					out<<"T->FN"<<endl;break;
				
				case 6:                             //N->*FN
					stack[top++]='N';
					stack[top++]='F';
					if(in[j]=='*')
						stack[top]='*';
					else stack[top]='/';
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
					    else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					if(stack[top]=='/')
						out<<"N->/FN"<<endl;
					else out<<"N->*FN"<<endl;break;
				
				case 7:                          //N->ξ
					top=top-1;			
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
					    else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					out<<"N->ξ"<<endl;break;
				case 8:                            //F->(E)
					stack[top++]=')';
					stack[top++]='E';
					stack[top]='(';
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
				    for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
						else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					out<<"F->(E)"<<endl;break;
			
				case 9:                              //F->i
					stack[top]=in[j];
					for( i=0;i<=top;i++)
						out<<stack[i];
					out<<'\t'<<'\t';
					for(i=0;i<n;i++)
					{
						if(i<j)out<<" ";
						else if(i>=i)
							out<<in[i];
					}
					out<<'\t'<<'\t';
					out<<"F->i"<<endl;break;

				}//switch
			}//else
		}//else
		if(stack[top]=='#'&&in[j]=='#')   //栈顶元素和输入流首字符斗为＃，则OK
		{
			cout<<"成功匹配!!"<<endl;
			out<<"成功匹配!!!"<<endl;
			j=n;
		}
}//for
}