RecursiveNonterminal.cpp

/*
 * RecursiveNonterminal.cpp
 *
 *  Created on: 16. 11. 2015
 *	  Author: Jan Travnicek
 */

#include "RecursiveNonterminal.h"
#include "NullableNonterminals.h"

#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 <set>
#include <deque>

#include <exception/CommonException.h>

namespace grammar {

namespace properties {

template < class T >
bool RecursiveNonterminal::isNonterminalRecursive ( const T & grammar, const alphabet::Symbol & nonterminal ) {
	if ( grammar.getNonterminalAlphabet ( ).count ( nonterminal ) == 0 )
		throw exception::CommonException ( "Nonterminal symbol \"" + ( std::string ) nonterminal + "\" is not present in grammar." );

	std::deque < std::set < alphabet::Symbol > > Ni;
	Ni.push_back ( std::set < alphabet::Symbol > { nonterminal } );
	unsigned i = 1;

	auto rawRules = grammar.getRawRules ( );
	auto nullable = grammar::properties::NullableNonterminals::getNullableNonterminals ( grammar );

	while ( i <= grammar.getNonterminalAlphabet ( ).size ( ) ) {
		Ni.push_back ( std::set < alphabet::Symbol > { } );

		for ( const alphabet::Symbol & lhs : Ni.at ( i - 1 ) )
			if ( rawRules.find ( lhs ) != rawRules.end ( ) )
				for ( const std::vector < alphabet::Symbol > & rhs : rawRules.find ( lhs )->second )
					for ( const alphabet::Symbol & rhsSymbol : rhs ) {
						if ( grammar.getTerminalAlphabet ( ).count ( rhsSymbol ) ) break;

						Ni.at ( i ).insert ( rhsSymbol );

						if ( !nullable.count ( rhsSymbol ) ) break;
					}



		if ( Ni.at ( i ).count ( nonterminal ) ) return true;

		i += 1;
	}

	return false;
}

auto RecursiveNonterminalCFG = RecursiveNonterminal::RegistratorWrapper < bool, grammar::CFG > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalEpsilonFreeCFG = RecursiveNonterminal::RegistratorWrapper < bool, grammar::EpsilonFreeCFG > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalGNF = RecursiveNonterminal::RegistratorWrapper < bool, grammar::GNF > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalCNF = RecursiveNonterminal::RegistratorWrapper < bool, grammar::CNF > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalLG	 = RecursiveNonterminal::RegistratorWrapper < bool, grammar::LG > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalLeftLG	 = RecursiveNonterminal::RegistratorWrapper < bool, grammar::LeftLG > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalLeftRG	 = RecursiveNonterminal::RegistratorWrapper < bool, grammar::LeftRG > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalRightLG = RecursiveNonterminal::RegistratorWrapper < bool, grammar::RightLG > ( RecursiveNonterminal::isNonterminalRecursive );
auto RecursiveNonterminalRightRG = RecursiveNonterminal::RegistratorWrapper < bool, grammar::RightRG > ( RecursiveNonterminal::isNonterminalRecursive );

bool RecursiveNonterminal::isNonterminalRecursive ( const grammar::Grammar & grammar, const alphabet::Symbol & nonterminal ) {
	return dispatch ( grammar.getData ( ), nonterminal );
}

} /* namespace properties */

} /* namespace grammar */