EpsilonRemover.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#include <alib/map>
 
#include <grammar/Grammar.h>
 
#include <grammar/ContextFree/CFG.h>
#include <grammar/ContextFree/EpsilonFreeCFG.h>
#include <grammar/ContextFree/CNF.h>
#include <grammar/ContextFree/GNF.h>
#include <grammar/ContextFree/LG.h>
#include <grammar/Regular/LeftLG.h>
#include <grammar/Regular/LeftRG.h>
#include <grammar/Regular/RightLG.h>
#include <grammar/Regular/RightRG.h>
 
#include <grammar/properties/NullableNonterminals.h>
 
#include <grammar/RawRules.h>
 
namespace grammar {
 
namespace simplify {
 
class EpsilonRemover {
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static void removeNullableNonterminals(grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, const ext::set < NonterminalSymbolType >& nullableNonterminals, const NonterminalSymbolType & lhs, const ext::vector<ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs, unsigned i, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > clear);
 
    template<class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > removeInternal( const T & grammar );
 
public:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::CFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::CNF < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
void EpsilonRemover::removeNullableNonterminals(grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, const ext::set < NonterminalSymbolType > & nullableNonterminals, const NonterminalSymbolType & lhs, const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs, unsigned i, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > clear) {
    if(rhs.size() == i) {
        if(clear.empty ( )) return;
        grammar.addRule(lhs, clear);
    } else if(rhs[i].template is < NonterminalSymbolType > ( ) && nullableNonterminals.find ( rhs [ i ].template get < NonterminalSymbolType > ( ) ) != nullableNonterminals.end()) {
        removeNullableNonterminals(grammar, nullableNonterminals, lhs, rhs, i+1, clear);
 
        clear.push_back ( rhs [ i ] );
        removeNullableNonterminals(grammar, nullableNonterminals, lhs, rhs, i+1, clear);
    } else {
        clear.push_back ( rhs [ i ] );
        removeNullableNonterminals(grammar, nullableNonterminals, lhs, rhs, i+1, clear);
    }
}
 
template<class T, class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::removeInternal( const T & grammar ) {
    grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > result(grammar.getInitialSymbol());
 
    for( const auto & symbol : grammar.getNonterminalAlphabet() )
        result.addNonterminalSymbol( symbol );
 
    for( const auto & symbol : grammar.getTerminalAlphabet() )
        result.addTerminalSymbol( symbol );
 
    ext::set < NonterminalSymbolType > nullableNonterminals = grammar::properties::NullableNonterminals::getNullableNonterminals(grammar);
 
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    for( const auto & rule : rawRules )
        for(const auto & rhs : rule.second) {
            if(rhs.empty ( )) continue;
 
            EpsilonRemover::removeNullableNonterminals(result, nullableNonterminals, rule.first, rhs, 0, {});
        }
 
    if(nullableNonterminals.find(grammar.getInitialSymbol()) != nullableNonterminals.end())
        result.setGeneratesEpsilon(true);
 
    return result;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::CFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return EpsilonRemover::removeInternal(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::CNF < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return EpsilonRemover::removeInternal(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return EpsilonRemover::removeInternal(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return EpsilonRemover::removeInternal(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > EpsilonRemover::remove(const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
} /* namespace simplify */
 
} /* namespace grammar */