LL1ParseTable.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
#include <alib/variant>
#include <alib/set>
#include <alib/map>
 
#include <grammar/Grammar.h>
 
#include "First.h"
#include "Follow.h"
 
namespace grammar {
 
namespace parsing {
 
class LL1ParseTable {
public:
    template < class T, class TerminalSymbolType = typename grammar::TerminalSymbolTypeOfGrammar < T >, class NonterminalSymbolType = typename grammar::NonterminalSymbolTypeOfGrammar < T > >
    static ext::map < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType >, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > parseTable ( const T & grammar );
 
};
 
template < class T, class TerminalSymbolType, class NonterminalSymbolType >
ext::map < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType >, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > LL1ParseTable::parseTable ( const T & grammar ) {
    ext::map < ext::pair < ext::vector < TerminalSymbolType >, NonterminalSymbolType >, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > res;
 
    ext::map < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > >, ext::set < ext::vector < TerminalSymbolType > > > first = First::first ( grammar );
    ext::map < NonterminalSymbolType, ext::set < ext::vector < TerminalSymbolType > > > follow = Follow::follow ( grammar );
 
    auto rawRules = grammar::RawRules::getRawRules ( grammar );
    for ( const std::pair < const NonterminalSymbolType, ext::set < ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > > > & transition : rawRules ) {
        const NonterminalSymbolType & lhs = transition.first;
 
        for ( const ext::vector < ext::variant < TerminalSymbolType, NonterminalSymbolType > > & rhs : transition.second ) {
            for ( const ext::vector < TerminalSymbolType > & firstElem : first[rhs] ) {
                if ( firstElem.empty ( ) )
                    continue;
 
                res [ ext::make_pair ( firstElem, lhs ) ].insert ( rhs );
            }
 
            if ( first[rhs].count ( ext::vector < TerminalSymbolType > ( ) ) )
                for ( const ext::vector < TerminalSymbolType > & followElem : follow[lhs] )
                    res [ ext::make_pair ( followElem, lhs ) ].insert ( rhs );
 
        }
    }
 
    return res;
}
 
} /* namespace parsing */
 
} /* namespace grammar */