zsyntax.cpp

很好玩的一个小游戏

///////////////////////////////////////////////////////////////
/*
	语法分析内核程序 0.1 (2003.10.22) [实现文件]
	作者:Dwing
*/
///////////////////////////////////////////////////////////////
#include "zSyntax.h"
///////////////////////////////////////////////////////////////
zSyntax::zSyntax()
{
	memset(this,0,sizeof(zSyntax));
}
///////////////////////////////////////////////////////////////
void zSyntax::reset()
{
	if(vn) delete vn;
	if(vt) delete vt;
	long i;
	for(i=0;i<MAX_P;i++)
		if(right[i]) delete right[i];
	for(i=0;i<MAX_VN;i++)
		if(first[i]) delete first[i];
	for(i=0;i<MAX_VN;i++)
		if(follow[i]) delete follow[i];
	for(i=0;i<MAX_P;i++)
		if(select[i]) delete select[i];
	memset(this,0,sizeof(zSyntax));
}
///////////////////////////////////////////////////////////////
int zSyntax::setvn(char *in)
{
	long i=strlen(in);
	if(i>MAX_VN) return -1;
	if(vn) delete vn;
	vn=new zAsmchar(i);
	if(!vn) return -100;
	while(*in)
		vn->add(*in++);
	return 0;
}
///////////////////////////////////////////////////////////////
int zSyntax::setvt(char *in)
{
	long i=strlen(in);
	if(i>MAX_VT) return -1;
	if(vt) delete vt;
	vt=new zAsmchar(i);
	if(!vt) return -100;
	while(*in)
		vt->add(*in++);
	return 0;
}
///////////////////////////////////////////////////////////////
int zSyntax::addp(char *p)
{
	if(pnum>=MAX_P) return -1;
	long i=strlen(p)-3;
	if(i<=0) return -2;
	if(i>MAX_RIGHT) return -3;
	left[pnum]=*p;
	right[pnum]=new zStrchar(i);
	if(!right[pnum]) return -100;
	right[pnum]->adds(p+3);
	pnum++;
	return 0;
}
///////////////////////////////////////////////////////////////
int zSyntax::settest(char *t)
{
	long i=strlen(t);
	if(i>MAX_TEST) return -1;
	strcpy(test,t);
	return 0;
}
///////////////////////////////////////////////////////////////
//测试Vn,Vt,P是否正确[返回值:0:正常;<0错误]
int zSyntax::check()
{
//测试Vn,Vt是否为空(返回-1/-2)
	if(!vn||!vn->getnum()) return -1;
	if(!vt||!vt->getnum()) return -2;
//测试Vn和Vt是否有交集(返回-3)
	long i,j;
	for(i=0;i<vn->getnum();i++)
		if(vt->find(vn->getdata()[i])>=0) return -3;
	for(i=0;i<vt->getnum();i++)
		if(vn->find(vt->getdata()[i])>=0) return -3;
//测试是否有初始符(返回-4)
	if(!start) return -4;
//测试初始符是否是非终结符(返回-5)
	if(vn->find(start)<0) return -5;
//测试是否有正规式(返回-6)
	if(!pnum) return -6;
//测试正规式中是否有以初始符为左部的正规式(返回-7)
	for(i=0;i<pnum;i++)
		if(vn->find(start)>=0) break;
	if(i==pnum) return -7;
//测试正规式左/右部是否有非法符号(返回-8/-9)
	char c;
	for(i=0;i<pnum;i++)
	{
		if(vn->find(left[i])<0) return -8;
		for(j=0;j<right[i]->getnum();j++)
		{
			c=right[i]->getdata()[j];
			if(c!='@'&&vn->find(c)<0&&vt->find(c)<0)
				return -9;
		}
	}
//测试是否有左递归(返回-10)
	char s[MAX_VN];
	memset(s,0,vn->getnum());
	for(i=0;i<pnum;i++)
	{
		j=vn->find(left[i]);
		s[j]=1;
		if(check1(s,right[i]->getdata()[0])) return -10;
		s[j]=0;
	}
//测试测试字串是否包含非法字符(返回-11)
	for(i=0;i<(signed)strlen(test)-1;i++)
		if(vt->find(test[i])<0) return -11;
//测试测试字串是否以'#'结尾(返回-12)
	if(test[i]!='#') return -12;
//正常(返回0)
	return 0;
}
///////////////////////////////////////////////////////////////
//递归函数(返回0无异常)
int zSyntax::check1(char *s,char c)
{
	if(c=='@'||vt->find(c)>=0) return 0;
	long i,j=vn->find(c);
	if(s[j]) return -1;
	s[j]=1;
	for(i=0;i<pnum;i++)
		if(left[i]==c)
			if(check1(s,right[i]->getdata()[0])) return -1;
	s[j]=0;
	return 0;
}
///////////////////////////////////////////////////////////////
int zSyntax::dofirst()//Let's begin to show the most complex part...
{
	long i;
	for(i=0;i<MAX_VN;i++)
		if(first[i])
		{
			delete first[i];
			first[i]=0;
		}
	for(i=0;i<vn->getnum();i++)
	{
		first[i]=new zAsmchar(MAX_FIRST);
		if(!first[i]) return -100;
		if(!dofirst1(i,vn->getdata()[i])) first[i]->add('@');
	}
	return 0;
}
///////////////////////////////////////////////////////////////
int zSyntax::dofirst1(long &i,char d)//What a MESS & ROCK Function!
{
	long j,k,r=1;
	char c;
	for(j=0;j<pnum;j++)
		if(left[j]==d)
		{
			for(k=0;k<right[j]->getnum();k++)
			{
				c=right[j]->getdata()[k];
				if(vn->find(c)<0||dofirst1(i,c)) goto not_vn;
			}r=0;continue;			//Continue for j(pnum)
not_vn:		if(vt->find(c)>=0) first[i]->add(c);
			else if(c=='@') r=0;
		}
	return r;
}
//////////////////////////////////////////////////////////////
int zSyntax::dofollow()//Easy to Learn? :)
{
	long i,j,r,n,rn;
	char c;
	for(i=0;i<MAX_VN;i++)
		if(follow[i])
		{
			delete follow[i];
			follow[i]=0;
		}
	for(i=0;i<vn->getnum();i++)
	{
		follow[i]=new zAsmchar(MAX_FOLLOW);
		if(!follow[i]) return -100;
	}
	follow[vn->find(start)]->add('#');
	do{
		r=0;
		for(i=0;i<pnum;i++)
		{
			rn=right[i]->getnum();
			for(j=0;j<rn;j++)
			{
				c=right[i]->getdata()[j];
				if(c=='@'||vt->find(c)>=0) continue;
				n=vn->find(c);
				if(j+1==rn) 
				{
					if(!follow[n]->or(*follow[vn->find(left[i])])) r=1;
				}
				else
				{
					c=right[i]->getdata()[j+1];
					if(vt->find(c)>=0)
					{
						if(!follow[n]->add(c)) r=1;
					}
					else
					{
						follow[n]->add('@');
						if(!follow[n]->or(*first[vn->find(c)])) r=1;
						follow[n]->del('@');
						if(first[vn->find(c)]->find('@')>=0)
							if(!follow[n]->or(*follow[vn->find(c)])) r=1;
					}
				}
			}
		}
	}while(r);
	return 0;
}
///////////////////////////////////////////////////////////////
int zSyntax::doselect()//Need {First} & {Follow}
{
	long i,j,n;
	char c;
	for(i=0;i<MAX_P;i++)
		if(select[i])
		{
			delete select[i];
			select[i]=0;
		}
	for(i=0;i<pnum;i++)
	{
		select[i]=new zAsmchar(MAX_SELECT);
		if(!select[i]) return -100;
		for(j=0;j<right[i]->getnum();j++)
		{
			c=right[i]->getdata()[j];
			if(c=='@')
				j=right[i]->getnum();
			else
			{
				n=vn->find(c);
				if(n<0)
					select[i]->add(c);
				else
				{
					select[i]->or(*first[n]);
					if(first[n]->find('@')>=0)
					{
						select[i]->del('@');
						continue;
					}
				}
			}
			break;
		}
		if(j==right[i]->getnum())
		{
			select[i]->add('@');
			select[i]->or(*follow[vn->find(left[i])]);
		}
	}
	return 0;
}
///////////////////////////////////////////////////////////////
int zSyntax::checkll1()//返回0表示符合LL(1)文法
{
	long i,j,k,n;
	char c,*p=new char[vt->getnum()+2];
	for(i=0;i<vn->getnum();i++)
	{
		memset(p,0,vt->getnum()+2);
		for(j=0;j<pnum;j++)
		{
			if(left[j]==vn->getdata()[i])
				for(k=0;k<select[j]->getnum();k++)
				{
					c=select[j]->getdata()[k];
					n=vt->find(c);
					if(c=='@') n=vt->getnum();
					if(c=='#') n=vt->getnum()+1;
					if(p[n]++) return 1;
				}
		}
	}
	return 0;
}
///////////////////////////////////////////////////////////////
void zSyntax::doform()//产生分析表...
{
	memset(m,0,sizeof(m));
	long i,j,n;
	char c;
	for(i=0;i<pnum;i++)
	{
		for(j=0;j<select[i]->getnum();j++)
		{
			c=select[i]->getdata()[j];
			if(c=='@') continue;
			if(c=='#') n=vt->getnum();
			else n=vt->find(c);
			m[vn->find(left[i])][n]=right[i];
		}
	}
}
///////////////////////////////////////////////////////////////
int zSyntax::dotest(char *b)//Include outputing to "b"
{
	zStkchar s;//(MAX_STACK);
	char c,*in=test,t[256];
	int i,n;
	zStrchar *p;
	*b=0;
	s.push('#');
	s.push(start);
	while(1)
	{
		s.print(t);
		strcat(b,t);
		sprintf(t,"\t%s\t",in);
		strcat(b,t);
		if(s.pop(c)) return -1;
		if(vn->find(c)>=0)
		{
			n=vt->find(*in);
			if(*in=='#') n=vt->getnum();
			p=m[vn->find(c)][n];
			if(!p) return -2;
			sprintf(t,"\t%c->%s\r\n",c,p->getdata());
			strcat(b,t);
			if(*p->getdata()!='@')
				for(i=p->getnum()-1;i>=0;i--)
					if(s.push(p->getdata()[i])<0) return -100;
		}
		else
		{
			if(c=='#')
				if(*in=='#') break;
				else return -4;
			if(c!=*in++) return -3;
			sprintf(t,"\t%c匹配\r\n",c);
			strcat(b,t);
		}
	}
	strcat(b,"\t接受\r\n");
	return 0;
}
///////////////////////////////////////////////////////////////
//PS:Hope NO bugs...