#pragma once #include "../automatas/FinateStateAutomata.hpp" #include "../grammars/RegularGrammar.hpp" namespace tp { class ContextFreeCompiler { public: struct SymbolVal { SymbolVal() = default; SymbolVal(ualni aId, ualni aStart, ualni aLen) { id = aId; start = aStart; len = aLen; }; SymbolVal(ualni val) { id = val; } operator ualni() const { return id; } bool operator==(const SymbolVal& in) const { return in.id == id; } SymbolVal& operator=(const SymbolVal& in) = default; ualni id = 0; ualni start = 0; ualni len = 0; }; struct Item { const ContextFreeGrammar::Rule* mRule = nullptr; ualni mAdvanceIdx = 0; ualni numArgs() const { return mRule ? mRule->getArgs()->size() : 0; } }; struct Symbol { String mId; bool mIsTerminal = false; }; struct Action { enum Type { ERROR, SHIFT, REDUCE, ACCEPT } type = ERROR; ualni num = 0; // target state (shift) or rule index (reduce) }; private: struct NonTerminal { Buffer rules; Map references; Map referencing; public: [[nodiscard]] bool isProductive() const { for (auto rule : rules) { if (rule->isProductive()) return true; } return false; } [[nodiscard]] bool isLooped(Map& processed, const String& id) const { for (auto ref : referencing) { if (processed.presents(ref->key)) return true; } processed.put(id, {}); for (auto ref : referencing) { if (ref->val->isLooped(processed, ref->key)) return true; } return false; } }; struct LrItem { ualni rule = 0; // 0 is the augmented start rule ualni dot = 0; ualni look = 0; // terminal index (local), T == EOF }; struct Edge { ualni from = 0; alni symbol = 0; // global symbol index, -1 for none ualni to = 0; }; public: bool compile(const ContextFreeGrammar& grammar); [[nodiscard]] const Buffer* getSymbols() const; [[nodiscard]] SymbolVal getSymbolId(const String& name) const; [[nodiscard]] const Buffer* getTerminals() const; [[nodiscard]] const Buffer* getNonTerminals() const; [[nodiscard]] SymbolVal getStartSymbol() const; [[nodiscard]] const Buffer2D* getActionTable() const; [[nodiscard]] const Buffer2D* getGotoTable() const; [[nodiscard]] const Buffer* getRuleLhs() const; [[nodiscard]] const Buffer* getRulePopCount() const; private: bool init(const ContextFreeGrammar& grammar); void findNonTerminals(const ContextFreeGrammar& grammar); void findAllReferences(const ContextFreeGrammar& grammar); static bool argIsEpsilon(const ContextFreeGrammar::Arg& arg); bool buildTable(const ContextFreeGrammar& grammar); private: Map mNonTerminals; Buffer mSymbols; Map mSymbolLookup; Buffer mNonTerminalSymbols; Buffer mTerminalSymbols; Map mNonTerminalIdx; Map mTerminalIdx; SymbolVal mStartSymbol = SymbolVal(0); Buffer2D mActionTable; Buffer2D mGotoTable; Buffer mRuleLhs; Buffer mRulePopCount; }; } #include "compilers/ContextFreeCompiler.ipp"