nfa_dfa.cpp

编译原理---正则表达式到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;


//本程序要用到的公用接口：
extern	  Node* FirstTable[100];
extern    int FirstNodeQuantity;
extern    char AllChar[20];   //接收到哪些字符
extern    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 NFA_DFA()
{
   int i;


	ScanForAGroup(1);   //扫描得到第一个集。
    OpTempGroup( );   //对先保存在 TempGroup 中的集进行处理
    for(i=1;i<=curGroupNum;i++)  //注意：这里curGroupNum是动态的
   {                            //在for里面的操作中curGroupNum可能会增加。
  		SearchNewGroups(i);
   }

   //填充SecondTable
   FillSecondTable();

}


//返回一个集作为SecondTable状态点的状态：即是初始结点，中间结点，还是终止结点
int GetNodeState(int wishGroup)
{
   int i;
   int state=0;
   for(i=1;i<=NodeGroup[wishGroup][0];i++)
   {
   	if(NodeGroup[wishGroup][i]==FirstNodeQuantity)
      	return 1;
      if(NodeGroup[wishGroup][i]==1)
      	state=-1;
   }
   return state;
}


/////////////////////////
/*逐一填写SecondTable的每一行。
比如说：填第一行，即填写与NodeGroup中的第一个集的临接集，扫描GroupRelate[20][3]表
			中GroupRelate[i][0]=1 的关系，其对于的集就是必须填在第一行中的。
*/
void FillSecondTable()
{
   int i,j,flag;
   Node* pCurrent,* temp;

   //设置secondNodeQuantity 的值
	SecondNodeQuantity=curGroupNum;

   //初始化SecondTable
   for(i=1;i<=SecondNodeQuantity+1;i++)
   	SecondTable[i]=NULL;

   //在SecondTable[0]行中保存第一个状态的信息
   temp=new Node;
   temp->NeighborNode=1;
   temp->ConvertChar='@';
   temp->NodeState=GetNodeState(1);
   temp->Next=NULL;
   SecondTable[0]=temp;
  
   for(i=1;i<=SecondNodeQuantity;i++)
   {
      flag=0;
   	//SecondTable[i]=pCurrent;
   	for(j=1;j<=curRelateNum;j++)
      {
         if(GroupRelate[j][0]==i)
         {
         	flag++;
         	temp=new Node;
            temp->NeighborNode=GroupRelate[j][2];
            temp->ConvertChar=AllChar[(GroupRelate[j][1])];
            temp->NodeState=GetNodeState(temp->NeighborNode);
            temp->Next=NULL;

            if(flag==1)
             	SecondTable[i]=temp;
            else
            	pCurrent->Next=temp;

            pCurrent=temp;
         }
      }
   }

}

///////////////
//合并两个集的函数：
void CombineGroups()
{
	int i=1;
   int j=1;
   int Temp[30];
   int k=0;
   while(i>TempGroup[0][0]||j>TempGroup[1][0])
   {
   	if(TempGroup[0][i]<=TempGroup[1][j])
      {
         k++;
      	Temp[k]=TempGroup[0][i];
         if(TempGroup[0][i]==TempGroup[1][j])
         	j++;

         i++;
      }
      else
      {
         k++;
      	Temp[k]=TempGroup[1][j];
         j++;
      }
   }
  	while(i<=TempGroup[0][0])  // TempGroup[0] 中还有数的话，继续搬到 Temp 中
   {
      k++;
     	Temp[k]=TempGroup[0][i];
      i++;
   }
   while(j<=TempGroup[1][0])     // TempGroup[1] 中还有数的话，继续搬到 Temp 中
   {
    	k++;
     	Temp[k]=TempGroup[1][j];
      j++;
   }
   Temp[0]=k;
   for(i=0;i<=Temp[0];i++)           //将数据重新搬回到TempGroup【0】中
   	TempGroup[0][i]=Temp[i];

   TempGroup[curTempNum][0]=0;
   curTempNum=0;                     //置TempNum=0; 即合并后少了一集
};


//扫描程序开始：  这是通过e的
//扫描程序的作用是：从当前的状态结点开始（ScanStartNode），扫描通过一个或者
   //多个E可以到达的所有状态,将他们归为一个集
   //得到的临时集将放在 TempGroup中

void ScanForAGroup(int ScanStartNode)     //  应该可以在这里找出集的状态，但是这里生成的只是
{                                           //    临时的Group，是在这里吗？？？
   int i,temp;                              //    是不是用一个返回值来表征
   curTempNum++;
	TempGroup[curTempNum][0]=1;
   TempGroup[curTempNum][1]=ScanStartNode;

   Node* ScanCurrentNode;
	while(1)
   {
   	ScanCurrentNode=FirstTable[ScanStartNode];

      //出现问题：这里ScanCurrentNode=NULL
  		while(ScanCurrentNode!=NULL)     //扫描当前列，将为e的压入栈
   	{
   		if(ScanCurrentNode->ConvertChar=='@')
      	{
      		ObjStack.push(ScanCurrentNode->NeighborNode);
  //          cout<<"Stack push: "<<ObjStack.NodeStack[ObjStack.TopNode]<<endl;

      	}

      	ScanCurrentNode=ScanCurrentNode->Next;
   	}

      if(ObjStack.IsEmpty())   //如果是因为栈空而退出 while(!ObjStack.IsEmpty())
     		break;                //则也跳出 while(1)循环

   	while(!ObjStack.IsEmpty())
   	{
   		temp=ObjStack.pop();
   //      cout<<"Stack pop: "<<temp<<endl;

      	//注意：这里检查弹出的状态结点在之前是否已经有了，
      	// 			也就是说，是否出现了重复
       //	需要这样吗？
      	for(i=1;i<=TempGroup[curTempNum][0];i++)
      	{
         	if(temp==TempGroup[curTempNum][i])
       			break;
     		}

      	if(i>TempGroup[curTempNum][0])      //将状态号加入到TempGroup中
      	{
         	TempGroup[curTempNum][0]++;
         	i=TempGroup[curTempNum][0];
         	TempGroup[curTempNum][i]=temp;
    //        cout<<"Add "<<temp<<" in TempGroup"<<endl;

            ScanStartNode=temp;
         	break;    //跳出 while(!ObjStack.IsEmpty()) 循环
            			//它会进入while(1)，也就是会重新扫描新的一行
      	}
   	}
   }

}

//注：栈的类型是否只要 int 就行了，而不用 Node×，或者是根本就不能用Node* ???

//扫描程序结束！


////////////////////
//一个集通过AllChar各元素获得新集：       这是通过char的
void SearchNewGroups(int curSourceGroup)  //curSouceGroup标志当前是对 NodeGroup
            											//这那一集进行操作
{
	int i,j,k;
   char curConvertChar;
   for(i=1;i<=CharQuantity;i++) //CharQuantity 林景灼给出的字符个数
   {
      curConvertChar=AllChar[i];
      k=SearchOneGroup(curSourceGroup,curConvertChar); //获取通过当前字符得到的新集
      if(k)
      {
      	j=OpTempGroup();

      	//在这里建立 集之间的关系！！！
      	curRelateNum++;
      	GroupRelate[curRelateNum][0]=curSourceGroup;
      	GroupRelate[curRelateNum][1]=i;
      	GroupRelate[curRelateNum][2]=j;
      }

   }
}

/////////////////////
//获取当前集通过当前字符得到的新集：

//现在是第一集通过'a'的扫描，结果是错误的多了一个10
int SearchOneGroup(int curSourceGroup,char curConvertChar)  // 这是通过char的
{
	int i,k,flag=0;
   Node* Temp;
   for(i=1;i<=NodeGroup[curSourceGroup][0];i++)
   {
      k=NodeGroup[curSourceGroup][i];  //取出当前集的第 i 个元素进行扫描
      											//则 k 为结点状态号
      Temp=FirstTable[k];
 
      if(Temp==NULL)
      	continue;           //这里曾经用了 return 0，导致错误
   	while(Temp!=NULL)
      {

      	if(Temp->ConvertChar==curConvertChar)
         {
           ScanForAGroup(Temp->NeighborNode); //扫描得到新组
           flag++;
         }

         if(curTempNum==1)
         {
           	CombineGroups(); //合并刚生成的两个集；
         }

         Temp=Temp->Next;
      }
   }
   return flag;
}

/////////////////////
/*处理一个临时集，为新集的话则加入到NodeGroup中：
重新定义返回值，返回临时集在NodeGroup中的位置 i。
	如果i<=curGroupNum,说明临时集不是新集，
   如果i>curGroupNum，说明其为新集。                 */
int OpTempGroup( )          //返回 1 时 ，表示临时集有效
{                                         //已经将其加入到NodeGroup中
   int i;
	SortAGroup();
   i=IsNewGroup( );               //否则，返回 0
   if(i==curGroupNum+1)
   {
     JointANewGroup( );
   }
   else
   	curTempNum=-1;

   return i;
}

///////////////////
//对一个集进行排序
void SortAGroup( )            //用冒泡排序
{
	int i,j,temp,flag;
   for(i=1;i<TempGroup[curTempNum][0];i++)
   {
   	flag=1;
      for(j=1;j<=TempGroup[curTempNum][0]-i;j++)
      {
      	if(TempGroup[curTempNum][j]>TempGroup[curTempNum][j+1])
         {
         	flag=0;
            temp=TempGroup[curTempNum][j];
            TempGroup[curTempNum][j]=TempGroup[curTempNum][j+1];
            TempGroup[curTempNum][j+1]=temp;
         }
      }
      if(flag)
      	break;
   }
}


/////////////////////
//定义返回值，返回临时集在NodeGroup中的位置 i。
//	如果i<=curGroupNum,说明临时集不是新集，
//   如果i>curGroupNum，说明其为新集。
int IsNewGroup( )
{
	int i,j;
   for(i=1;i<=curGroupNum;i++)      //只要有一集相同就可以退出，返回 0
   {
   	if(NodeGroup[i][0]==TempGroup[curTempNum][0])   //先判断元素个数是否相等，相等才处理
      {
      	for(j=1;j<=TempGroup[curTempNum][0];j++)
         {
         	if(NodeGroup[i][j]!=TempGroup[curTempNum][j])      //发现有不同元素，就跳出循环
            	break;
         }
         if(j>TempGroup[curTempNum][0])     //如果 if 成立的话，说明刚才
         	return i;                      //NodeGroup[i]与TempGroup[curTempNum]一样
      }
   }
   return curGroupNum+1;
}

/////////////////
//将一个临时集加入NodeGroup中
void JointANewGroup( )
{
   int i;
	curGroupNum++;
   for(i=0;i<=TempGroup[curTempNum][0];i++)
   	NodeGroup[curGroupNum][i]=TempGroup[curTempNum][i];

   TempGroup[curTempNum][0]=0;
   curTempNum=-1;

}



//////////////////////////////////
//栈的实现
TempStack::TempStack()
{
	MaxNum=20;
   TopNode=-1;
}

TempStack::~TempStack()
{
//Empty Now
}

int TempStack::push(int wishNode)
{
	if(TopNode==MaxNum-1)
   	return 0;

   TopNode++;
   NodeStack[TopNode]=wishNode;
   return 1;
}

int TempStack::pop( )
{
    if(TopNode==-1)
    	return 0;

    int temp;
    temp=NodeStack[TopNode];
    TopNode--;
    return temp;
}

int TempStack::IsEmpty()
{
	if(TopNode==-1)
   	return 1;

   return 0;
}