ll1_parser.hpp

#pragma once
#include "grammar.hpp"
#include "lexer.hpp"
#include "symbol_table.hpp"
#include <deque>
#include <queue>
#include <span>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
class LL1Parser {
    using ll1_table = std::unordered_map<
        symbol_table::TokenID,
        std::unordered_map<symbol_table::TokenID, std::vector<production>>>;
 
public:
    struct ParseNode {
        std::string                             symbol;    
        std::vector<std::unique_ptr<ParseNode>> children;  
    };
 
    using ParseTree = std::unique_ptr<ParseNode>;
    LL1Parser(Grammar gr, std::string text_file, bool table_format = true,
              bool text_is_raw = false);

    LL1Parser(const std::string& grammar_file, std::string text_file,
              bool table_format = true, bool text_is_raw = false);

    bool Parse();

    ParseTree ParseWithTree(const std::string& file);

    bool MatchTerminal(symbol_table::TokenID top_symbol,
                       symbol_table::TokenID current_symbol);

    bool ProcessNonTerminal(symbol_table::TokenID              top_symbol,
                            symbol_table::TokenID              current_symbol,
                            std::stack<symbol_table::TokenID>& symbol_stack);

    void PrintTable();

    void ExportTreeAsDot(const ParseTree& tree, const std::string& filename);
 
private:
    void ReportParseError(const std::string& input, size_t err_pos,
                          symbol_table::TokenID expected,
                          symbol_table::TokenID found);

    void First(std::span<const symbol_table::TokenID>     rule,
               std::unordered_set<symbol_table::TokenID>& result);

    void ComputeFirstSets();

    void ComputeFollowSets();

    bool UpdateFollow(symbol_table::TokenID symbol, symbol_table::TokenID lhs,
                      const production& rhs, size_t i);

    std::unordered_set<symbol_table::TokenID> Follow(symbol_table::TokenID arg);

    std::unordered_set<symbol_table::TokenID>
    PredictionSymbols(symbol_table::TokenID antecedent,
                      const production&     consequent);

    bool CreateLL1Table();

    void PrintTableUsingTabulate();

    ll1_table ll1_t_;

    Grammar gr_;

    std::unordered_map<symbol_table::TokenID,
                       std::unordered_set<symbol_table::TokenID>>
        first_sets_;

    std::unordered_map<symbol_table::TokenID,
                       std::unordered_set<symbol_table::TokenID>>
        follow_sets_;

    std::string grammar_file_;

    std::string text_file_;

    bool text_is_raw_{false};

    bool print_table_format_{true};
};