regularview.cpp

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

      	   	for(p=1;p<=NodeGroup[curOut][0];p++)
      			{
					x +=intervalx;
					str.Format("%d,",NodeGroup[curOut][p]);
					pDC->TextOut(x,y,str);
            		//cout<<NodeGroup[curOut][p]<<",";
      			}

			    x+=intervalx;
				pDC->TextOut(x,y,"}",1);//		cout<<" }";
               for(p=distance*k+NodeGroup[curOut][0]*2+4;p<=distance*(k+1);p++)
			   {
				  x+=intervalx;
				  pDC->TextOut(x,y," ",1);  // cout<<" ";
			   }
            }

         }
      }
      //现在已经输出完一行
   }

}



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;
}


//从NFA到DFA完*******************************************************************


/////////////////////////////////////////////////////////////////////////////
// CRegularView

IMPLEMENT_DYNCREATE(CRegularView, CView)

BEGIN_MESSAGE_MAP(CRegularView, CView)
	//{{AFX_MSG_MAP(CRegularView)
	ON_COMMAND(ID_DRAW, OnDrawNFA)
	ON_COMMAND(ID_INPUT_EXPRESSION, OnInputExpression)
	ON_COMMAND(ID_DRAW_DFA, OnDrawDfa)
	ON_COMMAND(ID_DRAW_TABLE, OnDrawTable)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CRegularView construction/destruction

CRegularView::CRegularView()
{

}

CRegularView::~CRegularView()
{
}