ToFTAThompson.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#include <global/GlobalData.h>
 
#include <automaton/TA/EpsilonNFTA.h>
 
#include <rte/formal/FormalRTE.h>
#include <rte/formal/FormalRTEElements.h>
 
namespace rte {
 
namespace convert {
 
class ToFTAThompson {
    template < class SymbolType >
    static ext::vector < unsigned > substitutionTargets ( const FormalRTESymbolSubst < SymbolType > & substitutionSymbol, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton ) {
        ext::vector < unsigned > substTargets;
        for ( const std::pair < const ext::variant < unsigned, ext::pair < common::ranked_symbol < SymbolType >, ext::vector < unsigned > > >, unsigned > & transition : automaton.getTransitions ( ) ) {
            if ( transition.first.template is < ext::pair < common::ranked_symbol < SymbolType >, ext::vector < unsigned > > > ( ) ) {
                const ext::pair < common::ranked_symbol < SymbolType >, ext::vector < unsigned > > & source = transition.first.template get < ext::pair < common::ranked_symbol < SymbolType >, ext::vector < unsigned > > > ( );
 
                if ( source.first == substitutionSymbol.getSymbol ( ) )
                    substTargets.push_back ( transition.second );
            }
        }
        return substTargets;
    }
 
public:
    template < class SymbolType >
    static automaton::EpsilonNFTA < SymbolType, unsigned > convert ( const rte::FormalRTE < SymbolType > & rte ) {
        unsigned nextState = 0;
        const unsigned * tailArg = nullptr;
 
        automaton::EpsilonNFTA < SymbolType, unsigned > automaton;
        automaton.setInputAlphabet ( rte.getAlphabet ( ) );
        automaton.addInputSymbols ( rte.getSubstitutionAlphabet ( ) );
 
        rte.getRTE ( ).getStructure ( ).template accept < void, ToFTAThompson::Formal < SymbolType > > ( automaton, nextState, tailArg );
 
        automaton.setInputAlphabet ( rte.getAlphabet ( ) );
 
        automaton.addFinalState ( * tailArg );
        return automaton;
    }
 
    template < class SymbolType >
    class Formal {
    public:
        static void visit ( const FormalRTEAlternation    < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg );
        static void visit ( const FormalRTESubstitution   < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg );
        static void visit ( const FormalRTEIteration      < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg );
        static void visit ( const FormalRTESymbolAlphabet < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg );
        static void visit ( const FormalRTESymbolSubst    < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg );
        static void visit ( const FormalRTEEmpty          < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg );
    };
};
 
template < class SymbolType >
void ToFTAThompson::Formal < SymbolType >::visit ( const rte::FormalRTEAlternation < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg ) {
    unsigned state = nextState ++;
    automaton.addState ( state );
 
    node.getLeftElement ( ).template accept < void, ToFTAThompson::Formal < SymbolType > > ( automaton, nextState, tailArg );
    automaton.addTransition ( * tailArg, state );
 
    node.getRightElement ( ).template accept < void, ToFTAThompson::Formal < SymbolType > > ( automaton, nextState, tailArg );
    automaton.addTransition ( * tailArg, state );
 
    tailArg = & * automaton.getStates ( ).find ( state );
}
 
template < class SymbolType >
void ToFTAThompson::Formal < SymbolType >::visit ( const rte::FormalRTESubstitution < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg ) {
    node.getLeftElement ( ).template accept < void, ToFTAThompson::Formal < SymbolType > > ( automaton, nextState, tailArg );
    const unsigned * result = tailArg;
 
    ext::vector < unsigned > substTargets = substitutionTargets ( node.getSubstitutionSymbol ( ), automaton );
 
    for ( unsigned substTarget : substTargets ) {
        automaton.removeTransition ( node.getSubstitutionSymbol ( ).getSymbol ( ), { }, substTarget);
    }
 
    node.getRightElement ( ).template accept < void, ToFTAThompson::Formal < SymbolType > > ( automaton, nextState, tailArg );
 
    for ( unsigned substTarget : substTargets ) {
        automaton.addTransition ( * tailArg, substTarget );
    }
 
    tailArg = result;
}
 
template < class SymbolType >
void ToFTAThompson::Formal < SymbolType >::visit ( const rte::FormalRTEIteration < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg ) {
    unsigned state = nextState ++;
 
    node.getElement ( ).template accept < void, ToFTAThompson::Formal < SymbolType > > ( automaton, nextState, tailArg );
 
    ext::vector < unsigned > substTargets = substitutionTargets ( node.getSubstitutionSymbol ( ), automaton );
 
    automaton.addState ( state );
    for ( unsigned substTarget : substTargets ) {
        std::cout << "eps transition from " << * tailArg << " to " << substTarget << std::endl;
        automaton.addTransition ( * tailArg, substTarget );
    }
 
    automaton.addTransition ( * tailArg, state );
    automaton.addTransition ( node.getSubstitutionSymbol ( ).getSymbol ( ), { }, state );
 
    tailArg = & * automaton.getStates ( ).find ( state );
}
 
template < class SymbolType >
void ToFTAThompson::Formal < SymbolType >::visit ( const rte::FormalRTESymbolAlphabet < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg ) {
    unsigned state = nextState ++;
    automaton.addState ( state );
    ext::vector < unsigned > from;
    for ( const rte::FormalRTEElement < SymbolType > & c : node.getElements ( ) ) {
        c.template accept < void, ToFTAThompson::Formal < SymbolType > > ( automaton, nextState, tailArg );
        from.push_back ( * tailArg );
    }
    automaton.addTransition ( node.getSymbol ( ), from, state );
    tailArg = & * automaton.getStates ( ).find ( state );
}
 
template < class SymbolType >
void ToFTAThompson::Formal < SymbolType >::visit ( const rte::FormalRTESymbolSubst < SymbolType > & node, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg ) {
    unsigned state = nextState ++;
    automaton.addState ( state );
    automaton.addTransition ( node.getSymbol ( ), { }, state );
    tailArg = & * automaton.getStates ( ).find ( state );
}
 
template < class SymbolType >
void ToFTAThompson::Formal < SymbolType >::visit ( const rte::FormalRTEEmpty < SymbolType > &, automaton::EpsilonNFTA < SymbolType, unsigned > & automaton, unsigned & nextState, const unsigned * & tailArg ) {
    unsigned state = nextState ++;
    automaton.addState ( state );
    tailArg = & * automaton.getStates ( ).find ( state );
}
 
} /* namespace convert */
 
} /* namespace rte */