ToPostfixPushdownAutomatonGlushkovNaive.h

Go to the documentation of this file.

 
#pragma once
 
#include <global/GlobalData.h>
 
#include <automaton/PDA/NPDA.h>
#include <rte/formal/FormalRTE.h>
// #include <rte/unbounded/UnboundedRegExp.h>
#include <alphabet/BottomOfTheStackSymbol.h>
#include <alphabet/EndSymbol.h>
 
#include "../glushkov/GlushkovFollowNaive.h"
#include "../glushkov/GlushkovIndexate.h"
#include "../glushkov/GlushkovFirst.h"
 
namespace rte {
 
namespace convert {
 
class ToPostfixPushdownAutomatonGlushkovNaive {
    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::NPDA < ext::variant < common::ranked_symbol < SymbolType >, alphabet::EndSymbol >, ext::variant < common::ranked_symbol < ext::pair < SymbolType, unsigned > >, alphabet::BottomOfTheStackSymbol >, char > convert ( const rte::FormalRTE < SymbolType > & rte );
};
 
template < class SymbolType >
automaton::NPDA < ext::variant < common::ranked_symbol < SymbolType >, alphabet::EndSymbol >, ext::variant < common::ranked_symbol < ext::pair < SymbolType, unsigned > >, alphabet::BottomOfTheStackSymbol >, char > ToPostfixPushdownAutomatonGlushkovNaive::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
    const ext::set < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > firstSet = rte::GlushkovFirst::first ( indexedRTE );
 
     // - follow set for every element of (non-indexed) RTE alphabet element
    ext::map < common::ranked_symbol < ext::pair < SymbolType, unsigned > >, ext::set < ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > > > followSet;
 
    for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symbol : indexedRTE.getAlphabet ( ) )
        followSet.insert ( std::make_pair ( symbol, rte::GlushkovFollowNaive::follow ( indexedRTE, symbol ) ) );
 
     /* check for exceptions -> there must be NO substitution symbol in first or follow sets */
    if ( ! ext::excludes ( firstSet.begin ( ), firstSet.end ( ), indexedRTE.getSubstitutionAlphabet ( ).begin ( ), indexedRTE.getSubstitutionAlphabet ( ).end ( ) ) )
        throw exception::CommonException ( "GlushkovRTE: Substitution symbol appeared in the first set" );
 
    for ( const auto & kv : followSet )
        for ( const auto & followTuple : kv.second )
            for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & followTupleElem : followTuple )
                if ( indexedRTE.getSubstitutionAlphabet ( ).count ( followTupleElem ) )
                    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
    char q = 'q';
    char f = 'f';
    automaton::NPDA < ext::variant < common::ranked_symbol < SymbolType >, alphabet::EndSymbol >, ext::variant < common::ranked_symbol < ext::pair < SymbolType, unsigned > >, alphabet::BottomOfTheStackSymbol >, char > automaton ( q, alphabet::BottomOfTheStackSymbol { } );
 
    automaton.addState ( f );
    automaton.addFinalState ( f );
 
    for ( const common::ranked_symbol < SymbolType > & symbol : rte.getAlphabet ( ) )
        automaton.addInputSymbol ( symbol );
 
    automaton.addInputSymbol ( alphabet::EndSymbol { } );
 
     // step 4; create pushdown store alphabet; it consists of elements of indexed RTE alphabet and BotS symbol
    for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symb : indexedRTE.getAlphabet ( ) )
        automaton.addPushdownStoreSymbol ( symb );
 
     /* DEBUG */
    if ( common::GlobalData::verbose ) {
        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 auto & kv : followSet ) {
            common::Streams::err << "Follow(RTE, " << kv.first << "):" << std::endl;
 
            if ( kv.second.empty ( ) )
                common::Streams::err << "\t" << "{}" << std::endl;
 
            for ( const auto & follow : kv.second ) {
                for ( const auto & symbol : follow )
                    common::Streams::err << "\t" << symbol << std::endl;
 
                common::Streams::err << std::endl;
            }
 
            common::Streams::err << std::endl;
        }
    }
    /* DEBUG END */
 
    for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symb : indexedRTE.getAlphabet ( ) ) {
        if ( symb.getRank ( ) == 0 )
            automaton.addTransition ( q, phi ( symb ), { }, q, { symb } );
        else
            for ( const ext::vector < common::ranked_symbol < ext::pair < SymbolType, unsigned > > > & follow : followSet[symb] ) {
                ext::vector < ext::variant < common::ranked_symbol < ext::pair < SymbolType, unsigned > >, alphabet::BottomOfTheStackSymbol > > fstring ( follow.rbegin ( ), follow.rend ( ) );
                automaton.addTransition ( q, phi ( symb ), fstring, q, { symb } );
            }
 
    }
 
    for ( const common::ranked_symbol < ext::pair < SymbolType, unsigned > > & symb : firstSet ) {
        ext::vector < ext::variant < common::ranked_symbol < ext::pair < SymbolType, unsigned > >, alphabet::BottomOfTheStackSymbol > > pop;
        pop.push_back ( symb );
        pop.push_back ( alphabet::BottomOfTheStackSymbol ( ) );
        automaton.addTransition ( q, alphabet::EndSymbol ( ), pop, f, { } );
    }
 
    return automaton;
}
 
} /* namespace convert */
 
} /* namespace rte */