语法分析

词法 语法分析程序 是编译程序设计 写的较好

#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
#define length 20
typedef struct BitNode{             //定义二叉链表结点
	char date;                     //数据域；
	int t;
	struct BitNode *lchild,*rchild;//左右孩子指针；
}BitNode,*BitTree;
void gramanaly(char * );//语法分析程序
void transfer( );       //翻译程序
void push(char *);      //分析栈进栈
char pop();             //分析栈出栈
void print(char *,int);  //从打印char数组，前int位用空格
int check(char ,char);   //查预测分析表
void PostOrderTraverse(BitTree);   //以四元组形式输出中间代码
void optimizebtree(BitTree);//优化带有非终结符的二叉树，除去非终结符
void movel(BitTree);        //左子树上移到根结点
void adjust(BitTree BT);
char chstack[length];       //分析栈
BitTree btstack[length];     //与分析栈对应的二叉树栈
char c[10][4]={"AE","AE+","AE-","","BF","BF*","BF/","",")S(","i"};
int p;
int t=1;
BitTree temp;
int select[5][8]={0};
string str[10]={"S->EA","A->+EA","A->-EA","A->$","E->FB","B->*FB","B->/FB","B->$","F->(S)","F->i"};
int main()
{
	char ch[length]={'\0'};  //申明输入字符串数组
	p=0;
    cout<<"请输入表达式：（用i表示操作数，以#号结束）"<<endl;
	cin.getline(ch,length,'\n');
	gramanaly(ch);           //语法分析
	transfer( );              //用语法分析中产生的二叉树翻译
	return 0;
}
void gramanaly(char *ch)
{
	select[0][0]=1;select[0][5]=1;select[1][1]=2;select[1][2]=3;select[1][6]=4;select[1][7]=4;select[2][0]=5;select[2][5]=5;
	select[3][1]=8;select[3][2]=8;select[3][3]=6;select[3][4]=7;select[3][6]=8;select[3][7]=8;select[4][0]=10;select[4][5]=9;
	chstack[p]='#';
	BitTree B=new BitNode();
	B->date='S';
	btstack[p++]=B;
	btstack[p]=B;
	chstack[p++]='S';
	int inp=0;//输入串指针；
	int sel=1;   //selec值；
	char chtop;//
	cout<<setw(2)<<"序号 "<<"分析栈"<<setw(length+6)<<"剩余输入串"<<setw(length)<<"所用产生式或匹配"<<endl;
	while(sel){
		if(t<10) cout<<" ";
		cout<<" "<<t++<<"   ";
		t++;
		print(chstack,0);
		print(ch,inp);
		cout.setf(ios::left);
		chtop=pop();
		sel=check(chtop,ch[inp]);
		if(sel>0&&sel<11){
			push(c[sel-1]);
			cout<<str[sel-1]<<endl;
		}
		else if(sel==200) 
		{   cout<<"接受！"<<endl;
		cout<<"语法分析成功！"<<endl;
		cout<<endl;
		break;
		}
		else if(sel==100) 
		{
		cout<<chtop<<"匹配"<<endl;
			inp++;
		}
		else
		{
			cout<<"语法分析错误！出错位置:"<<ch[inp]<<endl;
			break;
		}
	cout.unsetf(ios::left);
	}
}
void push(char ch[]){
	for(int i=0;(i<3)&(ch[i]!='\0');i++)
	{
		if(ch[i]=='('||ch[i]==')'){
			btstack[p]=NULL;
		}
		else if(ch[i]=='S'){
			temp->date='S';
			temp->t=-1;
			btstack[p]=temp;
		}
		else if(i==2) 
		{temp->date=ch[i];
		btstack[p]=temp;
		}
		else{
			BitTree B=new BitNode();
			B->date=ch[i];
			B->lchild=NULL;
			B->rchild=NULL;
			btstack[p]=B;
			if (i==0) temp->lchild=B;
			else temp->rchild=B;
		}
		chstack[p++]=ch[i];
	}
}
char pop(){
	char a;
	p--;
	temp=btstack[p];
	if(chstack[p]!='#')
		btstack[p]=NULL;
	a=chstack[p];
	chstack[p]='\0';
	return a;
}
void print(char ch[],int i){
	for(int j=0;j<i;j++)
		cout<<" ";
	for(;i<length;i++){
	if(ch[i]!='\0') cout<<ch[i];
		else cout<<" ";
	}
}
int check(char a,char b){
	int x, y;
	if(a==b&&a=='#')  return 200;
	else if(a==b) return 100;
	else{
		switch(a){
		case 'S': x=0;break;
		case 'A':x=1;break;
		case 'E':x=2;break;
		case 'B':x=3;break;
		case 'F':x=4;break;
		default : return 0;
		}
		switch(b){
		case 'i': y=0;break;
		case '+':y=1;break;
		case '-':y=2;break;
		case '*':y=3;break;
		case '/':y=4;break;
		case '(':y=5;break;
		case ')':y=6;break;
		case '#':y=7;break;
		default : return 0;
		}
		return select[x][y];
	}
}
void PostOrderTraverse(BitTree BT){        //以四元组形式输出中间代码
	if(BT!=NULL){
		if(BT->lchild!=NULL||BT->rchild!=NULL)  //若二叉树只有一个结点，空操作
		{                               
			PostOrderTraverse(BT->rchild);       //递归处理右子树
			PostOrderTraverse(BT->lchild);       //递归处理左子树
			cout<<"   ("<<BT->date<<",";
			if(BT->rchild->date!='t')
				cout<<BT->rchild->date<<" ";
			else cout<<"t"<<BT->rchild->t;
			if(BT->lchild->date!='t')
				cout<<","<<BT->lchild->date<<" ,t"<<t<<")"<<endl;
			else  cout<<",t"<<BT->lchild->t<<",t"<<t<<")"<<endl;
			BT->date='t';BT->t=t++;
			delete BT->lchild;
			delete BT->rchild;
			BT->lchild=NULL;
			BT->rchild=NULL;  
		}
	}
}
void optimizebtree(BitTree BT){
	if(BT!=NULL){
		optimizebtree(BT->lchild);
		optimizebtree(BT->rchild);
		BitTree b;
		if(BT->lchild!=NULL){
			if(BT->lchild->date>='A'&&BT->lchild->date<='Z'&&BT->lchild->lchild==NULL&&BT->lchild->rchild==NULL)
			{	delete BT->lchild;BT->lchild=NULL;}
		}
		if(BT->rchild!=NULL){
			if(BT->rchild->date>='A'&&BT->rchild->date<='Z'&&BT->rchild->lchild==NULL&&BT->rchild->rchild==NULL)
			{delete BT->rchild;BT->rchild=NULL;}
		}
		if(BT->date>='A'&&BT->date<='Z'){
			if(BT->rchild==NULL&&BT->lchild!=NULL) {
				b=BT->lchild;
				BT->date=BT->lchild->date;
				BT->lchild=NULL;
				delete b;
			}
			else if(BT->lchild==NULL&&BT->rchild!=NULL){
				BT->date=BT->rchild->date;
				b=BT->rchild;
				BT->lchild=BT->rchild->lchild;
				BT->rchild=BT->rchild->rchild;
				delete b;
			}
			else if(BT->rchild!=NULL&&BT->lchild!=NULL){
				movel(BT);
			}
		}
	}
}
void transfer( ){
	cout<<"输出语义四元组："<<endl;
    t=1;
	optimizebtree(btstack[0]);
	adjust(btstack[0]);
	PostOrderTraverse(btstack[0]);
}
void movel(BitTree BT)
{
	BitTree b;
	if(BT->lchild->lchild==NULL){
		BT->date=BT->lchild->date;
		b=BT->lchild;
		BT->lchild=BT->lchild->rchild;
		delete b;}
	else {
		BT->date=BT->lchild->date;
		movel(BT->lchild);
	}
}
void adjust(BitTree BT){
	if(BT!=NULL){
		if((BT->lchild!=NULL)&&(((BT->date=='+'||BT->date=='-')&&(BT->lchild->date=='+'||BT->lchild->date=='-'))||((BT->date=='*'||BT->date=='/')&&(BT->lchild->date=='*'||BT->lchild->date=='/')))){
			char c;
			BitTree b;b=BT->lchild;
			c=b->date;b->date=BT->date;BT->date=c;
			BT->lchild=b->lchild;b->lchild=b->rchild;b->rchild=BT->rchild;BT->rchild=b;
			adjust(BT);
		}
		adjust(BT->lchild);
		adjust(BT->rchild);
	}
}