Skip to content

Instantly share code, notes, and snippets.

@nmanumr

nmanumr/cfg.h

Last active December 28, 2021 03:14
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save nmanumr/46aa0df92a57045f95302b7fb13ea4d0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save nmanumr/46aa0df92a57045f95302b7fb13ea4d0 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. nmanumr revised this gist Dec 28, 2021. 3 changed files with 125 additions and 21 deletions.
    20 changes: 11 additions & 9 deletions cfg.h
    View file
    Original file line number Diff line number Diff line change
    @@ -3,7 +3,6 @@
    #include <list>
    #include <unordered_map>
    #include <set>
    #include <utility>

    using namespace std;

    @@ -20,31 +19,32 @@ struct Token {
    };

    typedef list<Token> Rule;
    struct StandaloneRule {
    string nonTerminal;
    list<Token> rule;
    };
    struct CFG {
    string startSymbol;
    unordered_map<string, list<Rule>> rules;
    };

    unordered_map<string, set<string>> cacheSet;

    void printCfgRule(const string &name, const list<Rule> &rules) {
    void print(const string &name, const list<Rule> &rules) {
    cout << name << " -> ";
    for (const auto &rule : rules) {
    for (const auto &token: rule)
    cout << token.name;

    cout << endl;
    if (&rule != &rules.back()) cout << " | ";
    if (&rule != &rules.back()) cout << endl << " | ";
    }
    }

    void printCfg(CFG cfg) {
    printCfgRule(cfg.startSymbol, cfg.rules[cfg.startSymbol]);
    void print(CFG cfg) {
    print(cfg.startSymbol, cfg.rules[cfg.startSymbol]);

    for (const auto &rule: cfg.rules) {
    if (rule.first == cfg.startSymbol) continue;

    printCfgRule(rule.first, rule.second);
    print(rule.first, rule.second);
    }
    }

    @@ -121,6 +121,8 @@ set<string> getFollowSet(const CFG& cfg, const string &symbol, set<string> path)
    }
    }

    if (symbol == cfg.startSymbol)
    followSet.insert("$");
    return followSet;
    }

    96 changes: 96 additions & 0 deletions ll1.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,96 @@
    #include <iostream>
    #include <string>
    #include <list>
    #include <set>
    #include <unordered_map>
    #include <utility>

    #include "cfg.h"

    using namespace std;

    #ifndef CC_LL1_H
    #define CC_LL1_H

    struct Ll1Table {
    set<string> terminals;
    set<string> nonTerminals;
    unordered_map<string, StandaloneRule> table;
    };

    void addRule(Ll1Table &table, const string &terminal, const string &nonTerminal, const StandaloneRule &rule) {
    table.terminals.insert(terminal);
    table.nonTerminals.insert(nonTerminal);
    table.table[nonTerminal + "-" + terminal] = rule;
    }

    StandaloneRule *getRule(Ll1Table table, const string &terminal, const string &nonTerminal) {
    if (table.table.count(nonTerminal + "-" + terminal) == 1) {
    return &table.table[nonTerminal + "-" + terminal];
    }
    return nullptr;
    }

    Ll1Table toLl1Table(const CFG &cfg) {
    Ll1Table table;
    table.terminals.insert("$");

    for (const auto &rules: cfg.rules) {
    string nonTerminal = rules.first;

    for (Rule rule: rules.second) {
    set<string> set;
    if (rule.front().type == TokenType::TERMINAL) {
    set.insert(rule.front().name);
    } else if (rule.front().type == TokenType::NON_TERMINAL) {
    auto firstSet = getFirstSet(cfg, rule.front().name);
    set.insert(firstSet.begin(), firstSet.end());
    } else {
    auto followSet = getFollowSet(cfg, rule.front().name);
    set.insert(followSet.begin(), followSet.end());
    }

    for (const auto &terminal: set) {
    addRule(table, terminal, nonTerminal, {nonTerminal, rule});
    }

    for (const auto &token: rule) {
    if (token.type == TokenType::NON_TERMINAL)
    table.nonTerminals.insert(token.name);
    else
    table.terminals.insert(token.name);
    }
    }
    }

    return table;
    }

    void print(const Ll1Table &table) {
    list<string> nonTerminals(table.nonTerminals.begin(), table.nonTerminals.end());

    for (const auto &nonTerminal: nonTerminals) {
    if (nonTerminal == nonTerminals.front())
    cout << " " << "\t\t\t\t | ";
    else
    cout << nonTerminal << "\t\t\t\t | ";

    for (const auto &terminal: table.terminals) {
    if (nonTerminal == nonTerminals.front()) {
    cout << terminal << "\t\t\t\t | ";
    } else {
    auto rule = getRule(table, terminal, nonTerminal);
    if (rule != nullptr) {
    print(rule->nonTerminal, {rule->rule});
    cout << "\t\t\t | ";
    }
    else
    cout << " \t\t\t\t | ";
    }
    }

    cout << endl;
    }
    }

    #endif //CC_CFG_H
    30 changes: 18 additions & 12 deletions main.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -1,9 +1,14 @@
    #include "cfg.h"
    #include "ll1.h"

    using namespace std;

    int main() {
    CFG cfg1 = {
    Rule r1 = {
    {.name = "id", .type = TokenType::TERMINAL},
    };

    CFG cfg = {
    .startSymbol = "S",
    .rules = {
    {"S", {
    @@ -39,9 +44,7 @@ int main() {
    }
    }},
    {"F", {
    {
    {.name = "id", .type = TokenType::TERMINAL},
    }, {
    r1, {
    {.name = "(", .type = TokenType::TERMINAL},
    {.name = "S", .type = TokenType::NON_TERMINAL},
    {.name = ")", .type = TokenType::TERMINAL},
    @@ -50,13 +53,16 @@ int main() {
    },
    };

    printCfg(cfg1);

    set<string> firstSet = getFirstSet(cfg1, "A");
    for (const auto& token: firstSet)
    cout << token << ", ";
    // print(cfg);
    //
    // set<string> firstSet = getFirstSet(cfg, "A");
    // for (const auto& token: firstSet)
    // cout << token << ", ";
    //
    // set<string> followSet = getFollowSet(cfg, "A");
    // for (const auto& token: firstSet)
    // cout << token << ", ";

    set<string> followSet = getFirstSet(cfg1, "A");
    for (const auto& token: firstSet)
    cout << token << ", ";
    auto table = toLl1Table(cfg);
    print(table);
    }
  2. nmanumr created this gist Dec 27, 2021.
    131 changes: 131 additions & 0 deletions cfg.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,131 @@
    #include <iostream>
    #include <string>
    #include <list>
    #include <unordered_map>
    #include <set>
    #include <utility>

    using namespace std;

    #ifndef CC_CFG_H
    #define CC_CFG_H

    enum TokenType {
    TERMINAL, NON_TERMINAL, EPSILON
    };

    struct Token {
    string name;
    TokenType type;
    };

    typedef list<Token> Rule;
    struct CFG {
    string startSymbol;
    unordered_map<string, list<Rule>> rules;
    };

    unordered_map<string, set<string>> cacheSet;

    void printCfgRule(const string &name, const list<Rule> &rules) {
    cout << name << " -> ";
    for (const auto &rule : rules) {
    for (const auto &token: rule)
    cout << token.name;

    cout << endl;
    if (&rule != &rules.back()) cout << " | ";
    }
    }

    void printCfg(CFG cfg) {
    printCfgRule(cfg.startSymbol, cfg.rules[cfg.startSymbol]);

    for (const auto &rule: cfg.rules) {
    if (rule.first == cfg.startSymbol) continue;

    printCfgRule(rule.first, rule.second);
    }
    }

    set<string> getFirstSet(CFG cfg, const string &symbol, set<string> path) {
    if (path.count(symbol) == 1) return {};
    else path.insert(symbol);

    auto rules = cfg.rules[symbol];
    set<string> firstSet;

    for (auto rule: rules) {
    for (const auto &token: rule) {
    if (token.type == TokenType::TERMINAL) {
    firstSet.insert(token.name);
    break;
    }

    if (token.type == TokenType::NON_TERMINAL) {
    set<string> tokens = getFirstSet(cfg, token.name, path);
    auto hasEpsilon = tokens.count("ε") == 1;
    tokens.erase("ε");
    firstSet.insert(tokens.begin(), tokens.end());

    if (!hasEpsilon) break;
    if (&token == &rule.back()) firstSet.insert("ε");
    } else if (token.type == TokenType::EPSILON && &token == &rule.back())
    firstSet.insert("ε");
    }
    }

    return firstSet;
    }

    set<string> getFirstSet(const CFG& cfg, const string &symbol) {
    return getFirstSet(cfg, symbol, {});
    }

    set<string> getFollowSet(const CFG& cfg, const string &symbol, set<string> path) {
    if (path.count(symbol) == 1) return {};
    else path.insert(symbol);

    set<string> followSet;

    for (const auto &rules: cfg.rules) {
    for (const auto &rule: rules.second) {
    bool found = false;

    for (const auto &token: rule) {
    if (!found) {
    if (token.name == symbol) found = true;
    continue;
    }

    if (token.type == TokenType::TERMINAL) {
    followSet.insert(token.name);
    break;
    }

    if (token.type == TokenType::NON_TERMINAL) {
    set<string> firstSet = getFirstSet(cfg, token.name);
    auto hasEpsilon = firstSet.count("ε") == 1;
    firstSet.erase("ε");
    followSet.insert(firstSet.begin(), firstSet.end());

    if (!hasEpsilon) break;
    continue;
    }

    if (&token == &rule.back()) {
    auto _set = getFollowSet(cfg, rules.first, path);
    followSet.insert(_set.begin(), _set.end());
    }
    }
    }
    }

    return followSet;
    }

    set<string> getFollowSet(const CFG& cfg, const string &symbol) {
    return getFollowSet(cfg, symbol, {});
    }

    #endif //CC_CFG_H
    62 changes: 62 additions & 0 deletions main.cpp
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,62 @@
    #include "cfg.h"

    using namespace std;

    int main() {
    CFG cfg1 = {
    .startSymbol = "S",
    .rules = {
    {"S", {
    {
    {.name = "A", .type = TokenType::NON_TERMINAL},
    {.name = "B", .type = TokenType::NON_TERMINAL},
    },
    }},
    {"A", {
    {
    {.name = "F", .type = TokenType::NON_TERMINAL},
    {.name = "C", .type = TokenType::NON_TERMINAL},
    }, {
    {.name = "ε", .type = TokenType::EPSILON},
    }
    }},
    {"B", {
    {
    {.name = "+", .type = TokenType::TERMINAL},
    {.name = "A", .type = TokenType::NON_TERMINAL},
    {.name = "B", .type = TokenType::NON_TERMINAL},
    }, {
    {.name = "ε", .type = TokenType::EPSILON},
    }
    }},
    {"C", {
    {
    {.name = "*", .type = TokenType::TERMINAL},
    {.name = "F", .type = TokenType::NON_TERMINAL},
    {.name = "C", .type = TokenType::NON_TERMINAL},
    }, {
    {.name = "ε", .type = TokenType::EPSILON},
    }
    }},
    {"F", {
    {
    {.name = "id", .type = TokenType::TERMINAL},
    }, {
    {.name = "(", .type = TokenType::TERMINAL},
    {.name = "S", .type = TokenType::NON_TERMINAL},
    {.name = ")", .type = TokenType::TERMINAL},
    }
    }},
    },
    };

    printCfg(cfg1);

    set<string> firstSet = getFirstSet(cfg1, "A");
    for (const auto& token: firstSet)
    cout << token << ", ";

    set<string> followSet = getFirstSet(cfg1, "A");
    for (const auto& token: firstSet)
    cout << token << ", ";
    }