GlushkovRRG.cpp

/*
 * GlushkovRRG.cpp
 *
 *  Created on: 11. 1. 2014
 *      Author: tomas
 */

#include "GlushkovRRG.h"

using namespace alib;
using namespace alphabet;
using namespace grammar;
using namespace regexp;
using namespace std;

namespace conversions
{

GlushkovRRG::GlushkovRRG( const RegExp & re ) : m_re( re )
{

}

GlushkovRRG::~GlushkovRRG( void )
{

}

RightRegularGrammar GlushkovRRG::convert( void )
{
    RightRegularGrammar grammar;

    // step 1
    for( auto const& symbol : m_re.getAlphabet( ) )
        grammar.addTerminalSymbol( symbol.getSymbol( ) );

    // steps 2, 3, 4
    m_first = GlushkovTraversal::first( m_re );
    m_last = GlushkovTraversal::last( m_re );
    for( auto const& x : GlushkovTraversal::getSymbols( m_re ) )
        for( auto const& f : GlushkovTraversal::follow( m_re, x ) )
            m_pairs.insert( GlushkovPair( x, f ) );
    // \e in q0 check is in step 7

    // step 5
    Symbol S = grammar.createUniqueNonTerminalSymbol( "S" );
    grammar.setStartSymbol( S );

    int nonterminalId = 0;

    for( auto const& symbol : GlushkovTraversal::getSymbols( m_re ) )
    {
        Symbol a = grammar.createUniqueNonTerminalSymbol( toBase26( nonterminalId ++ ) + to_string( symbol.getId( ) ) );

        m_symbolMap.insert( std::pair<GlushkovSymbol, Symbol>( symbol, a ) );
    }

    // step 6
    for( auto const& symbol : m_first )
    {
        Symbol const& a = m_symbolMap.find( symbol )->second;

        list<Symbol> leftSide = { S };
        list<Symbol> rightSide = { symbol.getInputSymbol( ), a };
        grammar.addRule( Rule( leftSide, rightSide ) );
    }

    for( auto const& pair : m_pairs )
    {
        Symbol const& a = m_symbolMap.find( pair.getFirst( ) )->second;
        Symbol const& b = m_symbolMap.find( pair.getSecond( ) )->second;

        list<Symbol> leftSide = { a };
        list<Symbol> rightSide = { pair.getSecond( ).getInputSymbol( ), b };

        grammar.addRule( Rule( leftSide, rightSide ) );
    }

    // step 7
    for( auto const& symbol : m_last )
    {
        /*
         * for all rules where ns.m_nonTerminal is on rightSide:
         *  add Rule: leftSide -> symbol.getSymbol( )
         *  unless it already exists
         */

        Symbol const& a = m_symbolMap.find( symbol )->second;

        for( auto const & rule : grammar.getRules( ) )
        {
            if( isInList( a, rule.getRightSide( ) ) )
            {
                list<Symbol> leftSide = rule.getLeftSide( );
                list<Symbol> rightSide = { symbol.getInputSymbol( ) };
                Rule r( leftSide, rightSide );

                if( ! isInSet( r, grammar.getRules( ) ) )
                    grammar.addRule( r );
            }
        }
    }

    if( m_re.containsEmptyString( ) )
    {
        list<Symbol> leftSide = { S };
        list<Symbol> rightSide = { };
        grammar.addRule( Rule( leftSide, rightSide ) );
    }

    return grammar;
}

} /* namespace conversions */