auto_machine.cpp

很好用的词法分析器

#include "StdAfx.h"
#include ".\auto_machine.h"
#include "State.h"
#include "set"
#include "algorithm"
#include "list"
using namespace std;
auto_machine::auto_machine(void)
{
}

auto_machine::~auto_machine(void)
{
}

void auto_machine::insert_map(State* HeadState, char InputChar, State* TailState)
{
	ArcNode _arcnode;
	_arcnode.InputChar = InputChar;
	_arcnode.NextState = TailState;
	HeadState->MapTo.push_back( _arcnode );
}

void auto_machine::insert_state(State* StateNode)
{
	if( !inserted( StateNode ) )
		StateCollect.push_back(StateNode);
	return ;
}

bool auto_machine::inserted(State* &StateNode)
{
	list<State*>::iterator it;
	for( it = StateCollect.begin( ); it != StateCollect.end( ); ++it )
		if( (*it)->GrammarName == StateNode->GrammarName && (*it)->StateName == StateNode->StateName )
			break;
	if(it == StateCollect.end())
		return false;
	else
	{
		State* buff = StateNode;
		StateNode = (*it);
		delete buff;
		return true;
	}
}

void auto_machine::insert_endstate( State* endstate )
{
	EndState.push_back( endstate );
}

void auto_machine::_$closure(State* I, set<State*> &closure)
{
	pair< set<State*>::iterator, bool > ret = closure.insert( I );
	if( !ret.second )
		return;
	else
	{
		list<ArcNode> map = I->MapTo;
		list<ArcNode>::iterator it;
		for( it = map.begin(); it != map.end(); ++it )
			if( it->InputChar == '$' )
				_$closure( it->NextState, closure );
		return;
	}	
}

set<State*> auto_machine::_closure(State* I, char InputChar)
{// 状态I通过输入字符InputChar所到状态
	set<State*> closure;
	for(list<ArcNode>::iterator it = I->MapTo.begin(); it != I->MapTo.end(); ++it)
	{
		if(it->InputChar == InputChar)
			closure.insert( it->NextState );
	}
	set<State*>::iterator outerit = closure.begin();
	set<State*>::size_type j = closure.size( );
	for( set<State*>::size_type i = 0; i < j; ++i )
	{//将closure中元素的$闭包的元素加入closure中
		set<State*> _$clo;
		_$closure( *outerit, _$clo );
		for( set<State*>::iterator itx = _$clo.begin( ); itx != _$clo.end( ); ++itx )
			closure.insert( *itx );
		++outerit;
	}
	return closure;
}


void auto_machine::NFA_TO_DFA(auto_machine &DFA)
{// 有穷自动机的确定化.
	DFA.InCharColl = DFAInCharColl;
	set<State*> StartState;
	_$closure( BeginState, StartState );
	State* PreState = new State;
	CombineState( StartState, PreState );
	Define( StartState, &DFA, PreState);
	return;
}

void auto_machine::insert_char(char Input)
{
	InCharColl.insert( Input );
	if( Input != '$' )
		DFAInCharColl.insert( Input );
	return;
}

void auto_machine::CombineState(set<State*> StateCol,State* Combined)
{
	set<State*>::iterator outerit = StateCol.begin();
	Combined->GrammarName = (*outerit)->GrammarName;
	for( set<State*>::iterator it = StateCol.begin( ); it != StateCol.end( ); ++it )
	{
		Combined->StateName += (*it)->StateName;
//		for(list<ArcNode>::iterator inerit = (*it)->MapTo.begin( ); inerit != (*it)->MapTo.end( ); ++inerit )
//			if( !Combined->ArcNode_inserted( *inerit ) && (*inerit).InputChar != '$' )
//				Combined->MapTo.push_back( *inerit );
	}
	return ;
}

void auto_machine::Define(set<State*> GenState, auto_machine *DFA, State* Combined )
{//确定化
	if( DFA->constinserted( Combined ) || !GenState.size( ) )
		return;
	else
	{
		DFA->insert_state( Combined );
		if( Combined->GrammarName == "" )
			DFA->insert_beginstate( Combined );
		for( set<State*>::iterator it = GenState.begin( ); it != GenState.end( ); ++it )
		{//添加DFA的终态集.
			list<State*>::iterator inerit = find( EndState.begin( ), EndState.end( ), *it );
			if( inerit != EndState.end( ) )
			{
				DFA->insert_endstate( Combined );
				break;
			}
		}
		for( set<char>::iterator it = DFAInCharColl.begin( ); it != DFAInCharColl.end( ); ++it )
		{
			set<State*> NewState;
			for( set<State*>::iterator inerit = GenState.begin( ); inerit != GenState.end( ); ++inerit )
			{
				set<State*> buffer = _closure( *inerit, *it );
				for( set<State*>::iterator itx = buffer.begin( ); itx != buffer.end( ); ++itx )
					NewState.insert( *itx );
			}
			State* NextCombined = new State;
			if(NewState.size( ) != 0)
			{
				CombineState( NewState, NextCombined );
				DFA->inserted( NextCombined );
				DFA->insert_map( Combined, *it, NextCombined );
			}
			Define( NewState, DFA, NextCombined );
		}
		return;
	}
}

// DFA最小化
void auto_machine::Minimize(void)
{
}

void auto_machine::insert_beginstate(State* begin)
{
	BeginState = begin;
}
bool auto_machine::constinserted(State* StateNode)
{
	list<State*>::iterator it;
	for( it = StateCollect.begin( ); it != StateCollect.end( ); ++it )
		if( (*it)->GrammarName == StateNode->GrammarName && (*it)->StateName == StateNode->StateName )
			break;
	if(it == StateCollect.end())
		return false;
	else
		return true;
}

void auto_machine::Destroy(void)
{
	for( list<State*>::iterator it = StateCollect.begin( ); it != StateCollect.end( ); ++it )
		delete *it;
}