NullableNonterminals.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 NullableNonterminals {
public:
    template<class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::set < NonterminalSymbolType > getNullableNonterminals ( const T & grammar );
};
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::set < NonterminalSymbolType > NullableNonterminals::getNullableNonterminals ( const T & grammar ) {
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    ext::deque < ext::set < NonterminalSymbolType > > Ni;
 
    Ni.push_back ( ext::set < NonterminalSymbolType > { } );
    int i = 0;
 
    auto testCallback = [ & ] ( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & symb ) {
        return Ni.at ( i - 1 ).count ( symb );
    };
 
    do {
        i += 1;
 
        Ni.push_back ( ext::set < NonterminalSymbolType > { } );
        for ( const auto & rule : rawRules ) {
            for ( const auto & rhs : rule.second ) {
                if ( rhs.empty ( ) || std::all_of ( rhs.begin ( ), rhs.end ( ), testCallback ) ) {
                    Ni.at ( i ).insert ( rule.first );
                }
            }
        }
 
    } while ( Ni.at ( i ) != Ni.at ( i - 1 ) );
 
    return Ni.at(i);
}
 
} /* namespace properties */
 
} /* namespace grammar */