tonfadoc.cpp

正规(则)表达式转化为NFA

// TONFADoc.cpp : implementation of the CTONFADoc class
//

#include "stdafx.h"
#include "TONFA.h"

#include "TONFADoc.h"
#include "MainFrm.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CTONFADoc

IMPLEMENT_DYNCREATE(CTONFADoc, CDocument)

BEGIN_MESSAGE_MAP(CTONFADoc, CDocument)
	//{{AFX_MSG_MAP(CTONFADoc)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTONFADoc construction/destruction

CTONFADoc::CTONFADoc()
{
	// TODO: add one-time construction code here
	redraw=false;
	m_Title=_T("");
	//for(int j=0;j<100;j++)
	//	DA[j]=NULL;
}

CTONFADoc::~CTONFADoc()
{	
	//for(int h=0;h<100;h++)
		//DA[h]->ClearList();
	m_flag=-1;
}

BOOL CTONFADoc::OnNewDocument()
{
	if (!CDocument::OnNewDocument())
		return FALSE;

	// TODO: add reinitialization code here
	// (SDI documents will reuse this document)

	return TRUE;
}



/////////////////////////////////////////////////////////////////////////////
// CTONFADoc serialization

void CTONFADoc::Serialize(CArchive& ar)
{
	POSITION pos=GetFirstViewPosition();
	CTONFAView* pView =(CTONFAView *)(GetNextView(pos));
	if (ar.IsStoring())
	{
		// TODO: add storing code here
		ar<<m_Title<<m_flag;//<<pView->flag;
	}
	else
	{
		// TODO: add loading code here
		ar>>m_Title>>m_flag;//>>pView->flag;
		if(m_flag>=0)
		{
			pView->SetNFAPos.num=ExpToNfa();
			pView->flag=0;
			pView->m_TBarNFA=true;
		    if(m_flag>=1){
				pView->flag=1;//
				pView->SetDFAPos.num=NfaToDfa();
				pView->m_TBarTABLE=true;
				pView->m_TBarDFA=true;	
					if(m_flag==2){
					pView->SetMINPos.num=DfaToMin();
					pView->flag=2;
					pView->m_TBarNFA=true;
					pView->m_TBarMINTABLE=true;
					pView->m_TBarMINDFA=true;
					pView->m_TBarTABLE=false;
					pView->m_TBarDFA=false;
					}
				}			//pView->Invalidate(TRUE);
		}
		pView->Invalidate(TRUE);
	}
}

/////////////////////////////////////////////////////////////////////////////
// CTONFADoc diagnostics

#ifdef _DEBUG
void CTONFADoc::AssertValid() const
{
	CDocument::AssertValid();
}

void CTONFADoc::Dump(CDumpContext& dc) const
{
	CDocument::Dump(dc);
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CTONFADoc commands
void CTONFADoc::DeleteContents()
{

//	CTONFAApp *pApp=(CTONFAApp *)AfxGetApp();
//	pApp->pView->flag=-1;
//	pApp->pView->Invalidate(TRUE);
//	CMainFrame *pFrame = (CMainFrame *)(AfxGetApp()->m_pMainWnd);
	//CStatusBar *pStatus =&pFrame->m_wndStatusBar;
//	CMyDlgBar *pDlg=&pFrame->m_wndDlgBar;	
//	pDlg->m_CmdValue=_T("");
//	pDlg->UpdateData(FALSE);
//	AfxMessageBox("");
}
int CTONFADoc::ExpToNfa()
{
	if(CheckExp()){
	int i;
	int temp1,temp2,temp3;
	int k=0;
	t=0;
	int q=0;
	int ST0=0;
	int ST1;
	char sym,a;
	//StateTable NFATable;
	NFATable.ClearTable();
	LPTSTR str=m_Title.GetBufferSetLength(m_Title.GetLength());
//	char str[128];
//	cin>>str;
	a=str[0]; 
	for(i=0;str[i]!='#'&&i<m_Title.GetLength();)
	{
		while((a>=65&&a<=90)||(a>=97&&a<=122)||(a>=48&&a<=57))
		{	
			sym=str[++i];
			if(sym=='*')
			{
				NFATable.Insert(t,k+1,'$');
				NFATable.Insert(k+1,k+1,a);
				NFATable.Insert(k+1,k+2,'$');
			    k=k+2;
			    t=k;
			    a=str[++i];
			}
			else
			{
		    NFATable.Insert(t,k+1,a);
		    k=k+1;
		    t=k;
		    a=sym;
			}
		}
		while(a=='|')
		{
			if(q==0)
			{
				ST1=t;
				q=1;
				t=ST0;
				a=str[++i];
			}
			else
			{
				NFATable.Insert(t,ST1,'$');
				t=ST0;
				a=str[++i];
			}
		}
		while(a=='(')
		{
			temp1=ST0;
			temp2=ST1;
			temp3=q;
			NFATable.Insert(t,k+1,'$');
			k=k+1;
			t=k;
			ST0=k;
			q=0;
			a=str[++i];
		}
		while(a==')')
		{
			if(q==1)
			{
				NFATable.Insert(t,ST1,'$');
				t=ST1;
			}
			sym=str[++i];
			if(sym!='*')
				a=sym;
			else	
			{
				NFATable.Insert(t,ST0,'$');
				NFATable.Insert(ST0,k+1,'$');
				k=k+1;
				t=k;
				a=str[++i];
			}
			ST0=temp1;
			ST1=temp2;
			q=temp3;
		}
	}
	if(q==1)
	{
		NFATable.Insert(t,ST1,'$');
		t=ST1;
	}
//	CTONFADoc::NFATable=NFATable;
	return k;
	}
	return 0;//0说明有错
}

int CTONFADoc::CheckExp()
{
	if(m_Title=="")
	{
	//	AfxMessageBox("请输入正则表达式");
		redraw=false;
		return 0;
	}
	else
	{
		int i,j;
		int n=0;//正则表达式里的个数
		bool flag;
		bool flag1=false;
		
		LPTSTR str=m_Title.GetBufferSetLength(m_Title.GetLength());
		for(i=0;str[i]!=0;i++)//判断输入的正则表达式的正确性
		{
			if((str[i]<65||str[i]>90)&&(str[i]<97||str[i]>122)&&(str[i]<48||str[i]>57))
				if(str[i]!='#'&&str[i]!='('&&str[i]!=')'&&str[i]!='|'&&str[i]!='*')
				{
					//cout<<"error symbol: "<<str[i]<<endl;
					AfxMessageBox("请输入正确的表达式");
					redraw=false;
					flag1=true;
					break;
				}
		
			if((str[i]=='*'||str[i]=='|'||str[i]=='#')&&str[i]==str[i+1])
			{
			    //cout<<"expression warning: "<<str[i]<<str[i+1]<<endl;
				AfxMessageBox("请输入正确的表达式");
				redraw=false;
				flag1=true;
				break;
			}

			if((str[i+1]==0&&str[i]!='#')||(str[i]=='#'&&str[i+1]!=0))
			{
				//cout<<"enexpected ending"<<endl;
				AfxMessageBox("请输入结束符号'#'!!");
				redraw=false;
				flag1=true;
				break;
			}	
		}

		if(flag1==true)//正则表达式错译则退出
			return 0;
		else
		{
			for(i=0;str[i]!=0;i++) //正则表达式的排列字母和字母个数
			{
				flag=true;
			
				for(j=0;j<=n;j++)
				{
					if(str[i]==character[j])
						flag=false;
				}
			
				if(str[i]=='#')
					str[i+1]=0;
			
				if(flag==true&&str[i]!='#'&&((str[i]>=65&&str[i]<=90)||(str[i]>=97&&str[i]<=122)||(str[i]>=48&&str[i]<=57)))
					character[n++]=str[i];	
			}
			character[n]=0;
			letternum=n;
			return 1;
		}
	}
}

LinkList* CTONFADoc::Epsilon_Closure(LinkList *xList)
{
	Stack stack1;
	int nState;
	ListNode *p;
	p=xList->head;
	LinkList * yList;
	yList=new LinkList;
	
	//cout<<p->data<<endl;
	
	while(p!=NULL)
	{
		stack1.Push(p->data);
		yList->InsertTail(p->data);
		p=p->next;
	}
	while(!stack1.IsEmpty())
	{
		nState=stack1.Pop();
		
		//cout<<nState<<endl;
		
		ListNode * tempnode;
		tempnode=NFATable.tableList[nState].next;

		//cout<<tempnode->token<<endl;
		//cout<<tempnode->data<<endl;

		while(tempnode!=NULL)
		{
			if(tempnode->token=='$')
			{
				p=yList->head;
				while(p!=NULL)
				{
					if(tempnode->data==p->data)
						break;
					p=p->next;
				}
				if(p==NULL)//t不属于y
				{
					stack1.Push(tempnode->data);
					yList->InsertTail(tempnode->data);
				}
			}
			tempnode=tempnode->next;
		}
	}//while(!stack1.IsEmpty())
	return yList;
}

LinkList* CTONFADoc::Closure(LinkList *xList, char a)
{
	LinkList * R;
	R=new LinkList;
	int nCurrentState;
	ListNode * tempnode;
	ListNode * p;
	p=xList->head;
	while(p!=NULL)
	{
		nCurrentState=p->data;
		
		//cout<<nCurrentState<<endl;
		
		
		tempnode=NFATable.tableList[nCurrentState].next;
		while(tempnode!=NULL)
		{
			//if(tempnode->token=='$')
				//xList->InsertTail(tempnode->data);
			//else
			//{
				if(tempnode->token==a)
					R->InsertTail(tempnode->data);
			//}
			tempnode=tempnode->next;
		}
		p=p->next;
	}
	LinkList * yList;
	if(R->head==NULL)
		yList=NULL;
	else
		yList=Epsilon_Closure(R);
	delete R;
	return yList;
}

void CTONFADoc::Sort(LinkList *a)
{
	int k;
	ListNode *p,*q,*temp;
	p=a->head;
	q=p->next;
	while(q!=NULL)
	{
		temp=p;
		while(q!=NULL)
		{
			if(q->data<temp->data)
				temp=q;
			q=q->next;
		}
		if(temp!=p)
		{
			k=p->data;
			p->data=temp->data;
			temp->data=k;
		}
		p=p->next;
		q=p->next;
	}
}

int CTONFADoc::IsEqual(LinkList *a, LinkList *b)
{
	ListNode *p,*q;
	Sort(a);
	Sort(b);
	p=a->head;
	q=b->head;
	while(p!=NULL&&q!=NULL)
	{
		if(p->data!=q->data)
			return 0;
		p=p->next;
		q=q->next;
	}
	if(p==NULL&&q==NULL)
		return 1;
	else
		return 0;
}

int CTONFADoc::NfaToDfa()
{
	DFATable.ClearTable();
	MINTable.ClearTable();
	LinkList * xList;//x集合，用一个链表表示
	LinkList * yList;//y集合，用一个链表表示
	//LinkList * zList;//z集合，是终结状态集合，用一个链表表示
	//LinkList * DA[100];//链表指针数组，表示状态集表
//	for(int mm=0;t<100;t++);
//		DA[mm]->ClearList();
    zList.ClearList();
	ListNode * p;
	int i=0,j,n=0,r;

	xList=new LinkList;
	//zList=new LinkList;
	xList->InsertTail(0);
	
	//cout<<xList->head->data<<endl;
	
	yList=Epsilon_Closure(xList);
	
	//cout<<yList->head->data<<endl;	
	
	DA[0]=yList;
	p=yList->head;
	while(p!=NULL)
	{
		if(p->data==t)
		zList.InsertTail(0);//若y中含有终结状态则将N送进zList中
		p=p->next;
	}
	/*p=DA[0]->head;
	while(p!=NULL)
	{
		cout<<p->data<<endl;//x=DA[i]
		p=p->next;
	}*/
	
	while(i<=n)
	{
//////////////////////////////////////////////////////////		
		xList->ClearList();
		p=DA[i]->head;
		while(p!=NULL)
		{
			xList->InsertTail(p->data);//x=DA[i]
			p=p->next;
		}
////////////////////////////////////////////////////////////
		
		//
		
		for(r=0;character[r]!=0;r++)
		{
			//cout<<"jkdlfjl"<<endl;

			yList=Closure(xList,character[r]);
			
			//cout<<"gjhjg"<<yList->head->data<<endl;

			if(yList!=NULL)
			{
				j=0; 
				while(j<=n)
				{
					if(!IsEqual(yList,DA[j]))
						j++;
					else
					{
						DFATable.Insert(i,j,character[r]);
						MINTable.Insert(i,j,character[r]);
						break;
					}
				}
				if(j==n+1)
				{
					n++;
//////////////////////////////////////////////////////////////////////
					DA[n]=yList;
					p=yList->head;
					while(p!=NULL)
					{
						if(p->data==t)
							zList.InsertTail(n);//若y中含有终结状态则将N送进zList中
						p=p->next;
					}
//////////////////////////////////////////////////////////////////////
					DFATable.Insert(i,n,character[r]);
					MINTable.Insert(i,j,character[r]);
				}
			}//if(yList->head!=NULL)
			else
			{
				DFATable.Insert(i,-1,character[r]);
				//MINTable.Insert(i,j,character[r]);
				MINTable.Insert(i,-1,character[r]);
			}
			//	DFATable.Insert(i,'$',character[r]);
		}//for
		i++;
	}//while
	delete xList;
	//delete zList;

	return n;
}

CString CTONFADoc::ListStr(int data)
{
		
	ListNode *p;
	p=DA[data]->head;
	CString tempStr="{";
	CString temp="";
	while(p!=NULL)
	{	
		if(p->next!=NULL)
		temp.Format("%d,",p->data);
		else
		temp.Format("%d}",p->data);
		tempStr+=temp;
		p=p->next;
	}
	return tempStr;
}

CString CTONFADoc::ListStrMIN(int data)
{
		
	ListNode *p;
	p=MA[data]->head;
	//if(p==NULL)
		//return _T("");
	CString tempStr="{";
	CString temp="";
	while(p!=NULL)
	{	
		if(p->next!=NULL)
		temp.Format("%d,",p->data);
		else
		temp.Format("%d}",p->data);
		tempStr+=temp;
		p=p->next;
	}
	return tempStr;
}

int CTONFADoc::DfaToMin()
{
		int i;
		int j;
		int flag4=0;
        int n=0;
		bool flag3=true;
	    ListNode * q,* k,* p;		
		//
		LinkList * yList;
		ListNode * m;
	    ListNode * tt;
		int a[TABNUM];
		int b[TABNUM];
		for(i=0;i<TABNUM;i++)
		{
			a[i]=100;
			b[i]=100;
		}
		for(j=0;j<100;j++)
			MA[j]=NULL;		
 	    for(i=0;i<TABNUM;i++)
		{
			yList=new LinkList;
			for(j=0;j<TABNUM;j++)
			{	
				
				p=MINTable.tableList[i].next;
				q=MINTable.tableList[j].next;
				while((p!=NULL)&&(q!=NULL))
				{
					if((p->data!=q->data)||(p->token!=q->token)||(i==j))
						flag3=false;
					p=p->next;
					q=q->next;
					
				}
				if((flag3==true)&&(MINTable.tableList[i].next!=NULL)&&(MINTable.tableList[j].next))
				{
						tt=DA[i]->head;
						m=DA[j]->head;
						while(m!=NULL)
						{
							k=yList->head;
							while(k!=NULL)
							{
								if(k->data==m->data)
									break;
								k=k->next;
							}
							if(k==NULL)
								yList->InsertTail(m->data);
							m=m->next;
						}
					MINTable.tableList[j].next=NULL;
					flag4=j;
				}

				flag3=true;
			}
			if((MINTable.tableList[i].next!=NULL)||(flag4==i))
			{
				//ListNode * s=yList->head;
			    //ListNode * l=yList->head;
				//10|(01|1)*0|1*#
				if(MINTable.tableList[i].next!=NULL)
				{
				tt=DA[i]->head;
                
				while(tt!=NULL)
				{//(a|b)b*#
                    k=yList->head;
					while(k!=NULL)
					{
						if(k->data==tt->data)
							break;
						k=k->next;
					}
					if(k==NULL)
						yList->InsertTail(tt->data);
					tt=tt->next;
				}
				
			


		        Sort(yList);
				}
				MA[n]=yList;
				p=yList->head;
				while(p!=NULL)
				{
					if(p->data==t)
						zzList.InsertTail(n);//若y中含有终结状态t则将N送进zList中
					p=p->next;
				}
				n++;
			}

		}
	    
		j=0;
		//cout<<"MA表:"<<endl;
		for(int h=0;h<=n-1;h++)
		{
			p=MA[h]->head;
		    //cout<<h<<",";
		    while(p!=NULL)
			{
				a[j]=p->data;
				b[j++]=h;
				//cout<<p->data<<",";
				p=p->next;
			}
			j++;
		    //cout<<endl;
		    //MA[h]->ClearList();
		}
        //cout<<endl;
		
		//cout<<"MINDFA表:"<<endl;
		for(i=0;i<TABNUM;i++)
		{
			//cout<<i<<",";
			p=MINTable.tableList[i].next;
			while(p!=NULL)
			{
				j=0;
				while((a[j]!=p->data)&&(j<=TABNUM-1))
					j++;
				if(j!=TABNUM)
					p->data=b[j];
				//cout<<p->data<<","<<p->token<<",";
				p=p->next;
			}
			//cout<<endl;
		}
        //cout<<endl;
		
	return n-1;
}