ruleset.cpp

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

#include "RuleSet.h"
#include <stdio.h>
/*--------------------- RULE_SET 规则集合类的实现 --------------------------*/
FOLLOW_SET::FOLLOW_SET() : FollowSet()
{
}

FOLLOW_SET::~FOLLOW_SET()
{
	FollowSet.Reset();
}
// 压缩：去掉和左边相同的符号，已经重复的符号
void FOLLOW_SET::Compact()
{
	int i,len;	
	SIGN_SET TempSet;

	len = FollowSet.GetSignNum();
	i = 0;
	for(i = 0; i < len; i++)
		if (FollowSet[i] != Sign)
			TempSet.AppendSign(FollowSet[i]);
	
	FollowSet = TempSet;
}

int FOLLOW_SET::GetNonTerminalSignNum()
{
	int i,len,num = 0;
	len = FollowSet.GetSignNum();
	for(i = 0; i < len; i++)
		if(IsNonTerminalSign(FollowSet[i])) 
			num ++;
	return num;
}
/*--------------------- RULE_SET 规则集合类的实现 --------------------------*/
RULE_SET::RULE_SET() : SelectTable()
{	
	RuleNum = 0;
	pRules  = NULL;
	NonTerSignNum = 0;
	FollowSet = NULL;
	FollowSetCalced = false;
	StartSign = END_SIGN;	
}

RULE_SET::~RULE_SET()
{
	Reset();
}

int RULE_SET::GetRuleNum()
{
	return RuleNum;
}

RULE RULE_SET::GetRule(int no)
{
	RULE rule;	
	if (no >= 0 && no < RuleNum) rule = pRules[no];
	return rule;
}

void RULE_SET::AddRule(RULE rule)
{
	// 检查规则是否已经存在(集合不允许重复元素的存在)
	int no;
	for(no = 0; no < RuleNum; no++)
		if (pRules[no] == rule) return;
		
	RULE* pTemp;
	
	pTemp  = pRules;
	pRules = new RULE[RuleNum + 1];
	CopyMemory(pRules,pTemp,sizeof(RULE) * RuleNum);
	CopyMemory(pRules + RuleNum,&rule,sizeof(RULE));
	RuleNum = RuleNum + 1;
	delete []pTemp;

	FollowSetCalced = false;
}

bool RULE_SET::SetStartSign(SIGN Sign)
{
	if (Sign == StartSign) return true;

	StartSign = Sign;	
	if (FollowSet != NULL)   delete []FollowSet;
	FollowSet = NULL;
	FollowSetCalced = false;
	return true;
}

SIGN  RULE_SET::GetStartSign()
{
	return StartSign;
}

bool RULE_SET::IsLeftRecursive()
{	
	return CheckLeftRecursive();
}

void RULE_SET::Reset()
{
	if (pRules != NULL)      delete []pRules;
	if (FollowSet != NULL)   delete []FollowSet;
	RuleNum = 0;
	pRules  = NULL;
	NonTerSignNum = 0;

	FollowSet = NULL;
	FollowSetCalced = false;
	StartSign = END_SIGN;
	SelectTable.Reset();	
}
/* ------------------- 判断某符号是否能够推导出空串 -----------------------*/
bool RULE_SET::CanPushOutNULLString(SIGN Sign)
{
	int   i,j,len;
	RULE  Rule;
	bool  HasTerminalSign;	
	SIGN  TempSign;

	if (!IsNonTerminalSign(Sign)) return false; // 终极符不能推导出空串

	for(i = 0; i < RuleNum; i++)
	{
		Rule = pRules[i];
		if (Rule.Left != Sign) continue;
		if (0 == (len = strlen(Rule.Right))) return true; // 可以直接推导出空串

		HasTerminalSign = false;
		for(j = 0; !HasTerminalSign && j < len; j++)
		{
			TempSign = Rule.Right[j];
			if (!IsNonTerminalSign(TempSign))     HasTerminalSign = true;			
			else if (!CanPushOutNULLString(TempSign)) 
				HasTerminalSign = true;			
		}
		if (HasTerminalSign) continue; // 规则右边含有终极符或者某个非终极符不能推导出空串
		else  return true;
	}
	return false;
}

/*---------------------- 判断某输入串是否可以推导出空串 -----------------*/
bool RULE_SET::CanPushOutNULLString(const SIGN_SET& SignStr)
{
	int        i,len;	
	SIGN       Sign;	
	SIGN_SET   SignString;

	SignString = SignStr;
	len = SignString.GetSignNum();
	if (len == 0) return true;
	for(i = 0; i < len; i++)
	{
		Sign = SignString[i];
		// 串中含有终极符，不能推导出空串
		if (!IsNonTerminalSign(Sign)) return false;  
		// 如果此非终极符不能推导出空串,则整个串也不能推导出空串
		if (!CanPushOutNULLString(Sign)) return false;		
	}
	return true;
	
}

/*----------------------- 取某符号的 FIRST 集合 ----------------------*/
SIGN_SET RULE_SET::GetFIRSTSignSet(SIGN Sign)
{
	int       i,j,len;
	RULE      Rule;
	SIGN      TempSign;
	SIGN_SET  TempResult,ResultSet;
	bool      CanPushOutNULL;
	
	if (!IsNonTerminalSign(Sign)) // 终极符的 FIRST 集就是本身
	{
		ResultSet.AppendSign(Sign);
		return ResultSet;
	}
		
	for(i = 0; i < RuleNum; i++)
	{
		Rule = pRules[i];
		if (Rule.Left != Sign) continue;
		
		len = strlen(Rule.Right);
		if (len == 0) continue;
		// 对左边是 Sign 的规则的右部求 FIRST 集合
		j = 0;
		do   
		{
			TempSign = Rule.Right[j++];
			TempResult = GetFIRSTSignSet(TempSign);			
			ResultSet += TempResult;   			
				
			CanPushOutNULL = CanPushOutNULLString(TempSign);
		}while(j < len && CanPushOutNULL);		
	}
	return ResultSet;
}

/*---------------------- 取某输入串的 FIRST 符号集 ----------------------*/
void RULE_SET::GetFIRSTSignSet(const SIGN_SET& SignStr,SIGN_SET& ResultSet)
{
	int       i,len;
	SIGN      Sign;
	SIGN_SET  SignString,TempResult;	
	bool      CanPushOutNULL;

	ResultSet.Reset();
	SignString = SignStr;
	len = SignString.GetSignNum();	
	if (len == 0) return;

	i = 0;
	do
	{
		Sign = SignString[i++];
		TempResult = GetFIRSTSignSet(Sign);
		ResultSet += TempResult;

		CanPushOutNULL = CanPushOutNULLString(Sign);
	}while (i < len && CanPushOutNULL);
}

/*-------------------------- 计算 FOLLOW 集合 ----------------------------*/
int  RULE_SET::CalcFOLLOWSet()
{
	if (StartSign == END_SIGN || FollowSetCalced) 
		return NonTerSignNum; // 如果还没有设置开始符号或者已经计算过，不重复计算

	int i,j,k,len;
	SIGN_SET  NonTerSignSet,TempResult,TempString;
	SIGN  Sign;
	RULE  Rule;
	bool  Replaced;
	
	if (FollowSet != NULL) delete []FollowSet;	
	for(i = 0; i < RuleNum; i++)	
		NonTerSignSet.AppendSign(pRules[i].Left);
	NonTerSignNum = NonTerSignSet.GetSignNum();

	FollowSet = new FOLLOW_SET[NonTerSignNum];
	for(i = 0; i < NonTerSignNum; i++)
	{
		FollowSet[i].Sign = NonTerSignSet[i];	
		if (FollowSet[i].Sign == StartSign)		// 为文法的开始符号添加 # 到 FOLLOW 集合
			FollowSet[i].FollowSet.AppendSign(END_SIGN);
	}
	// 对各个非终极符
	for(i = 0; i < NonTerSignNum; i++)
	{
		Sign = NonTerSignSet[i];
		for(j = 0; j < RuleNum; j++) // 对各个规则式
		{
			Rule = pRules[j];
			len = strlen(Rule.Right);
			k = 0; 
			do
			{
				while ( k < len && Rule.Right[k] != Sign) k++;
				if (k == len - 1)  
					FollowSet[i].FollowSet.AppendSign(Rule.Left);  // (4)
				else if ( k < len)
				{
					TempString = Rule.Right + (k + 1);
					GetFIRSTSignSet(TempString,TempResult); // (2) (3)
					FollowSet[i].FollowSet += TempResult;

					if (CanPushOutNULLString(TempString))//后续部分可以推导出空串
						FollowSet[i].FollowSet.AppendSign(Rule.Left);
				}
				k = k + 1;
			}while(k < len);
		}
	}
	/*------------------------------ 化 简 -----------------------------*/	
	do
	{
		Replaced = false;
		for(i = 0; i < NonTerSignNum; i++)
		{
			if (0 == FollowSet[i].GetNonTerminalSignNum()) continue;

			TempResult = FollowSet[i].FollowSet;
			len = FollowSet[i].FollowSet.GetSignNum();

			for(j = 0; j < len; j++)
			{
				Sign = FollowSet[i].FollowSet[j];
				if (IsNonTerminalSign(Sign))   // 对 FOLLOW 集中的每个非终极符
				{
					for(k = 0; k < NonTerSignNum; k++)
					{
						if (k == i) continue;
						if (FollowSet[k].Sign != Sign) continue;
						if (FollowSet[k].GetNonTerminalSignNum() > 1) continue;
						// 如果能被替换成不多于 1 个非终极符，则替换
						TempResult.DeleteSign(Sign);
						TempResult += FollowSet[k].FollowSet;
						Replaced = true;
					}
				}
			}
			FollowSet[i].FollowSet = TempResult;
			FollowSet[i].Compact();
		}
	}while(Replaced);

	FollowSetCalced = true;

	return NonTerSignNum; // 返回非终极符个数	
}

// 取后随符号集
SIGN_SET RULE_SET::GetFollowSet(SIGN Sign)
{
	SIGN_SET ResultSet;
	int      i;

	if (!FollowSetCalced) CalcFOLLOWSet();
	for(i = 0; i < NonTerSignNum; i++)
		if (FollowSet[i].Sign == Sign)
		{
			ResultSet = FollowSet[i].FollowSet;
			break;
		}
	return ResultSet;
}

/*----------------------------- 取预测分析表 --------------------------*/
TABLE RULE_SET::CreateSELECTTable()
{
	SelectTable.Reset();

	if (!FollowSetCalced) CalcFOLLOWSet();
	int  i,j,len;
	RULE Rule;
	SIGN_SET  TempString,SelectSet;	

	for(i = 0; i < RuleNum; i++)
	{   // 计算规则的可选符号集
		Rule = pRules[i];		
		if (strlen(Rule.Right) == 0)
			SelectSet = GetFollowSet(Rule.Left);
		else 
		{
			TempString = Rule.Right;
			GetFIRSTSignSet(TempString,SelectSet);			
			if (CanPushOutNULLString(TempString))
				SelectSet += GetFollowSet(Rule.Left);
		}		
		// 加入到选择表
		SelectTable.StackTopSignSet.AppendSign(Rule.Left);
		len = SelectSet.GetSignNum();
		for(j = 0; j < len; j++)
		{
			SelectTable.InputSignSet.AppendSign(SelectSet[j]);
			SelectTable.AddGrid(Rule.Left,SelectSet[j],Rule);
		}
	}
	return SelectTable;
}

/*------------------- 检查文法中是否存在左递归 --------------------------*/
bool RULE_SET::CheckLeftRecursive()
{
	SIGN       Sign,FirstSign;
	SIGN_SET   SignStack,AllSigns;
	int        i,j,num,startpos,len;
	bool       LeftRecursive;
	bool       CanPushOutNULL;

	for(i = 0; i < RuleNum; i++)
		AllSigns.AppendSign(pRules[i].Left);
	num = AllSigns.GetSignNum();
	LeftRecursive = false;	
	
	for(i = 0; !LeftRecursive && i < num; i++)
	{
		Sign = AllSigns[i];
		SignStack.Reset();
		SignStack.AppendSign(Sign);
		for(j = 0; !LeftRecursive && j < RuleNum; j++)
		{
			if (pRules[j].Left == Sign && strlen(pRules[j].Right) != 0)
			{
				startpos = 0;
				len = strlen(pRules[i].Right);
				do
				{
					FirstSign = pRules[j].Right[startpos++];
					if (FirstSign == Sign) 
						LeftRecursive = true;
					else 
						LeftRecursive  = CanBeginWithSign(FirstSign,Sign,SignStack);
					if (!LeftRecursive)
						CanPushOutNULL = CanPushOutNULLString(FirstSign);
				}while(startpos < len && !LeftRecursive && CanPushOutNULL);			
			}
		}
	}
	return LeftRecursive;
}

bool RULE_SET::CanBeginWithSign(SIGN LeftSign,SIGN BeginSign,SIGN_SET& SignStack)
{
	if (!IsNonTerminalSign(LeftSign)) return false;
	if (!SignStack.AppendSign(LeftSign)) return true;

	int i;
	SIGN FirstSign;	

	for(i = 0; i < RuleNum; i++)
	{
		if (pRules[i].Left == LeftSign && strlen(pRules[i].Right) != 0)
		{
			FirstSign = pRules[i].Right[0];
			if (IsNonTerminalSign(FirstSign))
			{

				if (FirstSign == BeginSign) return true;
				else if (CanBeginWithSign(FirstSign,BeginSign,SignStack))
					return true;
			}			
		}
	}
	return false;
}