编译原理代码.txt

编译原理中算符优先表的生成

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

static char terminal[100],noterminal[100];

struct node//定义每个表达式文法
{
	char front;
	char back[20];
	node * next;
};

static node * head;//存储第一个表达式

int exist(char * ch,char a,int n)//判断前面数组里面是否存在下一个要进入的字符
{
	int flag=0;
	for(int i=0;i<n;i++)
		if(*(ch+i)==a)
			flag=1;
		return flag;
}

void check(char * ch)//将终结符号和非终结符号区分
{
	int m=strlen(noterminal),n=strlen(terminal);
	int mn=strlen(ch);
	for(int i=0;i<mn;i++)
	{
		if(ch[i]>64&&ch[i]<91&&!exist(noterminal,ch[i],m)&&ch[i]!='-'&&ch[i]!='>')
			noterminal[m++]=ch[i];
		if((ch[i]<=64||ch[i]>=91)&&!exist(terminal,ch[i],n)&&ch[i]!='-'&&ch[i]!='>')
			terminal[n++]=ch[i];
	}
}

void creatlist()//创建所有的表达式文法。表达式的第一个为$->#E#
{
	cout<<"输入表达式的文法：(输入“＃”结束)"<<endl;
	char ch[20];
	node *s,*r;
	head=(node *)malloc(sizeof(node));
	head->front='$';
	strcpy(head->back,"#E#");
	r=head;
	gets(ch);
	check(ch);
	while(strcmp(ch,"#"))
	{
		s=(node *)malloc(sizeof(node));
		s->front=ch[0];
		strcpy(s->back,strchr(ch,'>')+1);
		r->next=s;
		r=s;
		gets(ch);
		check(ch);
	}
	r->next=NULL;
}


void printlist()//输出表达式文法
{
	cout<<"输出表达式的文法:"<<endl;
	node *p;
	p=head;
	while(p)
	{
		cout<<p->front<<"->"<<p->back<<"   "<<strlen(p->back)<<endl;
		p=p->next;
	}
}

#define STACK_INIT_SIZE 10 //存储空间出事分配量
#define STACKINCREMENT 2  //存储空间分配增量

struct sqstack//建立一个顺序栈
{
	char *base;
	char *top;
	int stacksize;
}s;//顺序栈

int initstack(sqstack &s)//创建栈
{
	if(!(s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char))))
	exit(1);
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return 1;
}

int destorystack(sqstack &s)//销毁栈
{
	free(s.base);
	s.base=NULL;
	s.top=NULL;
	s.stacksize=0;
	return 1;
}

int stackempty(sqstack &s)//判断栈是否为空
{
	if(s.top==s.base)   return 1;
	else return 0;
}

int clearstack(sqstack &s)//清空栈
{
	s.top=s.base;
	return 1;
}

int stacklength(sqstack &s)//返回栈的长度
{
	return s.top-s.base;
}

int gettop(sqstack &s,char &e)//获取栈的头节点
{
	if(s.top>s.base)
	{
		e=*(s.top-1);
		return 1;
	}
	else
		return 0;
}

void push(sqstack &s,char e)//将e入栈
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));
		if(!s.base)
			exit(1);
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*(s.top)++=e;
}

void pop(sqstack &s, char &e)//将e出栈
{
	if(s.top==s.base)   
		cout<<"栈空！"<<endl;
	e=*--s.top;
}


void stacktraverse(sqstack s)//输出栈
{
	while(s.top>s.base)
		cout<<*(s.base++);
	cout<<endl;
}

void insertstack()//将形如A->a...或者A->Ba.......入栈
{
	node *p;
	p=head;
	while(p)
	{
		if((p->back[0]<65||p->back[0]>90))//35为＃
		{
			push(s,p->front);
			push(s,p->back[0]);
		}
		if(strlen(p->back)>1)
			if((p->back[0]>=65&&p->back[0]<=90)&&(p->back[1]<65||p->back[1]>90))
			{
				push(s,p->front);
				push(s,p->back[1]);
			}
			p=p->next;
	}
}

void insertstack1()//将形如A->...a或者A->......aC入栈????????????????????
{
	node *p;
	p=head;
	while(p)
	{
		if(p->back[(int)strlen(p->back)-1]<65||p->back[(int)strlen(p->back)-1]>90)
		{
			push(s,p->front);
			push(s,p->back[(int)strlen(p->back)-1]);
		}
		if(strlen(p->back)>1)
			if((p->back[(int)strlen(p->back)-1]>=65&&p->back[(int)strlen(p->back)-1]<=90)&&(p->back[(int)strlen(p->back)-2]>65||p->back[(int)strlen(p->back)-2]<90))
			{
				push(s,p->front);
				push(s,p->back[(int)strlen(p->back)-2]);
			}
			p=p->next;
	}
}

node * search(char s)
{
	node *p,*r;
	p=head;
	r=head;
	while(p)
	{
		if(p->back[0]==s&&p->front!=p->back[0])//注意这里其实字符要为"E" 例如E->E+T这里就要无限循环了 是否要设置标志位呢？
		{
			break;
		}
		p=p->next;
	}
	if(p==NULL)
	{
		return NULL;
	}
	else
		return p;
}

node * search1(char s)
{
	node *p,*r;
	p=head;
	r=head;
	while(p)
	{
		if(p->back[(int)strlen(p->back)-1]==s&&p->front!=p->back[(int)strlen(p->back)-1])//注意这里其实字符要为"E" 例如E->E+T这里就要无限循环了 是否要设置标志位呢？
		{
			break;
		}
		p=p->next;
	}
	if(p==NULL)
	{
		return NULL;
	}
	else
		return p;
}

int Ftable[20][20]={0};
int Ltable[20][20]={0};
char FIRSTVT[20][20];
char LASTVT[20][20];
char result[20][20]={'0'};


void table(int noterminalnum,int terminalnum)//输出构造FISTVT集合的表（以 01 形式）
{
	
	node *w;
	char m,n;//m--terminal, n--noterminal
	while(s.top>s.base)
	{
		pop(s,m);
		pop(s,n);
		for(int i=0;i<noterminalnum;i++)
		{
			if(noterminal[i]==n)
				break;
		}
		for(int j=0;j<terminalnum;j++)
		{
			if(terminal[j]==m)
				break;
		}
		Ftable[i][j]=1;

		w=search(n);//????????????????
		if(w)
		{
			push(s,w->front);
			push(s,m);
		}
		stacktraverse(s);//输出
		cout<<endl;
	}
	for(int i=0;i<noterminalnum;i++)
	{
		for(int j=0;j<terminalnum;j++)
			cout<<Ftable[i][j]<<"  ";
		cout<<endl;
	}
}

void table1(int noterminalnum,int terminalnum)//输出构造LASTVT集合的表（以 01 形式）
{
	
	node *w;
	char m,n;//m--terminal, n--noterminal
	while(s.top>s.base)
	{
		pop(s,m);
		pop(s,n);
		for(int i=0;i<noterminalnum;i++)
		{
			if(noterminal[i]==n)
				break;
		}
		for(int j=0;j<terminalnum;j++)
		{
			if(terminal[j]==m)
				break;
		}
		Ltable[i][j]=1;

		w=search1(n);//????????????????
		if(w)
		{
			push(s,w->front);
			push(s,m);
		}
		stacktraverse(s);//输出
		cout<<endl;
	}
	for(int i=0;i<noterminalnum;i++)
	{
		for(int j=0;j<terminalnum;j++)
			cout<<Ltable[i][j]<<"  ";
		cout<<endl;
	}
}

void FIRSTVTTABLE()//输出每个非终结字符的FIRSTVT集合
{
	int noterminalnum=strlen(noterminal);
	int terminalnum=strlen(terminal);
	int m=0,n=0;
	for(int i=0;i<noterminalnum;i++)
	{
		n=0;
		for(int j=0;j<terminalnum;j++)
		{
			if(Ftable[i][j]==1)
				FIRSTVT[m][n++]=terminal[j];
		}
		m++;
	}
	for(i=0;i<noterminalnum;i++)
	{
		cout<<noterminal[i]<<"的FIRSTVT集合为：";
		for(int j=0;j<terminalnum;j++)
		{	
			cout<<FIRSTVT[i][j]<<"  ";
		}
		cout<<endl;
	}
}

void LASTVTTABLE()//输出每个非终结字符的LASTVT集合
{
	int noterminalnum=strlen(noterminal);
	int terminalnum=strlen(terminal);
	int m=0,n=0;
	for(int i=0;i<noterminalnum;i++)
	{
		n=0;
		for(int j=0;j<terminalnum;j++)
		{
			if(Ltable[i][j]==1)
				LASTVT[m][n++]=terminal[j];
		}
		m++;
	}
	for(i=0;i<noterminalnum;i++)
	{
		cout<<noterminal[i]<<"的LASTVT集合为：";
		for(int j=0;j<terminalnum;j++)
		{	
			cout<<LASTVT[i][j]<<"  ";
		}
		cout<<endl;
	}
}

char *  FIRSTD(char A)//找出大写字母A的FIRSTVT集合，返回头指针
{
	for(int i=0;i<(int)strlen(noterminal);i++)
	{
		if(A==noterminal[i])
			break;
	}
	return FIRSTVT[i];
}

char * LASTD(char A)
{
	for(int i=0;i<(int)strlen(noterminal);i++)
	{
		if(A==noterminal[i])
			break;
	}
	return LASTVT[i];
}

void createtable()
{
	cout<<"   ";
	for(int j=0;j<(int)strlen(terminal);j++)
		cout<<terminal[j]<<"  ";
	cout<<endl;
	for(int i=0;i<(int)strlen(terminal);i++)
	{
		cout<<terminal[i]<<"  ";
		for(int j=0;j<(int)strlen(terminal);j++)
		{
			result[i][j]='0';
			cout<<result[i][j]<<"  ";
		}
		cout<<endl;
	}
}

void resulttable()
{
	node * p;
	p=head;
	char * ch;
	cout<<"*******************************************************"<<endl;
	for(int i=0;i<(int)strlen(terminal);i++)
	{
		while(p)
		{
			for(int m=0;m<(int)strlen(p->back);m++)
			{
				if(terminal[i]==p->back[m]&&m!=((int)strlen(p->back)-1)&&(p->back[m+1]>=65&&p->back[m+1]<=90))
				{
					ch=FIRSTD(p->back[m+1]);
					for(int n=0;n<(int)strlen(ch);n++)
						for(int q=0;q<(int)strlen(terminal);q++)
							if(ch[n]==terminal[q])
								result[i][q]='<';
				}
			}
			p=p->next;
		}
		p=head;
	}
	p=head;
	for(i=0;i<(int)strlen(terminal);i++)
	{
		while(p)
		{
			for(int m=0;m<(int)strlen(p->back);m++)
			{
				if(terminal[i]==p->back[m]&&m&&(p->back[m-1]>=65&&p->back[m-1]<=90))
				{
					ch=LASTD(p->back[m-1]);
					for(int n=0;n<(int)strlen(ch);n++)
						for(int q=0;q<(int)strlen(terminal);q++)
							if(ch[n]==terminal[q])
								result[q][i]='>';//为什么这里转置了呢？？？？？？？？？？？？？想不通了
				}
			}
			p=p->next;
		}
		p=head;
	}
	cout<<"   ";
	for(int j=0;j<(int)strlen(terminal);j++)
		cout<<terminal[j]<<"  ";
	cout<<endl;
	for(i=0;i<(int)strlen(terminal);i++)
	{
		cout<<terminal[i]<<"  ";
		for(int j=0;j<(int)strlen(terminal);j++)
		{
			cout<<result[i][j]<<"  ";
		}
		cout<<endl;
	}

}

void equtable()
{
	node * p;
	p=head;
	while(p)
	{
		for(int i=0;i<(int)strlen(p->back);i++)
		{
			if((p->back[i]<65||p->back[i]>90))
			{
				if((p->back[i+1]<65||p->back[i+1]>90))
				{
					for(int q=0;q<(int)strlen(terminal);q++)
					{
						if(p->back[i]==terminal[q])  break;
					}
					for(int w=0;w<(int)strlen(terminal);w++)
					{
						if(p->back[i+1]==terminal[w]) break;
					}
							result[q][w]='=';
				}
				else
					if(p->back[i+2]<65||p->back[i+2]>90)
					{
						for(int q=0;q<(int)strlen(terminal);q++)
						{
							if(p->back[i]==terminal[q])  break;
						}
						for(int w=0;w<(int)strlen(terminal);w++)
						{
							if(p->back[i+2]==terminal[w]) break;
						}
						result[q][w]='=';
					}
			}
		}
		p=p->next;
	}
}

void main()
{
	creatlist();
	printlist();
	cout<<"noterminal:  "<<noterminal<<"  "<<strlen(noterminal)<<endl;
	cout<<"terminal:  "<<terminal<<"  "<<strlen(terminal)<<endl;
	//下面是FIRSTVT()
	insertstack();//形如A->a...或者A->Ba.......入栈
	cout<<"*******************************************************"<<endl;
	stacktraverse(s);//输出进栈出栈情况
	cout<<"*******************************************************"<<endl;
	table(strlen(noterminal),strlen(terminal));//输出构造FISTVT集合的表（以 01 形式）
	cout<<"*******************************************************"<<endl;
	FIRSTVTTABLE();//输出每个非终结字符的FIRSTVT集合


	cout<<"*******************************************************"<<endl;

	//下面是LASTVT()
	clearstack(s);
	insertstack1();
	cout<<"*******************************************************"<<endl;
	stacktraverse(s);//输出进栈出栈情况
	cout<<"*******************************************************"<<endl;
	table1(strlen(noterminal),strlen(terminal));//输出构造LASTVT集合的表（以 01 形式）
	cout<<"*******************************************************"<<endl;
	LASTVTTABLE();//输出每个非终结字符的LASTVT集合


	cout<<"*******************************************************"<<endl;
	cout<<"表达式文法算符优先关系表："<<endl;
	createtable();
	equtable();
	resulttable();
	cout<<"*******************************************************"<<endl;

						
	cin.get();
}