RightRegularEquationSolver.h

Go to the documentation of this file.

 
#pragma once
 
#include "RegularEquationSolver.h"
#include "regexp/unbounded/UnboundedRegExpElements.h"
 
#include <regexp/simplify/RegExpOptimize.h>
 
namespace equations {
 
template < class TerminalSymbolType, class VariableSymbolType >
class RightRegularEquationSolver : public RegularEquationSolver < TerminalSymbolType, VariableSymbolType > {
    regexp::UnboundedRegExp < TerminalSymbolType > eliminate ( ) override;
 
};
 
template < class TerminalSymbolType, class VariableSymbolType >
regexp::UnboundedRegExp < TerminalSymbolType > RightRegularEquationSolver < TerminalSymbolType, VariableSymbolType >::eliminate ( ) {
    for ( auto itA = this->nonterminalSymbolsByDepth.rbegin ( ); itA != this->nonterminalSymbolsByDepth.rend ( ); ++ itA ) {
        const VariableSymbolType & a = * itA;
 
        /*
         * Apply Arden's Lemma
         * A = 0A + 1B + 2C
         * => A = 0*1B + 0*2C
         */
        regexp::UnboundedRegExpIteration < TerminalSymbolType > loop ( std::move ( this->equationTransition.at ( std::make_pair ( a, a ) ) ) );
        regexp::simplify::RegExpOptimize::optimize ( loop );
 
        // for all transitions from A apply Arden's Lemma
        for ( auto itB = std::next ( itA ); itB != this->nonterminalSymbolsByDepth.rend ( ); ++ itB ) {
            const VariableSymbolType & b = * itB;
 
            regexp::UnboundedRegExpConcatenation < TerminalSymbolType > concat;
            concat.appendElement ( loop );
            concat.appendElement ( std::move ( this->equationTransition.at ( std::make_pair ( a, b ) ) ) );
            regexp::UnboundedRegExpAlternation < TerminalSymbolType > alt;
            alt.appendElement ( std::move ( concat ) );
            this->equationTransition.at ( std::make_pair ( a, b ) ) = std::move ( alt );
            regexp::simplify::RegExpOptimize::optimize ( this->equationTransition.at ( std::make_pair ( a, b ) ) );
        }
 
        {
            regexp::UnboundedRegExpConcatenation < TerminalSymbolType > concat;
            concat.appendElement ( std::move ( loop ) );
            concat.appendElement ( std::move ( this->equationFinal.at ( a ) ) );
            regexp::UnboundedRegExpAlternation < TerminalSymbolType > alt;
            alt.appendElement ( std::move ( concat ) );
            this->equationFinal.at ( a ) = std::move ( alt );
            regexp::simplify::RegExpOptimize::optimize ( this->equationFinal.at ( a ) );
        }
 
        /*
         * eliminate A from rest of the equations using this pattern:
         * B->C = B->C + concatenate(B->A, A->C)
         */
        for ( auto itB = std::next ( itA ); itB != this->nonterminalSymbolsByDepth.rend ( ); ++ itB ) {
            const VariableSymbolType & b = * itB;
 
            for ( auto itC = std::next ( itA ); itC != this->nonterminalSymbolsByDepth.rend ( ); ++ itC ) {
                const VariableSymbolType & c = * itC;
 
                regexp::UnboundedRegExpConcatenation < TerminalSymbolType > concat;
                concat.appendElement ( this->equationTransition.at ( std::make_pair ( b, a ) ) );
                concat.appendElement ( this->equationTransition.at ( std::make_pair ( a, c ) ) );
                regexp::UnboundedRegExpAlternation < TerminalSymbolType > alt;
                alt.appendElement ( std::move ( this->equationTransition.at ( std::make_pair ( b, c ) ) ) );
                alt.appendElement ( std::move ( concat ) );
                this->equationTransition.at ( std::make_pair ( b, c ) ) = std::move ( alt );
                regexp::simplify::RegExpOptimize::optimize ( this->equationTransition.at ( std::make_pair ( b, c ) ) );
            }
 
            {
                regexp::UnboundedRegExpConcatenation < TerminalSymbolType > concat;
                concat.appendElement ( std::move ( this->equationTransition.at ( std::make_pair ( b, a ) ) ) );
                concat.appendElement ( this->equationFinal.at ( a ) );
                regexp::UnboundedRegExpAlternation < TerminalSymbolType > alt;
                alt.appendElement ( std::move ( this->equationFinal.at ( b ) ) );
                alt.appendElement ( std::move ( concat ) );
                this->equationFinal.at ( b ) = std::move ( alt );
                regexp::simplify::RegExpOptimize::optimize ( this->equationFinal.at ( b ) );
            }
        }
    }
 
    return regexp::UnboundedRegExp < TerminalSymbolType > ( regexp::simplify::RegExpOptimize::optimize ( regexp::UnboundedRegExpStructure < TerminalSymbolType > ( std::move ( this->equationFinal.at ( * this->nonterminalSymbolsByDepth.begin ( ) ) ) ) ) );
}
 
} /* namespace equations */