编译原理——LR(0)分析器

直接输入根据己知文法构造的LR(0)分析表，对于输入的文法和符号串，所编制的语法分析程序应能正确判断此串是否为文法的句子，并要求输出分析过程。

#include<bits/stdc++.h>
using namespace std;
const string ERROR="出错，该句子不被当前文法识别！";
const int MAX=100;	
int gone=0;	//步骤
int state[MAX];	//状态栈
int statetop=-1; //状态栈指针 
char sign[MAX]; //符号栈
int signtop=-1;	//符号栈指针
string s;	//输入串
queue<char> sq;	//存放输入串的队列 
string ACTION[MAX][MAX];	//ACTION表 
int GOTO[MAX][MAX];		//GOTO表 
int sta;	//状态数 
int vt;		//终结符数
int vn;		//非终结符数  
char c;		//暂存字符变量 
map<char,int> mpvt;	//映射ACTION表中终结符的列号 
map<char,int>::iterator vtit;	//遍历vt列号的迭代器 
map<char,int> mpvn;	//映射GOTO表中非终结符的列号 
map<char,int>::iterator vnit;	//遍历vn列号的迭代器 
int ms_num;	//产生式数 
string ms_str; //暂存产生式  
map<int,string> ms;	//保存产生式 
map<int,string>::iterator msit;	//访问产生式映射  
int Action;		//保存从 Si中解析出的要移进的状态
int whichms;	//保存从 ri中解析出的产生式编号 
int Goto;		//保存从 GOTO表中读取的要转向的状态 
string thems;	//保存当前次归约使用的产生式  

int FindSr(string s); 	//将 Si/ri中对应的状态/产生式编号解析出来    
void inputx();	//输入函数 
void outputx();	//输出函数  
void terror();	//出错处理 
void anysit();	//总控程序  
 
int main(){
	inputx();
	anysit();
	return 0;
}
int FindSr(string s){
	int num=0;
	int k;
	int L=s.length();
	for(int i=1;i<L;i++){
		k=s[i]-'0';
		for(int j=i;j<L-1;j++){
			k*=10;
		}
		num+=k;
	}
	if(s[0]=='S'){
		Action=num;
		return Action;
	}
	else{
		whichms=num;
		return whichms;
	}
	
}
void inputx(){
	cout<<"输入文法的产生式的个数：";
	cin>>ms_num;
	cout<<"输入文法的产生式："<<endl;
	for(int i=1;i<=ms_num;i++){
		cin>>ms_str;
		ms[i]=ms_str;
	} 
	cout<<"输入状态数：";
	cin>>sta;
	cout<<"输入终结符数：";
	cin>>vt;
	cout<<"依次输入终结符：";
	for(int i=0;i<vt;i++){
		cin>>c;
		mpvt[c]=i;
	}
	cout<<"输入ACTION表（以 <> 表示空）："<<endl;
	for(int i=0;i<sta;i++){
		for(int j=0;j<vt;j++){
			cin>>ACTION[i][j];
		}
	}
	cout<<"输入非终结符数：";
	cin>>vn;
	cout<<"依次输入非终结符："; 
	for(int i=0;i<vn;i++){
		cin>>c;
		mpvn[c]=i;
	}
	cout<<"输入GOTO表（以 -1 表示空）："<<endl;
	for(int i=0;i<sta;i++){
		for(int j=0;j<vn;j++){
			cin>>GOTO[i][j];
		}
	}
	cout<<"输入要进行LR(0)分析的句子：";
	cin>>s;
	for(int i=0;i<s.length();i++){
		sq.push(s[i]);
	}
}
void outputx(){
	cout<<++gone<<"		";
	for(int i=0;i<=statetop;i++){
		cout<<state[i];
	}cout<<"		";
	for(int i=0;i<=signtop;i++){
		cout<<sign[i];
	}cout<<"		";
	int p=0;
	char x;
	while(p<sq.size()){
		x=sq.front();
		cout<<x;
		sq.pop();
		sq.push(x);
		p++;
	}
	cout<<"		";
}
void terror(){
	cout<<ERROR;
}
void anysit(){
	cout<<"对输入串 "<<s<<" 的LR(0)分析过程："<<endl; 
	cout<<"步骤		"<<"状态栈		"<<"符号栈		"<<"输入串		"<<"ACTION		"<<"GOTO		"<<"归约使用的产生式"<<endl;
	state[++statetop]=0;
	sign[++signtop]='#';
	int x,y;char cc;string now;
	do{
		outputx();
		x=state[statetop];
		cc=sq.front();
		for(vtit=mpvt.begin();vtit!=mpvt.end();vtit++){
			if(vtit->first==cc){
				y=vtit->second;
				break;
			}
		}
		now=ACTION[x][y];
		if(now=="<>"){
			terror();
			cout<<"(ACTION表出错)"<<endl; 
			break;
		}
		else if(now[0]=='S'){
			FindSr(now);
			cout<<now<<endl;
			state[++statetop]=Action;
			sign[++signtop]=cc;
			sq.pop(); 
		} 
		else if(now[0]=='r'){
			int p=FindSr(now);
			for(msit=ms.begin();msit!=ms.end();msit++){
				if(msit->first==p){
					thems=msit->second;
					break;
				}
			}
			for(int k=thems.length()-1;k>2;k--){
				if(sign[signtop]==thems[k]){
					signtop--;
					statetop--;
				}
			}
			sign[++signtop]=thems[0];
			x=state[statetop];
			cc=sign[signtop];
			for(vnit=mpvn.begin();vnit!=mpvn.end();vnit++){
				if(vnit->first==cc){
					y=vnit->second;
					break;
				}
			}
			Goto=GOTO[x][y];
			if(Goto==-1){
				terror();
				cout<<"(GOTO表出错)"<<endl; 
				break;
			}
			cout<<now<<"		"<<Goto<<"		"<<thems<<endl;
			state[++statetop]=Goto;
		}
	}while(now!="acc");
	if(now=="acc"){
		cout<<now<<endl;
		cout<<"该句子被成功识别！"<<endl; 
	}
}

输入：