RandomGrammarFactory.cpp

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

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

#include <algorithm>
#include <random>

namespace grammar {

namespace generate {

grammar::CFG < > RandomGrammarFactory::generateCFG( std::set<DefaultSymbolType> nonterminals, std::set<DefaultSymbolType> terminals, double density ) {
	std::deque<DefaultSymbolType> terminals2(terminals.begin(), terminals.end());
	std::deque<DefaultSymbolType> 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::CommonException("Too big terminals count.");

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

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

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

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

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

	if( nonterminals.size( ) <= 0 )
		throw exception::CommonException( "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 DefaultSymbolType& lhs = nonterminals[std::random_devices::semirandom() % nonterminals.size()];

		int rhsSize = std::random_devices::semirandom() % 5;
		std::vector<DefaultSymbolType> 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 */