ToGrammarRightRGGlushkov.h

Go to the documentation of this file.

 
#pragma once
 
#include <grammar/Regular/RightRG.h>
#include <regexp/formal/FormalRegExp.h>
#include <regexp/unbounded/UnboundedRegExp.h>
 
#include <ext/algorithm>
 
#include <alphabet/InitialSymbol.h>
 
#include "../glushkov/GlushkovFollow.h"
#include "../glushkov/GlushkovIndexate.h"
#include "../glushkov/GlushkovFirst.h"
#include "../glushkov/GlushkovLast.h"
 
#include <regexp/properties/RegExpEpsilon.h>
 
namespace regexp {
 
namespace convert {
 
class ToGrammarRightRGGlushkov {
public:
    template < class SymbolType >
    static grammar::RightRG < SymbolType, ext::pair < SymbolType, unsigned > > convert(const regexp::FormalRegExp < SymbolType > & regexp);
 
    template < class SymbolType >
    static grammar::RightRG < SymbolType, ext::pair < SymbolType, unsigned > > convert(const regexp::UnboundedRegExp < SymbolType > & regexp);
};
 
template < class SymbolType >
grammar::RightRG < SymbolType, ext::pair < SymbolType, unsigned > > ToGrammarRightRGGlushkov::convert ( const regexp::UnboundedRegExp < SymbolType > & regexp ) {
    ext::pair < SymbolType, unsigned > S = ext::make_pair ( alphabet::InitialSymbol::instance < SymbolType > ( ), 0 );
    grammar::RightRG < SymbolType, ext::pair < SymbolType, unsigned > > grammar ( S );
 
     // step 1
    grammar.setTerminalAlphabet ( regexp.getAlphabet ( ) );
 
    regexp::UnboundedRegExp < ext::pair < SymbolType, unsigned > > indexedRegExp = regexp::GlushkovIndexate::index ( regexp );
 
     // steps 2, 3, 4
    const ext::set < regexp::UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > > first = regexp::GlushkovFirst::first ( indexedRegExp );
    const ext::set < regexp::UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > > last = regexp::GlushkovLast::last ( indexedRegExp );
 
    // \e in q0 check is in step 7
 
     // step 5
    for ( const auto & nonterminal : indexedRegExp.getAlphabet ( ) )
        grammar.addNonterminalSymbol ( nonterminal );
 
     // step 6
    for ( const regexp::UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : first )
        grammar.addRule ( S, ext::make_pair ( symbol.getSymbol ( ).first, symbol.getSymbol ( ) ) );
 
    for ( const ext::pair < SymbolType, unsigned > & x : indexedRegExp.getAlphabet ( ) )
        for ( const regexp::UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > & f : regexp::GlushkovFollow::follow ( indexedRegExp, UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > ( x ) ) ) {
            const ext::pair < SymbolType, unsigned > & a = x;
            const ext::pair < SymbolType, unsigned > & b = f.getSymbol ( );
 
            grammar.addRule ( a, ext::make_pair ( b.first, b ) );
        }
 
    // step 7
 
    /*
     * for all rules where ns.m_nonTerminal is on rightSide:
     *  add Rule: leftSide -> symbol.getSymbol( )
     *  unless it already exists
     */
    for ( const auto & rule : grammar.getRules ( ) )
        for ( const auto & rhs : rule.second ) {
            if ( ! rhs.template is < ext::pair < SymbolType, ext::pair < SymbolType, unsigned > > > ( ) )
                continue;
 
            const ext::pair < SymbolType, ext::pair < SymbolType, unsigned > > & rawRhs = rhs.template get < ext::pair < SymbolType, ext::pair < SymbolType, unsigned >  > > ( );
 
            for ( const regexp::UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : last )
                if ( rawRhs.second == symbol.getSymbol ( ) )
                    grammar.addRule ( rule.first, rawRhs.first );
        }
 
    if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( regexp ) )
        grammar.setGeneratesEpsilon ( true );
 
    return grammar;
}
 
template < class SymbolType >
grammar::RightRG < SymbolType, ext::pair < SymbolType, unsigned > > ToGrammarRightRGGlushkov::convert ( const regexp::FormalRegExp < SymbolType > & regexp ) {
    return ToGrammarRightRGGlushkov::convert ( regexp::UnboundedRegExp < SymbolType > ( regexp ) );
}
 
} /* namespace convert */
 
} /* namespace regexp */