Follow.h

Go to the documentation of this file.

 
#pragma once
 
#include <ext/algorithm>
#include <ext/iterator>
 
#include <alib/vector>
#include <alib/set>
#include <alib/variant>
 
#include <exception/CommonException.h>
 
#include <grammar/Grammar.h>
 
#include "First.h"
 
namespace grammar {
 
namespace parsing {
 
class Follow {
    template < class T, class TerminalSymbolType, class NonterminalSymbolType >
    static void follow ( const T & grammar, ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > & followSet );
 
public:
    template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > follow ( const T & grammar );
 
    template < class T, class NonterminalSymbolType, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T > >
    static ext::set < ext::vector < TerminalSymbolType > > follow ( const T & grammar, const NonterminalSymbolType & nt );
};
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
void Follow::follow ( const T & grammar, ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > & followSet ) {
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
    for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : rawRules ) {
        const NonterminalSymbolType & X = rule.first;
 
        for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rule.second )
             // every nt in rhs is Y
            for ( typename ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > >::const_iterator it = rhs.begin ( ); it != rhs.end ( ); ++ it ) {
                const ext::variant < TerminalSymbolType, NonterminalSymbolType > & Y = * it;
 
                if ( ! grammar.getNonterminalAlphabet ( ).count ( Y ) )
                    continue;
 
                ext::set < ext::vector < TerminalSymbolType > > firstBeta = First::first ( grammar, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > ( std::next ( it ), rhs.end ( ) ) );
 
                if ( firstBeta.count ( ext::vector < TerminalSymbolType > ( ) ) ) {
                    firstBeta.erase ( ext::vector < TerminalSymbolType > ( ) );
                    followSet [ Y.template get < TerminalSymbolType > ( ) ].insert ( followSet[X].begin ( ), followSet[X].end ( ) );
                }
 
                followSet [ Y.template get < TerminalSymbolType > ( ) ].insert ( firstBeta.begin ( ), firstBeta.end ( ) );
            }
 
    }
}
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > Follow::follow ( const T & grammar ) {
    /*
     * 1. Follow(S) = { \varepsilon }
     *    Follow(A) = {} forall A \in N, A \neq S
     * 2. Forall p \in P:
     *      if p == X -> \alpha Y \beta
     *      Follow(Y) = Follow(Y) \cup (First(\beta) \setminus { \varepsilon})
     *  if p == X -> \alpha Y \beta \wedge \varepsilon \in First(\beta)
     *      Follow(Y) = Follow(Y) \cup Follow(X)
     * 3. goto 2 if any follow set was changed in prev step.
     */
 
    ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > followSet1;
 
    for ( const NonterminalSymbolType & symb : grammar.getNonterminalAlphabet ( ) )
        followSet1[symb];
 
    followSet1[grammar.getInitialSymbol ( )] = { ext::vector < TerminalSymbolType > ( ) };
 
    ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > followSet2 = followSet1;
 
    do {
        follow ( grammar, followSet2 );
 
        if ( followSet1 == followSet2 )
            break;
 
        followSet1 = followSet2;
    } while ( true );
 
    return followSet1;
}
 
template < class T, class NonterminalSymbolType, class TerminalSymbolType >
ext::set < ext::vector < TerminalSymbolType > > Follow::follow ( const T & grammar, const NonterminalSymbolType & nt ) {
    if ( ! grammar.getNonterminalAlphabet ( ).count ( nt ) )
        throw exception::CommonException ( "Follow: Given symbol is not nonterminal." );
 
    return follow ( grammar )[nt];
}
 
} /* namespace parsing */
 
} /* namespace grammar */