ex4.cpp

实现LR(0)算法,在构造好的action和goto表的情况下实现LR(0)算法的句子分析过程

#include<iostream>
#include<string>
using namespace std;
#define max 20  //句子的最大长度
#define GrammarNum 4 //文法的表达式的个数
int OperaterStackTop;  //指向符号栈顶
int InputStringTop;    //指向输入串当前第一元素
int StateStackTop;    //指向状态栈
int num;//输入串长度
char OperaterStack[max]; //符号栈
char InputString[max]; //输入串
int  StateStack[max];  //状态栈
enum Vt{a,c,e,b,d,neq};  //终结符关键字
enum Vn{S,A,B};  //非终结符关键字
string action;  //表示ACTION表中的内容
string OperaterStackAction;  //用来显示动作
//Action表
string ActionTable[10][6]={
	{"s2","","","","",""},
	{"","","","","","acc"},
	{"","","","s4","",""},
	{"","s5","","s6","",""},
	{"r2","r2","r2","r2","r2","r2"},
	{"","","","","s8",""},
	{"r3","r3","r3","r3","r3","r3"},
	{"","","s9","","",""},
	{"r4","r4","r4","r4","r4","r4"},
	{"r1","r1","r1","r1","r1","r1"}
};
//GOTO表
int GotoTable[10][3]={
	{1,0,0},
	{0,0,0},
	{0,3,0},
	{0,0,0},
	{0,0,0},
	{0,0,7},
	{0,0,0},
	{0,0,0},
	{0,0,0},
	{0,0,0}
};
//表达式结构体
struct ProduceFormula
{
	
	char leftPart;  //左边
	string rightPart; //右边
	
};
ProduceFormula Grammar[GrammarNum];  //文法，由表达式数组构成
//初始化表达式
void InitGrammar()
{
	
	Grammar[0].leftPart='S';
	Grammar[0].rightPart="aAcBe";
	

	Grammar[1].leftPart='A';
	Grammar[1].rightPart="b";
	

	Grammar[2].leftPart='A';
	Grammar[2].rightPart="Ab";
	

	Grammar[3].leftPart='B';
	Grammar[3].rightPart="d";
	


}
//判断是否是终结符
bool IsVt(char a)
{
	switch(a)
	{
	case'a':
	case'b':
	case'c':
	case'd':
	case'e':
	case'#':
		return true;
	
	default:
		return false;
		
	}

}

//取得终结符号的sym的函数
Vt getVtsym(char n)
{
	if(n=='a')
		return a;
	else if(n=='c')
		return c;
	else if(n=='e')
		return e;
	else if(n=='b')
		return b;
	else if(n=='d')
		return d;
	else 
		return neq;

}
//取得非终结符号的sym的函数
Vn getVnsym(char n)
{
	if(n=='S')
     return S;
	else if(n=='A')
     return A;
	else 
	 return B;
}
//显示符号栈
void DisplayOperaterStack()
{
	for(int i=0;i<=OperaterStackTop;i++)
		cout<<OperaterStack[i];
}
//显示当前输入串
void DisplayInputString()
{
	for(int i=InputStringTop;i<=num;i++)
		cout<<InputString[i];

}
//显示状态栈
void DisplayStateStack()
{
	for(int i=0;i<=StateStackTop;i++)
		cout<<StateStack[i];
}
//显示
void Display()
{
	cout<<endl<<"-------------------------------------------------------------------------"<<endl;
	DisplayOperaterStack();
		cout<<"          ";
		DisplayInputString();
		cout<<"      "<<OperaterStackAction<<"          ";  //显示动作
		DisplayStateStack();
		cout<<"          ";
		cout<<action;   //显示ACTION表中的内容
		cout<<"        ";
		

}
bool SearchTable();  //查找表函数
bool SearchActionTable();  //查找ACTION表函数
bool SearchGotoTable();  //查找GOTO表函数
//LR算法
void LR()
{ 
	cout<<"-------------------------------------------------------------------------"<<endl;
	cout<<endl<<"符号栈     "<<"输入串     "<<"动作           "<<"状态栈     "<<"ACTION    "<<"GOTO";
	
	bool state;
	do{
	state=SearchTable();
	}while(state);
	 cout<<endl<<"-------------------------------------------------------------------------"<<endl;
  
}
//查找表函数
bool SearchTable()
{
	bool InputStringTopIsVt=IsVt(InputString[InputStringTop]); //判断当前输入串的第一个元素是否是终结符
	if(InputStringTopIsVt) //当前输入串的第一个元素是终结符
	{
	     return SearchActionTable();  //查找ACTION表函数
	}
	else  //当前输入串的第一个元素不是终结符，返回错误
	{
		OperaterStackAction="错误";   
		Display();
		return false;
	}




}
bool SearchActionTable()
{
	enum Vt InputStringVtsym=getVtsym(InputString[InputStringTop]); //取得当前输入串的第一个元素的关键字
	int StateStackTopNum=StateStack[StateStackTop];  //取得状态栈栈顶
	action=ActionTable[StateStackTopNum][InputStringVtsym];  //查找取得相应ACTION表里的内容
	if(action=="acc")  //如果ACTION表中是acc的话
	{
		OperaterStackAction="接受";
		Display();
		return false;
	}
	else if(action[0]=='s')//如果ACTION表中是以s开头的
	{
		OperaterStackAction="移进";
		Display();
		OperaterStack[++OperaterStackTop]=InputString[InputStringTop++]; //符号栈栈顶+1并将输入串中的第一个元素压入符号栈栈顶，输入串中的第一个元素往后移
		StateStack[++StateStackTop]=action[1]-'0';  //状态栈栈顶+1并将ACTION表s后的那个数字压入栈顶
	    return true;
	}
	else if(action[0]=='r')//如果ACTION表中是以r开头的
	{
		
		int ProduceFormulaNum=action[1]-'0';
	
		OperaterStackAction="归约";
		
		Display();
		
		OperaterStackTop=OperaterStackTop-Grammar[ProduceFormulaNum-1].rightPart.length();//符号栈顶减去把要归约表达式右边长度
		StateStackTop=StateStackTop-Grammar[ProduceFormulaNum-1].rightPart.length();//状态栈顶减去把要归约表达式右边长度
		OperaterStack[++OperaterStackTop]=Grammar[ProduceFormulaNum-1].leftPart;//符号栈顶+1，并将归约表达式左边压入栈顶
		return SearchGotoTable(); //查找GOTO表

	}
	else  //在ACTION表中为空，返回错误
	{
		OperaterStackAction="错误";
		Display();
	
	return false;
	}



}
//查找GOTO表
bool SearchGotoTable()
{
	enum Vn GotoStackVtsym=getVnsym(OperaterStack[OperaterStackTop]); //取得符号栈中栈顶元素的关键字
	int StateStackTopNum=StateStack[StateStackTop];  //取得状态栈顶
	int Goto=GotoTable[StateStackTopNum][GotoStackVtsym];  //根据上面两个内容查找GOTO表中的内容
	if(Goto==0)  //如果是为0，也就是没有意义的，返回错误
	{
		
		cout<<"error!";
	    return false;
	}
	else   //如果是有内容则输出其内容
	{
		cout<<Goto;
		
		StateStack[++StateStackTop]=Goto;  //状态栈顶+1，并将GOTO表中内容压进栈顶
		return true;

	}




}

void main()
{

	InitGrammar();
	cout<<"文法G[S]为："<<endl;
	for(int i=0;i<GrammarNum;i++)
	{
		cout<<Grammar[i].leftPart<<"->"<<Grammar[i].rightPart<<endl;
	}
	cout<<"请输入句子（以#结束）：";
	num=0;
do
	{
		cin>>InputString[num++];
		
	}while(InputString[num-1]!='#');
     num-=1;
    OperaterStack[0]='#';
	OperaterStackTop=0;
	StateStack[0]=0;
	StateStackTop=0;
	InputStringTop=0;
	LR();
	
}