buildnfa.cpp

一个大学时候做的编译原理的实验.实验内容是正则表达式到NFA到DFA到最小化DFA最终生成词法分析代码的整个过程的演示.那时由于时间关系,词法分析代码自动生成部分还没完成.

#include "Globals.h"
//#include "MainFrm.h"
//#include "AutoMakeView1.h"

int R=20;//节点半径
int d=4*R;
list<int>::iterator CurrentIter=NULL;//当前演示指针

int xadd=80;//用于演示中x坐标的一次增减大小量
int yadd=50;//用于演示中y坐标的一次增减大小量
int startx=50,starty=300;//用于演示的结点的默认的坐标

//以下是NFA的数据结构
CString rExp;//正则表达式
LETTER_LIST letterlist;
NFA objNFA;
NODE_LIST* NFA_List=NULL;
int StateSum;//状态总数

///////////////////////////////////
CNODE_LIST cnodelist;
/////////////////////////////

//视图显示
list<int> operations;
list<State> drawstates;
list<ARC> arcs;
CPoint* StatesPoints;

/*以下是正则表达式到NFA的几个函数*/
void Translate(CString& r);//转换正则表达式
void GetLetters(CString& r);//获取字母表
void RToNFA(CString& r,NFA_LIST& NFAlist,CNODE_LIST &cnodelist,STATE_STACK &statestack);//正则表达式到NFA
void TranslateNFA(NFA_LIST& NFAlist);//改变NFA的存储结构
void GetStatesPos(CPoint& pt);//获取节点坐标

void ClearNFA()//清空数据结构里保存的东西
{
	//////////////////
	cnodelist.clear();
	/////////////////////
	letterlist.clear();
	if(NFA_List!=NULL)
	{
        delete []NFA_List;
		NFA_List=NULL;
	}
	operations.clear();
	drawstates.clear();
	arcs.clear();
	if(StatesPoints!=NULL)
	{
		delete []StatesPoints;
		StatesPoints=NULL;
	}
}

bool BuildNFA(CString& r)//创建NFA
{
	if(r.IsEmpty())
	{
		AfxMessageBox("请选择一个正则表达式进行操作!\n(双击列表中的一项)");
		return false;
	}
	CPoint pt(50,300);
	NFA_LIST NFAlist;
	//////////////////
	STATE_STACK statestack;
	//////////////////////
	Translate(r);
	GetLetters(r);
	RToNFA(r,NFAlist,cnodelist,statestack);
	TranslateNFA(NFAlist);
	GetStatesPos(pt);
	NFAlist.clear();
	return true;
}

/*正则表达式到NFA的几个函数的实现*/

void Translate(CString& r)//转换正则表达式,主要把连接符号以'&'标识出来
{
	list<char> chList;
	int i=0;
	r+='\0';
	int n=r.GetLength();
	///////////////////
	int num=0;//用于计算y的初始坐标是多少
	////////////////////////
    while(i<n-1)//以链表把转换后的正则表达式保存起来
	{
		chList.push_back(r[i]);
//		if(r[i]>='a'&&r[i]<='z'||r[i]>='A'&&r[i]<='Z'||r[i]==')'||r[i]=='*')
		if(r[i]!='('&&r[i]!='|')
			//满足此条件的字母后面加'&'
		{
//			if(r[i+1]>='a'&&r[i+1]<='z'||r[i+1]>='A'&&r[i+1]<='Z'||r[i+1]=='(')
			if(r[i+1]!=')'&&r[i+1]!='*'&&r[i+1]!='|'&&r[i+1]!='\0')
				chList.push_back('&');
		}
		/////////////////////
		if(r[i]=='|')
		{
			num++;
		}
		////////////////

		i++;
	}
	r.Empty();
	list<char>::iterator iter;
	for(iter=chList.begin();iter!=chList.end();iter++)
	{
		r+=*iter;
	}
	////////////////////
	if(num>5)
	{
		starty=num*60;
	}
	////////////////////
	
	chList.clear();//清空链表,释放内存空间
}

void GetLetters(CString& r)
{
	int i=0;
	char letter[128];
	memset(letter,0,128);
	int n=r.GetLength();
	while(i<n)
	{
		if(r[i]!='&'&&r[i]!='|'&&r[i]!='*'&&r[i]!='('&&r[i]!=')')
		{
			//letterlist.push_back(r[i]);
			letter[r[i]]=r[i];
		}
		i++;
	}
	for(i=0;i<128;i++)
	{
		if(letter[i]!=0)
		{
			letterlist.push_back((char)letter[i]);
		}
	}
}

///////////////////////////////////////////////////////////////////
int max_(int a,int b)//返回两者中的最大值
{
	if(a>b)
		return a;
	else
		return b;
}
int count(STATE_CHAIN &statechain)//用来计算状态链表的状态数
{
	int num=0;
	STATE_CHAIN::iterator iter;
	for(iter=statechain.begin();iter!=statechain.end();iter++)
	{
		num++;
	}
	return num;
}

void X_ADD(CNODE_LIST &cnodelist,STATE_LIST &statelist,int n)//x方向上的增加量，用于画图的方法
{
	int i;
	CNODE_LIST::iterator iter;
	STATE_LIST::iterator iter1;
	NODE_LIST::iterator iter2;
	for(iter1=statelist.begin();iter1!=statelist.end();iter1++)//对每一个结点的x值都增加值n
	{
		i=0;
		iter=cnodelist.begin();
		while(i!=*iter1)
		{
			iter++;
			i++;
		}
		iter->x+=n;		
	}
}

void Y_ADD(CNODE_LIST &cnodelist,STATE_LIST &statelist,int n)//x方向上的增加量，用于画图的方法
{
	int i;
	CNODE_LIST::iterator iter;
	STATE_LIST::iterator iter1;
	NODE_LIST::iterator iter2;
	for(iter1=statelist.begin();iter1!=statelist.end();iter1++)//对每一个结点的y值都增加值n
	{
		i=0;
		iter=cnodelist.begin();
		while(i!=*iter1)
		{
			iter++;
			i++;
		}
		iter->y+=n;		
	}
}

CNode FIND(CNODE_LIST cnodelist,State n)//找某一状态的坐标结点
{
	int i=0;
	CNODE_LIST::iterator iter;
	iter=cnodelist.begin();
	while(i!=n)
	{
		iter++;
		i++;
	}
	return *iter;
}
///////////////////////////////////////////////////////////////////

NFA AddAnd(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,NFA& val2)//连接操作,返回新状态的NFA
{
	ARC tem;
	NFA val;
	int i;
	NFA_LIST::iterator iter;

	//////////////////////////////////
	STATE_CHAIN::iterator iter1;
	STATE_CHAIN statechain,statechain1,statechain2;
	State state1,state2;
	//////////////////////////////////

	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)//寻找第val1.end个节点
	{
		if(i==val1.end)//向此节点的相邻节点链表加入一个节点
		{
			Node node;
			node.state=val2.start;
			node.symbol='\0';
			iter->push_back(node);
			
            operations.push_back(2);
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val2.start;
			arcs.push_back(tem);
			
			break;
		}
	}
	
	val.start=val1.start;//以左操作数的开始状态为初始状态为新NFA的开始状态
	val.end=val2.end;//以右操作数的开始状态为接受状态为新NFA的接受状态

	///////////////////////////////////////
	statechain1=statestack.back();
	statestack.pop_back();//取状态链表栈中的最顶不的链表
	statechain2=statestack.back();
	statestack.pop_back();
	state1=statechain2.front();
	state2=statechain2.back();
	i=FIND(cnodelist,state2).x-FIND(cnodelist,state1).x+xadd;
	X_ADD(cnodelist,statechain1,i);


//	statechain.push_back(val.start);//合并经过运算的状态链表
	for(iter1=statechain2.begin();iter1!=statechain2.end();iter1++)
	{
		statechain.push_back(*iter1);
	}
	for(iter1=statechain1.begin();iter1!=statechain1.end();iter1++)
	{
		statechain.push_back(*iter1);
	}
	
//	statechain.push_back(val.end);
	statestack.push_back(statechain);
	statechain.clear();
	statechain1.clear();
	statechain2.clear();
	///////////////////////////////////////
	
	return val;
}

NFA AddOr(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,NFA& val2,State& StateNum)//选择操作,返回新状态的NFA
{
	ARC tem;
	NFA val;
	int i;
	NODE_LIST nodelist1,nodelist2;
	Node node;
	NFA_LIST::iterator iter;

	//////////////////////////////////
	STATE_CHAIN::iterator iter1,iter2;
	STATE_CHAIN statechain,statechain1,statechain2;
	State state1,state2;
	CNode cnode;
	//////////////////////////////////
	
	node.state=val1.start;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	
	node.state=val2.start;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	NFAlist.push_back(nodelist1);//向邻接表加入两个新的链表
	NFAlist.push_back(nodelist2);
	
	operations.push_back(1);
	drawstates.push_back(StateNum);
    val.start=StateNum++;//新建两个新的状态
	operations.push_back(1);
	drawstates.push_back(StateNum);
	val.end=StateNum++;


	///////////////////////////////////////
	statechain1=statestack.back();
	statestack.pop_back();//取状态链表栈中的最顶不的链表
	statechain2=statestack.back();
	statestack.pop_back();
	X_ADD(cnodelist,statechain1,xadd);
	X_ADD(cnodelist,statechain2,xadd);
	Y_ADD(cnodelist,statechain1,yadd);
	Y_ADD(cnodelist,statechain2,-yadd);


	statechain.push_back(val.start);//合并经过运算的状态链表
	for(iter1=statechain1.begin();iter1!=statechain1.end();iter1++)
	{
		statechain.push_back(*iter1);
	}
	for(iter1=statechain2.begin();iter1!=statechain2.end();iter1++)
	{
		statechain.push_back(*iter1);
	}
	statechain.push_back(val.end);
	statestack.push_back(statechain);
	state1=statechain1.back();
	state2=statechain2.back();

	cnode.x=startx;
	cnode.y=starty;
	cnodelist.push_back(cnode);//添加一个该状态的结点，定义在这个链表的开头
	cnode.x=max_(FIND(cnodelist,state1).x,FIND(cnodelist,state2).x)+xadd;
	cnode.y=(FIND(cnodelist,state1).y+FIND(cnodelist,state2).y)/2;
	cnodelist.push_back(cnode);
	statechain.clear();
	statechain1.clear();
	statechain2.clear();
	///////////////////////////////////////////////////////////

	
	operations.push_back(2);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val1.start;
	arcs.push_back(tem);
	
	operations.push_back(2);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val2.start;
	arcs.push_back(tem);
	
	
	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		if(i==val1.end)//向此节点的相邻节点链表加入一个节点
		{
			Node node;
			node.state=val.end;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
			
			operations.push_back(2);
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val.end;
			arcs.push_back(tem);
			
			break;
		}
	}
	
	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		if(i==val2.end)//向此节点的相邻节点链表加入一个节点
		{
			Node node;
			node.state=val.end;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
			
            operations.push_back(2);
			tem.symbol='\0';
			tem.start=val2.end;
			tem.end=val.end;
			arcs.push_back(tem);
			
			break;
		}
	}
	nodelist1.clear();//清空链表,释放内存空间
	return val;
}

NFA AddRepeat(CNODE_LIST &cnodelist,STATE_STACK &statestack,NFA_LIST& NFAlist,NFA& val1,State& StateNum)//闭包操作,返回新状态的NFA
{
    NFA val;
	int i;
	Node node;
	NODE_LIST nodelist1,nodelist2;
	NFA_LIST::iterator iter;
	ARC tem;

	////////////////////////////////////////////////////////
	CNode cnode;
	STATE_CHAIN::iterator iter1;
	STATE_CHAIN statechain,statechain1;
	State state;
	/////////////////////////////////////////////////////////
	
	operations.push_back(1);
	drawstates.push_back(StateNum);
    val.start=StateNum++;//新建两个新的状态
	operations.push_back(1);
	drawstates.push_back(StateNum);
	val.end=StateNum++;

	/////////////////////////////////////////////////
	statechain1=statestack.back();
	statestack.pop_back();//取状态链表栈中的最顶不的链表

	X_ADD(cnodelist,statechain1,xadd);
	statechain.push_back(val.start);//合并经过运算的状态链表
	for(iter1=statechain1.begin();iter1!=statechain1.end();iter1++)
	{
		statechain.push_back(*iter1);
	}
	statechain.push_back(val.end);
	statestack.push_back(statechain);
	state=statechain1.back();


	cnode.x=startx;
	cnode.y=starty;
	cnodelist.push_back(cnode);//添加一个该状态的结点，定义在这个链表的开头
    cnode.x=FIND(cnodelist,state).x+xadd;
	cnode.y=FIND(cnodelist,state).y;
	cnodelist.push_back(cnode);

	statechain.clear();
	statechain1.clear();
	///////////////////////////////////////////////////////////
	
	node.state=val1.start;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	operations.push_back(2);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val1.start;
	arcs.push_back(tem);
	
	node.state=val.end;
	node.symbol='\0';//添加一条空字符的转换边
	nodelist1.push_back(node);
	operations.push_back(3);
	tem.symbol='\0';
	tem.start=val.start;
	tem.end=val.end;
	arcs.push_back(tem);
	
    NFAlist.push_back(nodelist1);//向邻接表加入两个新的链表
	NFAlist.push_back(nodelist2);
	
	for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		if(i==val1.end)
		{
			Node node;
			node.state=val1.start;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
            
			operations.push_back(3);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val1.start;
			arcs.push_back(tem);
			
			node.state=val.end;
			node.symbol='\0';//添加一条空字符的转换边
			iter->push_back(node);
			
			operations.push_back(2);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			tem.symbol='\0';
			tem.start=val1.end;
			tem.end=val.end;
			arcs.push_back(tem);
			break;
		}
	}
    nodelist1.clear();//清空链表,释放内存空间
	return val;
}

void RToNFA(CString& r,NFA_LIST& NFAlist,CNODE_LIST &cnodelist,STATE_STACK &statestack)//正则表达式到NFA
{
    ///////////////////
	STATE_CHAIN statechain;
	///////////////////////


	list<NFA> l1;//NFA栈,NFA保存的是一个NFA的开始状态和终止状态
	list<Symbol> l2;//符号栈,用于保存正则表达式运算符
	int i=0;//标志当前字符在正则表达式字符串中的位置
	char ch;//暂存出栈字符
    NFA val1,val2,val;//保存NFA运算操作数和结果
	State StateNum=0;//当前状态数
	ARC tem;
	int n=r.GetLength();
	
	while(i<n)//如果正则表达式还没结束,do
	{
//		if(r[i]>='a'&&r[i]<='z'||r[i]>='A'&&r[i]<='Z')//遇到正则表达式
		if(r[i]!='('&&r[i]!=')'&&r[i]!='*'&&r[i]!='|'&&r[i]!='&')
		{
			NODE_LIST nodelist1;
			NODE_LIST nodelist2;

			////////////////////////////////
			CNode cnode;
			///////////////////////////////

		//	NFA nfa;
			Node node;
			operations.push_back(1);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			drawstates.push_back(StateNum);
			val.start=StateNum++;//新建两个新的状态
			operations.push_back(1);//添加一个操作,1.为节点生成操作2.为直线边3.为曲线边
			drawstates.push_back(StateNum);
			node.state=val.end=StateNum++;
			node.symbol=r[i];
            l1.push_back(val);//nfa进栈

			///////////////////////////////////
			cnode.x=startx;
			cnode.y=starty;
			cnodelist.push_back(cnode);
			cnode.x=startx+xadd;
			cnode.y=starty;
			cnodelist.push_back(cnode);
			statechain.push_back(val.start);//添加两个状态组成的链表
			statechain.push_back(val.end);
			statestack.push_back(statechain);
			statechain.clear();
			/////////////////////////////////////

			tem.symbol=r[i];
			tem.start=val.start;
			tem.end=val.end;