SimpleRulesRemover.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#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/NonterminalUnitRuleCycle.h>
 
#include <grammar/Grammar.h>
 
#include <grammar/RawRules.h>
#include <grammar/AddRawRule.h>
 
namespace grammar {
 
namespace simplify {
 
class SimpleRulesRemover {
    template<class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static T removeNonEpsilonFree( const T & grammar );
 
public:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::CFG < 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::LG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::LeftLG < 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::RightLG < 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 T, class TerminalSymbolType, class NonterminalSymbolType >
T SimpleRulesRemover::removeNonEpsilonFree( const T & grammar ) {
    T result(grammar.getInitialSymbol());
 
    for( const auto & symbol : grammar.getNonterminalAlphabet() )
        result.addNonterminalSymbol( symbol );
 
    for( const auto & symbol : grammar.getTerminalAlphabet() )
        result.addTerminalSymbol( symbol );
 
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    for( const auto & symbol : grammar.getNonterminalAlphabet() ) {
        ext::set < NonterminalSymbolType > simpleRulesClosure = grammar::properties::NonterminalUnitRuleCycle::getNonterminalUnitRuleCycle(grammar, symbol);
        for( const auto & closureSymbol : simpleRulesClosure ) {
            auto rules = rawRules.find(closureSymbol);
            if(rules != rawRules.end()) for( const auto& rawRule : rules->second ) {
                if(rawRule.empty ( ) || (rawRule.size() == 1 && !grammar.getNonterminalAlphabet().count(rawRule[0])) || rawRule.size() >= 2)
                    grammar::AddRawRule::addRawRule ( result, symbol, rawRule);
            }
        }
    }
 
    return result;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::CFG < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::CFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return removeNonEpsilonFree(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & 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 );
 
    for( const auto & symbol : grammar.getNonterminalAlphabet() ) {
        ext::set < NonterminalSymbolType > simpleRulesClosure = grammar::properties::NonterminalUnitRuleCycle::getNonterminalUnitRuleCycle ( grammar, symbol );
        for( const auto & closureSymbol : simpleRulesClosure ) {
            auto rules = grammar.getRules().find(closureSymbol);
            if(rules != grammar.getRules().end()) for( const auto& rawRule : rules->second ) {
                if(rawRule.empty ( ) || (rawRule.size() == 1 && !grammar.getNonterminalAlphabet().count(rawRule[0])) || rawRule.size() >= 2)
                    result.addRule(symbol, rawRule);
            }
        }
    }
 
    result.setGeneratesEpsilon(grammar.getGeneratesEpsilon());
 
    return result;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::CNF < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::LG < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return removeNonEpsilonFree(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return removeNonEpsilonFree(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return removeNonEpsilonFree(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > SimpleRulesRemover::remove(const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
} /* namespace simplify */
 
} /* namespace grammar */