CockeYoungerKasamiVerbose.h

Go to the documentation of this file.

 
#pragma once
 
#include <global/GlobalData.h>
 
#include <grammar/ContextFree/CNF.h>
#include <string/LinearString.h>
 
namespace grammar {
 
namespace generate {
 
class CockeYoungerKasamiVerbose {
public:
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static ext::vector < ext::vector < ext::set < NonterminalSymbolType > > > generate ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, const string::LinearString < TerminalSymbolType > & string );
 
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
ext::vector < ext::vector < ext::set < NonterminalSymbolType > > > CockeYoungerKasamiVerbose::generate ( const grammar::CNF < TerminalSymbolType, NonterminalSymbolType > & grammar, const string::LinearString < TerminalSymbolType > & string ) {
    unsigned stringSize = string.getContent ( ).size ( );
 
    if ( ( stringSize == 0 ) && grammar.getGeneratesEpsilon ( ) ) return { };
 
    ext::vector < ext::vector < ext::set < NonterminalSymbolType > > > data;
    data.resize ( stringSize );
 
    for ( unsigned i = 0; i < stringSize; i++ )
        data[i].resize ( stringSize - i );
 
    for ( unsigned i = 0; i < stringSize; i++ )
        for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
            const NonterminalSymbolType & lhs = rule.first;
 
            for ( const ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > & rhs : rule.second )
                if ( rhs.template is < TerminalSymbolType > ( ) && ( rhs.template get < TerminalSymbolType > ( ) == string.getContent ( )[i] ) )
                    data[0][i].insert ( lhs );
 
        }
 
    for ( unsigned i = 1; i < stringSize; i++ )
        for ( unsigned j = 0; j < stringSize - i; j++ ) {
            ext::set < NonterminalSymbolType > & targetCell = data[i][j]; // Element to compute
 
            for ( unsigned k = 0; k < i; k++ ) {
                const ext::set < NonterminalSymbolType > & vertical = data[k][j];
                const ext::set < NonterminalSymbolType > & diagonal = data[i - 1 - k][j + 1 + k]; // Sources of data
 
                for ( const NonterminalSymbolType & verticalElement : vertical ) {
                    for ( const NonterminalSymbolType & diagonalElement : diagonal )
 
                        for ( const std::pair < const NonterminalSymbolType, ext::set < ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > > > & rule : grammar.getRules ( ) ) {
                            const NonterminalSymbolType & lhs = rule.first;
 
                            for ( const ext::variant < TerminalSymbolType, ext::pair < NonterminalSymbolType, NonterminalSymbolType > > & rhs : rule.second )
                                if ( rhs.template is < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( ) ) {
                                    const ext::pair < NonterminalSymbolType, NonterminalSymbolType > & rhsp = rhs.template get < ext::pair < NonterminalSymbolType, NonterminalSymbolType > > ( );
 
                                    if ( ( rhsp.first == verticalElement ) && ( rhsp.second == diagonalElement ) )
                                        targetCell.insert ( lhs );
                                }
 
                        }
 
                }
            }
        }
 
 
 
    if ( common::GlobalData::verbose )
        for ( const ext::vector < ext::set < NonterminalSymbolType > > & row : data ) {
            for ( const ext::set < NonterminalSymbolType > & element : row )
                common::Streams::log << element << " ";
 
            common::Streams::log << std::endl;
        }
 
    return data;
}
 
} /* namespace generate */
 
} /* namespace grammar */