RandomGrammarFactory.cpp

/*
 * RandomGrammarFactory.cpp
 *
 *  Created on: 27. 3. 2014
 *	  Author: Tomas Pecka
 */

#include "RandomGrammarFactory.h"
#include <grammar/Grammar.h>

#include <algorithm>
#include <random>

namespace grammar {

namespace generate {

grammar::CFG RandomGrammarFactory::generateCFG( std::set<alphabet::Symbol> nonterminals, std::set<alphabet::Symbol> terminals, double density ) {
	std::deque<alphabet::Symbol> terminals2(terminals.begin(), terminals.end());
	std::deque<alphabet::Symbol> nonterminals2(nonterminals.begin(), nonterminals.end());
	return RandomGrammarFactory::randomCFG( nonterminals2, terminals2, density );
}

grammar::CFG RandomGrammarFactory::generateCFG( size_t nonterminalsCount, size_t terminalsCount, bool randomizedAlphabet, double density ) {
	if(terminalsCount > 26)
		throw exception::AlibException("Too big terminals count.");

	std::vector<alphabet::Symbol> symbols;
	for(int i = 0; i < 26; i++) symbols.push_back(alphabet::symbolFrom(i + 'a'));
	if(randomizedAlphabet) shuffle(symbols.begin(), symbols.end(), std::random_devices::semirandom);
	std::deque<alphabet::Symbol> terminals(symbols.begin(), symbols.begin() + terminalsCount);

	if(nonterminalsCount > 26)
		throw exception::AlibException("Too big nonterminals count.");

	std::vector<alphabet::Symbol> symbols2;
	for(int i = 0; i < 26; i++) symbols2.push_back(alphabet::symbolFrom(i + 'A'));
	if(randomizedAlphabet) shuffle(symbols2.begin(), symbols2.end(), std::random_devices::semirandom);
	std::deque<alphabet::Symbol> nonterminals(symbols2.begin(), symbols2.begin() + nonterminalsCount);

	return RandomGrammarFactory::randomCFG( nonterminals, terminals, density );
}

grammar::CFG RandomGrammarFactory::randomCFG( const std::deque<alphabet::Symbol>& nonterminals, const std::deque<alphabet::Symbol> & terminals, double density ) {
	if( terminals.size( ) <= 0 )
		throw exception::AlibException( "Terminals count must be greater than 0." );

	if( nonterminals.size( ) <= 0 )
		throw exception::AlibException( "Nonterminals count must be greater than 0." );

	grammar::CFG grammar(nonterminals.front());
	grammar.setTerminalAlphabet({terminals.begin(), terminals.end()});
	grammar.setNonterminalAlphabet({nonterminals.begin(), nonterminals.end()});

	if(std::random_devices::semirandom() % 2)
		grammar.addRule(grammar.getInitialSymbol(), {});

	int rules = 0;
	while(rules < terminals.size() * nonterminals.size() * density / 100) {
		const alphabet::Symbol& lhs = nonterminals[std::random_devices::semirandom() % nonterminals.size()];

		int rhsSize = std::random_devices::semirandom() % 5;
		std::vector<alphabet::Symbol> rhs;
		int nonterminalsOnRHS = 0;
		for(int i = 0; i < rhsSize; i++) {
			if(std::random_devices::semirandom() % (nonterminals.size() + terminals.size()) < nonterminals.size()) {
				rhs.push_back(nonterminals[std::random_devices::semirandom() % nonterminals.size()]);
				nonterminalsOnRHS++;
			} else {
				rhs.push_back(terminals[std::random_devices::semirandom() % terminals.size()]);
			}
		}
		rules += nonterminalsOnRHS;
		grammar.addRule(lhs, rhs);
	}

	return grammar;
}

} /* namespace generate */

} /* namespace grammar */