mlr1.cpp

使用MFC实现编译原理词法分析器

#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){
	if(i<0||i>=GetIdentNum())return "";
	return FirstSet5(m_first[i].Fi,m_first[i].flag&2);
}
CString MLR1::GetFollow(int i){
	if(i<0||i>=GetIdentNum())return "";
	return FollowSet1(m_first[i].Fo,m_first[i].flag&0x08);
}
//----构造部分
MLR1::MLR1(){
}
MLR1::~MLR1(){
}
void MLR1::ReSet(FILE* pf){
//使用文件指针pf来重新驱动程序
	int i;
	p_file=pf;
	list_Express.RemoveAll();
	list_Ident.RemoveAll();
	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();
	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 '=':
			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){
//识别非终结符并加入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;
}
bool MLR1::Lex2(){
//将token中的非终结符用(-1) -- (-127)表示
//进行语法判断<终结符>=符号表;
	register char *s,*d;
	char * end;
	int i;
	s=d=token;
	end=&token[token_len];
	if(i=Lex2_1(s))*d++=-i;
	else return false;
	if(*s++!=-'=')return false;
	while(s<end){
		if(*s==-';')break;
		else if((int)*s==-'<'){
			if(i=Lex2_1(s,true))*d++=-i;
			else return false;
		}else
			*d++=*s++;
	}
	*d=0;
	return s<end;
}
bool MLR1::Lex3(){
//循环调用Lex1读入一句，调用Lex2进行语法分析
//判断bit_map是否为全零，如果不是则表示有未定义的非终结符
	while(Lex1()){
		if(token_len==0)continue;
		if(Lex2())
			list_Express.Add((CString)token);
		else return false;
	}
	for(int i=0;i<MAP_SIZE;i++)
		if(bit_map[i]!=0)return false;
	return true;
}
//----First集
/*	首先判断某非终结符能否推出LR_NULL
*/
bool	MLR1::FirstSet1(const char *X){
//判断表达式X能否推出LR_NULL
	const char *p=X+1;
	while(*p!=0){
		if(*p>=1){
			return false;
		}else{
			if(*p==*X)return false;
			if(!FirstSet2(*p))
				return false;
		}
		p++;
	}
	return true;
}
bool	MLR1::FirstSet2(const char X){
//判断非终结符X能否推出LR_NULL
	CString temp;
	if(m_first[-X-1].flag&0x40)return false;
	if(m_first[-X-1].flag&1)
		return (m_first[-X-1].flag&2)!=0;
	m_first[-X-1].flag|=0x40;
	for(int i=list_Express.GetSize();i>0;i--){
		temp=list_Express.GetAt(i-1);
		if(temp[0]==X){
			if(FirstSet1((LPCSTR)temp)){
				m_first[-X-1].flag|=3;
				return true;
			}
		}
	}
	m_first[-X-1].flag|=1;
	m_first[-X-1].flag^=0x40;
	return false;
}
bool MLR1::FirstSet3(const char *X,char*Fi){
//求产生式X的First集放在F中,如果LR_NULL在First集中则返回true
//如果要求符号串的First集,就将X[0]设为0
//假设X中不出现LR_NULL,LR_EOF和LR_EOS
//假设F的长度为MAP_SIZE,有128b
	const char *p=X;
	X++;
	while(*X!=0){
		if(*X>=1){
			Fi[(*X)/8]|=1<<(*X)%8;
			return false;
		}else{
			if(*X==*p){
				if(!FirstSet2(*X))
					return false;
			}else if(!FirstSet4(*X,Fi)){
					return false;
			}
		}
		X++;
	}
	return true;
}
bool MLR1::FirstSet4(char const X,char*Fi){
//求非终结符X的First集放在F中
//如果LR_NULL在其中则返回true
	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=list_Express.GetAt(i-1);
			if(temp[0]==X)
				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 (m_first[-X-1].flag&2);
}
CString MLR1::FirstSet5(const char*Fi,bool has_null){
//将集合表示的First变为字符串式
	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集
	int i;
	for(i=list_Ident.GetSize();i>0;i--){
		if((m_first[i-1].flag&1)==0)
			FirstSet2(-i);
	}
	for(i=list_Ident.GetSize();i>0;i--){
		if((m_first[i-1].flag&4)==0)
			FirstSet4(-i,m_first[i-1].Fi);
	}
}
CString MLR1::FollowSet1(const char*Fo,bool has_eof){
//将集合表示的Follow变为字符串式
	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,char * Fo){
//求非终结符X的Follow集
//只有在X的Follow集未被计算时才调用该函数
//必须在执行前将LR_EOF加入识别符号的Follow集中
//flag为真表示已经找到X,将找后继的第一个字符
//flag.b5该符号的Follow集正在被计算
	int i,j;
	bool flag,rc=true;
	char temp[LINE_LENGTH];
	char *p;
	//如果是非法符号则退出
	if(X>=0||X<-MAX_IDENT)return true;
	//如果该符号正被计算则退出
	if(m_first[-X-1].flag&0x20)return false;
	//如果该符号为被计算则计算
	if((m_first[-X-1].flag&0x10)==0){
		m_first[-X-1].flag|=0x20;
		for(i=list_Express.GetSize();i>0;i--){
			sprintf(temp,list_Express.GetAt(i-1));
			flag=false;
			p=temp+1;
			while(*p!=0){
				if(!flag){
					if(*p==X){
						//表达式中出现了符号X
						flag=true;}
				}else{
					if(*p>0){
						//规则2:X后碰上终结符
						flag=false;
						Fo[*p/8]|=1<<(*p%8);
					}else{
						//规则2:X后碰上非终结符则并上它的First集
						for(j=0;j<MAP_SIZE;j++)
							Fo[j]|=m_first[-*p-1].Fi[j];
						//如果X可以推出LR_NULL则继续
						if((m_first[-*p-1].flag&2)==0)
							flag=false;
					}
				}
				p++;
			}
			if(flag&&(X!=temp[0])){
				//规则3:将temp[0]的Follow集并到Fo上
				//如果是自反关系则不计算
				if(!FollowSet2(temp[0],m_first[-temp[0]-1].Fo))
					rc=false;
				for(j=0;j<MAP_SIZE;j++)
					Fo[j]|=m_first[-temp[0]-1].Fo[j];
				if(m_first[-temp[0]-1].flag&0x08)
					m_first[-X-1].flag|=0x08;
			}
		}
		if(rc)m_first[-X-1].flag|=0x10;
		m_first[-X-1].flag^=0x20;
	}
	if(Fo!=m_first[-X-1].Fo){
		for(i=0;i<MAP_SIZE;i++)
			Fo[i]|=m_first[-X-1].Fo[i];
	}
	return rc;
}
void MLR1::FollowSet3(){
//求各非终结符的Follow集
	int i;
	m_first[0].flag|=0x08;
	for(i=list_Ident.GetSize();i>0;i--){
		if((m_first[i-1].flag&0x10)==0){
			FollowSet2(-i,m_first[i-1].Fo);
		}
	}
}