regularview.cpp

编译原理---正则表达式到DFA的演示程序

// RegularView.cpp : implementation of the CRegularView class
//

#include "stdafx.h"
#include "Regular.h"

#include "RegularDoc.h"
#include "RegularView.h"

#include "node.h"
#include "Input.h"         //输入正则式对话框头文件
//#include "RegularToNFA.h"  //从正则到NFA头文件
//#include "assistant.h"     //从NFA到DFA头文件



#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

//*画图专用变量*********************************************************************
	int nNodeNum;  //结点个数，也就状态个数
	const int nIntervalx=100;
	const int nIntervaly=80;
	const int nRadusx=30;
	const int nRadusy=30;
 
struct NodeInfor
{
	BOOL bDrawNode;
	int  xPos;
	int	 yPos;
};
  
	NodeInfor*   NodeInfArray;//[nNodeNum+1]={0,};  //开始时初始化为0
	Node**		 NodeTable;//[nNodeNum+1]={0,};         //开始时初始化为0

	BOOL bChangeLine;   //1表示已到达路径尽头，为一条路径，需换行 0则否
	int nCountLine;     //记录行数
	int nLastXPos;      //记录上一个结点坐标
	int nLastYPos;
	int nEndNodeNum;	//记录结束状态结点号

//*********************************************************************


   /*
	* 正则输入对话框对外提供的接口
	*/
   char *string; //"10|(01|1)*0|1*#";  //提供给从正则到NFA正则字符串


	/*
	 * 本画图程序要用到的外部接口：
	 */
/*	Node* FirstTable[100];  //此邻接表由正则到NFA提供
	int FirstNodeQuantity;   //结点数量
	char AllChar[20];   //接收到哪些字符 
	int CharQuantity;   //接收字符个数，e除外 
	void RegularToNFA();
*/


//从正则到NFA***************************************************************************
#include <string.h>

Node* FirstTable[100]={0,};

int FirstNodeQuantity=0;   //结点数量
char AllChar[20];   //接收到哪些字符 
int CharQuantity=0;   //接收字符个数，e除外 */

//char string[]="10|1#";
int linepos=0;

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
struct stArc
{
		int ST0;
	    int ST1;
		int q;
};


class ListNode{
public:

        stArc arc;
		ListNode *next;
};


class Stack{
public:
	ListNode *top;
public:
	Stack(void){top=NULL;}

	void Push(stArc x);
	stArc Pop(void);
};
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
void Stack::Push(stArc x)
{
	ListNode *TempNode;
	TempNode=new ListNode;
	TempNode->arc=x;
	TempNode->next=top;
	top=TempNode;
}//Push

stArc Stack:: Pop(void)
{
stArc y={0,0,0};
stArc x;
	ListNode *TempNode;
	if(top==NULL)               //栈
    return y ;
	else
	{
		TempNode=top;
		top=top->next;
		x=TempNode->arc;
		delete TempNode;
		return x;
		
	}
}//pop

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

 
int  IsAlphabet(char a)
{  
	if(('0'<=a && a<='9') || ('a'<=a && a<='z') || ('A'<=a && a<='Z'))
	{ 
		for(int i=1;i<=CharQuantity;i++)
		{
		if(AllChar[i]==a)
	        i=CharQuantity+1;
		}
	 if(i==CharQuantity+1)
	 {
	  AllChar[CharQuantity]=a;
	  CharQuantity++;         //接收字符个数，e除外 */
	 }

		
	 return 1;}
   else return 0;
}

char GetNextCh(int size)
{
	if(linepos<size)	
	   return string[linepos++];
	else return NULL;
}
/////////////////////////////////////////////////////////////////////
void Isnull(int ftn,int x ,int y,char z)
			
{  	
	Node *p,*p2; 
	p2=p=FirstTable[ftn];
	 while(p!=NULL)
	 {	 p2=p;
		 p=p->Next;
	 }
		Node* temp=new Node;
		temp->NeighborNode=x;
		temp->ConvertChar=z;
		temp->Next=NULL;
		temp->NodeState=y;
		p=temp;
		if(NULL==FirstTable[ftn])
			FirstTable[ftn]=p;
		else p2->Next=p;
 }

void RegularToNFA()
{
  int k=1,T=1,ST0=1,q=0;int ST1;
  char a;char sym; Stack sk;
  stArc s,arc;

  int size;
	size=strlen(string);
  a=GetNextCh(size);
  while(a!='#')
  {
     if(IsAlphabet(a))
	 {
		 sym=GetNextCh(size);
	 if (sym=='*')
	 {   Isnull(T,k+1,0,'@');
	 
		 Isnull(k+1,k+1,0,a);
		  
		 Isnull(k+1,k+2,0,'@') ;
		  
//		    cout<<"from:"<<T<<"-->"<<k+1<<"∈"<<endl;
//	        cout<<"from:"<<k+1<<"-->"<<k+1<<a<<endl; 
//	       cout<<"from:"<<k+1<<"-->"<<k+2<<"∈"<<endl; 
	  
    k+=2; T=k;
   a=GetNextCh(size);
        }
		else
		{    
			Isnull(T,k+1,0,a);
//			 cout<<"from:"<<T<<"-->"<<k+1<<a<<endl; 
	     
		   k=k+1;T=k;
		   a=sym;
         }
	 }
    switch(a)
	{ 
	   case '|':
	     {
			 if(q==0)
		    {
			 ST1=T;T=ST0;q=1;
			 }
			else
			{   Isnull(T,ST1,0,'@') ;
//				cout<<"from:"<<T<<"-->"<<ST1<<"∈"<<endl; 
				
			T=ST0;
			
			}
         a=GetNextCh(size);
         break;
		 }//case
		case'(':
		   {
			arc.ST0=ST0;arc.ST1=ST1;arc.q=q;sk.Push(arc);
			Isnull(T,k+1,0,'@') ;
//			cout<<"from:"<<T<<"-->"<<k+1<<"∈"<<endl; 
		   
			k=k+1;T=k;
			ST0=k;q=0;
			a=GetNextCh(size);  
			break;
			}//
			
		case ')':
		  {
		    if(q=1){Isnull(T,ST1,0,'@') ;
//				    cout<<"from:"<<T<<"-->"<<ST1<<"∈"<<endl; 
			         
				   T=ST1;
				   }
				   sym=GetNextCh(size);
			if(sym!='*')a=sym;
			else
			{    Isnull(T,ST0,0,'@') ;
			     Isnull(ST0,k+1,0,'@') ; 
//				cout<<"from:"<<T<<"-->"<<ST0<<"∈"<<endl; 
//			  cout<<"from:"<<ST0<<"-->"<<k+1<<"∈"<<endl; 
			  
			   k=k+1;T=k;
			   a=GetNextCh(size);
			   }
			 s=sk.Pop();
			ST0=s.ST0;   ST1=s.ST1;q=s.q;  		
			}//case
         }//switch
  }//while

      if(q==1)
	  {   Isnull(T,ST1,0,'@') ;
//		  cout<<"from:"<<T<<"-->"<<ST1<<"∈"<<endl; 
		 
		 T=ST1;
		 }
	  CharQuantity=CharQuantity-1;//接收字符个数，e除外 
	  FirstNodeQuantity=k;//邻接表行数
	  Node* L=new Node;
	  L->NeighborNode=1;
	  L->NodeState=-1;
	  L->ConvertChar='@';
	  L->Next=NULL;
	  FirstTable[0]=L;//	 FirstTable[L] 为始点
	  
	Node *pc;            //查终态结点
	for(int i=1;i<=FirstNodeQuantity;i++)
	{
		pc=FirstTable[i];	
		while(pc!=NULL)
		{   if (pc->NeighborNode==T)
			pc->NodeState=1;
			pc=pc->Next;
		}
	}

	 // cout<<CharQuantity<<endl;
  }//end

//从正则到NFA完**************************************************************************



//从NFA到DFA********************************************************************
/*/////////////////////////////////////////////////
 流程构思：
	A. 扫描得到第一个集；
   B. 从AllChar[20]中取第一值附给char x ，分别取出第一个集中的各元素扫描其列上
      是否有通过x的结点，有的话，调用ScanForAGroup(int ScanStartNode);
      如果第一个集中同时有两个或两个以上的元素拥有通过x的结点，则还必须合并各自
      ScanForAGroup()得出的集。
   C. 保存上面B中得到的最终的集。
   D. 再从AllChar[20]中取第二个值附给x，重复做B和C  ，...依次类推，直到AllChar
      中所有元素用完。
      至此，将得到第一个集通过AllChar的所有新集。
   E. 再取出第二个集，按刚才对第一个集的操作一样，获得第二个集通过AllChar的所有
      新集。 ...依次类推，直到所有无法获得新的集为止。（注：新的集是指该集中个
      元素跟已有的所有集不完全一样，这里需要一个算法来确认这一点）
   F. 至此，所有集都出来了，将每一个集都看过一个结点，填充ThirdTable。

 *////////////////////////////////////////////

#include <iostream.h>
#include <stdio.h>
#include "assistant.h"

//本程序给出的公用接口：
	Node* SecondTable[100];
   int SecondNodeQuantity;


//本程序要用到的公用接口：
/*	Node* FirstTable[100];
   int FirstNodeQuantity;
   char AllChar[20];   //接收到哪些字符
	int CharQuantity;   //接收字符个数，e除外
*/
//本程序自己用的全局数据结构：
	int NodeGroup[20][20];   //比如说：NodeGroup[2]={6,1,2,3,5,8,9}
	int curGroupNum=0;

   int GroupRelate[20][3];
	int curRelateNum=0;

   int TempGroup[2][40];
	int curTempNum=-1;

   TempStack ObjStack;


/////////////////本程序自己用的数据结构的说明：//////////////////

/*
//用 NodeGroup[20][20] 表示扫描过程中得到的集，第一元表示第几集，第二元
// 							表示该集的信息，第二元中的0号表示该集中有多少个元素
int NodeGroup[20][20];   //比如说：NodeGroup[2]={6,1,2,3,5,8,9}
int curGroupNum=0;       // 规定：NodeGroup[0] 不保存数据
								//curGroupNum指向的是当前已有的集，
                        //如果想加一新集，curGroupNum必须先加 1 ；

///////////
定义另一个结构，GroupRelate[20][3]  可以辅助解决问题3
					从[i][1]开始用，
					在该结构中，[i][0]存放source Group 在NodeGroup中的位置
               				[i][1]存放联系字符char 在AllChar中的位置
                           [i][2]存放finish Group 在NodeGroup中的位置
           还有curRelateNum=0 表示之前已经又多少联系
int GroupRelate[20][3];
int curRelateNum=0;

//////////////////////
//定义一个空间来保存临时的Group，如果确定临时Group真的为新的，则再将其加入到
//NodeGroup中
int TempGroup[2][40];
int curTempNum=-1;


//int ThirdNodeQuantity;   //第三个表的结点数量

//定义一个栈实例：
TempStack ObjStack;
*/
//////////////////////////////////////////////////////////////////////

void PrintConvertTable(CDC* pDC)
{
   ASSERT(pDC != NULL);
   int startx=0,starty=0;
   int x=startx,y=starty;
   int intervaly=30;
   int intervalx=20;
   CString str;

   int i,j,k,curOut,p;
 //  Node *pCurrent;
   int distance=12;
   for(i=1;i<=CharQuantity;i++)
   {
	str.Format("%c",AllChar[i]);
	pDC->TextOut(200*i,y,str);  
	//cout<<AllChar[i];
   }
   for(i=1;i<=SecondNodeQuantity;i++)
   {
	  y += intervaly;
	  x=startx;
	  pDC->TextOut(x,y,"{",1);
      //cout<<endl<<"{";
      for(j=1;j<=NodeGroup[i][0];j++)
      {
		  x += intervalx;
		  str.Format("%d",NodeGroup[i][j]);
      	  pDC->TextOut(x,y,str);
		//  cout<<NodeGroup[i][j]<<",";
      }
	  x += intervalx;
      pDC->TextOut(x,y,"}",1);     //cout<<"}";
      for(p=distance*k+NodeGroup[i][0]*2;p<=distance*(k+1);p++)
	  {
		  x += intervalx;
		  pDC->TextOut(x,y," ",1);           //cout<<" ";
	  }

      //扫描 RelateGroup中首项为[0]为 i 的 所有项，得到 对于的 NodeGroup[2]

      for(j=1;j<=curRelateNum;j++)
      {
      	if(GroupRelate[j][0]==i)
         {
         	curOut=GroupRelate[j][2];
            k=GroupRelate[j][1];

            if(curOut>j)
            {
            	//	输出在 k*20的位置
				x += intervalx;
            	pDC->TextOut(x,y,"{",1); //cout<<"{ ";