grammar_factory.hpp

Go to the documentation of this file.

#pragma once
 
#include "grammar.hpp"
#include "symbol_table.hpp"
#include <string>
#include <unordered_map>
#include <vector>

struct GrammarFactory {

    struct FactoryItem {
        std::unordered_map<std::string, std::vector<production>> g_;

        SymbolTable st_;

        explicit FactoryItem(const std::unordered_map<std::string, std::vector<production>> &grammar);
    };

    void Init();

    Grammar PickOne(int level);

    Grammar GenLL1Grammar(int level);
    Grammar GenSLR1Grammar(int level);

    Grammar Lv1();

    Grammar Lv2();

    Grammar Lv3();

    Grammar Lv4();

    Grammar Lv5();

    Grammar Lv6();

    Grammar Lv7();

    FactoryItem CreateLv2Item();
 
    // -------- SANITY CHECKS --------

    bool HasUnreachableSymbols(Grammar& grammar) const;

    bool IsInfinite(Grammar& grammar) const;

    bool HasDirectLeftRecursion(const Grammar& grammar) const;

    bool HasIndirectLeftRecursion(const Grammar& grammar) const;

    bool HasCycle(const std::unordered_map<std::string, std::unordered_set<std::string>>& graph) const;

    std::unordered_set<std::string> NullableSymbols(const Grammar& grammar) const;
 
    // -------- TRANSFORMATIONS --------
    void RemoveLeftRecursion(Grammar& grammar);

    void LeftFactorize(Grammar& grammar);

    std::vector<std::string>
    LongestCommonPrefix(const std::vector<production>& productions);

    bool StartsWith(const production&               prod,
                    const std::vector<std::string>& prefix);

    std::string GenerateNewNonTerminal(Grammar&           grammar,
                                       const std::string& base);

    void NormalizeNonTerminals(FactoryItem& item, const std::string& nt) const;

    void AdjustTerminals(FactoryItem& base, const FactoryItem& cmb,
                         const std::string& target_nt) const;

    std::unordered_map<std::string, std::vector<production>>
    Merge(const FactoryItem& base, const FactoryItem& cmb) const;

    std::vector<FactoryItem> items;

    std::vector<std::string> terminal_alphabet_{"a", "b", "c", "d", "e", "f",
                                                "g", "h", "i", "j", "k", "l"};

    std::vector<std::string> non_terminal_alphabet_{"A", "B", "C", "D",
                                                    "E", "F", "G"};
};