LG.h

Go to the documentation of this file.

 
/*
 * This file is part of Algorithms library toolkit.
 * Copyright (C) 2017 Jan Travnicek (jan.travnicek@fit.cvut.cz)
 
 * Algorithms library toolkit is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 
 * Algorithms library toolkit is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 
 * You should have received a copy of the GNU General Public License
 * along with Algorithms library toolkit.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#pragma once
 
 
#include <ext/algorithm>
 
#include <alib/map>
#include <alib/set>
#include <alib/tuple>
#include <alib/vector>
#include <alib/variant>
 
#include <core/components.hpp>
 
#include <common/DefaultSymbolType.h>
 
#include <grammar/GrammarException.h>
 
#include <core/normalize.hpp>
#include <alphabet/common/SymbolNormalize.h>
#include <grammar/common/GrammarNormalize.h>
 
namespace grammar {
 
class TerminalAlphabet;
class NonterminalAlphabet;
class InitialSymbol;
 
template < class TerminalSymbolType = DefaultSymbolType, class NonterminalSymbolType = DefaultSymbolType >
class LG final : public core::Components < LG < TerminalSymbolType, NonterminalSymbolType >, ext::set < TerminalSymbolType >, component::Set, TerminalAlphabet, ext::set < NonterminalSymbolType >, component::Set, NonterminalAlphabet, NonterminalSymbolType, component::Value, InitialSymbol > {
    ext::map < NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > rules;
 
public:
    explicit LG ( NonterminalSymbolType initialSymbol );
 
    explicit LG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol );
 
    bool addRule ( NonterminalSymbolType leftHandSide, ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > rightHandSide );
 
    void addRules ( NonterminalSymbolType leftHandSide, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > rightHandSide );
 
    const ext::map < NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > & getRules ( ) const &;
 
    ext::map < NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > && getRules ( ) &&;
 
    bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > & rightHandSide );
 
    bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::vector < TerminalSymbolType > & rightHandSide );
 
    bool removeRule ( const NonterminalSymbolType & leftHandSide, const ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > & rightHandSide );
 
    const NonterminalSymbolType & getInitialSymbol ( ) const & {
        return this->template accessComponent < InitialSymbol > ( ).get ( );
    }
 
    NonterminalSymbolType && getInitialSymbol ( ) && {
        return std::move ( this->template accessComponent < InitialSymbol > ( ).get ( ) );
    }
 
    bool setInitialSymbol ( NonterminalSymbolType symbol ) {
        return this->template accessComponent < InitialSymbol > ( ).set ( std::move ( symbol ) );
    }
 
    const ext::set < NonterminalSymbolType > & getNonterminalAlphabet ( ) const & {
        return this->template accessComponent < NonterminalAlphabet > ( ).get ( );
    }
 
    ext::set < NonterminalSymbolType > && getNonterminalAlphabet ( ) && {
        return std::move ( this->template accessComponent < NonterminalAlphabet > ( ).get ( ) );
    }
 
    bool addNonterminalSymbol ( NonterminalSymbolType symbol ) {
        return this->template accessComponent < NonterminalAlphabet > ( ).add ( std::move ( symbol ) );
    }
 
    void setNonterminalAlphabet ( ext::set < NonterminalSymbolType > symbols ) {
        this->template accessComponent < NonterminalAlphabet > ( ).set ( std::move ( symbols ) );
    }
 
    const ext::set < TerminalSymbolType > & getTerminalAlphabet ( ) const & {
        return this->template accessComponent < TerminalAlphabet > ( ).get ( );
    }
 
    ext::set < TerminalSymbolType > && getTerminalAlphabet ( ) && {
        return std::move ( this->template accessComponent < TerminalAlphabet > ( ).get ( ) );
    }
 
    bool addTerminalSymbol ( TerminalSymbolType symbol ) {
        return this->template accessComponent < TerminalAlphabet > ( ).add ( std::move ( symbol ) );
    }
 
    void setTerminalAlphabet ( ext::set < TerminalSymbolType > symbols ) {
        this->template accessComponent < TerminalAlphabet > ( ).set ( std::move ( symbols ) );
    }
 
    auto operator <=> ( const LG & other ) const {
        return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) <=> std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
    }
 
    bool operator == ( const LG & other ) const {
        return std::tie ( getTerminalAlphabet ( ), getNonterminalAlphabet ( ), getInitialSymbol ( ), rules ) == std::tie ( other.getTerminalAlphabet ( ), other.getNonterminalAlphabet ( ), other.getInitialSymbol ( ), other.rules );
    }
 
    friend ext::ostream & operator << ( ext::ostream & out, const LG & instance ) {
        return out << "(LG"
               << " nonterminalAlphabet = " << instance.getNonterminalAlphabet ( )
               << " terminalAlphabet = " << instance.getTerminalAlphabet ( )
               << " initialSymbol = " << instance.getInitialSymbol ( )
               << " rules = " << instance.getRules ( )
               << ")";
    }
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
LG < TerminalSymbolType, NonterminalSymbolType >::LG ( NonterminalSymbolType initialSymbol ) : LG ( ext::set < NonterminalSymbolType > { initialSymbol }, ext::set < TerminalSymbolType > ( ), initialSymbol ) {
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
LG < TerminalSymbolType, NonterminalSymbolType >::LG ( ext::set < NonterminalSymbolType > nonterminalAlphabet, ext::set < TerminalSymbolType > terminalAlphabet, NonterminalSymbolType initialSymbol ) : core::Components < LG, ext::set < TerminalSymbolType >, component::Set, TerminalAlphabet, ext::set < NonterminalSymbolType >, component::Set, NonterminalAlphabet, NonterminalSymbolType, component::Value, InitialSymbol > ( std::move ( terminalAlphabet), std::move ( nonterminalAlphabet ), std::move ( initialSymbol ) ) {
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
bool LG < TerminalSymbolType, NonterminalSymbolType >::addRule ( NonterminalSymbolType leftHandSide, ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > rightHandSide ) {
    if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
        throw GrammarException ( "Rule must rewrite nonterminal symbol" );
 
    if ( rightHandSide.template is < ext::vector < TerminalSymbolType > > ( ) ) {
        const ext::vector < TerminalSymbolType > & rhs = rightHandSide.template get < ext::vector < TerminalSymbolType > > ( );
 
        for ( const TerminalSymbolType & symbol : rhs )
            if ( !getTerminalAlphabet ( ).count ( symbol ) )
                throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
    } else {
        const ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > & rhs = rightHandSide.template get < ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > ( );
 
        for ( const TerminalSymbolType & symbol : std::get < 0 > ( rhs ) )
            if ( !getTerminalAlphabet ( ).count ( symbol ) )
                throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
 
        if ( !getNonterminalAlphabet ( ).count ( std::get < 1 > ( rhs ) ) )
            throw GrammarException ( "Symbol " + ext::to_string ( std::get < 1 > ( rhs ) ) + " is not a nonterminal symbol" );
 
        for ( const TerminalSymbolType & symbol : std::get < 2 > ( rhs ) )
            if ( !getTerminalAlphabet ( ).count ( symbol ) )
                throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
    }
 
    return rules[std::move ( leftHandSide )].insert ( std::move ( rightHandSide ) ).second;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
void LG < TerminalSymbolType, NonterminalSymbolType >::addRules ( NonterminalSymbolType leftHandSide, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > rightHandSide ) {
    if ( !getNonterminalAlphabet ( ).count ( leftHandSide ) )
        throw GrammarException ( "Rule must rewrite nonterminal symbol" );
 
    for ( const ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > & element : rightHandSide ) {
        if ( element.template is < ext::vector < TerminalSymbolType > > ( ) ) {
            const ext::vector < TerminalSymbolType > & rhs = element.template get < ext::vector < TerminalSymbolType > > ( );
 
            for ( const TerminalSymbolType & symbol : rhs )
                if ( !getTerminalAlphabet ( ).count ( symbol ) )
                    throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
        } else {
            const ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > & rhs = element.template get < ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > ( );
 
            for ( const TerminalSymbolType & symbol : std::get < 0 > ( rhs ) )
                if ( !getTerminalAlphabet ( ).count ( symbol ) )
                    throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
 
            if ( !getNonterminalAlphabet ( ).count ( std::get < 1 > ( rhs ) ) )
                throw GrammarException ( "Symbol " + ext::to_string ( std::get < 1 > ( rhs ) ) + " is not a nonterminal symbol" );
 
            for ( const TerminalSymbolType & symbol : std::get < 2 > ( rhs ) )
                if ( !getTerminalAlphabet ( ).count ( symbol ) )
                    throw GrammarException ( "Symbol " + ext::to_string ( symbol ) + " is not a terminal symbol" );
        }
    }
 
    rules [ std::move ( leftHandSide ) ].insert ( ext::make_mover ( rightHandSide ).begin ( ), ext::make_mover ( rightHandSide ).end ( ) );
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
const ext::map < NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > & LG < TerminalSymbolType, NonterminalSymbolType >::getRules ( ) const & {
    return rules;
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
ext::map < NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > && LG < TerminalSymbolType, NonterminalSymbolType >::getRules ( ) && {
    return std::move ( rules );
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
bool LG < TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType & leftHandSide, const ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > & rightHandSide ) {
    return rules[leftHandSide].erase ( rightHandSide );
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
bool LG < TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType & leftHandSide, const ext::vector < TerminalSymbolType > & rightHandSide ) {
    ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > rhs ( rightHandSide );
 
    return removeRule ( leftHandSide, rhs );
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
bool LG < TerminalSymbolType, NonterminalSymbolType >::removeRule ( const NonterminalSymbolType & leftHandSide, const ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > & rightHandSide ) {
    ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > rhs ( rightHandSide );
 
    return removeRule ( leftHandSide, rhs );
}
 
} /* namespace grammar */
 
namespace core {
 
template < class TerminalSymbolType, class NonterminalSymbolType >
class SetConstraint< grammar::LG < TerminalSymbolType, NonterminalSymbolType >, TerminalSymbolType, grammar::TerminalAlphabet > {
public:
    static bool used ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
        for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > & rule : grammar.getRules ( ) ) {
            for ( const ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > & rhsTmp : rule.second )
                if ( rhsTmp.template is < ext::vector < TerminalSymbolType > > ( ) ) {
                    const ext::vector < TerminalSymbolType > & rhs = rhsTmp.template get < ext::vector < TerminalSymbolType > > ( );
 
                    if ( std::find ( rhs.begin ( ), rhs.end ( ), symbol ) != rhs.end ( ) )
                        return true;
                } else {
                    const ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > & rhs = rhsTmp.template get < ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > ( );
 
                    const ext::vector < TerminalSymbolType > & lPart = std::get < 0 > ( rhs );
 
                    if ( std::find ( lPart.begin ( ), lPart.end ( ), symbol ) != lPart.end ( ) )
                        return true;
 
                    const ext::vector < TerminalSymbolType > & rPart = std::get < 2 > ( rhs );
 
                    if ( std::find ( rPart.begin ( ), rPart.end ( ), symbol ) != rPart.end ( ) )
                        return true;
                }
 
        }
 
        return false;
    }
 
    static bool available ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > &, const TerminalSymbolType & ) {
        return true;
    }
 
    static void valid ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar, const TerminalSymbolType & symbol ) {
        if ( grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
            throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the terminal alphabet since it is already in the nonterminal alphabet." );
    }
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
class SetConstraint< grammar::LG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::NonterminalAlphabet > {
public:
    static bool used ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
        for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > & rule : grammar.getRules ( ) ) {
            if ( rule.first == symbol )
                return true;
 
            for ( const ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > & rhsTmp : rule.second )
                if ( rhsTmp.template is < ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > ( ) ) {
                    const ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > & rhs = rhsTmp.template get < ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > ( );
 
                    if ( std::get < 1 > ( rhs ) == symbol )
                        return true;
                }
 
        }
 
        return grammar.template accessComponent < grammar::InitialSymbol > ( ).get ( ) == symbol;
    }
 
    static bool available ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
        return true;
    }
 
    static void valid ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
        if ( grammar.template accessComponent < grammar::TerminalAlphabet > ( ).get ( ).count ( ext::poly_comp ( symbol ) ) )
            throw grammar::GrammarException ( "Symbol " + ext::to_string ( symbol ) + " cannot be in the nonterminal alphabet since it is already in the terminal alphabet." );
    }
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
class ElementConstraint< grammar::LG < TerminalSymbolType, NonterminalSymbolType >, NonterminalSymbolType, grammar::InitialSymbol > {
public:
    static bool available ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > & grammar, const NonterminalSymbolType & symbol ) {
        return grammar.template accessComponent < grammar::NonterminalAlphabet > ( ).get ( ).count ( symbol );
    }
 
    static void valid ( const grammar::LG < TerminalSymbolType, NonterminalSymbolType > &, const NonterminalSymbolType & ) {
    }
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
struct normalize < grammar::LG < TerminalSymbolType, NonterminalSymbolType > > {
    static grammar::LG < > eval ( grammar::LG < TerminalSymbolType, NonterminalSymbolType > && value ) {
        ext::set < DefaultSymbolType > nonterminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getNonterminalAlphabet ( ) );
        ext::set < DefaultSymbolType > terminals = alphabet::SymbolNormalize::normalizeAlphabet ( std::move ( value ).getTerminalAlphabet ( ) );
        DefaultSymbolType initialSymbol = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( value ).getInitialSymbol ( ) );
 
        grammar::LG < > res ( std::move ( nonterminals ), std::move ( terminals ), std::move ( initialSymbol ) );
 
        for ( std::pair < NonterminalSymbolType, ext::set < ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > > > && rule : ext::make_mover ( std::move ( value ).getRules ( ) ) ) {
 
            ext::set < ext::variant < ext::vector < DefaultSymbolType >, ext::tuple < ext::vector < DefaultSymbolType >, DefaultSymbolType, ext::vector < DefaultSymbolType > > > > rhs;
            for ( ext::variant < ext::vector < TerminalSymbolType >, ext::tuple < ext::vector < TerminalSymbolType >, NonterminalSymbolType, ext::vector < TerminalSymbolType > > > && target : ext::make_mover ( rule.second ) )
                rhs.insert ( grammar::GrammarNormalize::normalizeRHS ( std::move ( target ) ) );
 
            DefaultSymbolType lhs = alphabet::SymbolNormalize::normalizeSymbol ( std::move ( rule.first ) );
 
            res.addRules ( std::move ( lhs ), std::move ( rhs ) );
        }
 
        return res;
    }
};
 
} /* namespace core */
 
extern template class grammar::LG < >;