RandomGrammarFactory.h

Go to the documentation of this file.

 
#pragma once
 
#include <string>
 
#include <ext/algorithm>
#include <ext/random>
 
#include <alib/deque>
#include <alib/set>
 
#include <exception/CommonException.h>
 
#include <grammar/ContextFree/CFG.h>
 
namespace grammar {
 
namespace generate {
 
class RandomGrammarFactory {
public:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::CFG < TerminalSymbolType, NonterminalSymbolType > generateCFG ( ext::set < NonterminalSymbolType > nonterminals, ext::set < TerminalSymbolType > terminals, double density );
 
    static grammar::CFG < std::string, std::string > generateCFG( size_t nonterminalsCount, size_t terminalsCount, bool randomizedAlphabet, double density );
 
private:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::CFG < TerminalSymbolType, NonterminalSymbolType > randomCFG ( const ext::deque < NonterminalSymbolType > & nonterminals, const ext::deque < TerminalSymbolType > & terminals, double density );
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::CFG < TerminalSymbolType, NonterminalSymbolType > RandomGrammarFactory::generateCFG ( ext::set < NonterminalSymbolType > nonterminals, ext::set < TerminalSymbolType > terminals, double density ) {
    ext::deque < TerminalSymbolType > terminals2 ( terminals.begin ( ), terminals.end ( ) );
    ext::deque < NonterminalSymbolType > nonterminals2 ( nonterminals.begin ( ), nonterminals.end ( ) );
    return RandomGrammarFactory::randomCFG ( nonterminals2, terminals2, density );
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::CFG < TerminalSymbolType, NonterminalSymbolType > RandomGrammarFactory::randomCFG ( const ext::deque < NonterminalSymbolType > & nonterminals, const ext::deque < TerminalSymbolType > & terminals, double density ) {
    if( terminals.empty ( ) )
        throw exception::CommonException( "Terminals count must be greater than 0." );
 
    if( nonterminals.empty ( ) )
        throw exception::CommonException( "Nonterminals count must be greater than 0." );
 
    grammar::CFG < TerminalSymbolType, NonterminalSymbolType > grammar(nonterminals.front());
    grammar.setTerminalAlphabet({terminals.begin(), terminals.end()});
    grammar.setNonterminalAlphabet({nonterminals.begin(), nonterminals.end()});
 
    if(ext::random_devices::semirandom() % 2)
        grammar.addRule(grammar.getInitialSymbol(), {});
 
    int rules = 0;
    while(rules < terminals.size() * nonterminals.size() * density / 100) {
        const NonterminalSymbolType& lhs = nonterminals[ext::random_devices::semirandom() % nonterminals.size()];
 
        int rhsSize = ext::random_devices::semirandom() % 5;
        ext::vector<ext::variant<TerminalSymbolType, NonterminalSymbolType>> rhs;
        int nonterminalsOnRHS = 0;
        for(int i = 0; i < rhsSize; i++) {
            if(ext::random_devices::semirandom() % (nonterminals.size() + terminals.size()) < nonterminals.size()) {
                rhs.push_back(ext::variant < TerminalSymbolType, NonterminalSymbolType > ( nonterminals[ext::random_devices::semirandom() % nonterminals.size()]));
                nonterminalsOnRHS++;
            } else {
                rhs.push_back(ext::variant < TerminalSymbolType, NonterminalSymbolType > ( terminals[ext::random_devices::semirandom() % terminals.size()]));
            }
        }
        rules += nonterminalsOnRHS;
        grammar.addRule(lhs, rhs);
    }
 
    return grammar;
}
 
} /* namespace generate */
 
} /* namespace grammar */