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();
}

//********************************************************	
void FiniteAutomata::TransformToDFA()
{
	TABLE_LINE  Line;
	TABLE       Table;
	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;
	Table.AddLine(Line);
	Line.Reset();

	for(Row = 0; Row < Table.GetLineNum(); Row++)
	{
		for(Col = 1; Col <= RuleSet.GetSignNum(); Col++)
		{   // 填写一个格子
			Table[Row][0].GetMoveResultSet(RuleSet,RuleSet.GetSign(Col-1),ResultSet);
			Table[Row][Col] = ResultSet;
			// 检查新的结果是否已经在第一列中存在
			exist = false;
			if (ResultSet.GetStateNum() != 0)
			{
				for(no = 0; !exist && no < Table.GetLineNum(); no++)
					if (Table[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;

				Table.AddLine(Line);
			}			
		}
	}

	// 输出	
	printf("确定化过程中构造的转换矩阵表:\n");
	for(Row = 0; Row < Table.GetLineNum(); Row++)
	{
		printf("\n\n第%d行\n",Row + 1);
		for(Col = 0; Col <= RuleSet.GetSignNum(); Col++)
		{
			printf("\n第%d列",Col);
			Table[Row][Col].Output();
		}
	}
	// 根据转换矩阵构造 DFA
	STATE_SET   Temp;	
	RULE        Rule;
	RULE_SET    NewRuleSet;	
	bool        IsFinalState; 

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

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

			for(no = 0; no < Table.GetLineNum(); no++)
				if (Temp == Table[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;
	// 输出生成的 DFA
	printf("\n\n生成的DFA:\n");
	printf("开始状态:  0\n");
	printf("终止状态:  ");	EndSet.Output();

	printf("\n规则集合:\n");
	printf("%10s%10s%10s\n","原状态","输入","新状态");
	for(no = 0; no < RuleSet.GetRuleNum(); no++)
	{
		Rule = RuleSet.GetRule(no);
		printf("%10d",Rule.oldstate);
		if (Rule.input == 0)   printf("%10s","NULL");
		else                   printf("%10c",Rule.input);
		printf("%10d\n",Rule.newstate);
	}	
}
//********************************************************