parsing.cpp

这是用VC6.0开发的集词法分析、语法分析、语义分析为一体的一个程序

// Parsing.cpp: implementation of the CParsing class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "scanner.h"
#include "Parsing.h"

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

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

//初始化文法产生式
/************************************************************
 *	E -> E + T
 *	E -> E - T
 *	E -> T
 *	T -> T * F
 *	T -> T / F
 *	T -> F
 *	F -> i
 *	F -> ( E )
 ************************************************************/
const GProduction CParsing::m_production[PRODUCTIONSIZE][PRODUCTIONLEN+1]={
	{{Nonterminal,'E'},{Nonterminal,'E'},{Terminal,'+'},{Nonterminal,'T'},{Other,' '}},
	{{Nonterminal,'E'},{Nonterminal,'E'},{Terminal,'-'},{Nonterminal,'T'},{Other,' '}},
	{{Nonterminal,'E'},{Nonterminal,'T'},{Other,' '}},
	{{Nonterminal,'T'},{Nonterminal,'T'},{Terminal,'*'},{Nonterminal,'F'},{Other,' '}},
	{{Nonterminal,'T'},{Nonterminal,'T'},{Terminal,'/'},{Nonterminal,'F'},{Other,' '}},
	{{Nonterminal,'T'},{Nonterminal,'F'},{Other,' '}},
	{{Nonterminal,'F'},{Terminal,'i'},{Other,' '}},
	{{Nonterminal,'F'},{Terminal,'('},{Nonterminal,'E'},{Terminal,')'},{Other,' '}}
};

/**优先矩阵符号标示顺序
 *************************************************************
 *	+	-	*	/	(	)	i	#
 ************************************************************/
const char CParsing::m_operTableIndex[OPERTABLESIZE]={
	'+','-','*','/','(',')','i','#'
};

/**优先矩阵
/*************************************************************
 *		+	-	*	/	(	)	i	#
 *
 *	+	>	>	<	<	<	>	<	>
 *	-	>	>	<	<	<	>	<	>
 *	*	>	>	>	>	<	>	<	>
 *	/	>	>	>	>	<	>	<	>
 *	(	<	<	<	<	<	=	<	>
 *	)	>	>	>	>		>		>
 *	i	>	>	>	>		>		>
 *	#	<	<	<	<	<	<	<	
 ************************************************************/
const OperCompare CParsing::m_operTable[OPERTABLESIZE][OPERTABLESIZE]={
	{More,	More,	Less,	Less,	Less,	More,	Less,	More},
	{More,	More,	Less,	Less,	Less,	More,	Less,	More},
	{More,	More,	More,	More,	Less,	More,	Less,	More},
	{More,	More,	More,	More,	Less,	More,	Less,	More},
	{Less,	Less,	Less,	Less,	Less,	Equal,	Less,	More},
	{More,	More,	More,	More,	Unknown,More,	Unknown,More},
	{More,	More,	More,	More,	Unknown,More,	Unknown,More},
	{Less,	Less,	Less,	Less,	Less,	Less,	Less,	Unknown}
};

/**
 * 语法分析构造函数
 *
 * @param  pWordCode			字符表数组
 * @param  pTokenFile			token串头指针
 * @param  pSymbolTable			符号表头指针
 * @param  pErrorCollection		错误信息头指针
 *
 */
CParsing::CParsing(const char *pWordCode[],
				   PTokenNode pTokenFile,
				   PSTable pSymbolTable,
				   PErrorNode pErrorCollection)
{
	//初始化分析栈和当前识别的最左素短语
	this->m_stckTerTop.next=NULL;
	this->m_stckTop.next=NULL;

	InitStck();
	this->m_llp.next=NULL;

	this->m_pMorpheme=new CMorpheme(pWordCode,pTokenFile,pSymbolTable,pErrorCollection);
	this->m_pSymbolTable=pSymbolTable;
	for (int i=0;i<KEYWORDCOUNT+1;i++)
	{
		this->m_pWordCode[i]=pWordCode[i];
	}
}

/**
 * 语法分析构造函数
 *
 * @param  pWordCode			字符表数组
 * @param  pTokenFile			token串头指针
 * @param  pSymbolTable			符号表头指针
 * @param  pErrorCollection		错误信息头指针
 * @param  strSourceFile		源文件路径
 *
 */
CParsing::CParsing(const char *pWordCode[],
				   PTokenNode pTokenFile,
				   PSTable pSymbolTable,
				   PErrorNode pErrorCollection,
				   CString strSourceFile)
{
	//初始化分析栈和当前识别的最左素短语
	this->m_stckTerTop.next=NULL;
	this->m_stckTop.next=NULL;

	InitStck();
	this->m_llp.next=NULL;

	this->m_pMorpheme=new CMorpheme(pWordCode,pTokenFile,pSymbolTable,pErrorCollection,strSourceFile);
	this->m_pSymbolTable=pSymbolTable;
	for (int i=0;i<KEYWORDCOUNT+1;i++)
	{
		this->m_pWordCode[i]=pWordCode[i];
	}
}

CParsing::~CParsing()
{
	//释放分析栈
	DisposeStck();

	//释放最左素短语
	PGSymbol gs;
	while (this->m_llp.next!=NULL)
	{
		gs=this->m_llp.next;
		this->m_llp.next=gs->next;
		delete gs;
	}
}
//函数功能：进行语法分析  return CString 语法分析结果
CString CParsing::Parsing(CString strSourceFile/*=""*/)
{
	PTokenNode pToken=NULL;
	char word='0';
	bool morSucc=false;
	bool returnValue=true;
	//表达式结果为整型还是浮点型：false为整型
	bool resultType=false;
	//将#压入分析栈
	this->GSPut('#',pToken);
	
	//分析源程序
	morSucc=this->m_pMorpheme->StepMorpheme(pToken,strSourceFile);
	while (morSucc)
	{
		word='0';

		if (this->m_pWordCode[pToken->keycode]=="constfloat" ||
			this->m_pWordCode[pToken->keycode]=="constint")
		{
			word='i';
			//表达式结果为整型还是浮点型：false为整型
			if (this->m_pWordCode[pToken->keycode]=="constfloat") resultType=true;
		}
		else if (this->m_pWordCode[pToken->keycode]=="+" ||
				 this->m_pWordCode[pToken->keycode]=="-" ||
				 this->m_pWordCode[pToken->keycode]=="*" ||
				 this->m_pWordCode[pToken->keycode]=="/" ||
				 this->m_pWordCode[pToken->keycode]=="(" ||
				 this->m_pWordCode[pToken->keycode]==")" )
		{
			word=this->m_pWordCode[pToken->keycode][0];
		}
		else
		{
			this->m_pMorpheme->AddError("表达式非法!",this->m_pMorpheme->GetCurRow(),this->m_pMorpheme->GetCurCol());

		}

		//识别并归约
		if (this->CompOperator(this->GetNextTerSymbol()->word,word)==More)
		{
			returnValue=this->RecogLLP();
			if (returnValue)
			{
				returnValue=this->MatchProduction();				
			}
			if (!returnValue) 
			{
				this->m_pMorpheme->CloseSource();
				break;
			}
		}
		else
		{
			this->GSPut(word,pToken);
			morSucc=this->m_pMorpheme->StepMorpheme(pToken,strSourceFile);
		}
	}

	//源程序分析完毕，将分析栈剩余的句型规约
	CString str;
	if (returnValue)
	{
		while (this->GetGSTopSymbol()->next->word!='#' || this->GetGSTopSymbol()->sType!=Nonterminal)
		{
			returnValue=this->RecogLLP();
			if (returnValue)
			{
				returnValue=this->MatchProduction();
				if (!returnValue) break;
			}
			else break;	
		}
		//归约完成
		if (this->GetGSTopSymbol()->next->word=='#')
		{
			//CString str;
			if (resultType) str.Format("归约成功！\n表达式结果为：%f",this->GetGSTopSymbol()->value.dValue);
			else str.Format("归约成功！\n表达式结果为：%d",(int)this->GetGSTopSymbol()->value.dValue);
			//::AfxMessageBox(str);
			//return str;
		}
		else
		{
			returnValue=false;
		}
	}
	
	if (!returnValue) //::AfxMessageBox("归约失败，请检查表达式是否有错误！");
        str = "归约失败，请检查表达式是否有错误！";
	 return str;
}

/**
 * 进行终结符优先级比较
 * @param	char chOper1			比较符一
 * @param	char chOper2			比较符二
 *
 * @return	OperCompare				比较结果
 *
 */
OperCompare CParsing::CompOperator(char chOper1,char chOper2)
{
	OperCompare returnValue=Unknown;
	//匹配符号编号
	int iOper1=-1,iOper2=-1;
	for (int i=0;i<OPERTABLESIZE;i++)
	{
		if (iOper1 == -1) iOper1=(chOper1==this->m_operTableIndex[i])? i:-1;
		if (iOper2 == -1) iOper2=(chOper2==this->m_operTableIndex[i])? i:-1;
	}

	if (iOper1 != -1 && iOper2 != -1)
	{
		returnValue=this->m_operTable[iOper1][iOper2];
	}

	return returnValue;
	
}

/**
 * 识别素短语,先清空素短语列表
 *
 * @return		bool			是否识别最左素短语
 *
 */
bool CParsing::RecogLLP()
{
	bool returnValue=false;

	//释放当前素短语
	PGSymbol topGS;
	while (this->m_llp.next!=NULL)
	{
		topGS=this->m_llp.next;
		this->m_llp.next=topGS->next;
		delete topGS;
	}
	this->m_llp.next=NULL;
	
	//识别素短语,以Less为标志
	PGSymbol oper1,oper2;//分析栈中oper1在oper2下面
	oper2=this->GetNextTerSymbol();
	if (oper2!=NULL)
	{
		oper1=this->GetNextTerSymbol(oper2);
		while (oper1!=NULL)
		{
			if (Less==this->CompOperator(oper1->word,oper2->word))
			{
				//提取素短语
				PGSymbol pGS=this->GetGSTopSymbol();
				while (pGS!=oper1)
				{
					pGS=this->GSPop();
					pGS->next=this->m_llp.next;
					this->m_llp.next=pGS;					
					pGS=this->GetGSTopSymbol();
				}
				returnValue=true;
				break;
			}
			oper2=oper1;
			oper1=this->GetNextTerSymbol(oper2);
		}
	}

	return returnValue;
}

/**
 * 匹配当前识别的最左素短语，并进行归约计算表达式的值
 *
 * @return		bool		是否存在相应的产生式匹配并归约
 *
 */
bool CParsing::MatchProduction()
{
	bool returnValue=false;
	int iProIndex=-1;
	PGSymbol pGS=NULL;
	bool bMatch=false;

	//匹配产生式
	for (int i=0;i<PRODUCTIONSIZE;i++)
	{
		pGS=this->m_llp.next;
		if (pGS==NULL) break;
		bMatch=false;
		for (int j=1;j<PRODUCTIONLEN+1;j++)
		{
			if (this->m_production[i][j].sType==Other && pGS==NULL)
			{
				iProIndex=i;
				bMatch=true;
			}
			else
			{
				if (this->m_production[i][j].sType==Other) break;
				if (pGS==NULL) break;
					
				if (this->m_production[i][j].sType == pGS->sType)
				{
					if (pGS->sType==Terminal)
					{
						if (pGS->word != m_production[i][j].word) break;
					}
				}
				else break;
				pGS=pGS->next;
			}
		}
		if (bMatch) break;
	}

	//进行归约
	if (bMatch)
	{
		returnValue=true;

		PGSymbol pOper1,pOper2,pOper3;
		pOper1=this->m_llp.next;
		if (iProIndex!=6)
		{
			pOper2=pOper1->next;
			pOper3=pOper2->next;
		}
		
		switch (iProIndex)
		{
		case 6:	//F->i
			this->GSPut('F',
				this->m_pSymbolTable->sSubTable[pOper1->value.pToken->strId-1].val);
			break;
		case 0:	//E->E+T			
			this->GSPut('E',pOper1->value.dValue + pOper3->value.dValue);
			break;
		case 1:	//E->E-T
			GSPut('E',pOper1->value.dValue - pOper3->value.dValue);
			break;
		case 3:	//T->T*F
			GSPut('T',pOper1->value.dValue * pOper3->value.dValue);
			break;
		case 4:	//T->T/F
			if (pOper3->value.dValue==0)
			{
				this->m_pMorpheme->AddError("除数为零！",m_pMorpheme->GetCurRow());
				returnValue=false;
			}
			else
				GSPut('T',pOper1->value.dValue / pOper3->value.dValue);
			break;		
		case 7:	//F->(E)
			GSPut('F',pOper2->value.dValue);
			break;
		default:
			//无法识别
			returnValue=false;
		}
	}

	return returnValue;
}

/**
 * 归约当前识别的素短语并将归约结果入栈
 *
 * @param		int			规约产生式表达式编号
 *
 * @return		bool		归约成功
 *
 *
bool CParsing::Reduce(int iProIndex)
{
	bool returnValue=true;
	PGSymbol pOper1,pOper2,pOper3;
	pOper1=this->m_llp.next;
	if (pOper1!=NULL)
	{
		//检验已经识别的素短语
		if (iProIndex!=6)
		{
			pOper2=pOper1->next;
			if (pOper2==NULL)
			{
				return false;
			}
			else
			{
				pOper3=pOper2->next;
				if (pOper3==NULL)
				{
					return false;
				}
			}
		}

		switch (iProIndex)
		{
		case 0:	//E->E+T
			
			break;
		case 1:	//E->E-T
			break;
		case 3:	//T->T*F
			break;
		case 4:	//T->T/F
			break;
		case 6:	//F->i
			break;
		case 7:	//F->(E)
			break;
		default:
			//无法识别
			returnValue=false;
		}
	}
	else
	{
		returnValue=false;
	}

	return returnValue;
}*/

/**
 * 初始化分析栈
 *
 */
void CParsing::InitStck()
{
	DisposeStck();
	this->m_stckTop.next=NULL;
	this->m_stckTerTop.next=NULL;
}

/**
 * 弹出所有分析栈元素
 *
 */
void CParsing::DisposeStck()
{
	PGSymbol gs;
	while (m_stckTop.next!=NULL)
	{
		gs=this->m_stckTop.next;		
		this->m_stckTop.next=gs->next;
		//释放相应的token字
		if (gs->sType==Terminal)
			this->m_pMorpheme->DeleteToken(gs->value.pToken);

		delete gs;
	}
	this->m_stckTop.next=NULL;

	PTerNode tn;
	while (this->m_stckTerTop.next!=NULL)
	{
		tn=this->m_stckTerTop.next;
		this->m_stckTerTop.next=tn->next;
		delete tn;
	}
	this->m_stckTerTop.next=NULL;
}

/**
 * 弹出栈顶元素
 *
 * @return		PGSymbol		返回栈顶元素
 *
 */
PGSymbol CParsing::GSPop()
{
	PGSymbol returnValue=NULL;
	PTerNode pTerNode=NULL;

	if (this->m_stckTop.next!=NULL)
	{
		returnValue=this->m_stckTop.next;
		this->m_stckTop.next=returnValue->next;
		//清空相应的引用
		if (this->m_stckTerTop.next!=NULL && this->m_stckTerTop.next->pTerminal==returnValue)
		{
			pTerNode=this->m_stckTerTop.next;
			this->m_stckTerTop.next=pTerNode->next;
			delete pTerNode;
		}
	}

	return returnValue;
}

/**
 * 获取栈顶元素
 *
 * @return		PGSymbol		返回栈顶元素
 *
 */
PGSymbol CParsing::GetGSTopSymbol()
{
	PGSymbol returnValue=NULL;

	if (this->m_stckTop.next!=NULL)
	{
		returnValue=this->m_stckTop.next;
	}

	return returnValue;
}

/**
 * 根据当前终结符获取分析栈中下一个终结符元素
 *
 * @param		PGSymbol pGS			指定当前终结符元素
 *
 * @return		PGSymbol				返回下一个终结符元素
 *
 */
PGSymbol CParsing::GetNextTerSymbol(PGSymbol pGS/*=NULL*/)
{
	PGSymbol returnValue=NULL;
	PTerNode pTerNode=&this->m_stckTerTop;
	if (pGS==NULL)
	{
		if (pTerNode->next!=NULL)
		{
			returnValue=pTerNode->next->pTerminal;
		}
	}
	else
	{
		while (pTerNode->next!=NULL)
		{
			if (pTerNode->pTerminal == pGS)
			{
				if (pTerNode->next!=NULL)
				{
					returnValue=pTerNode->next->pTerminal;
				}
				break;
			}
			else
			{
				pTerNode=pTerNode->next;
			}
		}
	}
	return returnValue;
}

/**
 * 压栈，终结符
 *
 * @param	PTokenNode pToken		非终结符对应的token
 * @param	char		word		终结符在产生式中的表示
 *
 * @return  bool					压栈成功
 *
 */
bool CParsing::GSPut(char word,PTokenNode pToken)
{
	PGSymbol pGS=new GSymbol;
	if (pGS==NULL) return false;
	pGS->next=this->m_stckTop.next;
	this->m_stckTop.next=pGS;

	pGS->sType=Terminal;
	pGS->value.pToken=pToken;
	pGS->word=word;

	//对终结符进行引用
	PTerNode pTN=new TerNode;
	if (pTN==NULL) return false;
	pTN->next=this->m_stckTerTop.next;
	this->m_stckTerTop.next=pTN;

	pTN->pTerminal=pGS;

	return true;
}

/**
 * 压栈，非终结符
 *
 * @param	double dValue			终结符对应的规约值
 * @param	char   word				终结符在产生式中的表示
 *
 * @return  bool					压栈成功
 *
 */
bool CParsing::GSPut(char word,double dValue)
{
	PGSymbol pGS=new GSymbol;
	if (pGS==NULL) return false;
	pGS->next=this->m_stckTop.next;
	this->m_stckTop.next=pGS;

	pGS->sType=Nonterminal;
	pGS->value.dValue=dValue;
	pGS->word=word;

	return true;
}