ToGrammarRightRGDerivation.h

Go to the documentation of this file.

 
#pragma once
 
#include <grammar/Regular/RightRG.h>
#include <regexp/RegExp.h>
#include <regexp/formal/FormalRegExp.h>
#include <regexp/unbounded/UnboundedRegExp.h>
 
#include <ext/hexavigesimal>
 
#include <alib/set>
#include <alib/deque>
#include <alib/vector>
 
#include <common/createUnique.hpp>
 
#include <regexp/simplify/RegExpOptimize.h>
#include <regexp/transform/RegExpDerivation.h>
#include <regexp/properties/RegExpEpsilon.h>
 
namespace regexp {
 
namespace convert {
 
class ToGrammarRightRGDerivation {
public:
    template  < class T, class SymbolType = typename regexp::SymbolTypeOfRegexp < T > >
    static grammar::RightRG < SymbolType, unsigned > convert ( const T & regexp );
 
};
 
template < class T, class SymbolType >
grammar::RightRG < SymbolType, unsigned > ToGrammarRightRGDerivation::convert ( const T & regexp ) {
    // 1.
    T V = regexp::simplify::RegExpOptimize::optimize(regexp);
 
    // 2., 3.
    unsigned nonterminalId = 0;
    ext::map < T, unsigned > nonterminalMap;
 
    unsigned ntV = common::createUnique ( nonterminalId ++, regexp.getAlphabet ( ) );
    nonterminalMap.insert ( std::make_pair ( V, ntV ) );
 
    grammar::RightRG < SymbolType, unsigned > grammar(ntV);
    grammar.setTerminalAlphabet ( regexp.getAlphabet ( ) );
 
    ext::deque < T > Ni;
 
    Ni.push_back ( V );
 
    while(! Ni.empty()) {
        T r = std::move ( Ni.back ( ) );
        Ni.pop_back ( );
 
        for(const auto & a : regexp.getAlphabet()) {
            T derived = regexp::transform::RegExpDerivation::derivation(r, a);
            derived = regexp::simplify::RegExpOptimize::optimize(derived);
 
            // this will also add \emptyset as a regexp (and as FA state)
            if ( ! nonterminalMap.contains ( derived ) ) { // if this state has already been found, do not add
                Ni.push_back(derived);
                unsigned nt = common::createUnique ( nonterminalId ++, grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ) );
                grammar.addNonterminalSymbol ( nt );
                nonterminalMap.insert ( derived, nt );
            }
 
            if(regexp::properties::RegExpEpsilon::languageContainsEpsilon(derived))
                grammar.addRule(nonterminalMap.at(r), a);
 
            grammar.addRule(nonterminalMap.at(r), ext::make_pair(a, nonterminalMap.at(derived)));
        }
    }
 
    if(regexp::properties::RegExpEpsilon::languageContainsEpsilon(V))
        grammar.setGeneratesEpsilon(true); // okay, because of this feature we do not have to bother with extending the grammar with new rules and nonterminals. YAY!
 
    return grammar;
}
 
} /* namespace convert */
 
} /* namespace regexp */