analyse.cpp

这是一个用c++写的预测分析法程序,是编译原理课程设计的内容,可以预测分析语言

#include <windows.h>
#include <commctrl.h>
#include "RuleSet.h"

void InitRuleList(HWND);
void InsertRuleToList(HWND,RULE,SIGN);
void FillForecastList(HWND,TABLE&);
TABLE  GetForecastAnalyseTable(HWND hList);

static InitOutputList(HWND hList)
{	
	LVCOLUMN  colinfo;	
	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   = 40;
		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);		

		colinfo.cx   = 120;
		colinfo.pszText = TEXT("(栈顶，输入，动作)");
		ListView_InsertColumn(hList,3,&colinfo);		

		colinfo.cx   = 75;
		colinfo.pszText = TEXT("匹配产生式");
		ListView_InsertColumn(hList,4,&colinfo);				
	}
}

static void InsertLine(HWND hList,LPTSTR pFirst,LPTSTR pSecond,LPTSTR pThird,LPTSTR pFour)
{
	TCHAR  szSerial[10];
	int    count;
	LVITEM item;

	count = ListView_GetItemCount(hList);
	wsprintf(szSerial,TEXT("%d"),count + 1);

	item.mask     = LVIF_TEXT;
	item.iItem    = count;
	item.iSubItem = 0;
	item.pszText  = szSerial;	
	ListView_InsertItem(hList,&item);

	item.iSubItem = 1;
	item.pszText  = pFirst;	
	ListView_SetItem(hList,&item);

	item.iSubItem = 2;
	item.pszText  = pSecond;	
	ListView_SetItem(hList,&item);

	item.iSubItem = 3;
	item.pszText  = pThird;	
	ListView_SetItem(hList,&item);

	item.iSubItem = 4;
	item.pszText  = pFour;	
	ListView_SetItem(hList,&item);
}

/*
				预测分析
	pInputString --------   待分析的输入串
	hRuleList    --------   规则列表
	hTableList   --------   预测分析表列表
	hResultList  --------   输出列表窗口
*/
bool ForecastAnalyse(SIGN_SET& InputString,HWND hRuleList,HWND hTableList,HWND hResultList)
{
	int       i,j,k,RuleLen,InputLen,Top;
	TABLE     SelectTable;
	SIGN_SET  AnalyseStack;
	SIGN      InputSign,TopSign;
	RULE      Rule;

	TCHAR     szColFirst[MAX_PATH];
	TCHAR     szColSecond[MAX_PATH];
	TCHAR     szColThird[MAX_PATH];
	TCHAR     szColFour[MAX_PATH];
	TCHAR     szTemp[MAX_PATH];
	// 获取预测分析表		
	SelectTable = GetForecastAnalyseTable(hRuleList);
	FillForecastList(hTableList,SelectTable);
	if (SelectTable.LeftRecursive)
	{
		MessageBox(hRuleList,TEXT("输入的文法存在左递归，不能进行确定的自顶向下分析!\n"),
					TEXT("非LL(1)文法"),MB_OK | MB_ICONWARNING);
		return false;
	}
	else if (!SelectTable.IsDeterminate())
	{
		MessageBox(hRuleList,TEXT("输入的文法不是LL(1)文法，不能进行确定的自顶向下分析!\n"),
					TEXT("非LL(1)文法"),MB_OK | MB_ICONWARNING);
		return false;
	}

	InitOutputList(hResultList);
	// 进行预测分析
	AnalyseStack.AppendSign(END_SIGN);
	AnalyseStack.AppendSign(SelectTable.StartSign);	

	InputString.AppendSign(END_SIGN);
	InputLen = InputString.GetSignNum();
	i = 0;
	InputSign = InputString[i];
	do
	{
		ZeroMemory(szColFour,sizeof(TCHAR) * MAX_PATH);
		AnalyseStack.Output(szColFirst);
		InputString.Output(szColSecond,i);
		
		Top = AnalyseStack.GetSignNum() - 1;
		TopSign = AnalyseStack[Top];
		AnalyseStack.DeleteSign(Top);
		
		wsprintf(szColThird,TEXT("(%c，%c)   "),TopSign,InputSign);
		
		if (IsNonTerminalSign(TopSign))  // 非终极符
		{
			wsprintf(szTemp,TEXT("查表"));
			lstrcat(szColThird,szTemp);

			for(j = 0; j < SelectTable.nGrids; j++)			
				if (SelectTable[j].StackTopSign == TopSign && SelectTable[j].InputSign == InputSign)
				{
					// 规则式入栈
					Rule = SelectTable[j].SelectableRule;
					RuleLen = strlen(Rule.Right);
					for(k = RuleLen - 1; k >= 0; k--)
						AnalyseStack.AppendSign(Rule.Right[k],true);
					wsprintf(szColFour,TEXT(" %c --> %s"),Rule.Left,Rule.Right);
					break;
				}		
			// 预测分析表中没有匹配项
			if (j == SelectTable.nGrids)	wsprintf(szColFour,TEXT("找不到匹配项"));			
			if (j == SelectTable.nGrids) break;			
		}
		else if (TopSign == InputSign)   // 匹配一个终极符
		{	
			if (TopSign != END_SIGN)	wsprintf(szTemp,TEXT("%c匹配"),InputSign);
			else                        wsprintf(szTemp,TEXT("成功接受输入串"));
			lstrcat(szColThird,szTemp);			
			++i;
			if (i < InputLen)	
				InputSign = InputString[i];			
		}
		else
		{
			wsprintf(szTemp,TEXT("%c不能匹配"),InputSign);
			lstrcat(szColThird,szTemp);			
			break;			
		}
		InsertLine(hResultList,szColFirst,szColSecond,szColThird,szColFour);
	}while(TopSign != END_SIGN);
	
	if (TopSign == END_SIGN && TopSign == InputSign)
	{
		MessageBox(hRuleList,TEXT("输入串符合语法规则，顺利通过语法分析!\n"),
					TEXT("分析成功"),MB_OK | MB_ICONINFORMATION);
		return true;
	}
	else
	{
		MessageBox(hRuleList,TEXT("输入串不符合语法规则!\n"),
					TEXT("分析失败"),MB_OK | MB_ICONWARNING);
		return false;
	}
}