ToGNF.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#include <alib/map>
 
#include <grammar/ContextFree/CFG.h>
#include <grammar/ContextFree/EpsilonFreeCFG.h>
#include <grammar/ContextFree/CNF.h>
#include <grammar/ContextFree/GNF.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 "EpsilonRemover.h"
#include "SimpleRulesRemover.h"
#include "LeftRecursionRemover.h"
#include <grammar/convert/ToGrammarRightRG.h>
#include <common/createUnique.hpp>
 
namespace grammar {
 
namespace simplify {
 
class ToGNF {
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > assignNonterminals(const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar);
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convertInternal( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
public:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert( const grammar::CFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, NonterminalSymbolType > convert( const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert( const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > convert( const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > convert( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > convert( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > ToGNF::assignNonterminals(const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > res(grammar.getInitialSymbol());
    res.setNonterminalAlphabet(grammar.getNonterminalAlphabet());
    res.setTerminalAlphabet(grammar.getTerminalAlphabet());
    res.setGeneratesEpsilon(grammar.getGeneratesEpsilon());
 
    for ( const std::pair < const NonterminalSymbolType, ext::set<ext::vector<ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
        for(const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & singleRHS : rule.second) {
            if(res.getTerminalAlphabet().count(singleRHS[0])) { //do not substitute terminals
                res.addRule(rule.first, singleRHS);
                continue;
            }
            const ext::variant < TerminalSymbolType, NonterminalSymbolType > & secondLHS = singleRHS[0];
            if(grammar.getRules().find(secondLHS) == grammar.getRules().end()) { //is there any right hand side to substitue with?
                //if not well this rule does not generate anything anyway
                continue;
            }
 
            for(const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & secondSingleRHS : grammar.getRules().find(secondLHS)->second) { // do the substitution
                ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > newRHS(secondSingleRHS);
                newRHS.insert(newRHS.end(), singleRHS.begin() + 1, singleRHS.end());
                res.addRule(rule.first, newRHS);
            }
        }
    }
    return res;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToGNF::convertInternal( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar ) {
    grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > step(grammar);
    while(true) {
        grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > nextStep = assignNonterminals(step);
 
        if(step == nextStep) break;
        step = std::move(nextStep);
    }
 
    grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > res(step.getInitialSymbol());
    res.setTerminalAlphabet(step.getTerminalAlphabet());
    for ( const NonterminalSymbolType & nonterminal : step.getNonterminalAlphabet ( ) )
        res.addNonterminalSymbol ( ext::variant < TerminalSymbolType, NonterminalSymbolType > ( nonterminal ) );
    res.setGeneratesEpsilon(step.getGeneratesEpsilon());
    ext::map < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > terminalToPrimed;
    for ( const TerminalSymbolType & terminal : step.getTerminalAlphabet ( ) ) {
        ext::variant < TerminalSymbolType, NonterminalSymbolType > primed = common::createUnique ( terminal, res.getTerminalAlphabet(), res.getNonterminalAlphabet());
        terminalToPrimed.insert(std::make_pair(terminal, primed));
        res.addNonterminalSymbol(primed);
        res.addRule(primed, ext::make_pair(terminal, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > { } ) );
    }
    for(const auto& rule : step.getRules()) {
        for(const auto& rhs : rule.second) {
            ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > convertedNonterminals;
            bool first = true;
            for(const ext::variant < TerminalSymbolType, NonterminalSymbolType > & rhsSymbol : rhs) {
                if(first) {
                    first = false;
                    continue;
                }
 
                if(res.getNonterminalAlphabet().count(rhsSymbol))
                    convertedNonterminals.push_back(rhsSymbol);
                else
                    convertedNonterminals.push_back(terminalToPrimed.find(rhsSymbol)->second);
            }
            res.addRule(rule.first, ext::make_pair(rhs[0].template get < TerminalSymbolType > ( ), std::move(convertedNonterminals)));
        }
    }
    return res;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToGNF::convert ( const grammar::CFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convert(grammar::simplify::EpsilonRemover::remove(grammar));
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToGNF::convert(const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar::simplify::LeftRecursionRemover::remove(grammar)));
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToGNF::convert(const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convertInternal(grammar::simplify::LeftRecursionRemover::remove(grammar));
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, NonterminalSymbolType > ToGNF::convert(const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToGNF::convert(const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar::simplify::LeftRecursionRemover::remove(grammar::simplify::EpsilonRemover::remove(grammar))));
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToGNF::convert(const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar::simplify::LeftRecursionRemover::remove(grammar::simplify::EpsilonRemover::remove(grammar))));
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > ToGNF::convert(const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convert::ToGrammarRightRG::convert(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, ext::variant < TerminalSymbolType, NonterminalSymbolType > > ToGNF::convert(const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convertInternal(grammar::simplify::SimpleRulesRemover::remove(grammar::simplify::LeftRecursionRemover::remove(grammar::simplify::EpsilonRemover::remove(grammar))));
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > ToGNF::convert(const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
} /* namespace simplify */
 
} /* namespace grammar */