LeftRecursionRemover.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
 
#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 <grammar/convert/ToGrammarRightRG.h>
#include <exception/CommonException.h>
 
#include <alib/vector>
#include <common/createUnique.hpp>
 
namespace grammar {
 
namespace simplify {
 
class LeftRecursionRemover {
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > directLeftRecursionRemoveAsOrder ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > assignAsOrder ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, unsigned i, const ext::set < NonterminalSymbolType > & origNonterminals );
public:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::GNF < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > remove( const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & grammar );
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::directLeftRecursionRemoveAsOrder(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 auto& nonterminal : grammar.getNonterminalAlphabet()) {
        if(grammar.getRules().find(nonterminal) == grammar.getRules().end()) continue;
 
        if(std::any_of(grammar.getRules().find(nonterminal)->second.begin(), grammar.getRules().find(nonterminal)->second.end(), [&](const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & singleRHS ) {
                return singleRHS[0] == nonterminal; // is there a direct left recursion?
            } ) && std::all_of(grammar.getRules().find(nonterminal)->second.begin(), grammar.getRules().find(nonterminal)->second.end(), [&](const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & singleRHS) {
                return grammar.getTerminalAlphabet().count(singleRHS[0]) || singleRHS[0] >= nonterminal; // only remove left recursion when all nonterminals are bigger than the left hand side
            })) {
            NonterminalSymbolType primed = common::createUnique(nonterminal, res.getTerminalAlphabet(), res.getNonterminalAlphabet());
            res.addNonterminalSymbol(primed);
            for(const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & singleRHS : grammar.getRules().find(nonterminal)->second) { // do the removal
                if(singleRHS[0] == nonterminal) { // A -> A alpha
                    ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmpRHS(singleRHS.begin() + 1, singleRHS.end());
 
                    res.addRule(primed, tmpRHS); // A' -> alpha
 
                    tmpRHS.push_back(primed);
                    res.addRule(primed, tmpRHS); // A' -> alpha A'
                } else { // a -> beta
                    ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > tmpRHS(singleRHS);
 
                    res.addRule(nonterminal, tmpRHS); // A -> beta
 
                    tmpRHS.push_back(primed);
                    res.addRule(nonterminal, tmpRHS); // A -> beta A'
                }
            }
        } else {
            for(const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & singleRHS : grammar.getRules().at(nonterminal)) {
                res.addRule(nonterminal, singleRHS);
            }
        }
    }
    return res;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::assignAsOrder ( const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar, unsigned i, const ext::set < NonterminalSymbolType > & origNonterminals) {
    grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > res(grammar.getInitialSymbol());
    res.setNonterminalAlphabet(grammar.getNonterminalAlphabet());
    res.setTerminalAlphabet(grammar.getTerminalAlphabet());
    res.setGeneratesEpsilon(grammar.getGeneratesEpsilon());
 
    for(const NonterminalSymbolType& lhs : grammar.getNonterminalAlphabet()) {
        if(i > 0) {
            if(grammar.getRules().find(lhs) == grammar.getRules().end()) continue;
            for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rule : grammar.getRules().find(lhs)->second) {
                res.addRule(lhs, rule);
            }
 
            i--;
            continue; // substitue only in i-th up to n-th nonterminals
        }
        if(grammar.getRules().find(lhs) == grammar.getRules().end()) continue;
        if(!origNonterminals.contains(lhs)) { // do not subsitute in nonoriginal nonterminals
            for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rule : grammar.getRules().find(lhs)->second) {
                res.addRule(lhs, rule);
            }
            continue;
        }
 
        const ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > & rule = grammar.getRules().find(lhs)->second;
 
        for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & singleRHS : rule ) {
            if(res.getTerminalAlphabet().contains(singleRHS[0])) { //do not substitute terminals
                res.addRule(lhs, singleRHS);
                continue;
            }
            const ext::variant < TerminalSymbolType, NonterminalSymbolType > & secondLHS = singleRHS[0];
            if(secondLHS >= lhs) { // substitute only by 0th up to i-th nonterminals right hand sides
                res.addRule(lhs, singleRHS);
                continue;
            }
            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(lhs, newRHS);
            }
        }
    }
    return res;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::remove(const grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > step = grammar;
    for(const NonterminalSymbolType& nonterminal : step.getNonterminalAlphabet()) { // remove identities
        step.removeRule(nonterminal, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > >{nonterminal});
    }
    unsigned i = 0;
    while(i < grammar.getNonterminalAlphabet().size()) {
        grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > nextStep = assignAsOrder(directLeftRecursionRemoveAsOrder(step), i, grammar.getNonterminalAlphabet());
 
        if(step == nextStep) break;
        step = std::move(nextStep);
        i++;
    };
 
    return step;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::remove(const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    EpsilonFreeCFG < TerminalSymbolType, NonterminalSymbolType > tmp(grammar.getInitialSymbol());
    tmp.setTerminalAlphabet(grammar.getTerminalAlphabet());
    tmp.setNonterminalAlphabet(grammar.getNonterminalAlphabet());
    tmp.setGeneratesEpsilon(grammar.getGeneratesEpsilon());
    for(const auto& rule : grammar.getRules()) {
        for(const auto& rhs : rule.second) {
            if(rhs.template is < TerminalSymbolType > ( ) ) {
                tmp.addRule ( rule.first, { rhs.template get < TerminalSymbolType > ( ) } );
            } else {
                const auto & rhsPair = rhs.template get < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( );
                tmp.addRule(rule.first, {rhsPair.first, rhsPair.second});
            }
        }
    }
    return remove(tmp);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::GNF < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::remove(const grammar::GNF < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::remove(const grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::remove(const grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return grammar;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightRG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::remove(const grammar::LeftRG < TerminalSymbolType, NonterminalSymbolType > & grammar) {
    return convert::ToGrammarRightRG::convert(grammar);
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
grammar::RightLG < TerminalSymbolType, NonterminalSymbolType > LeftRecursionRemover::remove(const grammar::LeftLG < TerminalSymbolType, NonterminalSymbolType > & /* grammar */) {
    throw exception::CommonException("LeftRecursionRemover: Removing from LeftLG NYI"); // TODO
}
 
} /* namespace simplify */
 
} /* namespace grammar */