grammar_factory.hpp

Go to the documentation of this file.

/*
 * SyntaxTutor - Interactive Tutorial About Syntax Analyzers
 * Copyright (C) 2025 Jose R. (jose-rzm)
 *
 * This program is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#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();

    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;

 
    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"};
};