ToFTAGlushkov.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#include <alib/set>
#include <alib/variant>
 
#include <global/GlobalData.h>
 
#include <automaton/TA/NFTA.h>
#include <rte/formal/FormalRTE.h>
 
#include "../glushkov/GlushkovFollow.h"
#include "../glushkov/GlushkovIndexate.h"
#include "../glushkov/GlushkovFirst.h"
 
namespace rte {
 
namespace convert {
 
class ToFTAGlushkov {
private:
    template < class SymbolType >
    static common::ranked_symbol < SymbolType > phi ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symbol ) {
        return common::ranked_symbol < SymbolType > ( symbol.getSymbol ( ).first, symbol.getRank ( ) );
    }
 
public:
    template < class SymbolType >
    static automaton::NFTA < SymbolType, ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > convert ( const rte::FormalRTE < SymbolType > & rte );
};
 
template < class SymbolType >
automaton::NFTA < SymbolType, ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > ToFTAGlushkov::convert ( const rte::FormalRTE < SymbolType > & rte ) {
 
    // step 1; index RTE
    rte::FormalRTE < ext::pair < SymbolType, unsigned > > indexedRTE = rte::GlushkovIndexate::index ( rte );
 
    // step 2; compute:
    // - first set
    // - follow set for every element of (non-indexed) RTE alphabet element
    const ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > firstSet = rte::GlushkovFirst::first ( indexedRTE );
    const ext::map < common::ranked_symbol < ext::pair < SymbolType, unsigned > >, TFollowTuple < SymbolType > > followSet = rte::GlushkovFollow::follow ( indexedRTE );
 
    /* check for exceptions -> there must be NO substitution symbol in first set */
    if ( ! ext::excludes ( firstSet.begin ( ), firstSet.end ( ), indexedRTE.getSubstitutionAlphabet ( ).begin ( ), indexedRTE.getSubstitutionAlphabet ( ).end ( ) ) )
        throw exception::CommonException ( "GlushkovRTE: Substitution symbol appeared in the first set" );
    /* check end */
 
    /* check for exceptions -> there must be NO substitution symbol in follow sets */
    for ( const std::pair < const common::ranked_symbol < ext::pair < SymbolType, unsigned > >, TFollowTuple < SymbolType > > & kv : followSet ) {
        const TFollowTuple < SymbolType > & followTuple = kv.second; // TFollowTuple = vector < set < ranked_symbol > >
        for ( const ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > & followTupleElem : followTuple )
            if ( ! ext::excludes ( followTupleElem.begin ( ), followTupleElem.end ( ), indexedRTE.getSubstitutionAlphabet ( ).begin ( ), indexedRTE.getSubstitutionAlphabet ( ).end ( ) ) )
                throw exception::CommonException ( "GlushkovRTE: Substitution symbol appeared in a follow set" );
    }
    /* check end */
 
    // step 3; create PDA (w/o transitions yet) and initialize input alphabet = (non-indexed) RTE alphabet and END symbol
    automaton::NFTA < SymbolType, ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > automaton;
 
    for ( const common::ranked_symbol < SymbolType > & symbol : rte.getAlphabet ( ) )
        automaton.addInputSymbol ( symbol );
 
    // step 4; create pushdown store alphabet;
 
    // simple
    for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symb : indexedRTE.getAlphabet ( ) )
        automaton.addState ( ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > ( { symb } ) );
 
    // complex
    // any element (set) from any follow tuple is a complex state
    for ( const std::pair < const common::ranked_symbol < ext::pair < SymbolType, unsigned > >, TFollowTuple < SymbolType > > & kv : followSet ) {
        const TFollowTuple < SymbolType > & followTuple = kv.second; // TFollowTuple = vector < set < ranked_symbol > >
        for ( const ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > & followTupleElem : followTuple )
            automaton.addState ( followTupleElem );
    }
 
    // add final states
    for ( const auto & symbol : firstSet )
        automaton.addFinalState ( ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > ( { symbol } ) );
 
    /* DEBUG */
    if ( common::GlobalData::verbose ) {
        common::Streams::err << "---------------------------------------------------------" << std::endl;
        common::Streams::err << "RTE:" << std::endl;
        for ( const auto & symbol : indexedRTE.getAlphabet ( ) )
            common::Streams::err << "\t" << symbol << std::endl;
        common::Streams::err << std::endl;
 
        common::Streams::err << "First(RTE):" << std::endl;
        for ( const auto & symbol : firstSet )
            common::Streams::err << "\t" << symbol << std::endl;
        common::Streams::err << std::endl;
 
        for ( const std::pair < const common::ranked_symbol < ext::pair < SymbolType, unsigned > >, TFollowTuple < SymbolType > > & kv : followSet ) {
            common::Streams::err << "Follow(RTE, " << kv.first << "):" << std::endl;
 
            if ( kv.second.empty ( ) )
                common::Streams::err << "\t" << "{}" << std::endl;
 
            const TFollowTuple < SymbolType > & followTuple = kv.second; // TFollowTuple = vector < set < ranked_symbol > >
            common::Streams::err << " \t - FollowTuple:" << std::endl;
            for ( const ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > & child : followTuple )
                common::Streams::err << "\t\t - " << child << std::endl;
 
            common::Streams::err << std::endl;
        }
 
        common::Streams::err << "---------------------------------------------------------" << std::endl;
        common::Streams::err << "FTA:" << std::endl;
        common::Streams::err << " states: " << automaton.getStates ( ) << std::endl;
        common::Streams::err << "fstates: " << automaton.getFinalStates ( ) << std::endl;
        common::Streams::err << "symbols: " << automaton.getInputAlphabet ( ) << std::endl;
        common::Streams::err << std::endl;
    }
    /* DEBUG END */
 
    /* TRANSITIONS */
    // Pattern 3 and 2
    for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symb : indexedRTE.getAlphabet ( ) ) {
        ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > stateTo ( { symb } );
 
        if ( symb.getRank ( ) == 0 ) {
            if ( common::GlobalData::verbose ) {
                common::Streams::err << "Transition 3: " << phi ( symb ) << " -> " <<  stateTo << std::endl;
            }
            automaton.addTransition ( phi ( symb ), { }, std::move ( stateTo ) );
        } else {
            const TFollowTuple < SymbolType > & followTuple = followSet.at ( symb ); //tuple = vector < set < symb > >
            ext::vector < ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > stateFrom;
 
            for ( const auto & e : followTuple )
                stateFrom.push_back ( e );
 
            if ( common::GlobalData::verbose ) {
                common::Streams::err << "Transition 2: " << phi ( symb ) << " ( " << stateFrom << " ) -> " << stateTo << std::endl;
            }
            automaton.addTransition ( phi ( symb ), std::move ( stateFrom ), std::move ( stateTo ) );
        }
    }
 
    // Pattern 1
    // if a symbol is in some FollowTuple's element (lets call it X), then create transition: a4 ( Follow(a4) ) -> X
    for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symb : indexedRTE.getAlphabet ( ) ) {
        for ( const std::pair < const common::ranked_symbol < ext::pair < SymbolType, unsigned > >, TFollowTuple < SymbolType > > & symbolFollowMapPair : followSet ) {
            const TFollowTuple < SymbolType > & followTuple = symbolFollowMapPair.second;
            for ( const ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > & followTupleElem : followTuple ) {
                // pokud je symb v followTupleElem....
                if ( followTupleElem.count ( symb ) == 0 )
                    continue;
 
                const TFollowTuple < SymbolType > & symbFollowTuple = followSet.at ( symb );
                ext::vector < ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > stateFrom;
                ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > stateTo = followTupleElem;
 
                for ( const auto & e : symbFollowTuple )
                    stateFrom.push_back ( e );
 
                if ( common::GlobalData::verbose ) {
                    common::Streams::err << "Transition 1" << ( stateFrom.empty() ? "a" : "b" ) <<  ": " << phi ( symb ) << " ( " << stateFrom << " ) -> " << stateTo << std::endl;
                }
 
                automaton.addTransition ( phi ( symb ), std::move ( stateFrom ), std::move ( stateTo ) );
            }
        }
    }
 
    /* TRANSITIONS END */
 
    return automaton;
}
 
} /* namespace convert */
 
} /* namespace rte */