ToAutomaton.h

Go to the documentation of this file.

 
#pragma once
 
#include <grammar/Grammar.h>
#include <grammar/Regular/LeftRG.h>
#include <grammar/Regular/RightRG.h>
#include <grammar/ContextFree/CFG.h>
#include <grammar/ContextFree/EpsilonFreeCFG.h>
 
#include <automaton/FSM/NFA.h>
#include <automaton/PDA/NPDA.h>
 
#include <common/createUnique.hpp>
 
#include <label/InitialStateLabel.h>
#include <label/FinalStateLabel.h>
 
#include <grammar/convert/ToAutomatonTopDown.h>
 
namespace grammar {
 
namespace convert {
 
class ToAutomaton {
public:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static automaton::NFA < TerminalSymbolType, NonterminalSymbolType > convert ( const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static automaton::NFA < TerminalSymbolType, NonterminalSymbolType > convert ( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    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 TerminalSymbolType, class NonterminalSymbolType >
automaton::NFA < TerminalSymbolType, NonterminalSymbolType > ToAutomaton::convert(const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    // step 1, 4
    NonterminalSymbolType q0 = common::createUnique ( label::InitialStateLabel::instance < NonterminalSymbolType > ( ), grammar.getNonterminalAlphabet ( ) );
    automaton::NFA < TerminalSymbolType, NonterminalSymbolType > automaton ( q0 );
    automaton.setInputAlphabet(grammar.getTerminalAlphabet());
    for ( const NonterminalSymbolType & nonterminal : grammar.getNonterminalAlphabet ( ) )
        automaton.addState ( nonterminal );
 
    // step 3
    for(const auto& rule : grammar.getRules()) {
        const NonterminalSymbolType& lhs = rule.first;
        for(const auto& ruleRHS : rule.second) {
            if ( ruleRHS.template is < ext::pair < NonterminalSymbolType, TerminalSymbolType > > ( ) ) { // if B->Ca => \delta(C,a)=B
                const ext::pair < NonterminalSymbolType, TerminalSymbolType > & rhs = ruleRHS.template get < ext::pair < NonterminalSymbolType, TerminalSymbolType > > ( );
                automaton.addTransition(rhs.first, rhs.second, lhs);
            }
            else { // if B->a => \delta(StartState,a)=B
                const TerminalSymbolType& rhs = ruleRHS.template get < TerminalSymbolType > ( );
                automaton.addTransition(q0, rhs, lhs);
            }
        }
    }
 
    // step 5
    automaton.addFinalState(grammar.getInitialSymbol());
    if(grammar.getGeneratesEpsilon())
        automaton.addFinalState(q0);
 
    return automaton;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
automaton::NFA < TerminalSymbolType, NonterminalSymbolType > ToAutomaton::convert(const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    // step 1, 4
    NonterminalSymbolType AState = common::createUnique(label::FinalStateLabel::instance < NonterminalSymbolType > ( ), grammar.getNonterminalAlphabet ( ) );
    automaton::NFA < > automaton(grammar.getInitialSymbol());
    for ( const NonterminalSymbolType & nonterminal : grammar.getNonterminalAlphabet ( ) )
        automaton.addState ( nonterminal );
    automaton.addState(AState);
 
    automaton.setInputAlphabet(grammar.getTerminalAlphabet());
 
    // step 3
    for(const auto& rule : grammar.getRules()) {
        const NonterminalSymbolType& lhs = rule.first;
        for(const auto& ruleRHS : rule.second) {
            if ( ruleRHS.template is < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( ) ) { // if B->aC => \delta(B,a)=C
                const ext::pair < TerminalSymbolType, NonterminalSymbolType > & rhs = ruleRHS.template get < ext::pair < TerminalSymbolType, NonterminalSymbolType > > ( );
                automaton.addTransition(lhs, rhs.first, rhs.second);
            }
            else { // if B->a => \delta(B,a)=AState
                const TerminalSymbolType& rhs = ruleRHS.template get < TerminalSymbolType > ( );
                automaton.addTransition(lhs, rhs, AState);
            }
        }
    }
 
    // step 5
    automaton.addFinalState(AState);
    if(grammar.getGeneratesEpsilon())
        automaton.addFinalState(automaton.getInitialState());
 
    return automaton;
}
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
automaton::NPDA < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType >, unsigned > ToAutomaton::convert ( const T & grammar ) {
    return ToAutomatonTopDown::convert ( grammar );
}
 
} /* namespace convert */
 
} /* namespace grammar */