a2.cpp

LL(1)分析实验

//建立如下文法LL(1)分析表,并对输入串进行语法分析
//消除递归前的文法                   消除递归后的等价文法
//    E→E+T                               E→TP
//    E→T                                 P→+TP|ε
//    T→T*F                               T→FQ
//    T→F                                 Q→*FQ|ε
//    F→(E)|i                             F→(E)|i

#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <string.h>

class stack{                  //分析过程中使用的堆栈
public:
	stack();
	void push(char ch);
	void push(char * ch);
	char pop();
	void prt();
private:
	char st[80];
	int top;
};

stack::stack()              //初始化堆栈
{
	st[0]='#';
	top=1;    
}

void stack::prt()           //显示堆栈的内容
{
	int i=0;
	cout<<setw(10)<<st;
}

void stack::push(char * ch)   //把字符串ch逆序压入堆栈
{
	int len,i;
	len=strlen(ch);
	for (i=len-1;i>=0;i--)
		push(*(ch+i));
}

void stack::push(char ch)     //把字符ch压入堆栈
{
	st[top++]=ch;
	st[top]='\0';
}

char stack::pop()           //弹出栈顶元素
{
	char temp;
	top--;
	temp=st[top];
	st[top]='\0';
	return(temp);
}

class table{                 //分析表类
public:
	table();
	char * fd(char a,char b);
	void disp();
	char * getnull() {return expr[2];}
private:
	char * tab[5][6];        //文法的LL(1)分析表,只存放产生式的右部
	char v[6];
	char n[5];
	char * expr[7];
};

table::table()
{
	int i,j;
	expr[0]="TP";
	expr[1]="+TP";
	expr[2]="ε";
	expr[3]="FQ";
	expr[4]="*FQ";
	expr[5]="(E)";
	expr[6]="i";            //所有产生式的右部
	v[0]='i';v[1]='+';v[2]='*';v[3]='(';v[4]=')';v[5]='#';     //所有终结符
	n[0]='E';n[1]='P';n[2]='T';n[3]='Q';n[4]='F';              //所有非终结符
	for (i=0;i<5;i++)
		for (j=0;j<6;j++)
			tab[i][j]=NULL;
	tab[0][0]=expr[0];
	tab[0][3]=expr[0];
	tab[1][1]=expr[1];
	tab[1][4]=expr[2];
	tab[1][5]=expr[2];
	tab[2][0]=expr[3];
	tab[2][3]=expr[3];
	tab[3][1]=expr[2];
	tab[3][2]=expr[4];
	tab[3][4]=expr[2];
	tab[3][5]=expr[2];
	tab[4][0]=expr[6];
	tab[4][3]=expr[5];         //建立LL(1)分析表
}

void table::disp()             //输出该文法所有的产生式
{
	cout<<"文法所有的产生式:"<<endl;
	cout<<"E→"<<expr[0]<<endl;
	cout<<"P→"<<expr[1]<<endl;
	cout<<"P→"<<expr[2]<<endl;
	cout<<"T→"<<expr[3]<<endl;
	cout<<"Q→"<<expr[2]<<endl;
	cout<<"Q→"<<expr[4]<<endl;
	cout<<"F→"<<expr[5]<<endl;
	cout<<"F→"<<expr[6]<<endl;
}

char * table::fd(char a,char b) //根据栈顶元素a和输入串中的当前字符b,查LL(1)表,返回产生式的右部
{
	int i,j;
	for (i=0;i<5;i++)
		if (n[i]==a) break;
	for (j=0;j<6;j++)
		if (v[j]==b) break;
	if (i>4 || j>5) 
	{
		cout<<"\n\n"<<"输入串不能由该文法推导!"<<endl;
		exit(1);
	}
	return (tab[i][j]);
}

void main()         //主控程序
{
	char sktop,instr[80];
	char * rgt;
	int len,p=0;
	stack sk;
	table t;
	t.disp();
	cout<<"请输入待分析的字符串:"<<endl;
	cin>>instr;
	len=strlen(instr);
	instr[len++]='#';      //在输入串末尾加上"#"
	instr[len]='\0';
	sk.push('E');
	cout<<setw(10)<<"符号栈";
	cout<<setw(15)<<"输入串";
	cout<<setw(20)<<"所用产生式"<<endl;
	while (true)
	{
		sk.prt();
		cout<<setw(15)<<(instr+p);
		sktop=sk.pop();
		if (sktop=='#' && instr[p]=='#')  //栈顶元素和输入串的当前字符同时为"#",则分析成功
		{
			cout<<"\n\n"<<"分析成功，输入串可以由该文法推导!"<<endl;
			break;
		}
		if (sktop>'A' && sktop<'Z')   //栈顶元素是非终结符,则查LL(1)分析表
		{
			rgt=t.fd(sktop,instr[p]);
			if (rgt==NULL)            //如果分析表查得的结果为NULL,说明输入串不能由该文法推导
			{
				cout<<"\n\n"<<"输入串不能由该文法推导!";
				break;
			}
			cout<<setw(11)<<sktop<<"→"<<rgt<<endl;   //输出所用的产生式
			if (rgt!=t.getnull()) sk.push(rgt);
			continue;
		}
		if (sktop==instr[p])  //栈顶元素为终结符,且和输入串的当前字符相同
		{
			p++;
			cout<<endl;
		}
		else          //栈顶元素为终结符,但和输入串的当前字符不同
		{
			cout<<"\n\n"<<"输入串不能由该文法推导!";
			break;
		}
	}
}