machine.cpp

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

#include "Machine.h"

FiniteAutomata::FiniteAutomata()
{
}

FiniteAutomata::~FiniteAutomata()
{
	RuleSet.Reset();
	StartSet.Reset();
	EndSet.Reset();
}

void FiniteAutomata::AddRule(RULE rule)
{
	RuleSet.AddRule(rule);
}

void FiniteAutomata::AddStartState(STATE state)
{
	StartSet.AddState(state);
}

void FiniteAutomata::AddEndState(STATE state)
{
	EndSet.AddState(state);
}

void FiniteAutomata::Reset()
{
	RuleSet.Reset();
	StartSet.Reset();
	EndSet.Reset();
}

//********************************************************	
// 有限自动机确定化，用 TransTable 存放转换表
void FiniteAutomata::TransformToDFA(TABLE& TransTable)
{
	TABLE_LINE  Line;	
	STATE_SET   ResultSet;
	int         Row,Col,no;
	bool        exist;
    // 填写第一行第一列
	Line.Cols   = RuleSet.GetSignNum() + 1;
	Line.pGrids = new STATE_SET[Line.Cols];

	StartSet.GetNULLClosure(RuleSet,ResultSet);
	Line.pGrids[0] = ResultSet;
	TransTable.AddLine(Line);
	Line.Reset();

	for(Row = 0; Row < TransTable.GetLineNum(); Row++)
	{
		for(Col = 1; Col <= RuleSet.GetSignNum(); Col++)
		{   // 填写一个格子
			TransTable[Row][0].GetMoveResultSet(RuleSet,RuleSet.GetSign(Col-1),ResultSet);
			TransTable[Row][Col] = ResultSet;
			// 检查新的结果是否已经在第一列中存在
			exist = false;
			if (ResultSet.GetStateNum() != 0)
			{
				for(no = 0; !exist && no < TransTable.GetLineNum(); no++)
					if (TransTable[no][0] == ResultSet) exist = true;
			}
			else
				exist = true;
			// 如果不存在,则添加一个新行，且令第一格等于结果
			if(!exist)
			{   
				Line.Reset();
				Line.Cols   = RuleSet.GetSignNum() + 1;
				Line.pGrids = new STATE_SET[Line.Cols];
				Line.pGrids[0] = ResultSet;

				TransTable.AddLine(Line);
			}			
		}
	}	
	// 根据转换矩阵构造 DFA
	STATE_SET   Temp;	
	RULE        Rule;
	RULE_SET    NewRuleSet;	
	bool        IsFinalState; 

	ResultSet = EndSet;		
	StartSet.Reset();
	EndSet.Reset();

	StartSet.AddState(0);
	for(Row = 0; Row < TransTable.GetLineNum(); Row++) 
	{
		for(Col = 1; Col <= RuleSet.GetSignNum(); Col++)
		{
			// 查找格子中的状态集的编号
			Temp = TransTable[Row][Col];
			if (Temp.GetStateNum() == 0) continue;  // 格子为空

			for(no = 0; no < TransTable.GetLineNum(); no++)
				if (Temp == TransTable[no][0]) break;			
			// 添加一条规则
			Rule.oldstate = Row;
			Rule.newstate = no;
			Rule.input    = RuleSet.GetSign(Col - 1);
			NewRuleSet.AddRule(Rule);
			// 查看该状态集是否包含 NFA 的终态,即是否是 DFA 的终态
			IsFinalState = false;
			for(no = 0; !IsFinalState && no < Temp.GetStateNum(); no++)
				if (ResultSet.StateInSet(Temp.GetState(no))) IsFinalState = true;

			if (IsFinalState)
				EndSet.AddState(Rule.newstate);
		}
	}
	RuleSet = NewRuleSet;	
}
//********************************************************