builddfa.cpp

编译原理课程设计之正则表达式与自动机之间的变换

/*从NFA到DFA
子集构造法

DFA的“状态”Sd是NFA的非空状态子集，Sd?2S

DFA的初态Sd0－包括原NFA初态S0及其经?转换能到达的所有状态，即
	 Sd0 = { S0，u | S0 ??*  u }＝ ?-closure({S0})
 ?-closure(T) = {  从状态集合T的每一个状态t出发，经过若干空转换（ ?转换）所能到达的所有状态}

初始时，DFA的状态集合Dstates中只有初态Sd0且未标记。
   while ( Dstates中有未标记的状态 T ） do
	{   标记 T；
	    for 每个输入符号 a do
	    {   U = ?-closure(  { s | NFA状态转换函数?(t,a)=s, t?T} )
		 if  U 不在 Dstates中 则将其加入Dstates且未加标记；
		 记下DFA状态转换函数?d（T，a）＝ U ； 
        }
   }
*/
#include "Globals.h"

int RR=20;

NODE_LIST* DFAtransArray=NULL;
STATE_LIST* DFAStateArray=NULL;
int DFAStateNum;
STATE_LIST startlist;
STATE_LIST acceptlist;
CPoint* States;

//list<int>::iterator CurrentIter=NULL;//当前演示指针

void ClearDFA()
{
	if(DFAtransArray!=NULL)
	{
		delete []DFAtransArray;
		DFAtransArray=NULL;
	}
	if(DFAStateArray!=NULL)
	{
		delete []DFAStateArray;
		DFAStateArray=NULL;
	}
	startlist.clear();
	acceptlist.clear();
}

bool compare(STATE_LIST& T1,STATE_LIST& T2)//比较两个状态集
{
	bool flag=1;
	STATE_LIST::iterator iter1,iter2;
	if(T1.size()!=T2.size())//如果两个状态集的状态数相同do
	{
		flag=0;
		return flag;
	}
	for(iter1=T1.begin(),iter2=T2.begin();iter1!=T1.end();iter1++,iter2++)
	{//逐个状态比较
		if(*iter1!=*iter2)//如果有不同返回false
		{
			flag=0;
		    return flag;
		}
	}
	return flag;//如果没有不同的返回true
}

bool FindStateList(TRANS_LIST& DFAtranslist,STATE_LIST& T)//查找此状态集是否存在于DStates中
{
	bool flag=0;
	TRANS_LIST::iterator iter;
	for(iter=DFAtranslist.begin();iter!=DFAtranslist.end();iter++)
	{
		if(compare(T,iter->dstate))
		{
			flag=1;
			break;
		}
	}
	return flag;
}

bool DFAFindState(STATE_LIST& T,State state)//在状态集T中查找状态state
{
	bool flag=0;
	STATE_LIST::iterator iter;
	for(iter=T.begin();iter!=T.end();iter++)
	{
		if(*iter==state)//如果找到返回true,否则返回false
		{
			flag=1;
			break;
		}
	}
	return flag;
}

/*求出状态集T经过若干空字符转换所到达的状态集n_T*/
void Null_closure(NODE_LIST* NFA_List,STATE_LIST& T,STATE_LIST& n_T)
{
	stack<State> s;//申请一个临时栈,采用深度优先的算法
    STATE_LIST::iterator iter;
	NODE_LIST::iterator iter1;
	State state;
    for(iter=T.begin();iter!=T.end();iter++)//初始状态进栈
	{
		s.push(*iter);
		n_T.push_back(*iter);
	}
	while(!s.empty())//如果栈非空
	{
		state=s.top();//出栈
		s.pop();
		for(iter1=NFA_List[state].begin();iter1!=NFA_List[state].end();iter1++)
		{
			if(iter1->symbol=='\0')//如果是控制符'\0'
			{
				if(!DFAFindState(n_T,iter1->state))//如果还没加进n_T状态集
				{
					n_T.push_back(iter1->state);//加入n_T状态集
					s.push(iter1->state);//把此状态进栈,以便后来再次查找
				}//if
			}//if
		}//for
	}//while
}

/*求出状态集T经过一个字符r转换所到达的状态集r_T*/
void Move(NODE_LIST* NFA_List,char r,STATE_LIST& T,STATE_LIST& r_T)
{
    STATE_LIST::iterator iter;
	NODE_LIST::iterator iter1;
	for(iter=T.begin();iter!=T.end();iter++)//查找整个NFA的邻接表头
	{
		for(iter1=NFA_List[*iter].begin();iter1!=NFA_List[*iter].end();iter1++)
		{
			if(iter1->symbol==r)//如果转换字符为r
			{
				if(!DFAFindState(r_T,iter1->state))//如果还没加进n_T状态集
				{
					r_T.push_back(iter1->state);//加入n_T状态集
				}//if
			}//if
		}//for
	}
}

//用子集构造法创建DFA
void NFAToDFA(NODE_LIST* NFA_List,TRANS_LIST& DFAtranslist)
{
	StateListNode sln;
	TRANS_LIST::iterator curiter;
	LETTER_LIST::iterator iter;
	TransListNode translistnode;
	STATE_LIST T,n_T,r_T;

	T.push_back(objNFA.start);//初始化状态集为NFA状态
	Null_closure(NFA_List,T,n_T);//求出开始状态的经过空字符所到达的状态集,
	//以作为DFA转换表的开始状态集
	n_T.sort();//把n_T排序
    translistnode.dstate=n_T;
    DFAtranslist.push_back(translistnode);//加进转换表
	curiter=DFAtranslist.begin();//curiter把未标志和已标志状态集分开,
	//curiter已标志状态集的最后一个元素,其后后面的状态集全部为未标志的,
	//同时指向的也是转换表中正在添加状态集的表项
	n_T.clear();//n_T清空以便后来使用

	while(curiter!=DFAtranslist.end())//如果还存在未标志的状态表
	{
		T=curiter->dstate;//将当前curiter指向的状态集付给T
		for(iter=letterlist.begin();iter!=letterlist.end();iter++)//for整个字母表
		{
			Move(NFA_List,*iter,T,r_T);//查找T中状态经过字符(*iter)所到达的状态集r_T
			if(r_T.empty())//如果r_T为空,继续查找下一字母的情况
			{
				continue;
			}
			Null_closure(NFA_List,r_T,n_T);//求出状态集r_T经过若干空字符转换所到达的状态集n_T
			n_T.sort();//把状态集n_T的状态排序,以便后来比较状态集
			if(!FindStateList(DFAtranslist,n_T))//如果状态集n_T还没加进DStates中do
			{
				translistnode.dstate=n_T;
				DFAtranslist.push_back(translistnode);//加进DStates
			}
			sln.statelist=n_T;
			sln.symbol=*iter;
            curiter->slnList.push_back(sln);//将n_T及所经过的字符加进转换表
			n_T.clear();//n_T清空以便后来使用
			r_T.clear();//r_T清空以便后来使用
		}
		curiter++;//标志当前状态集
	}
}

int GetStateListIndex(STATE_LIST*& DFAStateArray,STATE_LIST& T)
{
	int i;
	for(i=0;i<DFAStateNum;i++)
	{
		if(compare(DFAStateArray[i],T))
		{
			break;
		}
	}
	return i;
}

void TranslateDFA(TRANS_LIST& DFAtranslist,NODE_LIST*& DFAtransArray)
{
	int i;
	Node node;
	TRANS_LIST::iterator iter;
	STATELISTNODE_LIST::iterator iter1;
	DFAStateNum=DFAtranslist.size();
	DFAStateArray=new STATE_LIST[DFAStateNum];
	DFAtransArray=new NODE_LIST[DFAStateNum];
	for(i=0,iter=DFAtranslist.begin();iter!=DFAtranslist.end();iter++,i++)
	{
		DFAStateArray[i]=iter->dstate;
	}
	for(iter=DFAtranslist.begin(),i=0;iter!=DFAtranslist.end();iter++,i++)
	{
		for(iter1=iter->slnList.begin();iter1!=iter->slnList.end();iter1++)
		{
			node.symbol=iter1->symbol;
			node.state=GetStateListIndex(DFAStateArray,iter1->statelist);
            DFAtransArray[i].push_back(node);
		}
	}
	for(i=0;i<DFAStateNum;i++)
	{
		if(DFAFindState(DFAStateArray[i],objNFA.start))
		{
			startlist.push_back(i);
		}
		if(DFAFindState(DFAStateArray[i],objNFA.end))
		{
			acceptlist.push_back(i);
		}
	}
}

/*以下函数只是为了检验结果的正确性*/
CString PrintStateList(STATE_LIST& T)
{
	STATE_LIST::iterator iter;
	CString str,str1;
	str+='{';
	for(iter=T.begin();iter!=T.end();iter++)
	{
		if(iter!=T.begin())
		{
			str+=',';
		}
		str1.Format("%d",*iter);
		str+=str1;
	}
	str+='}';
	return str;
}

int FindMax(STATE_LIST*& DFAStateArray,int n)//找状态集中具有最大状态的状态数
{
	int max=0,i,temp;
	for(i=0;i<n;i++)
	{
		temp=DFAStateArray[i].size();
		if(temp>max)
			max=temp;
	}
	return max;

}

void BuildDFA()
{
	TRANS_LIST DFAtranslist;//保存DFA转换表
	NFAToDFA(NFA_List,DFAtranslist);
	TranslateDFA(DFAtranslist,DFAtransArray);
	DFAtranslist.clear();
}

/////////////////////////以下是动态演示过程////////////////////////////

void DrawArrow(CDC* pDC,CPoint& start,CPoint& end)//画箭头
{
	int dx,dy,x,y;
	double dq;

	dx=start.x-end.x;
	dy=start.y-end.y;

	dx=dx-dy;
	dy=dx+2*dy;

    dq=sqrt(dx*dx+dy*dy);
	x=int(10*dx/dq);
	y=int(10*dy/dq);

	pDC->MoveTo(end);
	pDC->LineTo(end.x+x,end.y+y);
    pDC->MoveTo(end);
	pDC->LineTo(end.x+y,end.y-x);
}

void DrawRect(CDC* pDC,CPoint& start,CPoint& end,CString str)//画矩形箭头
{
//	CPen pen(PS_SOLID,5,RGB(0,0,0));
//	CPen* poldpen;

//	pDC->SetBkMode(TRANSPARENT);

//	poldpen=pDC->SelectObject(&pen);

	int tempx,tempy;
	pDC->MoveTo(start.x,start.y);
	pDC->LineTo(end.x,start.y);
	pDC->MoveTo(start.x,start.y);
	pDC->LineTo(start.x,end.y);
	pDC->MoveTo(end.x,end.y);
	pDC->LineTo(end.x,start.y);
	pDC->MoveTo(end.x,end.y);
	pDC->LineTo(start.x,end.y);

//	DrawArrow(pDC,newstart,newend);

//	tempx=(start.x+end.x)/2;
	tempx=start.x;
	tempy=(start.y+end.y)/2-10;

	pDC->TextOut(tempx,tempy,str);

//	pDC->SelectObject(poldpen);
//	pen.DeleteObject();
}

void DrawArc(CDC* pDC,CPoint& start,CPoint& end,int r,CString str)//画曲线箭头
{
//	pDC->SetBkMode(TRANSPARENT);
    CPoint* pts;
	pts=new CPoint[4];
	pts[0].x=start.x;
	pts[0].y=start.y-r;
	pts[1].x=(3*start.x+end.x)/4;
	pts[1].y=start.y-abs(start.x-end.x)/2;
	pts[2].x=(start.x+3*end.x)/4;
	pts[2].y=start.y-abs(start.x-end.x)/2;
	pts[3].x=end.x;
	pts[3].y=end.y-r;
	pDC->PolyBezier(pts,4);
	DrawArrow(pDC,pts[2],pts[3]);

	int x,y;
	x=(pts[0].x+pts[3].x)/2;
	y=pts[2].y+abs(start.x-end.x)/30;
	pDC->TextOut(x,y,str);

	delete []pts;
}

void DrawArc(CDC* pDC,CPoint& point,int r,int n,CString str)//重载画曲线箭头，处理只有一个结点的情况
{
//	pDC->SetBkMode(TRANSPARENT);
    CPoint* pts;
	pts=new CPoint[4];
	pts[0].x=point.x-r*sin(1);
	pts[0].y=point.y+r*cos(1);
	pts[1].x=point.x-r*(n+1)*sin(0.5);
	pts[1].y=point.y+r*(n+1)*cos(0.5);
	pts[2].x=point.x+r*(n+1)*sin(0.5);;
	pts[2].y=point.y+r*(n+1)*cos(0.5);
	pts[3].x=point.x+r*sin(1);
	pts[3].y=point.y+r*cos(1);
	pDC->PolyBezier(pts,4);
	DrawArrow(pDC,pts[2],pts[3]);

	int x,y;
	x=(pts[0].x+pts[3].x)/2;
	y=point.y+(n+1)*r-15;
	pDC->TextOut(x,y,str);

	delete []pts;
}

//画DFA图和转换表
void PaintDFA(CDC* pDC,CAutoMakeView2*pView)
{
	CPen* pNewPen=new CPen(PS_SOLID,2,RGB(0,0,0));
	CBrush* pNewBrush=new CBrush(RGB(255,255,255));
	CPen* pOldPen=pDC->SelectObject(pNewPen);
	CBrush* pOldBrush=pDC->SelectObject(pNewBrush);
	pDC->SetBkMode(TRANSPARENT);
	CPoint pt,pt1;
	CString str;
	NODE_LIST::iterator iter;
	LETTER_LIST::iterator iter1;
	STATE_LIST::iterator iter2;
	int i,j,xadd,yadd=18,max,dec=0;
	max=FindMax(DFAStateArray,DFAStateNum);
	xadd=18*max;
	if(xadd<50)
	{
		xadd=50;
	}
	States=new CPoint[DFAStateNum];
	for(i=0;i<DFAStateNum;i++)//确定各个状态的结点位置
	{
		//画各个结点
		if(i==0)
		{
			States[i].x=50;
	        States[i].y=300;
		}
		else
		{
			States[i].x=States[i-1].x+100;
		    States[i].y=States[i-1].y;
		}
		str.Format("%d",i);
		pView->OnPrepareDC(pDC);	
		pt=States[i];
		CRect rc(pt.x-RR,pt.y-RR,pt.x+RR,pt.y+RR);
		pDC->Ellipse(&rc);
		for(iter2=acceptlist.begin();iter2!=acceptlist.end();iter2++)
		{
			if(i==*iter2)//如果是接受状态
			{
				rc.SetRect(pt.x-RR+3,pt.y-RR+3,pt.x+RR-3,pt.y+RR-3);
			    pDC->Ellipse(&rc);
			}
		}
		pDC->DrawText(str,&rc,DT_SINGLELINE|DT_VCENTER|DT_CENTER);
	}
	for(i=0;i<DFAStateNum;i++)////////////////画状态转换的曲线
	{
		j=1;
		for(iter=DFAtransArray[i].begin();iter!=DFAtransArray[i].end();iter++)
		{
			pt=States[i];
			pt1=States[iter->state];
			if(pt==pt1)
			{
				DrawArc(pDC,pt,RR,j,iter->symbol);
				j++;
			}
			else
			{
                DrawArc(pDC,pt,pt1,RR,iter->symbol);
			}
		}
	}
    pt.x=pt.y=0;
	pt1.x=xadd+pt.x;
	pt1.y=yadd+pt.y;
	for(i=0;i<=DFAStateNum;i++)///////////画转换表
	{
		if(i==0)
		{
			DrawRect(pDC,pt,pt1,"替换状态");
		    pt.x+=xadd;
		    pt1.x+=xadd;
		}
		else
		{
		   str.Format("%d",i-1);//处理第一列的情况
		   DrawRect(pDC,pt,pt1,str);
		   pt.x+=xadd;
		   pt1.x+=xadd;
		}
		j=0;
		if(j==0&&i!=0)//处理第二列的情况
		{
			DrawRect(pDC,pt,pt1,PrintStateList(DFAStateArray[i-1]));
			pt.x+=xadd;
			pt1.x+=xadd;

		}
		else if(i==0)
		{
			DrawRect(pDC,pt,pt1,"转换表");
			pt.x+=xadd;
			pt1.x+=xadd;
		}
		for(j=1,iter1=letterlist.begin();j<=letterlist.size();j++,iter1++)
		{
			dec=0;
			if(i==0)
			{
				DrawRect(pDC,pt,pt1,*iter1);
				pt.x+=xadd;
			    pt1.x+=xadd;
			}
			else//处理其他情况
			{
				for(iter=DFAtransArray[i-1].begin();iter!=DFAtransArray[i-1].end();iter++)
				{
					if(iter->symbol==*iter1)
					{
						DrawRect(pDC,pt,pt1,PrintStateList(DFAStateArray[iter->state]));
			            pt.x+=xadd;
			            pt1.x+=xadd;
						dec=1;
						break;
					}						
				}
				if(dec!=1)//如果不存在某一字符的转换
				{
					DrawRect(pDC,pt,pt1,"");
			        pt.x+=xadd;
			        pt1.x+=xadd;
				}
			}
		}
		pt.x=0;
		pt1.x=xadd;
		pt.y+=yadd;
		pt1.y+=yadd;
	}
	pDC->SelectObject(pOldPen);
	pDC->SelectObject(pOldBrush);
	pNewPen->DeleteObject();
	pNewBrush->DeleteObject();
}