RecursiveNonterminal.h

Go to the documentation of this file.

 
#pragma once
 
#include "NullableNonterminals.h"
 
#include <alib/set>
#include <alib/deque>
 
#include <exception/CommonException.h>
 
#include <grammar/RawRules.h>
 
namespace grammar {
 
namespace properties {
 
class RecursiveNonterminal {
public:
    template < class T, class NonterminalSymbolType, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T > >
    static bool isNonterminalRecursive ( const T & grammar, const NonterminalSymbolType & nonterminal );
 
};
 
template < class T, class NonterminalSymbolType, class TerminalSymbolType >
bool RecursiveNonterminal::isNonterminalRecursive ( const T & grammar, const NonterminalSymbolType & nonterminal ) {
    if ( grammar.getNonterminalAlphabet ( ).count ( nonterminal ) == 0 )
        throw exception::CommonException ( "Nonterminal symbol \"" + ext::to_string ( nonterminal ) + "\" is not present in grammar." );
 
    ext::deque < ext::set < NonterminalSymbolType > > Ni;
    Ni.push_back ( ext::set < NonterminalSymbolType > { nonterminal } );
    unsigned i = 1;
 
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
    auto nullable = grammar::properties::NullableNonterminals::getNullableNonterminals ( grammar );
 
    while ( i <= grammar.getNonterminalAlphabet ( ).size ( ) ) {
        Ni.push_back ( ext::set < NonterminalSymbolType > { } );
 
        for ( const NonterminalSymbolType & lhs : Ni.at ( i - 1 ) )
            if ( rawRules.find ( lhs ) != rawRules.end ( ) )
                for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rawRules.find ( lhs )->second )
                    for ( const ext::variant < TerminalSymbolType, NonterminalSymbolType > & rhsSymbol : rhs ) {
                        if ( grammar.getTerminalAlphabet ( ).count ( rhsSymbol ) )
                            break;
 
                        Ni.at ( i ).insert ( rhsSymbol.template get < NonterminalSymbolType > ( ) );
 
                        if ( ! nullable.count ( rhsSymbol.template get < NonterminalSymbolType > ( ) ) )
                            break;
                    }
 
        if ( Ni.at ( i ).count ( nonterminal ) )
            return true;
 
        i += 1;
    }
 
    return false;
}
 
} /* namespace properties */
 
} /* namespace grammar */