main.cpp

此程序可以把编译原理中的不确定的有限自动机确定化

#include <windows.h>
#include <commctrl.h>
#include "resource.h"
#include "Machine.h"

#define  IsDigit(ch)   (ch >= '0' && ch <= '9')

BOOL CALLBACK AddRuleDlgProc(HWND,UINT,WPARAM,LPARAM);
BOOL CALLBACK MainDlgProc(HWND,UINT,WPARAM,LPARAM);

void InitRuleList(HWND);
void InsertRule(HWND,RULE_PARAM);
int  GetNextNumber(TCHAR**);

void CreateMachine(HWND);
void UpdateTransTable(HWND);
void UpdateTransResult(HWND);

HWND hAddDlg = NULL;
static FiniteAutomata  Machine;
static TABLE           TransTable;

int WINAPI WinMain(HINSTANCE hInst,HINSTANCE hPrev,LPSTR lpCmdLine,int nShowCmd)
{
	HWND hMain;
	MSG  msg;

	InitCommonControls();	
	hMain = CreateDialog(hInst,MAKEINTRESOURCE(IDD_MAINDLG),NULL,MainDlgProc);
	ShowWindow(hMain,SW_SHOW);

	while(GetMessage(&msg,NULL,0,0))
		if (!IsDialogMessage(hMain,&msg) && !IsDialogMessage(hAddDlg,&msg))
			DispatchMessage(&msg);

	return 0;
}

BOOL CALLBACK MainDlgProc(HWND hwnd,UINT msg,WPARAM wParam,LPARAM lParam)
{			
	switch(msg)
	{
	case WM_INITDIALOG:
		InitRuleList(GetDlgItem(hwnd,IDC_RULELIST));
		return FALSE;		
	case WM_COMMAND:
		if (LOWORD(wParam) == IDC_ADD)
		{	// 添加规则
			if (hAddDlg == NULL)
			{
				hAddDlg = CreateDialog(NULL,MAKEINTRESOURCE(IDD_DLG_ADDRULE),hwnd,AddRuleDlgProc);
				ShowWindow(hAddDlg,SW_SHOW);
			}
			SetFocus(hAddDlg);
		}		
		else if (LOWORD(wParam) == IDC_TRANS)
		{	// 转换成确定的有限自动机
			Machine.Reset();
			TransTable.Reset();

			CreateMachine(GetDlgItem(hwnd,IDC_RULELIST));			
			Machine.TransformToDFA(TransTable);

			UpdateTransTable(GetDlgItem(hwnd,IDC_TRANSLIST));
			UpdateTransResult(GetDlgItem(hwnd,IDC_DFALIST));			
		}
		else if (LOWORD(wParam) == IDC_DELALL)
		{	// 重新来过		
			Machine.Reset();
			TransTable.Reset();				
			
			InitRuleList(GetDlgItem(hwnd,IDC_RULELIST));			
			UpdateTransTable(GetDlgItem(hwnd,IDC_TRANSLIST));						
			UpdateTransResult(GetDlgItem(hwnd,IDC_DFALIST));			
		}
		return TRUE;
	
	case WM_ADDRULE: // 添加规则	
		InsertRule(GetDlgItem(hwnd,IDC_RULELIST),*((RULE_PARAM *)wParam));
		return TRUE;
	
	case WM_CLOSE:
		if (hAddDlg) DestroyWindow(hAddDlg);
		PostQuitMessage(0);
		EndDialog(hwnd,0);		
		return TRUE;
	}
	return FALSE;
}

void InitRuleList(HWND hList)
{	
	LVCOLUMN  colinfo;
	LVITEM    item;
	int       count;	
	HWND      hHead;	

	ListView_DeleteAllItems(hList);
	hHead = ListView_GetHeader(hList);
	count = Header_GetItemCount(hHead);
	if (count == 0)
	{	// 设置表头
		colinfo.mask = LVCF_FMT | LVCF_TEXT | LVCF_WIDTH;
		colinfo.fmt  = LVCFMT_CENTER;
		colinfo.cx   = 75;
		colinfo.pszText = TEXT("原状态");
		ListView_InsertColumn(hList,0,&colinfo);

		colinfo.cx   = 75;
		colinfo.pszText = TEXT("输入");
		ListView_InsertColumn(hList,1,&colinfo);

		colinfo.cx   = 75;
		colinfo.pszText = TEXT("新状态");
		ListView_InsertColumn(hList,2,&colinfo);
	}
	// 头两行
	item.mask     = LVIF_TEXT | LVIF_PARAM;
	item.iItem    = 0;
	item.iSubItem = 0;
	item.pszText  = TEXT("开始状态");
	item.lParam   = 0;
	ListView_InsertItem(hList,&item);

	item.mask     = LVIF_TEXT | LVIF_PARAM;
	item.iItem    = 1;
	item.iSubItem = 0;
	item.pszText  = TEXT("终止状态");
	item.lParam   = 0;
	ListView_InsertItem(hList,&item);
}

// 向列表 hList 添加一条规则 Rule
void InsertRule(HWND hList,RULE_PARAM param)
{
	int       num;
	LVITEM    item;
	TCHAR     szText[MAX_PATH];
	TCHAR     szTemp[MAX_PATH];

	num = ListView_GetItemCount(hList);
	// 添加转换规则
	if (param.Rule.oldstate >= 0 && param.Rule.newstate >= 0)
	{
		item.mask     = LVIF_TEXT;
		item.iItem    = num;
		item.iSubItem = 0;
		wsprintf(szText,TEXT("%d"),param.Rule.oldstate);
		item.pszText  = szText;		
		ListView_InsertItem(hList,&item);
		
		item.iSubItem = 1;
		if (param.Rule.input != 0)
			wsprintf(szText,TEXT("%c"),param.Rule.input);
		else
			wsprintf(szText,TEXT("NULL"));
		item.pszText  = szText;		
		ListView_SetItem(hList,&item);

		item.iSubItem = 2;
		wsprintf(szText,TEXT("%d"),param.Rule.newstate);
		item.pszText  = szText;		
		ListView_SetItem(hList,&item);
	}
	// 开始状态
	if (param.StartState >= 0)
	{
		item.mask     = LVIF_TEXT;
		item.iItem    = 0;
		item.iSubItem = 1;
		item.pszText  = szText;
		item.cchTextMax = MAX_PATH;
		ListView_GetItem(hList,&item);
		
		if (lstrlen(szText)==0)	wsprintf(szTemp,TEXT("%d"),param.StartState);
		else				    wsprintf(szTemp,TEXT(",%d"),param.StartState);
		lstrcat(szText,szTemp);			
		item.mask     = LVIF_TEXT;
		ListView_SetItem(hList,&item);		
	}
	// 结束状态
	if (param.EndState >= 0)
	{		
		item.mask     = LVIF_TEXT ;
		item.iItem    = 1;
		item.iSubItem = 1;
		item.pszText  = szText;
		item.cchTextMax = MAX_PATH;
		ListView_GetItem(hList,&item);	
		
		if (lstrlen(szText)==0)	wsprintf(szTemp,TEXT("%d"),param.EndState);
		else				    wsprintf(szTemp,TEXT(",%d"),param.EndState);		
		lstrcat(szText,szTemp);			
		item.mask     = LVIF_TEXT;
		ListView_SetItem(hList,&item);			
	}
	num = ListView_GetItemCount(hList);
	if (num != 0)
	ListView_SetSelectionMark(hList,num - 1);
}

// 从规则列表创建有限自动机
void CreateMachine(HWND hList)
{
	TCHAR     szText[MAX_PATH];
	TCHAR     *pText;
	LVITEM    item;
	RULE Rule;	
	int  i,total;

	total = ListView_GetItemCount(hList);
	for(i = 2; i < total; i++)
	{   // 依次添加各条规则
		item.mask  = LVIF_TEXT;
		item.iItem = i;
		item.iSubItem = 0;	
		item.pszText    = szText;
		item.cchTextMax = MAX_PATH;
		ListView_GetItem(hList,&item);		
		pText = szText;
		Rule.oldstate = GetNextNumber(&pText);
		
		item.iSubItem = 1;		
		ListView_GetItem(hList,&item);		
		if (lstrcmp(szText,TEXT("NULL")) == 0) Rule.input = 0;		
		else								   Rule.input = szText[0];

		item.iSubItem = 2;		
		ListView_GetItem(hList,&item);
		pText = szText;
		Rule.newstate = GetNextNumber(&pText);				

		Machine.AddRule(Rule);
	}
	// 添加开始状态
	item.mask  = LVIF_TEXT;
	item.iItem = 0;
	item.iSubItem = 1;	
	item.pszText  = szText;
	item.cchTextMax = MAX_PATH;
	ListView_GetItem(hList,&item);
	pText = szText;
	while(*pText)	
		Machine.AddStartState(GetNextNumber(&pText));	
	// 添加结束状态	
	item.iItem = 1;	
	ListView_GetItem(hList,&item);	
	pText = szText;
	while(*pText)	
		Machine.AddEndState(GetNextNumber(&pText));		
}

// 从字符串中读取下一个整数
int GetNextNumber(TCHAR** pStr)
{
	int  res;
	TCHAR* pStart;
	res = 0;
	pStart = *pStr;
	while (*pStart != NULL && IsDigit(*pStart))
	{
		res = 10 * res + (*pStart - '0');
		pStart++;
	}
	*pStr = pStart;
	return res;
}

// 更新转换过程表
void UpdateTransTable(HWND hList)
{
	LVCOLUMN   colinfo;	
	LVITEM     item;
	TCHAR      szText[MAX_PATH];
	int        i,j,count;		
	HWND       hHead;	
	// 清除原内容
	ListView_DeleteAllItems(hList);	
	hHead = ListView_GetHeader(hList);
	count = Header_GetItemCount(hHead);	
	if (count > 1)
		for(i = 0; i < count - 1; i++)	ListView_DeleteColumn(hList,1);				
	if (TransTable.GetLineNum() == 0) return;
	// 设置表头	
	if (count == 0)
	{   // 插入辅助的宽度为零的第一列
		colinfo.mask =LVCF_TEXT | LVCF_WIDTH;			
		colinfo.cx   = 0;
		colinfo.pszText = TEXT("");
		ListView_InsertColumn(hList,0,&colinfo);
	}

	colinfo.mask = LVCF_FMT | LVCF_TEXT | LVCF_WIDTH;	
	colinfo.fmt  = LVCFMT_CENTER;	
	colinfo.cx   = 75;
	colinfo.pszText = TEXT("状态集合");
	ListView_InsertColumn(hList,1,&colinfo);
	// 添加代表各个输入符号的表头	
	RULE_SET& RuleSet = Machine.GetRuleSet();
	for(i = 0; i < RuleSet.GetSignNum(); i++)
	{
		wsprintf(szText,TEXT("%c"),RuleSet.GetSign(i));
		colinfo.pszText = szText;
		ListView_InsertColumn(hList,i + 2,&colinfo);
	}
	// 填写状态转换表
	item.mask     = LVIF_TEXT;
	for(i = 0; i < TransTable.GetLineNum(); i++)	
	{
		item.iItem    = i;
		item.iSubItem = 0;
		item.pszText  = TEXT("");
		ListView_InsertItem(hList,&item);

		for(j = 0; j < RuleSet.GetSignNum() + 1; j++)
		{
			TransTable[i][j].Output(szText);// 取格子代表的状态集合					
			item.iSubItem = j + 1;
			item.pszText  = szText;	
			ListView_SetItem(hList,&item);
		}
	}
}

// 更新确定的有限自动机的状态表
void UpdateTransResult(HWND hList)
{	
	LVITEM     item;
	TCHAR      szText[MAX_PATH];	
	int        i;	
	RULE       Rule;
	RULE_SET&  RuleSet = Machine.GetRuleSet();
	// 清除原内容
	ListView_DeleteAllItems(hList);	
	InitRuleList(hList);
	if (RuleSet.GetRuleNum() == 0) return;
	// 填写开始状态
	item.mask     = LVIF_TEXT;
	item.iItem    = 0;
	item.iSubItem = 1;	
	Machine.GetStartSet().Output(szText);
	item.pszText  = szText;	
	ListView_SetItem(hList,&item);
	// 填写结束状态
	item.iItem    = 1;
	item.iSubItem = 1;
	Machine.GetEndSet().Output(szText);
	item.pszText  = szText;	
	ListView_SetItem(hList,&item);
	// 填写状态转换表	
	for(i = 0; i < RuleSet.GetRuleNum(); i++)	
	{
		item.iItem    = i + 2;
		Rule = RuleSet.GetRule(i);

		item.iSubItem = 0;
		wsprintf(szText,TEXT("%d"),Rule.oldstate);		
		item.pszText  = szText;	
		ListView_InsertItem(hList,&item);

		item.iSubItem = 1;
		wsprintf(szText,TEXT("%c"),Rule.input);	
		item.pszText  = szText;	
		ListView_SetItem(hList,&item);

		item.iSubItem = 2;
		wsprintf(szText,TEXT("%d"),Rule.newstate);		
		item.pszText  = szText;	
		ListView_SetItem(hList,&item);
	}		
}