ll1_grammar_checker.cpp

// ============================================================================
// Simulador de gramáticas LL(1)
// Marcos Medeiros, 2015
// ============================================================================
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <string>
#include <set>
#include <algorithm>
#include <stack>
#include <sstream>
#include <cassert>

using namespace std;

template<class T>
class iter_stack : public list<T> {
public:
    void push(const T &value) {
        this->push_front(value);
    }
    void pop() {
        this->pop_front();
    }
    T& top() {
        return this->front();
    }
};

struct symbol {
    int value;
    list<vector<int>> rules;
    bool initial = false;

    operator int() { return value; }

    symbol &operator+=(const vector<int> &ls) {
        rules.push_back(ls);
    }

    template<typename...Rules>
    void rule(Rules...rs) {
        rules.push_back(vector<int>({rs...}));
    }

    symbol *operator->() { return this; }
};

class ll1_grammar_checker {

    int m_prod_count;
    int m_tmp_count;
    int m_action_count;
    list<int> m_productions;
    map<int, symbol> m_symbols;
    map<int, std::string> m_names;
    map<int, set<int>> m_firsts;
    map<int, set<int>> m_follows;
    map<int, vector<int>> m_actions;
    map<int, map<int, int>> m_parse_table;


    bool is_nonterm(int n) {
        return (n >= 256);
    }

    bool is_terminal(int n) {
        return (n < 256 && n >= 0) || (n == Epsilon);
    }

    // Cálcula o conjunto de PRIMEIROS de uma produção recursivamente
    void first_find(int prod, vector<int> &firsts) {
        // Se for um terminal então este é um PRIMEIRO
        if (!is_nonterm(prod)) {
            firsts.push_back(prod);
            return;
        }

        const auto &production = m_symbols[prod];
        // alguma coisa errada
        if (production.rules.empty())
            return;

        for (auto &rule : production.rules) {
            if (!rule.empty() && rule[0] != prod)
                first_find(rule[0], firsts);
        }
    }

    // Encontra o conjunto de PRIMEIROS de uma produção
    vector<int> first(int prod) {
        vector<int> firsts;
        first_find(prod, firsts);
        return firsts;
    }

    symbol &get_production(int p) {
        return m_symbols[p];
    }

    bool compute_follow_for(int X) {
        symbol &x_prod = get_production(X);
        bool changes = false;

        // Vamos verificar se houve mudanças baseado no tamanho do conjunto
        const int size = m_follows[X].size();

        auto &x_follow = m_follows[X];

        // Se P for a produção inicial, então SEQ(X) <- $
        if (x_prod.initial) {
            x_follow.insert(Start);
        }

        for (const auto &subprod : x_prod.rules) {
            // X -> AB
            for (int a_idx = 0, b_idx = 1; a_idx < subprod.size(); a_idx++, b_idx++) {
                const int A = subprod[a_idx];
                const int B = subprod[b_idx];

                // Se A for um terminal, não faz nada.
                if (!is_nonterm(A)) {
                    continue;
                }

                // Senão SEQ(A) = PRIM(B)
                const auto &follow_a = m_follows[A];

                // Se B for o fim da cadeia de produções então SEQ(A) <- SEQ(X)
                if (b_idx >= subprod.size()) {
                    m_follows[A].insert(begin(x_follow), end(x_follow));
                } else {

                    // Se B for um terminal, então ele é a SEQ
                    if (is_terminal(B)) {
                        assert(B != 0);

                        m_follows[A].insert(B);
                        continue;
                    }

                    set<int> b_first = m_firsts[B];

                    // SEQ(A) = PRIM(B) - Epsilon

                    // Se PRIM(B) ter Epislon, então SEQ(A) <- SEQ(X)
                    if (b_first.find(Epsilon) != b_first.end()) {
                        // remove Epsilon do conjunto
                        b_first.erase(Epsilon);
                        m_follows[A].insert(begin(x_follow), end(x_follow));
                    }
                    // SEQ(A) <- PRIM(B)
                    m_follows[A].insert(begin(b_first), end(b_first));
                }
            }
        }
        return (m_follows[X].size() != size);
    }

    void compute_firsts() {
        for (auto prod : m_productions) {
            auto f = first(prod);
            m_firsts[prod].insert(begin(f), end(f));
        }
    }

    // Calcula os conjuntos de SEQUENCIA
    void compute_follows() {
        m_follows.clear();

        bool changes = true;
        do {
            changes = false;
            for (auto X : m_productions) {

                if (compute_follow_for(X))
                    changes = true;
            }
        } while (changes);

    };

    void describe_rule(const vector<int> &subrules) {
        for (auto subrule : subrules) {
            cout << m_names[subrule] << ' ';
        }
    }

    void show_production(int X, const vector<int> &prods) {
        cout << m_names[X] << " -> ";
        describe_rule(prods);
    }

    string next_tmp_name() {
        // cria Xn
        stringstream ss;
        ss << "X" << m_tmp_count;
        m_tmp_count++;
        return ss.str();
    }

    // Elimina recursão direta à esquerda de uma produção
    // Apenas na forma A -> Ax | ?
    void rem_direct_left_rec(int prod, vector<int> &rule) {

        cout << "Eliminando recursão a esquerda" << endl;
        assert(rule.front() == prod);

        // Elima o simbolo de recursão
        rule.erase(rule.begin());
        symbol &production = get_production(prod);

        vector<int> new_rules = rule;
        // Como estamos modificando a regra enquanto iteramos sobre
        // ela não é possível remove-la diretamente, então apenas
        // limpamos as regras, depois removeremos essas produções.
        rule.clear();

        // Cria a nova produção
        auto &new_rule = make_prod(next_tmp_name());

        new_rules.push_back(new_rule);
        new_rule->rule(new_rules);
        new_rule->rule(Epsilon);

        // Para cada produção restante colocamos a nova produção com sufixo
        // !!! Isso apenas funciona em recursao direta A -> Ax | ?
        for (auto &rr : production.rules) {
            if (!rr.empty()) {
                rr.push_back(new_rule);
            }
        }

        cout << "Recursão eliminada" << endl;
    }

    void refactor_grammar() {
        cout << "Refatorando gramática..." << endl;

        for (int X : m_productions) {
            symbol &x_prod = get_production(X);

            for (auto &subrules : x_prod.rules) {

                // Isso não deveria ser vazio.
                if (subrules.empty())
                    continue;

                if (subrules[0] == X) {
                    cout << "Recursão direta a esquerda encontrada ";
                    show_production(X, subrules);
                    cout << endl;
                    rem_direct_left_rec(X, subrules);
                }

            }

            // remove as produções que ficaram vazias
            for (auto it = x_prod.rules.begin(); it != x_prod.rules.end();) {
                if ((*it).empty()) {
                    it = x_prod.rules.erase(it);
                } else {
                    it++;
                }
            }
        }

        show_grammar();
    }

    template<typename...Rules>
    int make_action(Rules...rs) {
        const int action = ++m_action_count;
        m_actions[action] = vector<int>({rs...});
        return action;
    }

    void build_parse_table() {
        cout << endl << "Gerando tabela de analise preditiva LL(1)" << endl;

        auto expand_action = [&](int A, int t, const vector<int> &p) {
            m_parse_table[A][t] = make_action(p);
            cout << "M[" << m_names[A] << ',' << m_names[t] << "] = ";
            describe_rule(p);
            cout << endl;
        };

        for (auto PA : m_productions) {
            symbol &a_prod = get_production(PA);

            for (auto &rule : a_prod.rules) {

                assert(!rule.empty());

                if (is_terminal(rule[0]) && rule[0] != Epsilon) {
                    expand_action(PA, rule[0], rule);
                    continue;
                }

                const auto &first_p = m_firsts[rule[0]];
                for (auto t : first_p) {
                    expand_action(PA, t, rule);
                }

                // Se Epsilon pertence a PRIM(a), M[A,FOLLOW(A)] = a
                if ((first_p.find(Epsilon) != first_p.end()) || rule[0] == Epsilon) {
                    const auto &follow_p = m_follows[PA];

                    for (auto t : follow_p) {
                        expand_action(PA, t, rule);
                    }
                }

            }
        }
    }


protected:
    const int Epsilon, Start;

    symbol &make_prod(const string &str) {
        symbol prod;
        prod.value = m_prod_count++;

        m_symbols[prod.value] = prod;
        m_names[prod.value] = str;
        m_productions.push_back(prod.value);

        return m_symbols[prod.value];
    }

    void clear_grammar() {
        m_prod_count = 1000;
        m_tmp_count = 0;
        m_action_count = 0;
    }

    void finish_grammar() {
        refactor_grammar();
        compute_firsts();
        compute_follows();
        build_parse_table();
    }

    int find_init_prod() {
        for (auto i : m_productions) {
            if (m_symbols[i].initial)
                return i;
        }
        return Start;
    }

public:

    ll1_grammar_checker() : Epsilon(-2), Start(-1), m_prod_count(1000),
                   m_tmp_count(0), m_action_count(0) {

        m_names[Epsilon] = "Epsilon";
        m_names[Start] = "$";
        for (int i = 0; i < 256; i++)
            m_names[i] = (char) i;
    }


    void show_firsts() {
        cout << endl << "Conjuntos de PRIMEIRO" << endl;
        for (auto prod : m_productions) {
            cout << "PRIM(" << m_names[prod] << ") = { ";
            for (auto p : m_firsts[prod]) {
                cout << m_names[p] << ", ";
            }
            cout << " }" << endl;
        }
    }

    void show_follows() {
        cout << endl << "Conjuntos de SEQUENCIA" << endl;

        for (auto prod : m_productions) {
            if (m_names.find(prod) != m_names.end()) {
                cout << "SEQ(" << m_names[prod] << ") = { ";

                for (auto x : m_follows[prod]) {
                    cout << m_names[x] << ", ";
                }

                cout << " }" << endl;
            } else {
                cout << "Simbolo inválido " << prod << endl;
            }
        }
    }

    void show_grammar() {
        cout << endl;
        for (int P : m_productions) {
            auto &pp = get_production(P);
            for (const auto &t : pp.rules) {
                show_production(P, t);
                cout << endl;
            }
        }
    }

    bool parse(const string &input) {
        int ipos = 0;
        iter_stack<int> stack;

        int iprod = find_init_prod();
        if (iprod == Start) {
            cout << "Gramática não possui produção inicial!!!" << endl;
            return false;
        }
        stack.push(iprod);

        // Função lambda que retorna o caracter atual
        auto curr_input = [&]() -> int {
            if (ipos >= input.size())
                return Start;
            return input.at(ipos);
        };

        auto show_stack = [&]() {
            cout << "P: ";
            for (auto s : stack) {
                cout << m_names[s] << " ";
            }
            cout << '$' << endl;
        };

        auto show_input = [&]() {
            cout << "E: ";
            cout << input.substr(ipos, input.size()-ipos) << '$' << endl;
        };


        cout << "Verificando entrada > " << input << endl;
        while (!stack.empty()) {
            show_stack();
            show_input();
            int curr_stack = stack.top();

            if (is_nonterm(curr_stack)) {
                const int naction = m_parse_table[curr_stack][curr_input()];
                cout << "A: " << m_names[curr_stack] << " -> ";
                describe_rule(m_actions[naction]);
                cout << endl;

                if (!naction) {
                    cout << "Erro na expansão do não terminal" << endl;
                    break;
                }
                stack.pop();

                const auto &action = m_actions[naction];
                // Se a ação não for Epsilon então expande na pilha
                if (action[0] != Epsilon) {
                    for (auto it = action.rbegin(); it != action.rend(); it++) {
                        stack.push(*it);
                    }
                }
            } else {
                if (curr_input() != curr_stack) {
                    cout << "Erro no casamento do terminal" << endl;
                    break;
                } else {
                    cout << "A: casamento" << endl;
                    ipos++;
                    stack.pop();
                }
            }
            cout << endl;
        }
        // Exibe a pilha e a entrada mais uma vez...
        show_stack();
        show_input();

        if (stack.empty() && (curr_input() == Start))
            cout << "Entrada aceita" << endl;
        else
            cout << "Entrada rejeitada" << endl;

        return false;
    }
};


// E -> EST | T
// S -> + | -
// T -> TMF | F
// M -> *
// F -> (E) | n
class G1 : public ll1_grammar_checker {
public:
    G1() : ll1_grammar_checker() {
        auto &E = make_prod("E");
        auto &S = make_prod("S");
        auto &T = make_prod("T");
        auto &M = make_prod("M");
        auto &F = make_prod("F");

        E.initial = true;

        E->rule(E, S, T);
        E->rule(T);
        S->rule('+');
        S->rule('-');
        T->rule(T, M, F);
        T->rule(F);
        M->rule('*');
        F->rule('(', E, ')');
        F->rule('n');

        finish_grammar();
        show_grammar();
    }
};


class G2 : public ll1_grammar_checker {
public:
    G2() : ll1_grammar_checker() {
        auto &S = make_prod("S");
        auto &A = make_prod("A");
        auto &B = make_prod("B");

        S.initial = true;

        S->rule('(', A, ')');
        S->rule('b');
        A->rule(A, ';', B);
        A->rule(B);
        B->rule('a');
        B->rule(Epsilon);

        finish_grammar();
        show_grammar();
    }
};


class G3 : public ll1_grammar_checker {
public:
    G3() : ll1_grammar_checker() {
        auto &E = make_prod("E");
        auto &X = make_prod("X");
        auto &S = make_prod("S");
        auto &T = make_prod("T");
        auto &Y = make_prod("Y");
        auto &M = make_prod("M");
        auto &F = make_prod("F");

        // E é a produção inicial
        E.initial = true;

        // define a gramática
        E->rule(T, X);
        X->rule(S, T, X);
        X->rule(Epsilon);
        S->rule('+');
        S->rule('-');
        T->rule(F, Y);
        Y->rule(M, F, Y);
        Y->rule(Epsilon);
        M->rule('*');
        F->rule('(', E, ')');
        F->rule('n');

        finish_grammar();
        show_grammar();
    }
};


class G4 : public ll1_grammar_checker {
public:
    G4() : ll1_grammar_checker() {
        auto &E = make_prod("E");
        auto &T = make_prod("T");
        auto &X = make_prod("X");
        auto &Y = make_prod("Y");

        // E é a produção inicial
        E.initial = true;

        // define a gramática
        E->rule(T, X);
        T->rule('(', E, ')');
        T->rule('i', Y);
        X->rule('+', E);
        X->rule(Epsilon);
        Y->rule('*', T);
        Y->rule(Epsilon);

        finish_grammar();
        show_grammar();
    }
};

class G5 : public ll1_grammar_checker {
public:
    G5() : ll1_grammar_checker() {
        auto &S = make_prod("S");


        // S é a produção inicial
        S.initial = true;

        S->rule('(', S, ')', S);
        S->rule(Epsilon);
        finish_grammar();
        show_grammar();
    }
};

int main() {

    G1 g;
    g.show_firsts();
    g.show_follows();
    cout << endl;

    g.parse("n+n*n");
    return 0;
}