ReachableSymbols.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#include <alib/deque>
#include <alib/set>
 
#include <grammar/Grammar.h>
 
#include <grammar/RawRules.h>
 
namespace grammar {
 
namespace properties {
 
class ReachableSymbols {
public:
    template<class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::set < ext::variant < TerminalSymbolType, NonterminalSymbolType > > getReachableSymbols ( const T & grammar );
};
 
template<class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::set < ext::variant < TerminalSymbolType, NonterminalSymbolType > > ReachableSymbols::getReachableSymbols( const T & grammar ) {
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    // 1
    ext::deque < ext::set < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > Vi;
    Vi.push_back ( ext::set < ext::variant < TerminalSymbolType, NonterminalSymbolType > > ( ) );
    Vi.at ( 0 ).insert ( grammar.getInitialSymbol ( ) );
 
    int i = 0;
 
    // 2.
    do {
        i = i + 1;
 
        Vi.push_back ( Vi.at ( i - 1 ) );
 
        for ( const auto & rule : rawRules ) {
            if ( Vi.at( i - 1 ).count ( rule.first ) ) {
                for ( const auto & rhs : rule.second ) {
                    Vi.at ( i ).insert( rhs.begin( ), rhs.end( ) );
                }
            }
        }
 
    } while ( Vi.at( i ) != Vi.at( i - 1 ) );
 
    // 3.
    return Vi.at( i );
}
 
} /* namespace properties */
 
} /* namespace grammar */