buildnfa.cpp

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

			arcs.push_back(tem);
			operations.push_back(2);
			
			
			nodelist1.push_back(node);//加入一条人r[i]字符的转换边
			NFAlist.push_back(nodelist1);//向邻接表加入两个新的链表
			NFAlist.push_back(nodelist2);
			nodelist1.clear();//清空链表,释放内存空间
		}
		else if(r[i]=='(')//遇到'(',暂存,以待后来作为一个括号运算完的判断
		{
			l2.push_back(r[i]);
		}
		else if(r[i]==')')//遇到'(',舍弃,运算括号内的表达式
		{
			ch=l2.back();
			l2.pop_back();
			while(ch!='(')//如果括号内的表达式还没运算完,do
			{
				switch(ch)
				{
				case '&'://连接操作
					val2=l1.back();//取操作数val2
					l1.pop_back();
					val1=l1.back();//取操作数val1
					l1.pop_back();
					val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);//运算
					l1.push_back(val);//结果放回NFA栈
					break;
				case '|':
					val2=l1.back();//取操作数val2
					l1.pop_back();
					val1=l1.back();//取操作数val1
					l1.pop_back();
					val=AddOr(cnodelist,statestack,NFAlist,val1,val2,StateNum);//运算
					l1.push_back(val);//结果放回NFA栈
					break;
				case '*':
					val1=l1.back();//闭包运算只取一个操作数val1
					l1.pop_back();
					val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);//运算
					l1.push_back(val);//结果放回NFA栈
					break;
				}
				ch=l2.back();//取出下一运算符
				l2.pop_back();
			}
		}
		else if(r[i]=='|')//遇到'|'
		{
			if(!l2.empty())
			{
				ch=l2.back();
				while(ch!='(')//向左运算级高,先运算左边的表达式
				{
					ch=l2.back();
					l2.pop_back();
					switch(ch)
					{
					case '*':
						val1=l1.back();
						l1.pop_back();
						val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
						l1.push_back(val);
						break;
					case '&':
						val2=l1.back();
						l1.pop_back();
						val1=l1.back();
						l1.pop_back();
						val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);
						l1.push_back(val);
						break;
					case '|':
						val2=l1.back();
						l1.pop_back();
						val1=l1.back();
						l1.pop_back();
						val=AddOr(cnodelist,statestack,NFAlist,val1,val2,StateNum);
						l1.push_back(val);
						break;
					}
					if(!l2.empty())
						ch=l2.back();
					else
						break;
				}//while
			}//if
			l2.push_back(r[i]);//保存操作符
		}
		else if(r[i]=='&')//遇到'&'
		{
			if(!l2.empty())
			{
				ch=l2.back();
				switch(ch)//向左运算级高,先运算左边的表达式
				{
				case '*':
					ch=l2.back();
					l2.pop_back();
					val1=l1.back();
					l1.pop_back();
					val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
					l1.push_back(val);
					break;
				case '&':
					ch=l2.back();
					l2.pop_back();
					val2=l1.back();
					l1.pop_back();
					val1=l1.back();
					l1.pop_back();
					val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);
					l1.push_back(val);
					break;
				}
			}//if
			l2.push_back(r[i]);//保存操作符
		}
		else if(r[i]=='*')//遇到'*'
		{
			if(!l2.empty())
			{
				ch=l2.back();
				switch(ch)//向左运算级高,先运算左边的表达式
				{
				case '*':
					ch=l2.back();
					l2.pop_back();
					val1=l1.back();
					l1.pop_back();
					val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
					l1.push_back(val);
					break;
				}
			}//if
			l2.push_back(r[i]);//保存操作符
		}//else if
		i++;
	}//while
	while(!l2.empty())//剩余在'()'外的表达式的运算
	{
		ch=l2.back();
		l2.pop_back();
		switch(ch)
		{
		case '*':
			val1=l1.back();
			l1.pop_back();
			val=AddRepeat(cnodelist,statestack,NFAlist,val1,StateNum);
			l1.push_back(val);
			break;
		case '&':
			val2=l1.back();
			l1.pop_back();
			val1=l1.back();
			l1.pop_back();
			val=AddAnd(cnodelist,statestack,NFAlist,val1,val2);
			l1.push_back(val);
			break;
		case '|':
			val2=l1.back();
			l1.pop_back();
			val1=l1.back();
			l1.pop_back();
			val=AddOr(cnodelist,statestack,NFAlist,val1,val2,StateNum);
			l1.push_back(val);
			break;
		}
	}
	objNFA=val;//保存最终的NFA的始态和终态
}

void TranslateNFA(NFA_LIST& NFAlist)//改变NFA的存储结构
{
	int i;
	NFA_LIST::iterator iter;
	NODE_LIST::iterator iter1;
	StateSum=NFAlist.size();
    NFA_List=new NODE_LIST[StateSum];
    for(i=0,iter=NFAlist.begin();iter!=NFAlist.end();iter++,i++)
	{
		for(iter1=iter->begin();iter1!=iter->end();iter1++)
			NFA_List[i].push_back(*iter1);
	}
}

void GetStatesPos(CPoint& pt)//用图的广度优先算法进行节点坐标的生成
{
	NODE_LIST::iterator iter;
	CPoint tempt;
	State tem;
	bool* flags=new bool[StateSum];
	
	for(int i=0;i<StateSum;i++)
	{
		flags[i]=0;
	}
	StatesPoints=new CPoint[StateSum];
	StatesPoints[objNFA.start]=pt;
	flags[objNFA.start]=1;
	queue<State> q;
	q.push(objNFA.start);
	while(!q.empty())
	{
		tem=q.front();
		q.pop();
		if(NFA_List[tem].size()==2)
		{
			iter=NFA_List[tem].begin();
			if(flags[iter->state]==0)
			{
				tempt.x=int(StatesPoints[tem].x+d*0.866);
				tempt.y=int(StatesPoints[tem].y+d*0.5);
				StatesPoints[iter->state]=tempt;
				flags[iter->state]=1;
				q.push(iter->state);
			}
			iter++;
			
			if(flags[iter->state]==0)
			{
				tempt.x=int(StatesPoints[tem].x+d*0.866);
				tempt.y=int(StatesPoints[tem].y-d*0.5);
				StatesPoints[iter->state]=tempt;
				flags[iter->state]=1;
				q.push(iter->state);
			}
		}
		else if(NFA_List[tem].size()==1)
		{
			iter=NFA_List[tem].begin();
			
			if(flags[iter->state]==0)
			{
				tempt.x=int(StatesPoints[tem].x+d);
				tempt.y=StatesPoints[tem].y;
				StatesPoints[iter->state]=tempt;
				flags[iter->state]=1;
				q.push(iter->state);
			}
		}
	}
	delete []flags;
}

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

void Delay(DWORD dwDelayTime)//延时函数
{
	MSG msg;
	DWORD dwTimeBegin,dwTimeEnd;
	dwTimeBegin=timeGetTime();
	do
	{
		dwTimeEnd=timeGetTime();
		if(PeekMessage(&msg,NULL,0,0,PM_REMOVE))
		{
			TranslateMessage(&msg);
			DispatchMessage(&msg);
		}
	}while(dwTimeEnd-dwTimeBegin<dwDelayTime);
}

/*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 DrawLine(CDC* pDC,CPoint& start,CPoint& end,int r,CString str)//画直线箭头
{
//	CPen pen(PS_SOLID,5,RGB(0,0,0));
//	CPen* poldpen;

//	pDC->SetBkMode(TRANSPARENT);

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

	int dx,dy;
	double q;
	CPoint newstart,newend;
	dx=start.x-end.x;
	dy=start.y-end.y;

	q=sqrt(dx*dx+dy*dy);
	int tempx=int(dx*r/q);
	int tempy=int(dy*r/q);
	newstart.x=start.x-tempx;
	newstart.y=start.y-tempy;

	newend.x=end.x+tempx;
	newend.y=end.y+tempy;

	pDC->MoveTo(newstart);
	pDC->LineTo(newend);
	DrawArrow(pDC,newstart,newend);

	tempx=(newstart.x+newend.x)/2-10;
	tempy=(newstart.y+newend.y)/2-15;

	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)/3;
	pts[2].x=(start.x+3*end.x)/4;
	pts[2].y=start.y-abs(start.x-end.x)/3;
	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 AutoShowNFA(CDC* pDC,CAutoMakeView1*pView)//动态演示NFA的生成过程
{
    CPen* pNewPen=new CPen(PS_SOLID,2,RGB(0,0,255));
	CBrush* pNewBrush=new CBrush(RGB(255,255,0));
	CPen* pOldPen=pDC->SelectObject(pNewPen);
	CBrush* pOldBrush=pDC->SelectObject(pNewBrush);
	pDC->SetBkMode(TRANSPARENT);

	CPoint pt,pt1;
	CString str;
	///////////////////////
    CNode cnode;
	////////////////////////
	list<int>::iterator iter;
	list<State>::iterator iter1;
	list<ARC>::iterator iter2;
	iter1=drawstates.begin();
	iter2=arcs.begin();
	for(iter=operations.begin();iter!=operations.end();CurrentIter=++iter)//遍历每一个操作
	{
		Delay(500);
		pView->OnPrepareDC(pDC);
		if(*iter==1)//添加状态节点
		{
			str.Format("%d",*iter1);
			
			//pt=StatesPoints[*iter1];

			////////////////////////////////
			cnode=FIND(cnodelist,*iter1);
			pt.x=cnode.x;
			pt.y=cnode.y;
			//////////////////////////////
			
			CRect rc(pt.x-R,pt.y-R,pt.x+R,pt.y+R);
			pDC->Ellipse(&rc);
			if(*iter1==objNFA.end)//如果是终止节点,画双椭圆
			{
				rc.SetRect(pt.x-R+3,pt.y-R+3,pt.x+R-3,pt.y+R-3);
			    pDC->Ellipse(&rc);
			}
			pDC->DrawText(str,&rc,DT_SINGLELINE|DT_VCENTER|DT_CENTER);
			iter1++;
		}
		else if(*iter==2)//添加直线箭头
		{
			if(iter2->symbol=='\0')
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawLine(pDC,pt,pt1,R,"ε");
				/////////////////////////////////////
				//DrawLine(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,"ε");
			}
			else
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawLine(pDC,pt,pt1,R,iter2->symbol);
				/////////////////////////////////////
			    //DrawLine(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,iter2->symbol);
			}
			iter2++;
		}
		else//添加曲线箭头
		{
		    if(iter2->symbol=='\0')
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawArc(pDC,pt,pt1,R,"ε");
				/////////////////////////////////////
				//DrawArc(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,"ε");
			}
			else
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawArc(pDC,pt,pt1,R,iter2->symbol);
				/////////////////////////////////////
			    //DrawArc(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,iter2->symbol);
			}
			iter2++;
		}
	}
	pDC->SelectObject(pOldPen);
	pDC->SelectObject(pOldBrush);
	pNewPen->DeleteObject();
	pNewBrush->DeleteObject();
}

void PaintNFA(CDC* pDC,list<int>::iterator curiter)//重新画NFA图
{
	CPen* pNewPen=new CPen(PS_SOLID,2,RGB(0,0,255));
	CBrush* pNewBrush=new CBrush(RGB(255,255,0));
	CPen* pOldPen=pDC->SelectObject(pNewPen);
	CBrush* pOldBrush=pDC->SelectObject(pNewBrush);
	pDC->SetBkMode(TRANSPARENT);

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

	CPoint pt,pt1;
	CString str;
	list<int>::iterator iter;
	list<State>::iterator iter1;
	list<ARC>::iterator iter2;
	iter1=drawstates.begin();
	iter2=arcs.begin();
	for(iter=operations.begin();iter!=curiter;iter++)//遍历每一个操作
	{
		if(*iter==1)//添加状态节点
		{
			str.Format("%d",*iter1);
			//pt=StatesPoints[*iter1];

			////////////////////////////////
			cnode=FIND(cnodelist,*iter1);
			pt.x=cnode.x;
			pt.y=cnode.y;
			//////////////////////////////

			CRect rc(pt.x-R,pt.y-R,pt.x+R,pt.y+R);
			pDC->Ellipse(&rc);
			if(*iter1==objNFA.end)//如果是终止节点,画双椭圆
			{
				rc.SetRect(pt.x-R+3,pt.y-R+3,pt.x+R-3,pt.y+R-3);
			    pDC->Ellipse(&rc);
			}
			pDC->DrawText(str,&rc,DT_SINGLELINE|DT_VCENTER|DT_CENTER);
			iter1++;
		}
		else if(*iter==2)//添加直线箭头
		{
			if(iter2->symbol=='\0')
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawLine(pDC,pt,pt1,R,"ε");
				/////////////////////////////////////
				//DrawLine(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,"ε");
			}
			else
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawLine(pDC,pt,pt1,R,iter2->symbol);
				/////////////////////////////////////
			//DrawLine(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,iter2->symbol);
			}
			iter2++;
		}
		else//添加曲线箭头
		{
		    if(iter2->symbol=='\0')
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawArc(pDC,pt,pt1,R,"ε");
				/////////////////////////////////////
				//DrawArc(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,"ε");
			}
			else
			{
				/////////////////////////////////////
				cnode=FIND(cnodelist,iter2->start);
				pt.x=cnode.x;
				pt.y=cnode.y;
				cnode=FIND(cnodelist,iter2->end);
				pt1.x=cnode.x;
				pt1.y=cnode.y;
				DrawArc(pDC,pt,pt1,R,iter2->symbol);
				/////////////////////////////////////
			//DrawArc(pDC,StatesPoints[iter2->start],StatesPoints[iter2->end],R,iter2->symbol);
			}
			iter2++;
		}
	}
	pDC->SelectObject(pOldPen);
	pDC->SelectObject(pOldBrush);
	pNewPen->DeleteObject();
	pNewBrush->DeleteObject();
}