First.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
#include <alib/set>
#include <alib/variant>
 
#include <grammar/Grammar.h>
#include <grammar/RawRules.h>
 
namespace grammar {
 
namespace parsing {
 
class First {
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static ext::set < ext::vector < TerminalSymbolType > > first ( const ext::set < TerminalSymbolType > & terminals, const ext::set < NonterminalSymbolType > & nonterminals, const ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > & firstOfNonterminal, const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs );
 
    template < class TerminalSymbolType, class NonterminalSymbolType >
    static ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > first ( const ext::set < TerminalSymbolType > & terminals, const ext::set < NonterminalSymbolType > & nonterminals, const ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rules );
 
public:
    template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::map < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > >, ext::set < ext::vector < TerminalSymbolType > > > first ( const T & grammar );
 
    template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::set < ext::vector < TerminalSymbolType > > first ( const T & grammar, const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs );
};
 
template < class TerminalSymbolType, class NonterminalSymbolType >
ext::set < ext::vector < TerminalSymbolType > > First::first ( const ext::set < TerminalSymbolType > & terminals, const ext::set < NonterminalSymbolType > & nonterminals, const ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > & firstOfNonterminal, const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs ) {
     // 1. FIRST(\varepsilon) = { \varepsilon }
    if ( rhs.empty ( ) ) {
        return { ext::vector < TerminalSymbolType > ( ) };
    }
 
     // 2. FIRST(a) = { a } forall a \in T
    else if ( terminals.count ( rhs[0] ) ) {
        return { ext::vector < TerminalSymbolType > { rhs[0].template get < TerminalSymbolType > ( ) } };
    }
 
     // 4. FIRST(A \alpha) = first(A) if A \in N and \varepsilon \notin first(A)
    else if ( nonterminals.count ( rhs[0] ) && !firstOfNonterminal.find ( rhs[0] )->second.count ( ext::vector < TerminalSymbolType > ( ) ) ) {
        return firstOfNonterminal.find ( rhs[0] )->second;
    }
 
     // 5. FIRST(A \alpha) = (first(A) - \varepsilon) \cup FIRST(\alpha) if A \in N and \varepsilon \in first(A)
    else if ( nonterminals.count ( rhs[0] ) && firstOfNonterminal.find ( rhs[0] )->second.count ( ext::vector < TerminalSymbolType > ( ) ) ) {
        ext::set < ext::vector < TerminalSymbolType > > res = firstOfNonterminal.find ( rhs[0] )->second;
        res.erase ( ext::vector < TerminalSymbolType > ( ) );
 
        ext::set < ext::vector < TerminalSymbolType > > next = first ( terminals, nonterminals, firstOfNonterminal, ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > ( rhs.begin ( ) + 1, rhs.end ( ) ) );
        res.insert ( next.begin ( ), next.end ( ) );
        return res;
    } else {
        throw exception::CommonException ( "Cant be reached" );
    }
}
 
template < class TerminalSymbolType, class NonterminalSymbolType >
ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > First::first ( const ext::set < TerminalSymbolType > & terminals, const ext::set < NonterminalSymbolType > & nonterminals, const ext::map < NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rules ) {
    /*
     *
     * 1. foreach A \in N: first(A) = \emptyset
     * 2. foreach A \rightarrow \alpha:
     *  first(A) = first(A) \cup FIRST(\alpha)
     * 3. repeat step 2 if at least one set first(A) has changed
     *
     */
    ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > firstOfNonterminal1;
 
    for ( const NonterminalSymbolType & nonterminal : nonterminals )
        firstOfNonterminal1[nonterminal];
 
    ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > firstOfNonterminal2 = firstOfNonterminal1;
 
    do {
        for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : rules )
            for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rule.second ) {
                ext::set < ext::vector < TerminalSymbolType > > newFirst = first ( terminals, nonterminals, firstOfNonterminal1, rhs );
                firstOfNonterminal2[rule.first].insert ( newFirst.begin ( ), newFirst.end ( ) );
            }
 
        if ( firstOfNonterminal1 == firstOfNonterminal2 )
            break;
 
        firstOfNonterminal1 = std::move ( firstOfNonterminal2 );
        firstOfNonterminal2.clear ( );
 
    } while ( true );
 
    return firstOfNonterminal1;
}
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::map < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > >, ext::set < ext::vector < TerminalSymbolType > > > First::first ( const T & grammar ) {
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > firstNt = first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), rawRules );
 
    ext::map < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > >, ext::set < ext::vector < TerminalSymbolType > > > res;
 
    for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & rule : rawRules )
        for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : rule.second )
            res.insert ( std::make_pair ( rhs, first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), firstNt, rhs ) ) );
 
    return res;
}
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::set < ext::vector < TerminalSymbolType > > First::first ( const T & grammar, const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs ) {
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
 
    ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > firstNt = first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), rawRules );
 
    return first ( grammar.getTerminalAlphabet ( ), grammar.getNonterminalAlphabet ( ), firstNt, rhs );
}
 
} /* namespace parsing */
 
} /* namespace grammar */