staterule.cpp

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

#include "StateRule.h"

bool RULE::operator ==(const RULE& other)
{
	if (input == other.input && 
		oldstate == other.oldstate && 
		newstate == other.newstate)
		return true;
	else
		return false;
}

// RULE_SET 规则集合类的实现
RULE_SET::RULE_SET()
{
	SignNum = 0;
	RuleNum = 0;
	pRules  = NULL;
	pSigns  = NULL;
}

RULE_SET::~RULE_SET()
{
	if (pRules != NULL) delete []pRules;
	if (pSigns != NULL) delete []pSigns;
}

int RULE_SET::GetSignNum()
{
	return SignNum;
}

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

RULE RULE_SET::GetRule(int no)
{
	RULE rule;
	rule.newstate = rule.oldstate = -1;
	rule.input = -1;

	if (no >= 0 && no < RuleNum) rule = pRules[no];
	return rule;
}

SIGN RULE_SET::GetSign(int no)
{
	SIGN sign;
	sign = NULL;
	if (no >=0 && no < SignNum) sign = pSigns[no];
	return sign;
}

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;
	// 更新符号表
	SIGN* pTempSign;
	if (rule.input == 0) return;
	for(no = 0; no < SignNum; no++)
		if (pSigns[no] == rule.input) return;

	pTempSign = pSigns;
	pSigns = new SIGN[SignNum + 1];
	CopyMemory(pSigns,pTempSign,sizeof(SIGN) * SignNum);
	CopyMemory(pSigns + SignNum,&(rule.input),sizeof(SIGN));
	SignNum = SignNum + 1;

	delete []pTempSign;
}

void RULE_SET::Reset()
{
	if (pRules != NULL) delete []pRules;
	if (pSigns != NULL) delete []pSigns;
	SignNum = 0;
	RuleNum = 0;
	pRules  = NULL;
	pSigns  = NULL;
}

bool RULE_SET::IsValidSign(SIGN sign)
{
	int no;
	for(no = 0; no < SignNum; no++)
		if (pSigns[no] == sign) return true;

	return false;
}

void RULE_SET::operator =(const RULE_SET& other)
{
	Reset();
	SignNum = other.SignNum;
	RuleNum = other.RuleNum;
	pSigns = new SIGN[SignNum];
	CopyMemory(pSigns,other.pSigns,sizeof(SIGN) * SignNum);
	pRules = new RULE[RuleNum];
	CopyMemory(pRules,other.pRules,sizeof(RULE) * RuleNum);
}

// STATE_SET  状态集合类的实现
STATE_SET::STATE_SET()
{
	StateNum = 0;
	pStates  = NULL;
}

STATE_SET::~STATE_SET()
{
	if (pStates != NULL) delete []pStates;
}

int STATE_SET::GetStateNum()
{
	return StateNum;
}

STATE STATE_SET::GetState(int no)
{
	STATE state;
	state = -1;
	if (no >=0 && no < StateNum) state = pStates[no];
	return state;
}

bool STATE_SET::AddState(STATE state)
{   // 检查状态是否已经存在(集合不允许重复元素)
	int no;
	for(no = 0; no < StateNum; no++)
		if (pStates[no] == state) return false;

	STATE* pTemp;
	pTemp = pStates;
	pStates = new STATE[StateNum + 1];
	CopyMemory(pStates,pTemp,sizeof(STATE) * StateNum);
	CopyMemory(pStates + StateNum,&state,sizeof(STATE));
	StateNum = StateNum + 1;
	delete []pTemp;
	return true;
}

void STATE_SET::Reset()
{
	if (pStates != NULL) delete []pStates;
	StateNum = 0;
	pStates  = NULL;
}

STATE_SET&  STATE_SET::operator=(const STATE_SET& other)
{
	Reset();
	StateNum = other.StateNum;
	pStates = new STATE[StateNum];
	CopyMemory(pStates,other.pStates,sizeof(STATE) * StateNum);
	return *this;
}

bool STATE_SET::operator==(const STATE_SET& other)
{
	if (StateNum != other.StateNum) return false;
	STATE_SET  Temp;
	Temp = *this;
	for(int i = 0; i < StateNum; i++)
		if (Temp.AddState(other.pStates[i])) return false;
	return true;
}

bool STATE_SET::StateInSet(STATE state)
{
	int no;
	for(no = 0; no < StateNum; no++)
		if (state == pStates[no]) return true;
	return false;
}

// 求在规则集 RuleSet 下，本状态集的 E 闭包
void STATE_SET::GetNULLClosure(RULE_SET& RuleSet,STATE_SET& ResultSet)
{
	int StateNO,RuleNO;
	STATE state;
	RULE  rule;

	ResultSet = *this;
	if (ResultSet.StateNum == 0) return;
	StateNO = 0;
	while (StateNO < ResultSet.StateNum)  // 对集合中的每个状态
	{
		state = ResultSet.GetState(StateNO);  
		for(RuleNO = 0; RuleNO < RuleSet.GetRuleNum(); RuleNO++)
		{
			rule = RuleSet.GetRule(RuleNO);
			// 若能从此状态经过空弧到达其它状态
			if (rule.oldstate == state && rule.input == NULL) 
				ResultSet.AddState(rule.newstate);
		}
		StateNO++;
	}
}

// 求在规则集 RuleSet 下，本状态集对符号 input 的移动 E 闭包
void STATE_SET::GetMoveResultSet(RULE_SET& RuleSet,SIGN input,STATE_SET& ResultSet)
{
	int       StateNO,RuleNO;
	STATE     state;
	RULE      rule;
	STATE_SET TempSet;

	ResultSet.Reset();
	for(StateNO = 0; StateNO < StateNum; StateNO++) 
	{
		state = pStates[StateNO];   // 对状态集中的每个状态
		for(RuleNO = 0; RuleNO < RuleSet.GetRuleNum(); RuleNO++)
		{
			rule = RuleSet.GetRule(RuleNO);
			// 如果有从此状态出发经过弧 input 到达的状态
			if (rule.oldstate == state && rule.input == input)
				ResultSet.AddState(rule.newstate);
		}
	}
	// 求 E 闭包
	ResultSet.GetNULLClosure(RuleSet,TempSet);
	ResultSet = TempSet;
}

void STATE_SET::Output()
{
	int i;
	for(i = 0; i < StateNum; i++)
		printf("%5d",pStates[i]);
}