rexalgorithm.cpp

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

	startStateSet.insert(m_pStartState);
    setPendingStateSets.insert(startStateSet);

    while( setPendingStateSets.size()>0 ){
        REXA_StateSet curStateSet= *setPendingStateSets.begin();
        setPendingStateSets.erase(curStateSet);
        if( m_mapTransitions.find(curStateSet)==m_mapTransitions.end() ){
            TransitionVector transVector(m_vecCharsets.size());
			for(int i=0;i<m_vecCharsets.size();i++){
				REXA_StateSet::const_iterator it;
				for(it= curStateSet.begin();it!=curStateSet.end();++it){
					for(int j=0;j<(*it)->m_transitions.size();j++){	
						const  REXA_NDFATransition& rTransition= (*it)->m_transitions[j];
						REXA_CharSet charSet= rTransition.m_transChars;
						charSet&= m_vecCharsets[i];
						if( charSet.any() ){
							transVector[i].insert(rTransition.m_nextState);
						}
					}
				}
			}
			m_mapTransitions.insert(make_pair(curStateSet,transVector));
			for(int l=0;l<transVector.size();l++){
				setPendingStateSets.insert(transVector[l]);
			}
        }
    }
}

static REXA_DFAState* GetIllegalState()
{
    static REXA_DFAState illegalState(REXA_DFAState::eNoAnswer,true);
    return &illegalState;
}
static REXA_DFAState* GetEosState()
{
    static bool bFirstTime= true;
    static REXA_DFAState eosState(REXA_DFAState::eEos,true);
    if( bFirstTime ){
        bFirstTime= false;
        for(int i=0;i<sizeof(eosState.aNext)/sizeof(eosState.aNext[0]);i++){
            eosState.aNext[i]= &eosState;
        }
    }
    return &eosState;
}

REXA_DFAState* REXA_DFAState::ms_pIllegalState= ::GetIllegalState();
REXA_DFAState* REXA_DFAState::ms_pEosState= ::GetEosState();

//-------------------------------------------------------------------------------
REXA_DFAState::REXA_DFAState(int nAnwserId,bool bIsFinal)
		:m_nAnwserId(nAnwserId),
         m_bIsFinal(bIsFinal),
         m_bIsAccepting(false)	
//-------------------------------------------------------------------------------
{
    for(int i=0;i<256;i++)	aNext[i]=0;
}

//-------------------------------------------------------------------------------
REXA_DFAState*      REXA_DFAState::Clone()
//-------------------------------------------------------------------------------
{
    map<REXA_DFAState*,REXA_DFAState*> mapStates;
    mapStates.insert(make_pair((REXA_DFAState*)0,(REXA_DFAState*)0));
    mapStates.insert(make_pair(ms_pIllegalState,ms_pIllegalState));
    mapStates.insert(make_pair(ms_pEosState,ms_pEosState));
	return CopyStates(this,mapStates);
}
//-------------------------------------------------------------------------------
REXA_DFAState::REXA_DFAState(const REXA_DFAState& dfaState)
:m_nAnwserId(dfaState.m_nAnwserId),m_bIsFinal(dfaState.m_bIsFinal),
    m_bIsAccepting(dfaState.m_bIsAccepting)
//-------------------------------------------------------------------------------
{
    for(int i=0;i<sizeof(dfaState.aNext)/sizeof(REXA_DFAState*);i++){
        aNext[i]= dfaState.aNext[i];
    }
}
//-------------------------------------------------------------------------------
REXA_DFAState*
                REXA_DFAState::CopyStates      (REXA_DFAState* pState,
                                map<REXA_DFAState*,REXA_DFAState*>& rMapStates)
//-------------------------------------------------------------------------------
{
    pair<map<REXA_DFAState*,REXA_DFAState*>::iterator,bool> itDone= 
			rMapStates.insert(make_pair(pState,(REXA_DFAState*)0));
	if( itDone.second ){
		REXA_DFAState* pNewState= new REXA_DFAState(*pState);
        itDone.first->second= pNewState;
		for(int i=0;i<sizeof(pNewState->aNext)/sizeof(REXA_DFAState*);i++){
			pNewState->aNext[i]=CopyStates(pNewState->aNext[i],rMapStates);
		}
	}
    return itDone.first->second;
}

//-------------------------------------------------------------------------------
static void   CollectStates(REXA_DFAState* pState,
                               map<REXA_DFAState*,int>& rmapStates, 
                               map<int,REXA_DFAState*>& rmapId,
                               int nCount)
//-------------------------------------------------------------------------------
{
    int nStateId= nCount;
    if(pState){
        nStateId= -10;
    }
    else if( pState ){
        if( pState==REXA_DFAState::ms_pIllegalState ){
            nStateId= -2;
        }else if( pState==REXA_DFAState::ms_pEosState ){
            nStateId= -1;
        }else{
            nCount++;
        }
    }
    pair<map<REXA_DFAState*,int>::iterator,bool> itBool= 
                                rmapStates.insert(make_pair(pState,nStateId));
    if( itBool.second ){
        rmapId.insert(make_pair(nStateId,pState));
        for(int i=0;i<256;i++){
            CollectStates((itBool.first->first)->aNext[i],rmapStates,rmapId,
                nCount);
        }
    }
}

//-------------------------------------------------------------------------------
void    REXA_DFAState::CollectStates(REXA_DFAState* pState,set<REXA_DFAState*>& rsetStates)
//-------------------------------------------------------------------------------
{
    if( !pState ) return;

    pair<set<REXA_DFAState*>::iterator,bool> itBool=    rsetStates.insert(pState);
    if( itBool.second ){
        for(int i=0;i<256;i++){
            CollectStates((*itBool.first)->aNext[i],rsetStates);
        }
    }
}

//-----------------------------------------------------------------------------
void    REXA_DFAState::DeleteAll()
//-----------------------------------------------------------------------------
{
    set<REXA_DFAState*> setStates;
    CollectStates(this,setStates);
    set<REXA_DFAState*>::iterator it;
    for(it= setStates.begin();it!=setStates.end();++it){
        if( *it!=ms_pIllegalState && *it!=ms_pEosState ){
            delete *it;
        }
    }
}

//-----------------------------------------------------------------------------
vector<REXA_CharSet> REXA_NDFAToTable::CharsetToVector(const REXA_CharSetSet& rCharSetSet)
//-----------------------------------------------------------------------------
{
	vector<REXA_CharSet> vecCharSet;
	REXA_CharSetSet::const_iterator it;
	for(it= rCharSetSet.begin();it!=rCharSetSet.end();++it){
		vecCharSet.push_back(*it);
	}
	return vecCharSet;
}
//-----------------------------------------------------------------------------
REXA_TranslatingTable::REXA_TranslatingTable    (const REXA_NDFAState* pStartState)
//-----------------------------------------------------------------------------
{
    set<int>                setVisitedStates;
    REXA_CharSetSet              charSets; 
	set<const REXA_NDFAState*>   setStates;
	
	REXA_NDFAState::CollectStates(pStartState,setStates);

	CollectCharSets(pStartState,setVisitedStates,charSets);
	m_vecCharsets=	REXA_NDFAToTable::CharsetToVector(
								ComputeDisjointCharSets(charSets));
    m_pStartState=	pStartState;
	GenerateTranslationTable(setStates);
	ComputeOccCounts();
}


//-----------------------------------------------------------------------------
REXA_NDFAToDfa::REXA_NDFAToDfa	(const REXA_TranslatingTable& rTable)
						:m_rTable(rTable)
//-----------------------------------------------------------------------------
{
	
}
//-----------------------------------------------------------------------------
REXA_DFAState* REXA_NDFAToDfa::CreateDfaStates(
					const REXA_StateSet&				    rStateSet,
					map<REXA_StateSet,REXA_DFAState*>&	rMapStateSetDFAState)
//-----------------------------------------------------------------------------
{  
    pair<map<REXA_StateSet,REXA_DFAState*>::iterator,bool> pairItBool=
			rMapStateSetDFAState.insert(make_pair(rStateSet,(REXA_DFAState*)0));
	if( pairItBool.second ){
		REXA_DFAState* pDFAState= new REXA_DFAState();
		pairItBool.first->second= pDFAState;
		REXA_TranslatingTable::TranslationMap::const_iterator it=
			m_rTable.m_mapTransitions.find(rStateSet);
		if( it!= m_rTable.m_mapTransitions.end() ){
			const TransitionVector& rvecTrans= it->second;
			for(int i=0;i<rvecTrans.size();i++){
				if( rvecTrans[i].size()>0 ){
					REXA_DFAState* pTransState= 
						CreateDfaStates(rvecTrans[i],rMapStateSetDFAState);
					for(int j=0;j<256;j++){
                        if( m_rTable.m_vecCharsets[i][j] ){
                            pDFAState->aNext[j]= pTransState;
                        }
					}
				}
			}
			if( rStateSet.IsAccepting() ){
				int nAnswerCode= m_rTable.GetAnswerCode(rStateSet);
                pDFAState->m_bIsAccepting= true;
                pDFAState->m_nAnwserId= nAnswerCode;
				REXA_DFAState* pAcceptState= 
					new REXA_DFAState(nAnswerCode,true);
                pAcceptState->m_bIsAccepting= true;
                bool bDone= false;
				for(int j=0;j<256;j++){
					if( !pDFAState->aNext[j] ){
						pDFAState->aNext[j]= pAcceptState;
                        bDone= true;
					}
				}
                if(!bDone){
                    delete pAcceptState;
                }
			}else{
				for(int j=0;j<256;j++){
					if( !pDFAState->aNext[j] ){
                        pDFAState->aNext[j]= REXA_DFAState::ms_pIllegalState;
					}
				}
			}
		}
        return pDFAState;
    }
	return  pairItBool.first->second;
}
//-----------------------------------------------------------------------------
REXA_DFAState* REXA_NDFAToDfa::TableToDfaStates()
//-----------------------------------------------------------------------------
{ 
	REXA_StateSet startStateSet;
	startStateSet.insert(m_rTable.m_pStartState);

	map<REXA_StateSet,REXA_DFAState*> mapStateSetDFAState;

    REXA_TranslatingTable::TranslationMap::const_iterator it;
	it= m_rTable.m_mapTransitions.find(startStateSet);
	if( it!=m_rTable.m_mapTransitions.end() ){
        REXA_DFAState* pDFAState= 
		            CreateDfaStates(
					it->first,
					mapStateSetDFAState);
        return pDFAState;
		
    }
    return 0;
}

//-----------------------------------------------------------------------------
REXA_Parser::REXA_Parser     ()
//-----------------------------------------------------------------------------
{
    m_pParserImp= new REXA_ParserImpl();

}
//-----------------------------------------------------------------------------
REXA_Parser::~REXA_Parser    ()
//-----------------------------------------------------------------------------
{
    delete m_pParserImp;
}
//-----------------------------------------------------------------------------
REXA_Parser::REXA_Parser    (const REXA_Parser& parserToCopy)
//-----------------------------------------------------------------------------
{
    m_pParserImp= new REXA_ParserImpl(*parserToCopy.m_pParserImp);
}
//-----------------------------------------------------------------------------
REXA_Parser&    
        REXA_Parser::operator=   (const REXA_Parser& parserToCopy)
//-----------------------------------------------------------------------------
{
    delete m_pParserImp;
    m_pParserImp= new REXA_ParserImpl(*parserToCopy.m_pParserImp);
    return *this;
}

//-----------------------------------------------------------------------------
REXA_DFAState*      REXA_Parser::ParseRegExp     (string strRegExp)
//-----------------------------------------------------------------------------
{
    const REXA_NDFAState*    pNdfa=  m_pParserImp->ParseRegExp(strRegExp);
	REXA_TranslatingTable    table(pNdfa);
	REXA_NDFAToDfa           ndfaToDfa(table);
    return                   ndfaToDfa.TableToDfaStates();
}
//-----------------------------------------------------------------------------
void                REXA_Parser::AddRegDefinition (   string strDefName,
                                                string strDefExpression,
                                                int nAnswer)
//-----------------------------------------------------------------------------
{
    string str= strDefName+ "=" + strDefExpression;
    m_pParserImp->ParseRegExpDefinition(str,nAnswer);
}
//-----------------------------------------------------------------------------
void                REXA_Parser::RemoveRegDefinition (   string strDefName)
//-----------------------------------------------------------------------------
{
    m_pParserImp->m_mapNamedStates.erase(strDefName);
}
//-----------------------------------------------------------------------------
void                REXA_Parser::GetRegDefinitions   (vector<string>& vecDefinitions)
//-----------------------------------------------------------------------------
{
    map<string,REXA_NDFAState*>::iterator it;
    for(it= m_pParserImp->m_mapNamedStates.begin();
        it!=m_pParserImp->m_mapNamedStates.end();
        ++it){
        vecDefinitions.push_back(it->first);
    }
}