release.cpp

译原理大作业。C语言编译器的实现。附大作业的doc文档说明部分。 [编译原理豪华版程序.rar] - 编译原理豪华版程序用VC++编写 [附录I Little C解释程序源代码.rar] -

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

#define MAX  100
#define AMAX 50

struct VnVt
{
	char vn;
	char vt;
	int flag;
};

struct Lode
{
	char n;
	char t;
};

struct charstack
{
    Lode *base;
    int top;
};

char vn[AMAX],vt[AMAX];
VnVt vnvt[AMAX];
char str[MAX][MAX],first[MAX][MAX],last[MAX][MAX];
int table[AMAX][AMAX];
int count,nc,tc,fc,lc,FLAG;


void Initstack(charstack &s)
{
	s.base=new Lode[AMAX];
    s.top=-1;
}
void push(charstack &s,Lode w)
{
	s.top++;
	s.base[s.top].n=w.n;
	s.base[s.top].t=w.t;
}
void pop(charstack &s,Lode &w)
{
	w.n=s.base[s.top].n;
	w.t=s.base[s.top].t;
	s.top--;
}
int IsEmpty(charstack s)
{
	if(s.top==-1)
		return 1;
	else return 0;
}
int Isvn(char ch)
{
	int flag=0;
	for(int i=0;i<nc;i++)
		if(ch==vn[i]) flag=1;
		return flag;
}

int judgeog(int n)
{
	int j=3,flag=1;
	for(int i=0;i<=n;i++)
		while(str[i][j]!='\0')
		{
			char a=str[i][j];
			char b=str[i][j+1];
			if(Isvn(a)&&Isvn(b))
			{flag=0;break;}
			else j++;
		}
		return flag;
}


int judgeopg(int n)
{
	int flag=1;
	for(int i=0;i<=n;i++)
		if(str[i][3]=='@'||judgeog(n)==0||FLAG==1)
		{
			flag=0;break;
		}
		return flag;

}

int vtequal(char r[],int k,char a)
{
	int flag=0;
	for(int i=0;i<k;i++)
		if(r[i]==a)
		{
			flag=1;
			break;
		}
		return flag; 
}

void create(int n)
{
	nc=0;
	int i=1;
	vn[0]=str[0][0];
	while(i<=n)
	{
		if(vn[nc]!=str[i][0])
		{
			nc++;
			vn[nc]=str[i][0];
			i++;
		}
		else i++;
	}
	tc=0;
    char c;
	for(i=0;i<=n;i++)
	{ 
		int j=3;
		while(str[i][j]!='\0')
		{
			c=str[i][j];
			if(Isvn(c)==0)
			{
				if(!vtequal(vt,tc,c))
					vt[tc]=c;
				tc++;
			}
			j++;
		}
	}
	count=0;
	for(i=0;i<nc;i++)
		for(int j=0;j<tc-1;j++)
		{
			vnvt[count].vn=vn[i];
			vnvt[count].vt=vt[j];
			vnvt[count].flag=0;
			count++;
		}
}

void setflag(Lode w)
{
	for(int i=0;i<count;i++)
		if(vnvt[i].vn==w.n&&vnvt[i].vt==w.t)
		{
			vnvt[i].flag=1;break;
		}
}

void FirstVT(int n)
{
	charstack stack;
	Lode l;
	int i=0;
	Initstack(stack);
	while(i<=n)
	{
		int k=3;
		l.n=str[i][0];
		char a=str[i][k];
		char b=str[i][k+1];
		if(!Isvn(a))//1
		{
			l.t=a;
			push(stack,l);
			setflag(l);
			i++;
		}
		else if(Isvn(a)&&b!='\0'&&!Isvn(b))//2
		{
			l.t=b;
			push(stack,l);
			setflag(l);
			i++;
		}
		else i++;
	}
	Lode ll;
	while(!IsEmpty(stack))//3
	{
		pop(stack,ll);
		for(i=0;i<=n;i++)
		{
			l.n=str[i][0];
			if(str[i][3]==ll.n&&str[i][4]=='\0')//
			{
				l.t=ll.t;
				push(stack,l);
				setflag(l);
				break;
			}
		}
	}
	fc=0;int k=1;i=1;
	while(i<count)
	{
		if(vnvt[i-1].flag==1)
		{
			first[fc][0]=vnvt[i-1].vn;
			first[fc][k]=vnvt[i-1].vt;
		}
		while(vnvt[i].flag==0&&i<count)
			i++;
		if(vnvt[i].flag==1)
		{
			if(vnvt[i].vn==first[fc][0])
				k++;
			else 
			{
				first[fc][k+1]='\0';
				fc++;
				k=1;
			}
			i++;
		}
	}   
}

void LastVT(int n)
{
	charstack stack;
	Lode l;
	for(int i=0;i<count;i++)
		vnvt[i].flag=0;
	i=0;
	Initstack(stack);
	while(i<=n)
	{
		int k=strlen(str[i]);
		l.n=str[i][0];
		char a=str[i][k-1];
		char b=str[i][k-2];
		if(!Isvn(a))
		{
			l.t=a;
			push(stack,l);
			setflag(l);
			i++;
		}
		else if(Isvn(a)&&!Isvn(b))
		{
			l.t=b;
			push(stack,l);
			setflag(l);
			i++;
		}
		else i++;
	}
	Lode ll;
	while(!IsEmpty(stack))
	{
		pop(stack,ll);
		for(i=0;i<=n;i++)
		{
			//int k=strlen(str[i]);
			l.n=str[i][0];
			if(str[i][3]==ll.n&&str[i][4]=='\0')
			{
				l.t=ll.t;
				push(stack,l);
				setflag(l);
			}
		}
	}
	int k=1;i=1;
	lc=0;
	while(i<count)
	{
		if(vnvt[i-1].flag==1)
		{
			last[lc][0]=vnvt[i-1].vn;
			last[lc][k]=vnvt[i-1].vt;
		}
		while(vnvt[i].flag==0&&i<count)
			i++;
		if(vnvt[i].flag==1)
		{
			if(vnvt[i].vn==first[lc][0])
				k++;
			else 
			{
				last[lc][k+1]='\0';
				lc++;
				k=1;
			}
			i++;
		}
	}   
}

void createtable(int n)
{
	int i,j;
    for(j=1;j<=tc;j++)
        table[0][j]=vt[j-1];
	for( i=1;i<=tc;i++)
		table[i][0]=vt[i-1];
	for(i=1;i<=tc;i++)
		for(j=1;j<=tc;j++)
			table[i][j]=0;
		int p=0,q=3;
		while(p<=n)
		{
			if(str[p][q+1]=='\0')
			{
				p++;
				q=3;
			}
			else
			{
				while(str[p][q+1]!='\0')
				{
					char aa=str[p][q];
					char bb=str[p][q+1];
					if(!Isvn(aa)&&!Isvn(bb))//equal=1
					{  
						for(i=1;i<=tc;i++)
						{ 
                            if(table[i][0]==aa)
								break; 
                        }
						for(j=1;j<=tc;j++)
						{
                            if(table[0][j]==bb)
								break;  
                        }
						if(table[i][j]==0)
							table[i][j]=1;
						else 
						{
							FLAG=1;
							p=n+1;
						}
						q++;
					}
					if(!Isvn(aa)&&Isvn(bb)&&str[p][q+2]!='\0'&&!Isvn(str[p][q+2]))//equal=1
					{  
						for(i=1;i<=tc;i++)
						{ 
                            if(table[i][0]==aa)
								break;
                        }
						for(int j=1;j<=tc;j++)
						{ 
                            if(table[0][j]==str[p][q+2])
								break;
                        }
						if(table[i][j]==0)
							table[i][j]=1;
						else 
						{
							FLAG=1;
							p=n+1;
						}
					}
					if(!Isvn(aa)&&Isvn(bb))//<
					{  
						for(i=1;i<=tc;i++)
						{ 
							if(aa==table[i][0])
								break;
						}
						for(j=0;j<=fc;j++)
						{ 
							if(bb==first[j][0])
								break;
						}
						for(int mm=1;first[j][mm]!='\0';mm++)
						{ 
							for(int pp=1;pp<=tc;pp++)
							{
								if(table[0][pp]==first[j][mm])
									break;
							}
							if(table[i][pp]==0)
								table[i][pp]=2;
							else 
							{
								FLAG=1;
								p=n+1;
							}
						}
						q++;
					}
					if(Isvn(aa)&&!Isvn(bb))//>
					{ 
						for(i=1;i<=tc;i++)
						{ 
							if(table[0][i]==bb)
								break;
						}
						for(j=0;j<=lc;j++)
						{
							if(aa==last[j][0])
								break;
						}
						for(int mm=1;last[j][mm]!='\0';mm++)
						{  
							for(int pp=1;pp<=tc;pp++)
							{
								if(table[pp][0]==last[j][mm])
									break;
							}
							if(table[pp][i]==0)
								table[pp][i]=3;
                            else 
							{
								FLAG=1;
								p=n+1;
							}
						}
						q++;
					}
				}
			}
		}
}

int equal(char s,char a)
{
	int i=1,j=1;
	while(table[i][0]!=s)
		i++;
	while(table[0][j]!=a)
		j++;
	if(table[i][j]==3) return 3;
	else if(table[i][j]==2) 
		return 2;
	else if(table[i][j]==1)
		return 1;
	else return 0;
}
void print(int step,char s[],int k,char string[],int begin,int end)
{
	cout<<step<<"        ";
	for(int i=0;i<=k;i++)
		cout<<s[i];
	cout<<"         ";
	for(i=begin;i<=end;i++)
		cout<<string[i];
	cout<<"        ";
}

void process(char string[],int end)
{ 
	vn[nc]='N';
	nc++;
	cout<<"步骤"<<"    "<<"符号栈"<<"    "<<"输入串"<<"       "<<"动作"<<endl;
	int step=0,k=0,begin=0;
	char s[MAX],a,b,q,i,j;
	s[k]='#';
	print(step,s,k,string,begin,end);
	cout<<"预备"<<endl;
	k++;
	step++;
    s[k]=string[begin];
	begin++;
	print(step,s,k,string,begin,end);
	cout<<"移进"<<endl;
	while(begin<=end)
	{
		a=string[begin];
		if(!Isvn(s[k])) j=k;
		else j=k-1;
		b=equal(s[j],a);
		if(b==3)
		{
			do
			{
				q=s[j];
				if(Isvn(s[j-1]))
					j=j-2;
				else
					j--;
			}while(equal(s[j],q)!=2);
			
			for(i=j+1;i<=k;i++)
				s[i]='\0';
			k=j+1;
			s[k]='N';
			step++;
			print(step,s,k,string,begin,end);
			cout<<"归约"<<endl;
		}
		else if(b==2 ||b==1)
		{
				k++;
				s[k]=a;
				step++;
				begin++;
				print(step,s,k,string,begin,end);
				cout<<"移进"<<endl;
		}
		else
		{
			cout<<"失败"<<endl;break;
		}
	}
		if(s[j]=='#'&&s[j+1]=='N'&&s[j+2]=='#')
		{
			cout<<"归约成功"<<endl;
		}
		else
			cout<<"规约失败"<<endl;
}

void main()
{
	int n,i,j;
	cout<<"请输入你要定义的文法G的产生式的个数n:";
    cin>>n;
	for(i=0;i<n;i++)
	{
		gets(str[i]);
		j=strlen(str[i]);
		str[i][j]='\0';
	}
	str[i][0]='Q';
	str[i][1]='-';
	str[i][2]='>';
	str[i][3]='#';
	str[i][4]=str[0][0];
	str[i][5]='#';
    str[i][6]='\0';

	cout<<"你定义的产生式如下:"<<endl;
    for(i=0;i<=n;i++)
		cout<<str[i]<<endl;

		create(n);
		FirstVT(n);
		LastVT(n);
		createtable(n);

	if(judgeopg(n))
	{
		cout<<"文法G是算符优先文法!"<<endl;

		for(i=0;i<=fc;i++)
		{
			cout<<"FirstVT("<<first[i][0]<<")={";
			for(int l=1;first[i][l+1]!='\0';l++)
				cout<<first[i][l]<<",";
			cout<<first[i][l]<<"}"<<endl;
		}
		cout<<"FirstVT(Q)={#}"<<endl; 
		for(i=0;i<=lc;i++)
		{
			cout<<"LastVT("<<first[i][0]<<")={";
			for(int l=1;last[i][l+1]!='\0';l++)
				cout<<last[i][l]<<",";
			cout<<last[i][l]<<"}"<<endl;
		}
		cout<<"LastVT(Q)={#}"<<endl;
		cout<<"优先表如下:"<<endl;
		for(i=0;i<tc;i++)
		{
			cout<<"   ";
			cout<<vt[i];
		}
		cout<<endl;
		for(i=1;i<tc;i++)
		{
			cout<<vt[i-1]<<" ";
			for(j=1;j<tc;j++)
			{
				if(table[i][j]==0)
					cout<<" ";
				else if(table[i][j]==1)
					cout<<"=";
				else if(table[i][j]==2)
					cout<<"<";
				else if(table[i][j]==3)
					cout<<">";
				cout<<"   ";
			}
			cout<<endl;
		}

		char string[MAX];
		cout<<"请输入要规约的字符串:"<<endl;
		gets(string);
		int end=strlen(string);
		string[end]='#';
		cout<<"下面是规约的过程:"<<endl;
		process(string,end);
	}
	else
		cout<<"文法G不是算符优先文法!"<<endl;
}