mlr1.cpp

着是个很好的代码

#include "stdafx.h"
#include "LR.h"
#include "MLR1.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
//----调试部分使用的代码
CString MLR1::GetFirst(int i){
	CString rc,f;
	if(i<0||i>=GetIdentNum())return "";
	rc=FirstSet5(m_first[i].Fi,m_first[i].flag&2);
	f.Format("First(%s) = %s",list_Ident.GetAt(i),rc);
	return f;
}
CString MLR1::GetFollow(int i){
	CString rc,f;
	if(i<0||i>=GetIdentNum())return "";
	rc=FollowSet1(m_first[i].Fo,m_first[i].flag&0x08);
	f.Format("Follow(%s) = %s",list_Ident.GetAt(i),rc);
	return f;
}
//----构造部分
MLR1::MLR1(){
	list_Index0=0;
}
MLR1::~MLR1(){
	if(list_Index0)delete[]list_Index0;
}
void MLR1::ReSet(FILE* pf){
//使用文件指针pf来重新驱动程序
	int i;
	p_file=pf;
	list_Express.RemoveAll();
	list_Ident.RemoveAll();
	list_Seed0.RemoveAll();
	list_Clouser0.RemoveAll();
	if(list_Index0)delete[]list_Index0;
	list_Index0=0;
	for(i=0;i<MAP_SIZE;i++)
		bit_map[i]=0;
	for(char* p=(char*)m_first+sizeof(s_first)*MAX_IDENT-1;
		p>=(char*)m_first;p--)
		*p=0;

	Lex3();
	FirstSet1();
	FirstSet6();
	FollowSet3();
}
//----输入分析部分
bool MLR1::Lex1(){
//截取一个分号段到tocken中
//功能字符取其负数
	char ch=0;
	bool end=false;
	token_len=0;
	if(feof(p_file))return false;
	while(!end&&!feof(p_file)){
		if(token_len>=LINE_LENGTH)break;		
		if(fread(&ch,1,1,p_file)<=0)break;
		if(ch<=0)goto error;
		switch(ch){
		case ';':
			end=true;
		case '<':
		case '>':
		case '=':
		case '|':
			ch=-ch;
			break;
		case '\\':
			fread(&ch,1,1,p_file);
			if(ch<=0)goto error;
			break;
		}
		token[token_len++]=ch;
	}
	token[token_len]=0;
	return true;
error:
	fprintf(stderr,"must be 1--127");
	return false;
}
int MLR1::Lex2_1(char*&s,bool isUse){
//该程序为Lex2独有的子程序
//识别非终结符并加入list_Ident
	char ident[ID_LENGTH+1];
	int  t=0;
	if((int)*s++!=-'<')return 0;
	if(isalpha(*s))ident[t++]=*s++;
	else return 0;
	while(isalpha(*s)||isdigit(*s))ident[t++]=*s++;
	while(*s=='\'')ident[t++]=*s++;
	if((int)*s++!=-'>')return 0;
	if(t==0)return 0;
	ident[t]=0;
	for(t=list_Ident.GetSize()-1;t>=0;t--)
		if(list_Ident[t]==(CString)ident)break;
	if(t<0){
		if(list_Ident.GetSize()>=MAX_IDENT)return false;
		list_Ident.Add((CString)ident);
		t=list_Ident.GetSize()-1;
		if(isUse)bit_map[t/8]|=1<<(t%8);
	}
	if(!isUse)bit_map[t/8]&=~(1<<(t%8));
	return t+1;
}
int MLR1::Lex2(){
//将token中的非终结符用(-1) -- (-127)表示
//进行语法判断<终结符>=符号表;
//-1表示出错,0表示结束,1表示还有或分支保存在token中指针s所指处
	char *d;
	char * end;
	int i;
	static char* s=0;
	if(s==0){
		s=d=token;		
		if(i=Lex2_1(s))*d++=-i;
		else return false;
		if(*s++!=-'=')return false;
	}else{
		d=token+1;
	}
	end=&token[token_len];
	while(s<=end){
		if(*s==-';'){
			s=0;
			*d=0;
			return 0;
		}else if((int)*s==-'<'){
			if(i=Lex2_1(s,true))*d++=-i;
			else
				return -1;
		}else if((int)*s==-'|'){
			s++;
			*d=0;
			return 1;
		}else
			*d++=*s++;
	}
	return -1;
}
bool MLR1::Lex3(){
//循环调用Lex1读入一句，调用Lex2进行语法分析
//判断bit_map是否为全零，如果不是则表示有未定义的非终结符
	int rc;
	while(Lex1()){
		if(token_len==0)continue;
		do{
			rc=Lex2();
			if(rc==-1)return false;
			list_Express.Add(new pchar(strlen(token)+ADJUST,token));
			//list_Express.Add((CString)token);
		}while(rc!=0);
	}
	for(int i=0;i<MAP_SIZE;i++)
		if(bit_map[i]!=0)return false;
	return true;
}
//----First集
void MLR1::FirstSet1(){
//用增量法判断所有非终结符能否推出LR_NULL
//时间复杂度为m*n
	bool chg;
	int  n,m,i,j;
	char temp[LINE_LENGTH];
	char *p;
	n=list_Ident.GetSize();
	m=list_Express.GetSize();
	do{
		chg=false;
		for(j=0;j<m;j++){
			strcpy(temp,((pchar*)list_Express.GetAt(j))->getData());
			//sprintf(temp,list_Express.GetAt(j));
			p=temp+1;
			while(*p!=0){
				if(*p>=1)break;
				if((m_first[-*p-1].flag&0x03)!=3)break;
				p++;
			}
			if(*p==0){
				m_first[-temp[0]-1].flag|=0x03;
				n--;
				chg=true;
			}
		}
	}while(chg&&(n>0));
	for(i=0;i<n;i++)
		m_first[i].flag|=0x01;
}
void MLR1::FirstSet2(int i,int j,int k){
//已经知道符号i依赖于符号（j*8+k）
//如果符号（j*8+k）依赖于其它符号则先做
//接下来把符号（j*8+k）的First加到符号i上
/*	有一个假设：图中没有环路存在
	程序中按非终结符的编号从大到小求其First集
	有循环时总是大的先调用小的，再有小的调用大的(被拒绝)
	因此依赖关系中没有大的依赖小的的情况，即无环路*/
	int ii,jj,kk;
	ii=j*8+k;
	for(jj=0;jj<16;jj++){
		for(kk=0;kk<8;kk++){
			if(token[ii*16+jj]&(1<<kk))
				FirstSet2(ii,jj,kk);}
	}
	for(ii=0;ii<MAP_SIZE;ii++)
		m_first[i-1].Fi[ii]|=m_first[j*8+k-1].Fi[ii];
	if(m_first[j*8+k-1].flag&0x02)
		m_first[i-1].flag|=0x02;
	token[i*16+j]^=1<<k;
}
bool MLR1::FirstSet3(const char *X,char*Fi){
//返回true表示计算完全
//求产生式X的First集放在Fi中
//如果要求符号串的First集,就将X[0]设为0
//假设X中不出现LR_NULL,LR_EOF和LR_EOS
//假设F的长度为MAP_SIZE,有128b
	const char *p=X+1;
	bool rc=true;
	while(*p!=0){
		if(*p>=1){
			Fi[(*p)/8]|=1<<(*p)%8;
			return rc;
		}else{
			if(*p!=*X){
				if(!FirstSet4(*p,Fi)){
					//token[*X,*p]=1,*X需要*p
					token[(-*X)*16+(-*p)/8]|=1<<(-*p)%8;
					rc=false;
				}
			}
			if((m_first[-*p-1].flag&0x02)==0)
				return rc;
		}
		p++;
	}
	return rc;
}
bool MLR1::FirstSet4(char const X,char*Fi){
//返回false表示没有进行计算
//求非终结符X的First集放在F中
//如果LR_NULL在其中则返回true
	char* temp;
	//CString temp;
	if(m_first[-X-1].flag&0x40)return false;
	if((m_first[-X-1].flag&4)==0){
		m_first[-X-1].flag|=0x40;
		for(int i=list_Express.GetSize();i>0;i--){
			temp=((pchar*)list_Express.GetAt(i-1))->getData();
			//temp=list_Express.GetAt(i-1);
			if(temp[0]==X)
				FirstSet3(temp,m_first[-X-1].Fi);
				//FirstSet3((LPCSTR)temp,m_first[-X-1].Fi);
		}
		m_first[-X-1].flag|=4;
		m_first[-X-1].flag^=0x40;
	}
	if(Fi!=m_first[-X-1].Fi){
		for(int i=0;i<MAP_SIZE;i++)
			Fi[i]|=m_first[-X-1].Fi[i];
	}
	return true;
}
CString MLR1::FirstSet5(const char*Fi,bool has_null){
//将集合表示的First变为字符串式
//LR_NULL也用特殊符号表示了
	char t[128];
	char *p=t;
	int  i,j;
	for(i=0;i<MAP_SIZE;i++){
		if(Fi[i])for(j=0;j<8;j++)
			if(Fi[i]&(1<<j))
				*p++=i*8+j;
	}
	if(has_null)*p++=LR_NULL;
	*p=0;
	return (CString)t;
}
void MLR1::FirstSet6(){
//为每个非终结符求First集
//在token中保存各非终结符之间的依赖关系
//最后根据依赖关系完成First集
/*  如遇到A=B;B=A;A=b;时
	计算First(B)时用到First(A)，可以保证First(B)包含First(A)
	计算First(A)时又用到First(B)，不能再调用First(B)而造成死循环
	计算完之后First(B)又有了新符号，为把该新符号写入First(A)中
	构造依赖表token表示A依赖于B
	如果B又依赖于C，则必须先求出完整的First(B)*/
	int i,j,k;
	for(i=0;i<2048;i++)
		token[i]=0;
	for(i=list_Ident.GetSize();i>0;i--){
		if((m_first[i-1].flag&4)==0)
			FirstSet4(-i,m_first[i-1].Fi);
	}
	for(i=0;i<128;i++){
		for(j=0;j<16;j++){
			if(token[i*16+j]){
				for(k=0;k<8;k++)
					if(token[i*16+j]&(1<<k))
						FirstSet2(i,j,k);
			}
		}
	}
}
CString MLR1::FollowSet1(const char*Fo,bool has_eof){
//将集合表示的Follow变为字符串式
//LR_EOF也用特殊符号表示了
	char t[128];
	char *p=t;
	int  i,j;
	for(i=0;i<MAP_SIZE;i++){
		if(Fo[i])for(j=0;j<8;j++)
			if(Fo[i]&(1<<j))
				*p++=i*8+j;
	}
	if(has_eof)*p++=LR_NULL;
	*p=0;
	return (CString)t;
}
bool MLR1::FollowSet2(const char *X){
//如果X中某字符可以推出LR_NULL则称此字符“通”
//q到(p-1)之间的字符串是通的
//它们都应该接受First(p)
//如果它们在X的最后面，则都要接受Follow(X[0])
//返回值保留
	const char *p,*q,*t;
	int  i;
	p=q=X+1;
	while(*p!=0){
		if(*p>0){
			for(t=q;t<p;t++)
				m_first[-*t-1].Fo[*p/8]|=1<<(*p%8);
			q=p+1;
		}else{
			for(t=q;t<p;t++)
				for(i=0;i<MAP_SIZE;i++)
					m_first[-*t-1].Fo[i]|=m_first[-*p-1].Fi[i];
			if((m_first[-*p-1].flag&0x02)==0)
				q=p;				
		}
		p++;
	}
	for(t=q;t<p;t++){
		//token[*t,*X]=1,*t需要*X
		token[(-*t)*16+(-*X)/8]|=1<<(-*X)%8;
	}
	return true;
}
void MLR1::FollowSet3(){
//此函数求各非终结符的Follow集
//先加入后续符号的First集
//再加入首符号的Follow集
//最后处理循环引用Follow集的情况
	int i,j,k;
	for(i=0;i<2048;i++)
		token[i]=0;
	m_first[0].flag|=0x08;
	for(i=list_Express.GetSize();i>0;i--)
		FollowSet2(((pchar*)list_Express.GetAt(i-1))->getData());
		//FollowSet2((LPCSTR)list_Express.GetAt(i-1));
	for(int c=0;c<2;c++){
	for(i=0;i<128;i++){
		for(j=0;j<16;j++){
			if(token[i*16+j]){
				for(k=0;k<8;k++)
					if(token[i*16+j]&(1<<k))
						FollowSet4(i,j,k);
			}
		}
	}}
}
bool MLR1::FollowSet4(int i,int j,int k){
//如果正在求X的Follow集则返回false
//如果没有求解i,则先求解i
	int ii,jj,kk;
	if(m_first[i-1].flag&0x20)return false;
		m_first[i-1].flag|=0x20;
		ii=j*8+k;
		for(jj=0;jj<16;jj++){
			for(kk=0;kk<8;kk++){
				if(token[ii*16+jj]&(1<<kk))
					FollowSet4(ii,jj,kk);}
		}
		m_first[i-1].flag^=0x20;
	for(ii=0;ii<MAP_SIZE;ii++)
		m_first[i-1].Fo[ii]|=m_first[j*8+k-1].Fo[ii];
	if(m_first[j*8+k-1].flag&0x08)
		m_first[i-1].flag|=0x08;
	token[i*16+j]^=1<<k;
	return false;
}
void MLR1::LR0_table1(){
//构造LR0分析表的主控函数
//s_size和c_size分别表示seed和clouser的索引表的大小
//st,和ct表示当前使用索引表的下标
//buf用于缓冲表达式和LR0项目
//index用于索引表，奇数为seed偶数为clouser
	char * buf=token;
	char * index=&token[LINE_LENGTH];
	int s_size,c_size;
	int	st,ct;
	s_size=c_size=0;
	st=ct=0;
	index[s_size++]=0;
	strcpy(buf,((pchar*)list_Express.GetAt(0))->getData());
	//sprintf(buf,"%s",list_Express.GetAt(0));
	LR0_table2(buf);
	list_Seed0.Add((CString)buf);
}
void MLR1::LR0_table2(char*s){
//将表达式s变为LR0项目，s[1]=LR_DOT
	int i;
	for(i=strlen(s);--i>=1;)
		s[i+1]=s[i];
	s[1]=LR_DOT;
}