ToAutomatonGlushkov.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/pair>
 
#include <regexp/formal/FormalRegExp.h>
#include <regexp/unbounded/UnboundedRegExp.h>
 
#include <automaton/FSM/NFA.h>
 
#include <global/GlobalData.h>
 
#include "../glushkov/GlushkovFirst.h"
#include "../glushkov/GlushkovFollow.h"
#include "../glushkov/GlushkovIndexate.h"
#include "../glushkov/GlushkovLast.h"
 
#include <regexp/properties/RegExpEpsilon.h>
#include <exception/CommonException.h>
 
#include <label/InitialStateLabel.h>
 
namespace regexp {
 
namespace convert {
 
class ToAutomatonGlushkov {
public:
    template < class SymbolType >
    static automaton::NFA < SymbolType, ext::pair < SymbolType, unsigned > > convert ( const regexp::UnboundedRegExp < SymbolType > & regexp );
 
    template < class SymbolType >
    static automaton::NFA < SymbolType, ext::pair < SymbolType, unsigned > > convert ( const regexp::FormalRegExp < SymbolType > & regexp );
 
};
 
template < class SymbolType >
automaton::NFA < SymbolType, ext::pair < SymbolType, unsigned > > ToAutomatonGlushkov::convert ( const regexp::UnboundedRegExp < SymbolType > & regexp ) {
    ext::pair < SymbolType, unsigned > q0 ( label::InitialStateLabel::instance < SymbolType > ( ), 0 );
    automaton::NFA < SymbolType, ext::pair < SymbolType, unsigned > > automaton ( q0 );
 
     // step 1
    automaton.setInputAlphabet ( 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 ext::pair < SymbolType, unsigned > & symbol : indexedRegExp.getAlphabet ( ) )
        automaton.addState ( symbol );
 
     // step 6
    for ( const regexp::UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : first )
        automaton.addTransition ( q0, symbol.getSymbol ( ).first, symbol.getSymbol ( ) );
 
    for ( const ext::pair < SymbolType, unsigned > & x : indexedRegExp.getAlphabet ( ) )
        for ( const auto & f : regexp::GlushkovFollow::follow ( indexedRegExp, UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > ( x ) ) ) {
            const ext::pair < SymbolType, unsigned > & p = x;
            const ext::pair < SymbolType, unsigned > & q = f.getSymbol ( );
 
            automaton.addTransition ( p, q.first, q );
        }
 
    // step 7
 
    for ( const regexp::UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : last )
        automaton.addFinalState ( symbol.getSymbol ( ) );
 
    if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( regexp ) )
        automaton.addFinalState ( q0 );
 
    if ( common::GlobalData::verbose ) {
        common::Streams::log << "First:" << first << std::endl;
        common::Streams::log << "Last: " << last << std::endl;
 
        if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( regexp ) )
            common::Streams::log << "      q0 because #E in L(RE)" << std::endl;
 
        for ( const ext::pair < SymbolType, unsigned > & x : indexedRegExp.getAlphabet ( ) )
            common::Streams::log << "Follow(" << x << ") = " << regexp::GlushkovFollow::follow ( indexedRegExp, UnboundedRegExpSymbol < ext::pair < SymbolType, unsigned > > ( x ) ) << std::endl;
    }
 
    return automaton;
}
 
template < class SymbolType >
automaton::NFA < SymbolType, ext::pair < SymbolType, unsigned > > ToAutomatonGlushkov::convert ( const regexp::FormalRegExp < SymbolType > & regexp ) {
    ext::pair < SymbolType, unsigned > q0 ( label::InitialStateLabel::instance < SymbolType > ( ), 0 );
    automaton::NFA < SymbolType, ext::pair < SymbolType, unsigned > > automaton ( q0 );
 
     // step 1
    automaton.setInputAlphabet ( regexp.getAlphabet ( ) );
 
    regexp::FormalRegExp < ext::pair < SymbolType, unsigned > > indexedRegExp = regexp::GlushkovIndexate::index ( regexp );
 
     // steps 2, 3, 4
    const ext::set < regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > > first = regexp::GlushkovFirst::first ( indexedRegExp );
    const ext::set < regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > > last = regexp::GlushkovLast::last ( indexedRegExp );
 
    // \e in q0 check is in step 7
 
     // step 5
    for ( const ext::pair < SymbolType, unsigned > & symbol : indexedRegExp.getAlphabet ( ) )
        automaton.addState ( symbol );
 
     // step 6
    for ( const regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : first )
        automaton.addTransition ( q0, symbol.getSymbol ( ).first, symbol.getSymbol ( ) );
 
    const ext::map < regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > >, ext::set < regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > > > follow = regexp::GlushkovFollow::follow ( indexedRegExp );
    for ( const std::pair < const regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > >, ext::set < regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > > > & entry : follow )
        for ( const auto & f : entry.second ) {
            const ext::pair < SymbolType, unsigned > & p = entry.first.getSymbol ( );
            const ext::pair < SymbolType, unsigned > & q = f.getSymbol ( );
 
            automaton.addTransition ( p, q.first, q );
        }
 
    // step 7
 
    for ( const regexp::FormalRegExpSymbol < ext::pair < SymbolType, unsigned > > & symbol : last )
        automaton.addFinalState ( symbol.getSymbol ( ) );
 
    if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( regexp ) )
        automaton.addFinalState ( q0 );
 
    if ( common::GlobalData::verbose ) {
        common::Streams::log << "First:" << first << std::endl;
        common::Streams::log << "Last: " << last << std::endl;
 
        if ( regexp::properties::RegExpEpsilon::languageContainsEpsilon ( regexp ) )
            common::Streams::log << "      q0 because #E in L(RE)" << std::endl;
 
        common::Streams::log << "Follow: " << regexp::GlushkovFollow::follow ( indexedRegExp ) << std::endl;
    }
 
    return automaton;
}
 
} /* namespace convert */
 
} /* namespace regexp */