checkformulary.cpp

自己在学习编译原理时用vc++写的算符优先分析器

// CheckFormulary.cpp: implementation of the CCheckFormulary class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "MyFormulary.h"
#include "CheckFormulary.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
int GetIndex(char ch)
{
	switch(ch)
	{
	case 'Z':
		return 0;
	case 'E':
		return 1;
	case 'W':
		return 2;
	case 'T':
		return 3;
	case 'F':
		return 4;
	case 'P':
		return 5;
	case '+':
		return 6;
	case '*':
		return 7;
	case '^':
		return 8;
	case '(':
		return 9;
	case ')':
		return 10;
	case 'I':
		return 11;
	case '#':
		return 12;
	}
	return -1;
}

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CCheckFormulary::CCheckFormulary()
{

}

CCheckFormulary::~CCheckFormulary()
{

}

void CCheckFormulary::GetTablePointer(CTable *pt)
{
	m_pTable=pt;
}

FormularyWord CCheckFormulary::GetFormularyWord(WORD num)
{
	FormularyWord fw;
	switch(num)
	{
	case CTable::OPERATOR+0x0002:
		fw.WordType='+';
		break;
	case CTable::OPERATOR+0x0009:
		fw.WordType='*';
		break;
	case CTable::OPERATOR+0x001F:
		fw.WordType='^';
		break;
	case CTable::SEPARATOR+0x0000:
		fw.WordType='(';
		break;
	case CTable::SEPARATOR+0x0001:
		fw.WordType=')';
		break;
	default:
		if(num>=CTable::INTEGER && num<CTable::UNKNOWN)
		{
			fw.WordType='I';
			if(num>=CTable::IDENTIFIER)fw.Number=0;
			else if(num>=CTable::REAL)fw.Number=m_pTable->m_RealTable.GetAt(num-CTable::REAL);
			else fw.Number=m_pTable->m_IntegerTable.GetAt(num-CTable::INTEGER);
		}
		else fw.WordType='U';
	}
	return fw;
}

FormularyWord CCheckFormulary::ReachWord(FormularyWord* s,int length)
{
	FormularyWord fw;
	if(length==1)
		switch(s[0].WordType)
		{
		case 'E':
			fw.WordType='Z';
			fw.Number=s[0].Number;
			break;
		case 'W':
			fw.WordType='E';
			fw.Number=s[0].Number;
			break;
		case 'T':
			fw.WordType='W';
			fw.Number=s[0].Number;
			break;
		case 'F':
			fw.WordType='T';
			fw.Number=s[0].Number;
			break;
		case 'P':
			fw.WordType='F';
			fw.Number=s[0].Number;
			break;
		case 'I':
			fw.WordType='P';
			fw.Number=s[0].Number;
			break;
		default:
			fw.WordType='U';
		}
	else if(length==3)
		switch(s[0].WordType)
		{
		case 'E':
			if(s[1].WordType=='+' && s[2].WordType=='W')
			{
				fw.WordType='E';
				fw.Number=s[0].Number+s[2].Number;
			}
			else fw.WordType='U';
			break;
		case 'T':
			if(s[1].WordType=='*' && s[2].WordType=='F')
			{
				fw.WordType='T';
				fw.Number=s[0].Number*s[2].Number;
			}
			else fw.WordType='U';
			break;
		case 'P':
			if(s[1].WordType=='^' && s[2].WordType=='F')
			{
				fw.WordType='F';
				fw.Number=pow(s[0].Number,s[2].Number);
			}
			else fw.WordType='U';
			break;
		case '(':
			if(s[1].WordType=='Z' && s[2].WordType==')')
			{
				fw.WordType='P';
				fw.Number=s[1].Number;
			}
			else fw.WordType='U';
			break;
		default:
			fw.WordType='U';
		}
	else fw.WordType='U';

	return fw;
}

BOOL CCheckFormulary::Check(CWordArray &Source,CString &output)
{
	BOOL IsSuccessful=TRUE;
	output=_T("");
	CString temp;
	/////////////////////////////////////////
	FormularyWord* T=new FormularyWord[Source.GetSize()+2];
	FormularyWord* S=new FormularyWord[Source.GetSize()+2];
	for(int i=0;i<Source.GetSize()+2;i++)
	{
		if(i==0 || i==Source.GetSize()+1)T[i].WordType='#';
		else
		{
			T[i]=GetFormularyWord(Source.GetAt(i-1));
			if(T[i].WordType=='U')
			{
				temp.Format("|错误:本文法无法识别单词%d.|\r\n",i);
				output+=temp;
				IsSuccessful=FALSE;
			}
		}
	}
	/////////////////////////////////////////
	if(IsSuccessful)
	{
		int nCount=0;
		int i=0,j,k=1;
		int g;
		S[i]=T[i];
		FormularyWord R=T[k++];
		FormularyWord V;
		temp.Format("|表达式%.3d|",nCount);
		output+=temp;
		for(int ii=0;ii<Source.GetSize()+2;ii++)output+=T[ii].WordType;
		output+=_T("\r\n");
		temp.Format("|运算值%.3d|",nCount++);
		output+=temp;
		for(ii=1;ii<=Source.GetSize();ii++)
		{
			char wt=T[ii].WordType;
			if(wt=='+' || wt=='*' || wt=='^' || wt=='(' || wt==')' || wt=='#')output+=T[ii].WordType;
			else
			{
				temp.Format("%g",T[ii].Number);
				output+=temp;
			}
		}
		output+=_T("\r\n\r\n");
		/////////////////////////////////////////
		while(TRUE)
		{
			if((g=GrammarTable[GetIndex(S[i].WordType)][GetIndex(R.WordType)])==__UNKNOWN__)
			{
				output+=_T("|错误:出现文法不可识别的单词连接");
				output+=S[i].WordType;
				output+=R.WordType;
				output+=_T("|\r\n");
				IsSuccessful=FALSE;
				break;
			}
			if(g!=__MORE__)
			{
				S[++i]=R;
				R=T[k++];
				continue;
			}
			j=i;
			while(j>0)
			{
				if((g=GrammarTable[GetIndex(S[j-1].WordType)][GetIndex(S[j].WordType)])==__UNKNOWN__ || g==__LESS__)break;
				j--;
			}
			if(g==__UNKNOWN__)
			{
				output+=_T("|错误:出现文法不可识别的单词连接");
				output+=S[j-1].WordType;
				output+=S[j].WordType;
				output+=_T("|\r\n");
				IsSuccessful=FALSE;
				break;
			}
			if((V=ReachWord(S+j,i-j+1)).WordType=='U')
			{
				if(i==1 && S[i].WordType=='Z' && R.WordType=='#')
				{
					output+=_T("|正确:表达式符合文法|\r\n");
					temp.Format("<运算结果=%g>\r\n",S[i].Number);
					output+=temp;
				}
				else
				{
					output+=_T("|错误:出现文法无法归约的产生式");
					for(ii=j;ii<=i;ii++)output+=S[ii].WordType;
					output+=_T("|\r\n");
					IsSuccessful=FALSE;
				}
				break;
			}
			S[i=j]=V;
			temp.Format("|表达式%.3d|",nCount);
			output+=temp;
			for(ii=0;ii<=i;ii++)output+=S[ii].WordType;
			for(ii=k-1;ii<Source.GetSize()+2;ii++)output+=T[ii].WordType;
			output+=_T("\r\n");
			temp.Format("|运算值%.3d|",nCount++);
			output+=temp;
			for(ii=1;ii<=i;ii++)
			{
				char wt=S[ii].WordType;
				if(wt=='+' || wt=='*' || wt=='^' || wt=='(' || wt==')' || wt=='#')output+=S[ii].WordType;
				else
				{
					temp.Format("%g",S[ii].Number);
					output+=temp;
				}
			}
			for(ii=k-1;ii<=Source.GetSize();ii++)
			{
				char wt=T[ii].WordType;
				if(wt=='+' || wt=='*' || wt=='^' || wt=='(' || wt==')' || wt=='#')output+=T[ii].WordType;
				else
				{
					temp.Format("%g",T[ii].Number);
					output+=temp;
				}
			}
			output+=_T("\r\n\r\n");
		}
	}		
	/////////////////////////////////////////////
	delete S;
	delete T;
	return IsSuccessful;
}