UnproductiveSymbolsRemover.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/ProductiveNonterminals.h>
#include <grammar/RawRules.h>
#include <grammar/AddRawRule.h>
 
#include <exception/CommonException.h>
 
namespace grammar {
 
namespace simplify {
 
class UnproductiveSymbolsRemover {
public:
    /*
     * Removes unproductive 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 unproductive 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 UnproductiveSymbolsRemover::remove( const T & grammar ) {
    // 1.
    ext::set < NonterminalSymbolType > Nt = grammar::properties::ProductiveNonterminals::getProductiveNonterminals ( grammar );
 
    T ret ( grammar.getInitialSymbol ( ) );
 
    for( const auto & symbol : Nt )
        ret.addNonterminalSymbol ( symbol );
 
    for( const auto & symbol : grammar.getTerminalAlphabet( ) )
        ret.addTerminalSymbol ( symbol );
 
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
    const ext::set < TerminalSymbolType > & terminals = ret.getTerminalAlphabet( );
 
    auto testCallback = [ & ] ( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol ) {
        return     ( symbol.template is < NonterminalSymbolType > ( ) && Nt.count ( symbol.template get < NonterminalSymbolType > ( ) ) )
            || ( symbol.template is < TerminalSymbolType > ( ) && terminals.count ( symbol.template get < TerminalSymbolType > ( ) ) );
    };
 
    for( const auto & rule : rawRules ) {
        if( Nt.count( rule.first ) ) {
            for( const auto & rhs : rule.second ) {
                if( all_of( rhs.begin( ), rhs.end( ), testCallback ) )
                    grammar::AddRawRule::addRawRule ( ret, rule.first, rhs );
            }
        }
    }
 
 
    /* if( ! G1.getNonTerminalSymbols( ) . count( grammar.getInitialSymbol( ) ) )
        throw CommonException( "Starting symbol of grammar was marked as unproductive and therefore it was removed." ); */
 
    // 2.
    return ret;
}
 
} /* namespace simplify */
 
} /* namespace grammar */