rexalgorithm.cpp

关于使用正则进行词法分析的程序

	}
	//2. if 'pState0' is accepting 
	//   add all transitions from 'pState1'  to 'pState0'
	if( pState0->m_isAccepting ){
		pState0->m_transitions.insert(	pState0->m_transitions.end(),
										pState1->m_transitions.begin(),
										pState1->m_transitions.end());
        if(pState1->m_isAccepting){
            bMakeState0Accepting= true;
        }
	}
	//3. accepting states of F1 are accepting states of the catenation
	//   accepting states of F0 are no langer accepting
	for(int j=0;j<vecAccepting.size();j++){
		vecAccepting[j]->m_isAccepting= false;
	}
    if(bMakeState0Accepting ){
        pState0->m_isAccepting= true;
    }
    return pState0;
}
//-----------------------------------------------------------------------------
REXA_NDFAState* REXA_ParserImpl::Union          (REXA_NDFAState* pState0,REXA_NDFAState* pState1)
//-----------------------------------------------------------------------------
{ //1. 'pState0' gets also the transitions of 'pState1'. 'pState0' is the start state
	pState0->m_transitions.insert(	pState0->m_transitions.end(),
									pState1->m_transitions.begin(),
									pState1->m_transitions.end());
 //2. if one of the start states is accepting the new start state is also accepting
	if( pState1->m_isAccepting ){
		pState0->m_isAccepting= true;
	} 
    return pState0;
}
//-----------------------------------------------------------------------------
REXA_NDFAState* REXA_ParserImpl::MakeStar       (REXA_NDFAState* pState)
//-----------------------------------------------------------------------------
{ // //1. for each transition  leading from state q to an accepting state 
	//   add a transition leading from q to 'pState
    vector<pair<REXA_NDFAState*,REXA_NDFATransition> > vecTrans= 
								CollectAcceptingTransitions(pState);
	for(int i=0;i<vecTrans.size();i++){
		vecTrans[i].first->m_transitions.push_back(
			REXA_NDFATransition(vecTrans[i].second.m_transChars,pState));
	}
    //2. pState gets accepting
	pState->m_isAccepting=true;
    return pState;
}
//-----------------------------------------------------------------------------
REXA_NDFAState* REXA_ParserImpl::MakePlus       (REXA_NDFAState* pState)
//-----------------------------------------------------------------------------
{ 
    return Concat(pState,MakeStar(CloneNDFA(pState)));
}
//-----------------------------------------------------------------------------
REXA_NDFAState* REXA_ParserImpl::MakeOptional   (REXA_NDFAState* pState)
//-----------------------------------------------------------------------------
{ //start state gets optional
    pState->m_isAccepting= true;
	return pState;
}
//-----------------------------------------------------------------------------
REXA_NDFAState* REXA_ParserImpl::MakeIgnoreCase (REXA_NDFAState* pState)
//-----------------------------------------------------------------------------
{
    set<REXA_NDFAState*>     setStates;
    REXA_NDFAState::CollectStates(pState,setStates);
    set<REXA_NDFAState*>::iterator it;
    for(it= setStates.begin();it!=setStates.end();++it){
        for(int i=0;i<(*it)->m_transitions.size();i++){
            for(int j=0;j<(*it)->m_transitions[i].m_transChars.size();j++){
                if(     (*it)->m_transitions[i].m_transChars[j]
                    &&  isupper(j) ){
                    (*it)->m_transitions[i].
                        m_transChars[(unsigned char)(tolower(j))]= true;
                }
                if(     (*it)->m_transitions[i].m_transChars[j]
                    &&  islower(j) ){
                    (*it)->m_transitions[i].
                        m_transChars[(unsigned char)(toupper(j))]= true;
                }
            }
        }
    }
    return pState;
}

//NDFA-Automaton helper  functions
//-----------------------------------------------------------------------------
vector<REXA_NDFAState*>  REXA_ParserImpl::CollectAcceptingStates(REXA_NDFAState* pState)
//-----------------------------------------------------------------------------
{
    set<REXA_NDFAState*>     setStates;
    vector<REXA_NDFAState*>  vecAcceptingStates;
    REXA_NDFAState::CollectStates(pState,setStates);
    set<REXA_NDFAState*>::iterator it;
    for(it= setStates.begin();it!=setStates.end();++it){
        if( (*it)->m_isAccepting ){
            vecAcceptingStates.push_back(*it);
        }
    }
    return vecAcceptingStates;
}

//-----------------------------------------------------------------------------
vector<pair<REXA_NDFAState*,REXA_NDFATransition> >	
			REXA_ParserImpl::CollectAcceptingTransitions(REXA_NDFAState*	pState)
//-----------------------------------------------------------------------------
{
	vector<pair<REXA_NDFAState*,REXA_NDFATransition> > vecStatTrans;

	set<REXA_NDFAState*> setStates;
    REXA_NDFAState::CollectStates(pState,setStates);
	set<REXA_NDFAState*>::iterator	it;
	for(it= setStates.begin();it!=setStates.end();++it){
        for(int i=0;i<(*it)->m_transitions.size();i++){
            if( (*it)->m_transitions[i].m_nextState->m_isAccepting ){
                vecStatTrans.push_back(make_pair(*it,(*it)->m_transitions[i]));
            }
        }
    }
	return vecStatTrans;
}

//-------------------------------------------------------------------------------
int  REXA_ParserImpl::NextStateId                  ()
//-------------------------------------------------------------------------------
{
    return m_nStateIdMax++;
}
//-------------------------------------------------------------------------------
REXA_NDFAState*   REXA_ParserImpl::CloneNDFA(REXA_NDFAState* pToClone)
//-------------------------------------------------------------------------------
{
    set<REXA_NDFAState*> setStates;
    REXA_NDFAState* pState= pToClone->Clone();
    REXA_NDFAState::CollectStates(pState,setStates);
    set<REXA_NDFAState*>::const_iterator it;
    for(it= setStates.begin();it!=setStates.end();++it){
        (*it)->m_id= NextStateId();
        m_vecAllStates.push_back(*it);
    }
    return pState;
}
//-------------------------------------------------------------------------------
REXA_NDFAState*   REXA_ParserImpl::GetNewNDFAState(int id,bool isAccepting)
//-------------------------------------------------------------------------------
{
    REXA_NDFAState* pState= new REXA_NDFAState(id,isAccepting);
    m_vecAllStates.push_back(pState);
    return pState;
}

//-----------------------------------------------------------------------------
void    REXA_NDFAState::DeleteAll()
//-----------------------------------------------------------------------------
{
    set<const REXA_NDFAState*> setStates;
    CollectStates(this,setStates);
    set<const REXA_NDFAState*>::iterator it;
    for(it= setStates.begin();it!=setStates.end();++it){
        delete *it;
    }
}
//-------------------------------------------------------------------------------
void         REXA_NDFAState::CollectStates(const REXA_NDFAState* pState,set<const REXA_NDFAState*>& rsetStates)
//-------------------------------------------------------------------------------
{
    pair<set<const REXA_NDFAState*>::iterator,bool> itBool=    rsetStates.insert(pState);
    if( itBool.second ){
        for(int i=0;i<(*itBool.first)->m_transitions.size();i++){
            CollectStates((*itBool.first)->m_transitions[i].m_nextState,rsetStates);
        }
    }
}
//-------------------------------------------------------------------------------
void         REXA_NDFAState::CollectStates   (REXA_NDFAState* pState,
                                            set<REXA_NDFAState*>& rsetStates)
//-------------------------------------------------------------------------------
{
    pair<set<REXA_NDFAState*>::iterator,bool> itBool=    rsetStates.insert(pState);
    if( itBool.second ){
        for(int i=0;i<(*itBool.first)->m_transitions.size();i++){
            CollectStates((*itBool.first)->m_transitions[i].m_nextState,rsetStates);
        }
    }
}
//-------------------------------------------------------------------------------
REXA_NDFAState*  REXA_NDFAState::CopyStates      
                        (REXA_NDFAState* pState,map<REXA_NDFAState*,REXA_NDFAState*>& rMapStates)
//-------------------------------------------------------------------------------
{
	pair<map<REXA_NDFAState*,REXA_NDFAState*>::iterator,bool> itDone= 
			rMapStates.insert(make_pair(pState,(REXA_NDFAState*)0));
	if( itDone.second ){
		REXA_NDFAState* pNewState= new REXA_NDFAState(*pState);
        itDone.first->second= pNewState;
		for(int i=0;i<pNewState->m_transitions.size();i++){
			pNewState->m_transitions[i].m_nextState=
				CopyStates(pNewState->m_transitions[i].m_nextState,rMapStates);
		}
	}
    return itDone.first->second;
}


//-----------------------------------------------------------------------------
REXA_NDFAState*		REXA_NDFAState::Clone()
//-----------------------------------------------------------------------------
{
	map<REXA_NDFAState*,REXA_NDFAState*> mapStates;
	return CopyStates(this,mapStates);
}

//-----------------------------------------------------------------------------
bool	REXA_StateSet::IsAccepting	()const
//-----------------------------------------------------------------------------
{
	REXA_StateSet::const_iterator it;
	for(it= begin();it!=end();++it){
		if( (*it)->m_isAccepting ){
			return true;
		}
	}
	return false;
}

//-----------------------------------------------------------------------------
int				REXA_TranslatingTable::GetAnswerCode	(const REXA_StateSet& rSet)const
//-----------------------------------------------------------------------------
{	
	REXA_StateSet::const_iterator it;
	int nAnswerCode=	REXA_DFAState::eNoAnswer;
	int nMinCount=		INT_MAX;
	for(it= rSet.begin();it!=rSet.end();++it){
		MapStateOccurrenceCount::const_iterator itMap=
			m_mapStateOccurrenceCount.find((*it));
		if( itMap!=m_mapStateOccurrenceCount.end() ){
			if( itMap->second<nMinCount ){
				nMinCount=		itMap->second;
				nAnswerCode=	itMap->first->m_nAnswer;
			}
		}
	}
	return nAnswerCode;
}
//-----------------------------------------------------------------------------
void			REXA_TranslatingTable::ComputeOccCounts	()
//-----------------------------------------------------------------------------
{	//computes the occurrences of all states with an existing answer code
	TranslationMap::const_iterator it;
	for(	it= m_mapTransitions.begin();
			it!=m_mapTransitions.end();
			++it){
				REXA_StateSet::const_iterator it1;
				for( it1= it->first.begin();it1!=it->first.end();++it1){
					if(		(*it1)->m_isAccepting 
						&&	(*it1)->m_nAnswer!=REXA_DFAState::eNoAnswer){
						pair<MapStateOccurrenceCount::iterator,bool> pairRes=
							m_mapStateOccurrenceCount.insert(make_pair(*it1,1));
						if( !pairRes.second ){
							pairRes.first->second++;
						}
					}
				}
			}
}

//-----------------------------------------------------------------------------
set<REXA_CharSet,REXA_LessCharSet> 
            REXA_TranslatingTable::ComputeDisjointCharSets(REXA_CharSetSet& rCharSets)
//-----------------------------------------------------------------------------
{
    vector< REXA_CharSetSet > charSets(256);
    vector< REXA_CharSet >    unionSets(256);
    REXA_CharSetSet           resultSet;
    REXA_CharSetSet::const_iterator it;
    for(it= rCharSets.begin();it!=rCharSets.end();++it){
        charSets[it->count()].insert(*it);
    }

//cumulative union
    for(int k= 1;k<256;k++){
        for(int j=0;j<k;j++){
            for(it= charSets[j].begin();it!= charSets[j].end();++it){
                unionSets[k]|= *it;
            }
        }
    }

//reduce charset into disjoint charsets
    for(int l=0;l<256;l++){
        for(it= charSets[l].begin();it!= charSets[l].end();++it){
            REXA_CharSet reducedSet= *it;
            REXA_CharSet unionSet= ~unionSets[l];
            reducedSet&= unionSet;
            resultSet.insert(reducedSet);
        }
    }

    return resultSet;
}
//-----------------------------------------------------------------------------
void REXA_TranslatingTable::CollectCharSets(const REXA_NDFAState* pCurState,
                     set<int>& rVisitedStates,
                     REXA_CharSetSet& rCharSets)
//-----------------------------------------------------------------------------
{
    if( rVisitedStates.find(pCurState->m_id) == rVisitedStates.end() ){
        rVisitedStates.insert(pCurState->m_id);
        for(int i=0;i<pCurState->m_transitions.size();i++){
            if( pCurState->m_transitions[i].m_transChars.count()!=0 ){
                rCharSets.insert(pCurState->m_transitions[i].m_transChars);
                CollectCharSets(
					pCurState->m_transitions[i].m_nextState,
					rVisitedStates,rCharSets);
            }
        }
    }
}



//# Generates a translation table from the NDFA-states present in 'vecpStates'
//example: NDFA having the States S,A,E.  S('a') -> A. S('a') -> E. A('b') -> A. A('b') -> E.
//TranslationTable: 
//  REXA_StateSet    'a'     'b'
//--------------------------
//    {S}      {A,E}    
//   {A,E}             {A,E}
// corresponding DFA: {S}('a') -> {A,E}. {A,E}('b') -> {A,E}
//-----------------------------------------------------------------------------
void REXA_TranslatingTable::GenerateTranslationTable(set<const REXA_NDFAState*>& rSetState)
//-----------------------------------------------------------------------------
{
    set< REXA_StateSet > setPendingStateSets;
	REXA_StateSet startStateSet;