// Gramática libre de contexto G = (V, Σ, R, S), en el formato .cfg de code/formats.md.
// Los procedimientos de decisión de la sesión A sobre gramáticas:
//
//   generating        E_CFG: marcar las variables que generan alguna cadena de terminales
//   derives_bounded   A_CFG como en la demostración: probar las derivaciones de 2n − 1 pasos
//   cyk               A_CFG con programación dinámica (semana 5)
#ifndef CFG_H
#define CFG_H

#include <cstddef>
#include <fstream>
#include <istream>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

// Una regla A → X1 X2 … Xk. Cada símbolo del cuerpo es el nombre de una variable o un terminal
// (una cadena de un carácter). El cuerpo vacío es la regla A → ε.
struct Rule {
    std::string head;
    std::vector<std::string> body;
};

struct Cfg {
    std::vector<std::string> variables;  // V
    std::vector<char> terminals;         // Σ
    std::vector<Rule> rules;             // R, en el orden del archivo
    std::string start;                   // S
};

inline bool is_variable(const Cfg& g, const std::string& symbol) {
    for (const std::string& v : g.variables) {
        if (v == symbol) {
            return true;
        }
    }
    return false;
}

inline Cfg read_cfg(std::istream& in) {
    int number = 0;
    auto fail = [&number](const std::string& message) {
        throw std::runtime_error("línea " + std::to_string(number) + ": " + message);
    };
    auto next_line = [&in, &number](std::vector<std::string>& words) {
        std::string line;
        while (std::getline(in, line)) {
            number++;
            if (!line.empty() && line[0] == '#') {
                continue;
            }
            std::istringstream text(line);
            words.clear();
            std::string word;
            while (text >> word) {
                words.push_back(word);
            }
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    auto field = [&next_line, &fail](const std::string& name) {
        std::vector<std::string> words;
        if (!next_line(words) || words[0] != name + ":") {
            fail("se esperaba el campo " + name + ":");
        }
        words.erase(words.begin());
        return words;
    };

    Cfg g;
    g.variables = field("variables");
    std::set<std::string> known(g.variables.begin(), g.variables.end());
    for (const std::string& symbol : field("terminals")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un terminal es un solo carácter distinto de #: " + symbol);
        }
        if (known.count(symbol) > 0) {
            fail("el símbolo " + symbol + " es variable y terminal a la vez");
        }
        g.terminals.push_back(symbol[0]);
        known.insert(symbol);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1 || !is_variable(g, start[0])) {
        fail("start: lleva exactamente una variable");
    }
    g.start = start[0];
    if (!field("rules").empty()) {
        fail("después de rules: las reglas van una por línea");
    }
    std::vector<std::string> words;
    while (next_line(words)) {
        if (words.size() < 3 || words[1] != "->" || !is_variable(g, words[0])) {
            fail("una regla se escribe: variable -> alternativa | alternativa");
        }
        Rule rule = {words[0], {}};
        bool is_eps = false;
        bool any = false;
        auto close = [&]() {
            if (!any || (is_eps && !rule.body.empty())) {
                fail("alternativa vacía o mal escrita (la vacía se escribe eps)");
            }
            g.rules.push_back(rule);
            rule.body.clear();
            is_eps = false;
            any = false;
        };
        for (std::size_t i = 2; i < words.size(); i++) {
            if (words[i] == "|") {
                close();
            } else if (words[i] == "eps") {
                is_eps = true;
                any = true;
            } else {
                if (known.count(words[i]) == 0) {
                    fail("símbolo desconocido: " + words[i]);
                }
                rule.body.push_back(words[i]);
                any = true;
            }
        }
        close();
    }
    return g;
}

inline Cfg load_cfg(const std::string& path) {
    std::ifstream file(path);
    if (!file) {
        throw std::runtime_error("no se pudo abrir " + path);
    }
    try {
        return read_cfg(file);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(path + ": " + error.what());
    }
}

inline std::string show_rule(const Rule& rule) {
    std::string text = rule.head + " →";
    for (const std::string& symbol : rule.body) {
        text += " " + symbol;
    }
    return rule.body.empty() ? text + " ε" : text;
}

// ------------------------------------------------------------
// E_CFG: marcar
// ------------------------------------------------------------

// Las variables que generan alguna cadena de terminales, agrupadas por ronda. En cada ronda
// se marca toda variable A con una regla A → X1 … Xk cuyos símbolos son todos terminales o
// variables marcadas en rondas anteriores. Se detiene cuando una ronda no marca nada: como en
// cada ronda útil se marca al menos una variable, hay a lo sumo |V| + 1 rondas.
inline std::vector<std::vector<std::string>> generating_rounds(const Cfg& g) {
    std::set<std::string> marked;
    std::vector<std::vector<std::string>> rounds;
    while (true) {
        std::vector<std::string> fresh;
        for (const std::string& v : g.variables) {
            if (marked.count(v) > 0) {
                continue;
            }
            for (const Rule& rule : g.rules) {
                if (rule.head != v) {
                    continue;
                }
                bool all = true;
                for (const std::string& symbol : rule.body) {
                    if (is_variable(g, symbol) && marked.count(symbol) == 0) {
                        all = false;
                        break;
                    }
                }
                if (all) {
                    fresh.push_back(v);
                    break;
                }
            }
        }
        if (fresh.empty()) {
            return rounds;
        }
        marked.insert(fresh.begin(), fresh.end());
        rounds.push_back(fresh);
    }
}

inline std::set<std::string> generating(const Cfg& g) {
    std::set<std::string> marked;
    for (const std::vector<std::string>& round : generating_rounds(g)) {
        marked.insert(round.begin(), round.end());
    }
    return marked;
}

// ¿L(G) = ∅? Es decir, ¿⟨G⟩ ∈ E_CFG? L(G) es vacío si y solo si S no queda marcada.
inline bool is_empty(const Cfg& g) {
    return generating(g).count(g.start) == 0;
}

// ------------------------------------------------------------
// A_CFG
// ------------------------------------------------------------

// ¿Está G en forma normal de Chomsky? Reglas A → BC, con B y C variables distintas de S;
// A → a; y S → ε, solo para la variable inicial.
inline bool is_chomsky(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        if (rule.body.empty()) {
            if (rule.head != g.start) {
                return false;
            }
        } else if (rule.body.size() == 1) {
            if (is_variable(g, rule.body[0])) {
                return false;
            }
        } else if (rule.body.size() == 2) {
            for (const std::string& symbol : rule.body) {
                if (!is_variable(g, symbol) || symbol == g.start) {
                    return false;
                }
            }
        } else {
            return false;
        }
    }
    return true;
}

// A_CFG como en la demostración. Con G en forma normal de Chomsky, toda derivación de una
// cadena de longitud n ≥ 1 tiene exactamente 2n − 1 pasos (y la de ε, un paso). Entonces basta
// probar las derivaciones por la izquierda de a lo sumo `steps` pasos, que son finitas.
// Se descartan las formas que ya no pueden dar w: en forma normal de Chomsky una forma nunca
// se acorta, y los terminales de su prefijo ya no cambian.
inline bool derives_within(const Cfg& g, const std::vector<std::string>& form, const std::string& w,
                           std::size_t steps) {
    if (form.size() > w.size() && !(w.empty() && form.size() == 1)) {
        return false;
    }
    std::size_t i = 0;
    while (i < form.size() && !is_variable(g, form[i])) {
        if (i >= w.size() || form[i][0] != w[i]) {
            return false;
        }
        i++;
    }
    if (i == form.size()) {
        return form.size() == w.size();
    }
    if (steps == 0) {
        return false;
    }
    for (const Rule& rule : g.rules) {
        if (rule.head != form[i]) {
            continue;
        }
        std::vector<std::string> next(form.begin(), form.begin() + static_cast<std::ptrdiff_t>(i));
        next.insert(next.end(), rule.body.begin(), rule.body.end());
        next.insert(next.end(), form.begin() + static_cast<std::ptrdiff_t>(i) + 1, form.end());
        if (derives_within(g, next, w, steps - 1)) {
            return true;
        }
    }
    return false;
}

inline bool derives_bounded(const Cfg& g, const std::string& w) {
    if (!is_chomsky(g)) {
        throw std::runtime_error("la gramática no está en forma normal de Chomsky");
    }
    std::size_t steps = w.empty() ? 1 : 2 * w.size() - 1;
    return derives_within(g, {g.start}, w, steps);
}

// CYK. table[i][j] es el conjunto de variables que generan la subcadena de w que empieza en
// la posición i y tiene longitud j + 1.
using CykTable = std::vector<std::vector<std::set<std::string>>>;

inline CykTable cyk_table(const Cfg& g, const std::string& w) {
    if (!is_chomsky(g)) {
        throw std::runtime_error("la gramática no está en forma normal de Chomsky");
    }
    std::size_t n = w.size();
    CykTable table(n, std::vector<std::set<std::string>>(n));
    for (std::size_t i = 0; i < n; i++) {
        for (const Rule& rule : g.rules) {
            if (rule.body.size() == 1 && rule.body[0][0] == w[i]) {
                table[i][0].insert(rule.head);
            }
        }
    }
    for (std::size_t len = 2; len <= n; len++) {
        for (std::size_t i = 0; i + len <= n; i++) {
            for (std::size_t left = 1; left < len; left++) {
                for (const Rule& rule : g.rules) {
                    if (rule.body.size() == 2 && table[i][left - 1].count(rule.body[0]) > 0 &&
                        table[i + left][len - left - 1].count(rule.body[1]) > 0) {
                        table[i][len - 1].insert(rule.head);
                    }
                }
            }
        }
    }
    return table;
}

inline bool cyk(const Cfg& g, const std::string& w) {
    if (w.empty()) {
        if (!is_chomsky(g)) {
            throw std::runtime_error("la gramática no está en forma normal de Chomsky");
        }
        for (const Rule& rule : g.rules) {
            if (rule.head == g.start && rule.body.empty()) {
                return true;
            }
        }
        return false;
    }
    return cyk_table(g, w)[0][w.size() - 1].count(g.start) > 0;
}

#endif
