a4.cpp

编译课程设计的LR分析

//根据下列文法建立LR(0)分析表,并对输入串进行语法分析
// (0) S→E
// (1) E→aA
// (2) E→bB
// (3) A→cA
// (4) A→d
// (5) B→cB
// (6) B→d              即:课本109页例5.10
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <string.h>

class stack{
public:
	stack();
	void spush(int a);     
	void xpush(char ch);   
	void pop();
	int get_s_top();
	char get_x_top();
	void sdisp();
	void xdisp();
private:
	int s[100];            //状态栈
	char x[100];           //符号栈
	int s_top;             //状态栈的栈顶指针
	int x_top;             //符号栈的栈顶指针
};

stack::stack()             //初始化堆栈
{
	s[0]=0;               
	x[0]='#';
	x[1]='\0';
	s_top=1;
	x_top=1;
}

void stack::spush(int a)    //压状态入栈
{
	s[s_top]=a;
	s_top++;	
}

void stack::xpush(char ch)  //压符号入栈
{
	x[x_top]=ch;
	x_top++;
	x[x_top]='\0';
}

void stack::pop()           //符号栈和状态栈同时弹出一个元素
{
	s_top--;
	x_top--;
}

int stack::get_s_top()      //取状态栈的栈顶元素
{
	return s[s_top-1];
}

char stack::get_x_top()     //取符号栈的栈顶元素
{
	return x[x_top-1];
}

void stack::sdisp()        //显示状态栈的内容
{
	int i,k=0;
	for (i=0;i<s_top;i++)
	{
		if (s[i]>9)	
		{
			cout<<'('<<s[i]<<')';
			k+=4;
		}
		else 
		{
			cout<<s[i];
			k++;
		}
	}
	for (i=1;i<=20-k;i++) cout<<' ';

}

void stack::xdisp()       //显示符号栈的内容
{
	cout<<x<<' ';
}

struct act          //定义Action表中元素的结构体
{
	bool s;         //s==true表入栈动作,s==false表规约动作
	int num;        //s==true,为的状态号;s==false,为规约所用的产生式编号
};

class table{        //定义分析表的类
public:
	table();
	void check_action(int a,char b,act * c);
	int check_goto(int a,char b);
private:
	act action[12][5];
	int go_to[12][3];
};

table::table()       //存入action表和go_to表
{
	int i,j,k;
	for (i=0;i<12;i++)
	{
		for (j=0;j<5;j++)
		{
			action[i][j].s=true;
			action[i][j].num=0;
		}
		for (k=0;k<3;k++) go_to[i][k]=0;
	}
	action[0][0].num=2;
	action[0][1].num=3;
	action[1][4].num=-1;       //-1表示接收
	action[2][2].num=4;
	action[2][3].num=10;
	action[3][2].num=5;
	action[3][3].num=11;
	action[4][2].num=4;
	action[4][3].num=10;
	action[5][2].num=5;
	action[5][3].num=11;
	for (j=0;j<5;j++) {action[6][j].s=false;action[6][j].num=1;}
	for (j=0;j<5;j++) {action[7][j].s=false;action[7][j].num=2;}
	for (j=0;j<5;j++) {action[8][j].s=false;action[8][j].num=3;}
	for (j=0;j<5;j++) {action[9][j].s=false;action[9][j].num=5;}
	for (j=0;j<5;j++) {action[10][j].s=false;action[10][j].num=4;}
	for (j=0;j<5;j++) {action[11][j].s=false;action[11][j].num=6;} 
	//至此,action表已全部存入
	go_to[0][0]=1;
	go_to[2][1]=6;
	go_to[3][2]=7;
	go_to[4][1]=8;
	go_to[5][2]=9;  //go_to表全部存入
}

void table::check_action(int a,char b,act* c)   //查action表,返回动作
{
	char * str="abcd#";
	int j;
	for (j=0;j<=4;j++)
		if (*(str+j)==b) break;
	if (j>4)                        //输入串中出现不在终结符集合中的字符
	{
		cout<<"输入串不能由该文法推导!"<<endl;
		exit(1);
	}
	c->s=action[a][j].s;
	c->num=action[a][j].num ;
}

int table::check_goto(int a,char b)        //查go_to表
{
	int j;
	if (b=='E') j=0;
	else if (b=='A') j=1;
	else j=2;
	return go_to[a][j];
}

struct formular            //定义产生式结构体
{
	char left;             //产生式左部
	char * right;          //产生式右部
};


void main()                  //LR(0)分析的主控程序
{
	int k,i,len,p;
	char input[100];         //存放输入的字符串
	stack stk;               //定义栈
	table tbl;               //定义分析表类对象
	act x;                   //定义act结构体变量
	formular equ[7];         //定义产生式数组,存放所有的产生式
    equ[0].left ='S';equ[0].right ="E";
	equ[1].left ='E';equ[1].right ="aA";
	equ[2].left ='E';equ[2].right ="bB";
	equ[3].left ='A';equ[3].right ="cA";
	equ[4].left ='A';equ[4].right ="d";
	equ[5].left ='B';equ[5].right ="cB";
	equ[6].left ='B';equ[6].right ="d";     //存入所有的产生式
	cout<<"请输入待分析的字符串:"<<endl;
	cin>>input;
	len=strlen(input);       //计算输入串的长度
	input[len++]='#';
	input[len]='\0';
	p=0;                     //指向输入串的当前字符
	cout.setf(ios::left);
	cout<<setw(20)<<"状  态"<<setw(20)<<"符 号"<<setw(20)<<"输入串"<<endl;
	while (true)
	{
		stk.sdisp();
		cout<<setw(20);
		stk.xdisp();
		cout<<setw(20);
		cout<<(input+p)<<endl;
		tbl.check_action (stk.get_s_top() ,*(input+p),&x);
		if (x.num==-1)
		{
			cout<<"分析成功!输入串可以由该文法推导!"<<endl;
			break;
		}
		if (x.num ==0)
		{
			cout<<"输入串不能由该文法推导!"<<endl;
			break;
		}
		if (x.s==true)         //查action表,入栈操作
		{
			stk.spush (x.num);
			stk.xpush (*(input+p));
			p++;
		}
		else                  //查action表,规约操作
		{
			len=strlen(equ[x.num].right);        //计算产生式右部的长度
			for (i=1;i<=len;i++) stk.pop();      //从栈中弹出len个元素
			stk.xpush(equ[x.num].left);          //产生式左部进栈
			k=tbl.check_goto(stk.get_s_top(),stk.get_x_top());  //查go_to表
			if (k==0) 
			{
				cout<<"输入串不能由该文法推导!"<<endl;
				exit(1);
			}
			else stk.spush(k);        //由go_to表查得的状态进栈
		}
	}
}