ToAutomatonBottomUp.h

Go to the documentation of this file.

 
#pragma once
 
#include <grammar/Grammar.h>
#include <grammar/ContextFree/CFG.h>
#include <grammar/ContextFree/EpsilonFreeCFG.h>
#include <grammar/RawRules.h>
 
#include <automaton/PDA/NPDA.h>
 
#include <alphabet/BottomOfTheStackSymbol.h>
#include <label/InitialStateLabel.h>
#include <label/FinalStateLabel.h>
 
namespace grammar {
 
namespace convert {
 
class ToAutomatonBottomUp {
public:
    template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static automaton::NPDA < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType >, unsigned > convert(const T& grammar);
};
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
automaton::NPDA < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType >, unsigned > ToAutomatonBottomUp::convert ( const T & grammar ) {
    unsigned q = label::InitialStateLabel::instance < unsigned > ( );
    unsigned r = label::FinalStateLabel::instance < unsigned > ( );
 
    automaton::NPDA < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType >, unsigned > automaton ( q, alphabet::BottomOfTheStackSymbol::instance < NonterminalSymbolType > ( ) );
    automaton.addState(r);
    automaton.addFinalState(r);
 
    automaton.setInputAlphabet(grammar.getTerminalAlphabet());
 
    for(const NonterminalSymbolType& symbol : grammar.getNonterminalAlphabet())
        automaton.addPushdownStoreSymbol(symbol);
    for(const TerminalSymbolType& symbol : grammar.getTerminalAlphabet())
        automaton.addPushdownStoreSymbol(symbol);
 
    for(const TerminalSymbolType& symbol : grammar.getTerminalAlphabet())
        automaton.addTransition ( automaton.getInitialState ( ), symbol, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { }, automaton.getInitialState ( ), ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { symbol } );
 
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
    for ( const auto & kv : rawRules )
        for(const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : kv.second) {
            automaton.addTransition ( automaton.getInitialState(), ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > ( rhs.rbegin ( ), rhs.rend ( ) ), automaton.getInitialState(), ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { kv.first } );
        }
 
    automaton.addTransition(automaton.getInitialState(), ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { grammar.getInitialSymbol ( ), alphabet::BottomOfTheStackSymbol::instance < NonterminalSymbolType > ( ) }, r, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } );
 
    return automaton;
}
 
} /* namespace convert */
 
} /* namespace grammar */