ProductiveNonterminals.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#include <alib/set>
#include <alib/deque>
 
#include <grammar/Grammar.h>
 
#include <grammar/RawRules.h>
 
namespace grammar {
 
namespace properties {
 
class ProductiveNonterminals {
public:
    /*
     * Retrieves set of nonterminals N = { A : A => T* }
     *
     * \tparam T the type of the tested grammar
     * \tparam TerminalSymbolType the type of terminal symbols in the tested grammar
     * \tparam NonterminalSymbolType the type of nonterminal symbols in the tested grammar
     *
     * \param grammar the tested grammar
     *
     * \returns set of nonterminals that can be rewriten to a sentence
     */
    template<class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::set < NonterminalSymbolType > getProductiveNonterminals ( const T & grammar );
};
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::set < NonterminalSymbolType > ProductiveNonterminals::getProductiveNonterminals ( const T & grammar ) {
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    // 1.
    ext::deque < ext::set < NonterminalSymbolType > > Ni;
    Ni.push_back ( ext::set < NonterminalSymbolType > ( ) );
 
    int i = 0;
    auto testCallback = [ & ]( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & symbol ) -> bool {
        return     ( symbol.template is < NonterminalSymbolType > ( ) && Ni.at( i - 1 ) . count ( symbol.template get < NonterminalSymbolType > ( ) ) )
            || ( symbol.template is < TerminalSymbolType > ( ) && grammar.getTerminalAlphabet( ). count ( symbol.template get < TerminalSymbolType > ( ) ) );
    };
 
    // 2.
    do {
        i = i + 1;
 
        Ni.push_back ( Ni.at( i - 1 ) );
 
        for ( const auto & rule : rawRules ) {
            for ( const auto & rhs : rule.second ) {
                if ( std::all_of ( rhs.begin ( ), rhs.end ( ), testCallback ) )
                    Ni.at ( i ).insert ( rule.first );
            }
        }
 
    } while ( Ni.at ( i ) != Ni.at ( i - 1 ) );
 
    // 3.
    return Ni.at ( i );
}
 
} /* namespace properties */
 
} /* namespace grammar */