UnreachableSymbolsRemover.h

Go to the documentation of this file.

 
#pragma once
 
#include <grammar/ContextFree/CFG.h>
#include <grammar/ContextFree/EpsilonFreeCFG.h>
#include <grammar/ContextFree/GNF.h>
#include <grammar/ContextFree/CNF.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 <ext/algorithm>
 
#include <alib/set>
 
#include <grammar/properties/ReachableSymbols.h>
 
#include <grammar/RawRules.h>
#include <grammar/AddRawRule.h>
 
namespace grammar {
 
namespace simplify {
 
class UnreachableSymbolsRemover {
public:
    /*
     * Removes unreachable symbols.
     *
     * \tparam T the type of modified grammar
     * \tparam TerminalSymbolType the type of terminal symbols of the grammar
     * \tparam NonterminalSymbolType the type of nonterminal symbols of the grammar
     *
     * \param grammar the modified grammar
     *
     * \return grammar equivalent to @p grammar without unreachable symbols
     */
    template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static T remove( const T & grammar );
};
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
T UnreachableSymbolsRemover::remove( const T & grammar) {
    // 1.
    ext::set < ext::variant < TerminalSymbolType, NonterminalSymbolType > > Vt = grammar::properties::ReachableSymbols::getReachableSymbols( grammar );
 
    T ret ( grammar.getInitialSymbol ( ) );
 
    ext::set < ext::variant < TerminalSymbolType, NonterminalSymbolType > > newNonTerminals;
    ext::set < ext::variant < TerminalSymbolType, NonterminalSymbolType > > newTerminals;
 
    set_intersection( Vt.begin( ), Vt.end( ), grammar.getNonterminalAlphabet( ).begin( ), grammar.getNonterminalAlphabet( ).end( ), std::inserter( newNonTerminals, newNonTerminals.begin( ) ) );
    for( const auto & symbol : newNonTerminals )
        ret.addNonterminalSymbol( symbol.template get < NonterminalSymbolType > ( ) );
 
    set_intersection( Vt.begin( ), Vt.end( ), grammar.getTerminalAlphabet( ).begin( ), grammar.getTerminalAlphabet( ).end( ), std::inserter( newTerminals, newTerminals.begin( ) ) );
    for( const auto & symbol : newTerminals )
        ret.addTerminalSymbol( symbol.template get < TerminalSymbolType > ( ) );
 
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    auto testCallback = [ & ] ( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & symb ) -> bool {
        return Vt.count( symb );
    };
 
    // A->\alpha: if A \in N' and \alpha in V_i*, then A->\alpha in P
    for( const auto & rule : rawRules ) {
        if( newNonTerminals.count( rule.first ) ) {
            for( const auto& rhs : rule.second ) {
                if( all_of( rhs.begin( ), rhs.end( ), testCallback ) )
                grammar::AddRawRule::addRawRule ( ret, rule.first, rhs );
            }
        }
    }
 
    // 2.
    return ret;
}
 
} /* namespace simplify */
 
} /* namespace grammar */