05
Lenguajes libres de contexto

Gramáticas libres de contexto

Lenguajes libres de contexto

Semana 5 — Gramáticas libres de contexto

Objetivos

  • Escribir una gramática libre de contexto para un lenguaje y derivar cadenas con ella.
  • Reconocer una gramática ambigua y, cuando se puede, dar una equivalente que no lo sea.
  • Convertir una gramática a forma normal de Chomsky.
  • Decidir si una gramática genera una cadena con el algoritmo CYK, y explicar su costo.

Sesión A — Gramáticas libres de contexto, derivaciones y ambigüedad

Lectura: Apuntes, semana 5.

Apoyo: Sipser, sec. 2.1 (Context-Free Grammars), hasta la ambigüedad. Erickson, Models of Computation, nota 5 (Context-free languages).

Temas:

  • Lo que las expresiones regulares no alcanzan: paréntesis balanceados, expresiones aritméticas, JSON. Estructura anidada.
  • Definición formal: G=(V,Σ,R,S)G = (V, \Sigma, R, S). Reglas A→wA \to w.
  • Derivaciones, u⇒vu \Rightarrow v y u⇒∗vu \Rightarrow^* v. El lenguaje L(G)L(G). Derivación por la izquierda.
  • Árbol de derivación: muestra la estructura, sin el orden de los reemplazos.
  • Diseñar gramáticas: {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}, palíndromos, paréntesis balanceados, igual número de a y b. Unir gramáticas; de un DFA a una gramática.
  • Demostrar que una gramática genera el lenguaje pedido: dos inclusiones, por inducción.
  • Ambigüedad: dos árboles para a+a*a. La gramática de expresiones con niveles de precedencia. El else colgante.
  • Hay lenguajes inherentemente ambiguos; se enuncia.
  • Error común: llamar ambigua a una gramática porque una cadena tiene dos derivaciones. Lo que cuenta son dos árboles, o dos derivaciones por la izquierda.

Sesión B — Forma normal de Chomsky y el algoritmo CYK

Lectura: Apuntes, semana 5.

Apoyo: Sipser, sec. 2.1 (Chomsky Normal Form) y, en la sec. 7.2, el teorema de que todo lenguaje libre de contexto está en P, que es CYK. Erickson, Models of Computation, nota 5.

Temas:

  • El problema: dada GG y ww, ¿GG genera ww? Probar todas las derivaciones no termina, o tarda un tiempo exponencial.
  • Forma normal de Chomsky: solo reglas A→BCA \to BC y A→aA \to a, y S→εS \to \varepsilon si hace falta.
  • La conversión en cuatro pasos, en este orden: variable inicial nueva, quitar reglas ε\varepsilon, quitar reglas unitarias, partir las reglas largas. Ejemplo completo.
  • Una derivación de una cadena de longitud nn en forma normal de Chomsky tiene exactamente 2n−12n - 1 pasos.
  • CYK: la tabla T[i][j]T[i][j] guarda las variables que generan la subcadena de ii a jj. Es programación dinámica sobre intervalos, como en Algoritmos.
  • Llenar la tabla a mano con una cadena de cinco símbolos. Recuperar el árbol.
  • Costo O(n3⋅∣G∣)O(n^3 \cdot |G|). Por qué los compiladores no usan CYK: sus gramáticas permiten parsers lineales.
  • Error común: quitar las reglas unitarias antes que las reglas ε\varepsilon, que vuelve a crear unitarias.

Laboratorio — Un parser con CYK

  1. Leer una gramática en forma normal de Chomsky y una lista de cadenas, y decir cuáles genera.
  2. Llenar la tabla de CYK por longitudes crecientes de subcadena.
  3. Para las cadenas aceptadas, imprimir un árbol de derivación.
  4. Pasar los casos de borde: la cadena vacía, y una gramática que no genera nada.
  5. Escribir en forma normal de Chomsky la gramática de los paréntesis balanceados y probarla con su parser.

Preguntas de repaso

  1. Den una gramática para { aibjck:i=j o j=k }\{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i = j \text{ o } j = k \,\}. ¿Es ambigua? ¿Qué cadenas tienen dos árboles?
  2. Demuestren que S→aSb∣εS \to \mathtt{a}S\mathtt{b} \mid \varepsilon genera exactamente {anbn}\{\mathtt{a}^n\mathtt{b}^n\}.
  3. Conviertan S→aSb∣SS∣εS \to \mathtt{a}S\mathtt{b} \mid SS \mid \varepsilon a forma normal de Chomsky, mostrando los cuatro pasos.
  4. Llenen la tabla de CYK para una cadena de cuatro símbolos con la gramática del punto anterior.
  5. ¿Por qué CYK necesita la forma normal de Chomsky? ¿Qué parte del algoritmo se rompería con una regla A→BCDA \to BCD?

Código de la semana

Compilar y probar dentro del contenedor del curso con make y make test.

Ejemplos (23)Errores (3)Pruebas (4)Laboratorio (4)Compilación (1)

Ejemplos

Los programas que usan los apuntes y la clase.

cfg.hDescargar cfg.h
// Gramática libre de contexto. El struct tiene los cuatro componentes de la definición
// G = (V, Σ, R, S), con los nombres del formato .cfg de code/formats.md.
// Además: leer y escribir ese formato, las cadenas que genera una gramática hasta una longitud,
// las derivaciones por la izquierda de una cadena y sus árboles de derivación.
// Las funciones que leen líneas siguen el esquema de code/week-01/dfa.h.
#ifndef CFG_H
#define CFG_H

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

// Una regla A → X1 X2 … Xk. Cada símbolo del lado derecho es el nombre de una variable o un
// terminal (una cadena de un solo carácter). La regla A → ε tiene el lado derecho vacío.
struct Rule {
    std::string head;
    std::vector<std::string> body;
    bool operator==(const Rule& other) const = default;
};

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

inline bool is_variable(const Cfg& g, const std::string& symbol) {
    return std::find(g.variables.begin(), g.variables.end(), symbol) != g.variables.end();
}

inline bool is_terminal(const Cfg& g, const std::string& symbol) {
    return symbol.size() == 1 && std::find(g.terminals.begin(), g.terminals.end(), symbol[0]) != g.terminals.end();
}

// ------------------------------------------------------------
// Comprobar que la cuádrupla es una gramática
// ------------------------------------------------------------

// Lanza std::runtime_error si g no cumple la definición.
inline void check_cfg(const Cfg& g) {
    std::set<std::string> v(g.variables.begin(), g.variables.end());
    std::set<char> sigma(g.terminals.begin(), g.terminals.end());
    if (g.variables.empty()) {
        throw std::runtime_error("V no puede ser vacío");
    }
    if (v.size() != g.variables.size()) {
        throw std::runtime_error("hay una variable repetida en variables");
    }
    if (sigma.size() != g.terminals.size()) {
        throw std::runtime_error("hay un terminal repetido en terminals");
    }
    for (const std::string& name : g.variables) {
        if (name == "eps" || name == "->" || name == "|") {
            throw std::runtime_error("una variable no puede llamarse " + name);
        }
        if (name.size() == 1 && sigma.count(name[0]) > 0) {
            throw std::runtime_error(name + " es variable y terminal a la vez: V y Σ no comparten símbolos");
        }
    }
    if (sigma.count('|') > 0) {
        throw std::runtime_error("el terminal | se confunde con el separador de alternativas");
    }
    if (v.count(g.start) == 0) {
        throw std::runtime_error("la variable inicial " + g.start + " no está en variables");
    }
    for (const Rule& rule : g.rules) {
        if (v.count(rule.head) == 0) {
            throw std::runtime_error("regla de " + rule.head + ", que no está en variables");
        }
        for (const std::string& symbol : rule.body) {
            if (!is_variable(g, symbol) && !is_terminal(g, symbol)) {
                throw std::runtime_error("en una regla de " + rule.head + " aparece " + symbol +
                                         ", que no es variable ni terminal");
            }
        }
    }
}

// ------------------------------------------------------------
// Leer y escribir el formato .cfg
// ------------------------------------------------------------

inline std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

// Agrega la regla si no estaba. Las reglas forman un conjunto: repetir una no cambia nada.
inline void add_rule(Cfg& g, const Rule& rule) {
    if (std::find(g.rules.begin(), g.rules.end(), rule) == g.rules.end()) {
        g.rules.push_back(rule);
    }
}

// Lee una descripción completa, hasta el final de la entrada.
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);
    };
    // Siguiente línea que no es comentario ni está vacía. Devuelve false al final.
    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;
            }
            words = split_words(line);
            if (!words.empty()) {
                return true;
            }
        }
        return false;
    };
    // Un campo: "nombre: valor valor ...". Devuelve los valores.
    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");
    for (const std::string& symbol : field("terminals")) {
        if (symbol.size() != 1 || symbol[0] == '#') {
            fail("un terminal es un solo carácter distinto de #: " + symbol);
        }
        g.terminals.push_back(symbol[0]);
    }
    std::vector<std::string> start = field("start");
    if (start.size() != 1) {
        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)) {
        // variable -> alternativa | alternativa …
        if (words.size() < 3 || words[1] != "->") {
            fail("una regla se escribe: variable -> símbolos | símbolos");
        }
        Rule rule;
        rule.head = words[0];
        bool has_eps = false;
        for (std::size_t i = 2; i <= words.size(); i++) {
            if (i < words.size() && words[i] != "|") {
                if (words[i] == "eps") {
                    has_eps = true;
                } else {
                    rule.body.push_back(words[i]);
                }
                continue;
            }
            // Terminó una alternativa.
            if (has_eps ? !rule.body.empty() : rule.body.empty()) {
                fail("una alternativa es una lista de símbolos, o eps sola");
            }
            add_rule(g, rule);
            rule.body.clear();
            has_eps = false;
        }
    }
    try {
        check_cfg(g);
    } catch (const std::runtime_error& error) {
        throw std::runtime_error(std::string("la gramática no es válida: ") + error.what());
    }
    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());
    }
}

// El lado derecho de una regla, con los símbolos separados por espacios, como en el archivo.
inline std::string body_text(const std::vector<std::string>& body) {
    if (body.empty()) {
        return "eps";
    }
    std::string text;
    for (const std::string& symbol : body) {
        text += (text.empty() ? "" : " ") + symbol;
    }
    return text;
}

// Escribe g en el formato .cfg: lo que escribe se puede volver a leer con read_cfg.
// Las alternativas de una variable van en una sola línea, en el orden en que están en R.
inline void write_cfg(std::ostream& out, const Cfg& g) {
    out << "variables:";
    for (const std::string& name : g.variables) {
        out << ' ' << name;
    }
    out << "\nterminals:";
    for (char a : g.terminals) {
        out << ' ' << a;
    }
    out << "\nstart: " << g.start << "\nrules:\n";
    for (const std::string& name : g.variables) {
        std::string line;
        for (const Rule& rule : g.rules) {
            if (rule.head == name) {
                line += (line.empty() ? name + " -> " : " | ") + body_text(rule.body);
            }
        }
        if (!line.empty()) {
            out << line << '\n';
        }
    }
}

// ------------------------------------------------------------
// Las cadenas que genera una gramática, hasta una longitud
// ------------------------------------------------------------

// Todas las cadenas sobre el alfabeto con longitud a lo sumo max_length, las más cortas primero.
inline std::vector<std::string> all_strings(const std::vector<char>& alphabet, std::size_t max_length) {
    std::vector<std::string> result = {""};
    std::size_t begin = 0;
    for (std::size_t length = 1; length <= max_length; length++) {
        std::size_t end = result.size();
        for (std::size_t i = begin; i < end; i++) {
            for (char a : alphabet) {
                result.push_back(result[i] + a);
            }
        }
        begin = end;
    }
    return result;
}

// Para cada variable A, el conjunto { w : A ⇒* w y |w| ≤ max_length }.
// Se calcula sin buscar derivaciones: se parte de conjuntos vacíos y se aplican las reglas
// (si A → X1…Xk y cada Xi genera wi, entonces A genera w1…wk) hasta que ningún conjunto crece.
// Como solo hay una cantidad finita de cadenas de longitud ≤ max_length, siempre termina,
// también con reglas ε y con reglas como S → SS.
inline std::map<std::string, std::set<std::string>> generated_by_variable(const Cfg& g, std::size_t max_length) {
    std::map<std::string, std::set<std::string>> language;
    for (const std::string& name : g.variables) {
        language[name];
    }
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            std::set<std::string> partial = {""};  // lo que generan los primeros símbolos del lado derecho
            for (const std::string& symbol : rule.body) {
                std::set<std::string> next;
                if (is_variable(g, symbol)) {
                    for (const std::string& left : partial) {
                        for (const std::string& right : language[symbol]) {
                            if (left.size() + right.size() <= max_length) {
                                next.insert(left + right);
                            }
                        }
                    }
                } else {
                    for (const std::string& left : partial) {
                        if (left.size() + 1 <= max_length) {
                            next.insert(left + symbol);
                        }
                    }
                }
                partial = next;
            }
            std::set<std::string>& target = language[rule.head];
            for (const std::string& w : partial) {
                if (target.insert(w).second) {
                    changed = true;
                }
            }
        }
    }
    return language;
}

// Las cadenas de L(G) con longitud a lo sumo max_length.
inline std::set<std::string> generated_strings(const Cfg& g, std::size_t max_length) {
    return generated_by_variable(g, max_length)[g.start];
}

// Las mismas cadenas, de la más corta a la más larga.
inline std::vector<std::string> shortest_first(const std::set<std::string>& language) {
    std::vector<std::string> words(language.begin(), language.end());
    std::stable_sort(words.begin(), words.end(),
                     [](const std::string& a, const std::string& b) { return a.size() < b.size(); });
    return words;
}

// La longitud de la cadena más corta que genera cada variable. Una variable que no genera
// ninguna cadena queda con el valor NO_STRING.
inline constexpr std::size_t NO_STRING = static_cast<std::size_t>(-1);

inline std::map<std::string, std::size_t> shortest_lengths(const Cfg& g) {
    std::map<std::string, std::size_t> shortest;
    for (const std::string& name : g.variables) {
        shortest[name] = NO_STRING;
    }
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            std::size_t total = 0;
            bool possible = true;
            for (const std::string& symbol : rule.body) {
                if (!is_variable(g, symbol)) {
                    total += 1;
                } else if (shortest[symbol] == NO_STRING) {
                    possible = false;
                    break;
                } else {
                    total += shortest[symbol];
                }
            }
            if (possible && total < shortest[rule.head]) {
                shortest[rule.head] = total;
                changed = true;
            }
        }
    }
    return shortest;
}

// ------------------------------------------------------------
// Derivaciones por la izquierda
// ------------------------------------------------------------

// Una derivación por la izquierda queda determinada por la lista de reglas que usa, en orden:
// cada paso reemplaza la variable que está más a la izquierda. Se guardan las posiciones en g.rules.
using Derivation = std::vector<std::size_t>;

struct DerivationSearch {
    std::vector<Derivation> found;  // las derivaciones por la izquierda de w que se encontraron
    bool complete = true;           // false si la búsqueda se cortó por alguno de los dos topes
    long explored = 0;              // pasos de derivación que se probaron
};

// Busca todas las derivaciones por la izquierda de w, probando reglas con backtracking.
// Abandona un camino cuando lo ya derivado no puede terminar en w: los terminales que quedaron
// a la izquierda de la primera variable no son un prefijo de w, o lo que falta derivar ya no
// cabe en |w| símbolos. Con reglas ε o unitarias la búsqueda puede no terminar: por eso se
// corta a los max_steps pasos de cada derivación y al encontrar max_found derivaciones.
inline DerivationSearch leftmost_derivations(const Cfg& g, const std::string& w, std::size_t max_steps,
                                             std::size_t max_found = 1000) {
    DerivationSearch search;
    std::map<std::string, std::size_t> shortest = shortest_lengths(g);
    std::vector<std::string> form = {g.start};
    Derivation used;

    auto visit = [&](auto&& self) -> void {
        if (search.found.size() >= max_found) {
            search.complete = false;
            return;
        }
        // Los terminales antes de la primera variable deben coincidir con w.
        std::size_t first = 0;
        while (first < form.size() && !is_variable(g, form[first])) {
            if (first >= w.size() || form[first][0] != w[first]) {
                return;
            }
            first++;
        }
        if (first == form.size()) {
            if (form.size() == w.size()) {
                search.found.push_back(used);
            }
            return;
        }
        // Lo más corto que puede generar la forma no debe pasar de |w|.
        std::size_t least = 0;
        for (const std::string& symbol : form) {
            std::size_t add = is_variable(g, symbol) ? shortest[symbol] : 1;
            if (add == NO_STRING || least + add > w.size()) {
                return;
            }
            least += add;
        }
        if (used.size() >= max_steps) {
            search.complete = false;
            return;
        }
        std::string variable = form[first];
        for (std::size_t r = 0; r < g.rules.size(); r++) {
            if (g.rules[r].head != variable) {
                continue;
            }
            const std::vector<std::string>& body = g.rules[r].body;
            search.explored++;
            form.erase(form.begin() + static_cast<std::ptrdiff_t>(first));
            form.insert(form.begin() + static_cast<std::ptrdiff_t>(first), body.begin(), body.end());
            used.push_back(r);
            self(self);
            used.pop_back();
            form.erase(form.begin() + static_cast<std::ptrdiff_t>(first),
                       form.begin() + static_cast<std::ptrdiff_t>(first + body.size()));
            form.insert(form.begin() + static_cast<std::ptrdiff_t>(first), variable);
        }
    };
    visit(visit);
    return search;
}

// Las formas por las que pasa una derivación por la izquierda: S, …, w. Cada forma es una
// lista de símbolos.
inline std::vector<std::vector<std::string>> sentential_forms(const Cfg& g, const Derivation& derivation) {
    std::vector<std::vector<std::string>> forms = {{g.start}};
    for (std::size_t r : derivation) {
        std::vector<std::string> form = forms.back();
        std::size_t first = 0;
        while (first < form.size() && !is_variable(g, form[first])) {
            first++;
        }
        if (first == form.size() || form[first] != g.rules[r].head) {
            throw std::runtime_error("la lista de reglas no es una derivación por la izquierda");
        }
        form.erase(form.begin() + static_cast<std::ptrdiff_t>(first));
        form.insert(form.begin() + static_cast<std::ptrdiff_t>(first), g.rules[r].body.begin(),
                    g.rules[r].body.end());
        forms.push_back(form);
    }
    return forms;
}

// Una forma como texto. Si todas las variables son de una letra, los símbolos van pegados
// (aSb); si no, separados por espacios. La forma sin símbolos es ε.
inline std::string form_text(const Cfg& g, const std::vector<std::string>& form) {
    if (form.empty()) {
        return "ε";
    }
    bool spaced = false;
    for (const std::string& name : g.variables) {
        spaced = spaced || name.size() > 1;
    }
    std::string text;
    for (const std::string& symbol : form) {
        text += ((spaced && !text.empty()) ? " " : "") + symbol;
    }
    return text;
}

// ------------------------------------------------------------
// Árboles de derivación
// ------------------------------------------------------------

// Un nodo lleva una variable y tiene un hijo por cada símbolo de la regla que se le aplicó.
// Una hoja lleva un terminal o ε.
struct Tree {
    std::string symbol;
    std::vector<Tree> children;
};

// El árbol de una derivación por la izquierda. Los pasos de la derivación recorren el árbol
// en preorden: primero el nodo, después sus hijos de izquierda a derecha.
inline Tree tree_of(const Cfg& g, const Derivation& derivation) {
    std::size_t next = 0;
    auto build = [&](auto&& self, const std::string& symbol) -> Tree {
        Tree node{symbol, {}};
        if (!is_variable(g, symbol)) {
            return node;
        }
        if (next >= derivation.size() || g.rules[derivation[next]].head != symbol) {
            throw std::runtime_error("la lista de reglas no es una derivación por la izquierda");
        }
        const Rule& rule = g.rules[derivation[next]];
        next++;
        if (rule.body.empty()) {
            node.children.push_back(Tree{"ε", {}});
        }
        for (const std::string& child : rule.body) {
            node.children.push_back(self(self, child));
        }
        return node;
    };
    Tree root = build(build, g.start);
    if (next != derivation.size()) {
        throw std::runtime_error("sobran pasos en la derivación");
    }
    return root;
}

// Las hojas del árbol, de izquierda a derecha: la cadena que el árbol deriva.
inline std::string yield_of(const Tree& tree) {
    if (tree.children.empty()) {
        return tree.symbol == "ε" ? "" : tree.symbol;
    }
    std::string text;
    for (const Tree& child : tree.children) {
        text += yield_of(child);
    }
    return text;
}

// Cuántos nodos del árbol llevan una variable: es la cantidad de pasos de sus derivaciones.
inline std::size_t count_inner(const Tree& tree) {
    if (tree.children.empty()) {
        return 0;
    }
    std::size_t total = 1;
    for (const Tree& child : tree.children) {
        total += count_inner(child);
    }
    return total;
}

// El árbol es un árbol de derivación de g: en cada nodo interno hay una variable, y sus hijos
// son el lado derecho de alguna regla de esa variable.
inline bool is_parse_tree(const Cfg& g, const Tree& tree) {
    if (tree.children.empty()) {
        return tree.symbol == "ε" || is_terminal(g, tree.symbol);
    }
    Rule rule{tree.symbol, {}};
    for (const Tree& child : tree.children) {
        if (child.symbol != "ε" || !child.children.empty()) {
            rule.body.push_back(child.symbol);
        } else if (tree.children.size() != 1) {
            return false;
        }
        if (!is_parse_tree(g, child)) {
            return false;
        }
    }
    return std::find(g.rules.begin(), g.rules.end(), rule) != g.rules.end();
}

// Dibuja el árbol con una línea por nodo.
inline void print_tree(std::ostream& out, const Tree& tree, const std::string& indent = "",
                       const std::string& prefix = "") {
    out << prefix << tree.symbol << '\n';
    for (std::size_t i = 0; i < tree.children.size(); i++) {
        bool last = (i + 1 == tree.children.size());
        print_tree(out, tree.children[i], indent + (last ? "    " : "│   "), indent + (last ? "└── " : "├── "));
    }
}

// El árbol en una línea: [A hijo hijo …], y una hoja es su símbolo. Es el formato del laboratorio.
inline std::string bracket_text(const Tree& tree) {
    if (tree.children.empty()) {
        return tree.symbol == "ε" ? "eps" : tree.symbol;
    }
    std::string text = "[" + tree.symbol;
    for (const Tree& child : tree.children) {
        text += " " + bracket_text(child);
    }
    return text + "]";
}

#endif
chomsky.hDescargar chomsky.h
// Forma normal de Chomsky: la conversión en cuatro pasos y el algoritmo CYK.
// Cada paso es una función que recibe una gramática y devuelve otra que genera el mismo lenguaje.
#ifndef CHOMSKY_H
#define CHOMSKY_H

#include <algorithm>
#include <cstddef>
#include <map>
#include <ostream>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "cfg.h"

// Un nombre de variable que la gramática todavía no usa: base, base', base''…
inline std::string fresh_name(const Cfg& g, const std::string& base) {
    std::string name = base;
    while (is_variable(g, name) || is_terminal(g, name)) {
        name += "'";
    }
    return name;
}

// ------------------------------------------------------------
// ¿Está en forma normal de Chomsky?
// ------------------------------------------------------------

// Devuelve "" si toda regla es A → BC (con B y C variables distintas de la inicial), A → a,
// o S → ε con S la variable inicial. Si no, devuelve la primera regla que lo impide y por qué.
inline std::string why_not_chomsky(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        std::string text = rule.head + " -> " + body_text(rule.body);
        if (rule.body.empty()) {
            if (rule.head != g.start) {
                return text + ": solo la variable inicial puede tener una regla ε";
            }
        } else if (rule.body.size() == 1) {
            if (is_variable(g, rule.body[0])) {
                return text + ": es una regla unitaria";
            }
        } else if (rule.body.size() == 2) {
            for (const std::string& symbol : rule.body) {
                if (!is_variable(g, symbol)) {
                    return text + ": en una regla de dos símbolos, los dos son variables";
                }
                if (symbol == g.start) {
                    return text + ": la variable inicial no aparece a la derecha";
                }
            }
        } else {
            return text + ": el lado derecho tiene más de dos símbolos";
        }
    }
    return "";
}

inline bool is_chomsky(const Cfg& g) {
    return why_not_chomsky(g).empty();
}

// ------------------------------------------------------------
// Paso 1: variable inicial nueva
// ------------------------------------------------------------

// Agrega S0 → S. Después de este paso la variable inicial no aparece en ningún lado derecho.
inline Cfg with_new_start(const Cfg& g) {
    Cfg result = g;
    result.start = fresh_name(g, g.start + "0");
    result.variables.insert(result.variables.begin(), result.start);
    result.rules.insert(result.rules.begin(), Rule{result.start, {g.start}});
    return result;
}

// ------------------------------------------------------------
// Paso 2: quitar las reglas ε
// ------------------------------------------------------------

// Las variables anulables: las que derivan ε. A es anulable si tiene una regla cuyo lado
// derecho son solo variables anulables (la regla A → ε es el caso de cero símbolos).
inline std::set<std::string> nullable_variables(const Cfg& g) {
    std::set<std::string> nullable;
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            bool all = true;
            for (const std::string& symbol : rule.body) {
                all = all && nullable.count(symbol) > 0;
            }
            if (all && nullable.insert(rule.head).second) {
                changed = true;
            }
        }
    }
    return nullable;
}

// Por cada regla A → X1…Xk, quedan todas las reglas que se obtienen borrando algunas
// apariciones de variables anulables, salvo la que borra todo. Si la variable inicial es
// anulable, conserva su regla ε.
inline Cfg without_epsilon_rules(const Cfg& g) {
    std::set<std::string> nullable = nullable_variables(g);
    Cfg result = g;
    result.rules.clear();
    for (const Rule& rule : g.rules) {
        std::vector<std::size_t> positions;  // las apariciones de variables anulables
        for (std::size_t i = 0; i < rule.body.size(); i++) {
            if (nullable.count(rule.body[i]) > 0) {
                positions.push_back(i);
            }
        }
        if (positions.size() > 20) {
            throw std::runtime_error("una regla tiene más de 20 variables anulables: saldrían más de un millón");
        }
        // Cada subconjunto de esas apariciones es una máscara de bits: el bit b dice si se borra positions[b].
        for (unsigned long mask = 0; mask < (1UL << positions.size()); mask++) {
            Rule shorter{rule.head, {}};
            for (std::size_t i = 0; i < rule.body.size(); i++) {
                auto where = std::find(positions.begin(), positions.end(), i);
                bool erased = where != positions.end() && ((mask >> (where - positions.begin())) & 1UL) != 0;
                if (!erased) {
                    shorter.body.push_back(rule.body[i]);
                }
            }
            if (!shorter.body.empty()) {
                add_rule(result, shorter);
            }
        }
    }
    if (nullable.count(g.start) > 0) {
        add_rule(result, Rule{g.start, {}});
    }
    return result;
}

// ------------------------------------------------------------
// Paso 3: quitar las reglas unitarias
// ------------------------------------------------------------

inline bool is_unit(const Cfg& g, const Rule& rule) {
    return rule.body.size() == 1 && is_variable(g, rule.body[0]);
}

// Los pares (A, B) tales que A ⇒* B usando solo reglas unitarias. Incluye los pares (A, A).
inline std::set<std::pair<std::string, std::string>> unit_pairs(const Cfg& g) {
    std::set<std::pair<std::string, std::string>> pairs;
    for (const std::string& name : g.variables) {
        pairs.insert({name, name});
    }
    bool changed = true;
    while (changed) {
        changed = false;
        for (const Rule& rule : g.rules) {
            if (!is_unit(g, rule)) {
                continue;
            }
            // Si A llega a rule.head, también llega a rule.body[0].
            for (const std::string& a : g.variables) {
                if (pairs.count({a, rule.head}) > 0 && pairs.insert({a, rule.body[0]}).second) {
                    changed = true;
                }
            }
        }
    }
    return pairs;
}

// Por cada par (A, B) y cada regla B → u que no es unitaria, queda la regla A → u.
inline Cfg without_unit_rules(const Cfg& g) {
    std::set<std::pair<std::string, std::string>> pairs = unit_pairs(g);
    Cfg result = g;
    result.rules.clear();
    for (const std::string& a : g.variables) {
        for (const std::string& b : g.variables) {
            if (pairs.count({a, b}) == 0) {
                continue;
            }
            for (const Rule& rule : g.rules) {
                if (rule.head == b && !is_unit(g, rule)) {
                    add_rule(result, Rule{a, rule.body});
                }
            }
        }
    }
    return result;
}

// ------------------------------------------------------------
// Paso 4: partir las reglas largas y sacar los terminales de las reglas de dos símbolos
// ------------------------------------------------------------

// A → X1 X2 … Xk con k ≥ 3 se cambia por A → X1 A_1, A_1 → X2 A_2, …, A_(k−2) → X(k−1) Xk.
// Después, en cada regla de dos símbolos, un terminal a se cambia por una variable U_a con
// la única regla U_a → a.
inline Cfg with_short_rules(const Cfg& g) {
    Cfg result = g;
    result.rules.clear();
    std::map<std::string, int> pieces;  // cuántas variables nuevas lleva cada variable original
    for (const Rule& rule : g.rules) {
        if (rule.body.size() <= 2) {
            add_rule(result, rule);
            continue;
        }
        std::string head = rule.head;
        for (std::size_t i = 0; i + 2 < rule.body.size(); i++) {
            pieces[rule.head]++;
            std::string piece = fresh_name(result, rule.head + "_" + std::to_string(pieces[rule.head]));
            result.variables.push_back(piece);
            add_rule(result, Rule{head, {rule.body[i], piece}});
            head = piece;
        }
        add_rule(result, Rule{head, {rule.body[rule.body.size() - 2], rule.body[rule.body.size() - 1]}});
    }
    std::map<std::string, std::string> variable_of;  // terminal → su variable U_a
    for (Rule& rule : result.rules) {
        if (rule.body.size() != 2) {
            continue;
        }
        for (std::string& symbol : rule.body) {
            if (is_variable(result, symbol)) {
                continue;
            }
            if (variable_of.count(symbol) == 0) {
                variable_of[symbol] = fresh_name(result, "U_" + symbol);
                result.variables.push_back(variable_of[symbol]);
            }
            symbol = variable_of[symbol];
        }
    }
    for (char a : g.terminals) {
        std::string terminal(1, a);
        if (variable_of.count(terminal) > 0) {
            result.rules.push_back(Rule{variable_of[terminal], {terminal}});
        }
    }
    // Al cambiar terminales por variables, dos reglas distintas pueden haber quedado iguales.
    Cfg clean = result;
    clean.rules.clear();
    for (const Rule& rule : result.rules) {
        add_rule(clean, rule);
    }
    return clean;
}

// Los cuatro pasos, en el orden correcto.
inline Cfg to_chomsky(const Cfg& g) {
    return with_short_rules(without_unit_rules(without_epsilon_rules(with_new_start(g))));
}

// ------------------------------------------------------------
// CYK
// ------------------------------------------------------------

struct CykTable {
    std::size_t n = 0;
    // cell[i][j], con 0 ≤ i ≤ j < n: las variables que generan la subcadena w[i..j].
    std::vector<std::vector<std::set<std::string>>> cell;
    long checks = 0;  // cuántas veces se probó una regla A → BC con un punto de corte
};

// Llena la tabla por longitudes crecientes de subcadena. g debe estar en forma normal de Chomsky.
inline CykTable cyk(const Cfg& g, const std::string& w) {
    std::string why = why_not_chomsky(g);
    if (!why.empty()) {
        throw std::runtime_error("CYK necesita una gramática en forma normal de Chomsky. " + why);
    }
    CykTable table;
    table.n = w.size();
    std::size_t n = w.size();
    table.cell.assign(n, std::vector<std::set<std::string>>(n));
    // Longitud 1: las reglas A → a.
    for (std::size_t i = 0; i < n; i++) {
        for (const Rule& rule : g.rules) {
            if (rule.body.size() == 1 && rule.body[0] == std::string(1, w[i])) {
                table.cell[i][i].insert(rule.head);
            }
        }
    }
    // Longitud ≥ 2: las reglas A → BC, con B para w[i..k] y C para w[k+1..j].
    for (std::size_t length = 2; length <= n; length++) {
        for (std::size_t i = 0; i + length <= n; i++) {
            std::size_t j = i + length - 1;
            for (std::size_t k = i; k < j; k++) {
                for (const Rule& rule : g.rules) {
                    if (rule.body.size() != 2) {
                        continue;
                    }
                    table.checks++;
                    if (table.cell[i][k].count(rule.body[0]) > 0 && table.cell[k + 1][j].count(rule.body[1]) > 0) {
                        table.cell[i][j].insert(rule.head);
                    }
                }
            }
        }
    }
    return table;
}

// ¿w ∈ L(G)? La cadena vacía se decide aparte: solo la regla S → ε la genera.
inline bool cyk_accepts(const Cfg& g, const CykTable& table) {
    if (table.n == 0) {
        return std::find(g.rules.begin(), g.rules.end(), Rule{g.start, {}}) != g.rules.end();
    }
    return table.cell[0][table.n - 1].count(g.start) > 0;
}

inline bool cyk_accepts(const Cfg& g, const std::string& w) {
    return cyk_accepts(g, cyk(g, w));
}

// Un árbol de derivación de w[i..j] con raíz A. Requiere que A esté en cell[i][j].
// Vuelve a buscar una regla y un punto de corte que justifiquen esa entrada de la tabla, y
// se queda con los primeros que encuentra: si hay varios árboles, devuelve uno.
inline Tree cyk_subtree(const Cfg& g, const CykTable& table, const std::string& w, const std::string& a,
                        std::size_t i, std::size_t j) {
    if (i == j) {
        return Tree{a, {Tree{std::string(1, w[i]), {}}}};
    }
    for (std::size_t k = i; k < j; k++) {
        for (const Rule& rule : g.rules) {
            if (rule.head == a && rule.body.size() == 2 && table.cell[i][k].count(rule.body[0]) > 0 &&
                table.cell[k + 1][j].count(rule.body[1]) > 0) {
                Tree left = cyk_subtree(g, table, w, rule.body[0], i, k);
                Tree right = cyk_subtree(g, table, w, rule.body[1], k + 1, j);
                return Tree{a, {left, right}};
            }
        }
    }
    throw std::runtime_error(a + " no está en esa celda de la tabla");
}

// Un árbol de derivación de w. Requiere que la gramática genere w.
inline Tree cyk_tree(const Cfg& g, const CykTable& table, const std::string& w) {
    if (!cyk_accepts(g, table)) {
        throw std::runtime_error("la gramática no genera la cadena");
    }
    if (w.empty()) {
        return Tree{g.start, {Tree{"ε", {}}}};
    }
    return cyk_subtree(g, table, w, g.start, 0, w.size() - 1);
}

// Imprime la tabla: la fila i y la columna j tienen las variables que generan w[i..j].
inline void print_cyk_table(std::ostream& out, const Cfg& g, const CykTable& table, const std::string& w) {
    std::size_t n = table.n;
    std::vector<std::vector<std::string>> text(n, std::vector<std::string>(n));
    std::size_t width = 5;
    for (std::size_t i = 0; i < n; i++) {
        for (std::size_t j = i; j < n; j++) {
            // Las variables en el orden de la gramática, no en orden alfabético.
            for (const std::string& name : g.variables) {
                if (table.cell[i][j].count(name) > 0) {
                    text[i][j] += (text[i][j].empty() ? "" : ",") + name;
                }
            }
            text[i][j] = text[i][j].empty() ? "∅" : "{" + text[i][j] + "}";
            // El símbolo ∅ ocupa tres bytes y una sola columna.
            std::size_t shown = text[i][j] == "∅" ? 1 : text[i][j].size();
            width = std::max(width, shown + 2);
        }
    }
    auto padded = [width](const std::string& s, std::size_t shown) { return s + std::string(width - shown, ' '); };
    // Cada línea se arma completa y se le quitan los espacios del final.
    auto emit = [&out](std::string line) {
        while (!line.empty() && line.back() == ' ') {
            line.pop_back();
        }
        out << line << '\n';
    };
    std::string line = "       ";
    for (std::size_t j = 0; j < n; j++) {
        std::string header = "j=" + std::to_string(j) + " " + w[j];
        line += padded(header, header.size());
    }
    emit(line);
    for (std::size_t i = 0; i < n; i++) {
        std::string number = std::to_string(i);
        line = "i=" + number + std::string(number.size() < 3 ? 3 - number.size() : 0, ' ') + w[i] + " ";
        for (std::size_t j = 0; j < n; j++) {
            if (j < i) {
                line += padded("", 0);
            } else {
                line += padded(text[i][j], text[i][j] == "∅" ? 1 : text[i][j].size());
            }
        }
        emit(line);
    }
}

// Cuántos árboles de derivación tiene w con raíz en la variable inicial. Es la misma tabla,
// con un número por variable en lugar de un sí o no: los árboles de A para w[i..j] son, sumando
// sobre las reglas A → BC y los cortes k, (árboles de B para w[i..k]) × (árboles de C para w[k+1..j]).
// El resultado se satura en MANY_TREES para no pasarse del tipo.
inline constexpr unsigned long long MANY_TREES = 1000000000000000000ULL;

inline unsigned long long count_trees(const Cfg& g, const std::string& w) {
    std::string why = why_not_chomsky(g);
    if (!why.empty()) {
        throw std::runtime_error("CYK necesita una gramática en forma normal de Chomsky. " + why);
    }
    std::size_t n = w.size();
    if (n == 0) {
        return cyk_accepts(g, w) ? 1 : 0;
    }
    std::vector<std::vector<std::map<std::string, unsigned long long>>> count(
        n, std::vector<std::map<std::string, unsigned long long>>(n));
    for (std::size_t i = 0; i < n; i++) {
        for (const Rule& rule : g.rules) {
            if (rule.body.size() == 1 && rule.body[0] == std::string(1, w[i])) {
                count[i][i][rule.head] = 1;
            }
        }
    }
    for (std::size_t length = 2; length <= n; length++) {
        for (std::size_t i = 0; i + length <= n; i++) {
            std::size_t j = i + length - 1;
            for (std::size_t k = i; k < j; k++) {
                for (const Rule& rule : g.rules) {
                    if (rule.body.size() != 2) {
                        continue;
                    }
                    auto left = count[i][k].find(rule.body[0]);
                    auto right = count[k + 1][j].find(rule.body[1]);
                    if (left == count[i][k].end() || right == count[k + 1][j].end()) {
                        continue;
                    }
                    unsigned long long& total = count[i][j][rule.head];
                    // left->second y right->second son a lo sumo 10^18, y su producto puede no caber.
                    if (left->second > MANY_TREES / right->second) {
                        total = MANY_TREES;
                    } else {
                        total = std::min(MANY_TREES, total + left->second * right->second);
                    }
                }
            }
        }
    }
    auto top = count[0][n - 1].find(g.start);
    return top == count[0][n - 1].end() ? 0 : top->second;
}

#endif
cyk.cppDescargar cyk.cpp
// CYK con una gramática en forma normal de Chomsky: cyk ARCHIVO.cfg CADENA...
// Con - en lugar del archivo, lee la gramática de la entrada estándar (por ejemplo, la
// salida de to_chomsky). Imprime la tabla, la respuesta y, si la cadena se genera, un árbol.
// La cadena vacía se pasa como '' en la terminal.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>

#include "cfg.h"
#include "chomsky.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: cyk ARCHIVO.cfg CADENA...\n";
        return 2;
    }
    try {
        std::string path = argv[1];
        Cfg g = (path == "-") ? read_cfg(std::cin) : load_cfg(path);
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            CykTable table = cyk(g, w);
            std::cout << (i == 2 ? "" : "\n") << "w = " << (w.empty() ? "ε" : w) << ", n = " << w.size() << '\n';
            if (!w.empty()) {
                print_cyk_table(std::cout, g, table, w);
            }
            bool generated = cyk_accepts(g, table);
            if (w.empty()) {
                std::cout << "la cadena vacía no usa la tabla: " << g.start << " → ε "
                          << (generated ? "es una regla" : "no es una regla");
            } else {
                std::cout << g.start << (generated ? " está" : " no está") << " en T[0][" << (w.size() - 1) << "]";
            }
            std::cout << ": " << (generated ? "genera" : "no genera") << "\ncomprobaciones de reglas A → BC: "
                      << table.checks << '\n';
            if (generated) {
                Tree tree = cyk_tree(g, table, w);
                unsigned long long trees = count_trees(g, w);
                std::cout << "árboles de derivación: " << (trees == MANY_TREES ? "al menos " : "") << trees
                          << ". Uno de ellos:\n";
                print_tree(std::cout, tree);
                std::cout << bracket_text(tree) << '\n';
            }
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
derive.cppDescargar derive.cpp
// Lista las derivaciones por la izquierda de una cadena, cada una con su árbol:
//   derive ARCHIVO.cfg CADENA [--pasos N] [--sin-arboles]
// La cadena vacía se pasa como '' en la terminal. --pasos es el tope de pasos de cada
// derivación (40 si no se indica): con reglas ε o unitarias la búsqueda puede no terminar.
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: derive ARCHIVO.cfg CADENA [--pasos N] [--sin-arboles]\n";
        return 2;
    }
    try {
        Cfg g = load_cfg(argv[1]);
        std::string w = argv[2];
        std::size_t max_steps = 40;
        bool trees = true;
        for (int i = 3; i < argc; i++) {
            std::string option = argv[i];
            if (option == "--pasos" && i + 1 < argc) {
                max_steps = std::stoul(argv[++i]);
            } else if (option == "--sin-arboles") {
                trees = false;
            } else {
                throw std::runtime_error("opción desconocida: " + option);
            }
        }
        DerivationSearch search = leftmost_derivations(g, w, max_steps, 20);
        std::cout << "w = " << (w.empty() ? "ε" : w) << "\nderivaciones por la izquierda: " << search.found.size();
        if (!search.complete) {
            std::cout << " (la búsqueda se cortó: derivaciones de hasta " << max_steps << " pasos, 20 como máximo)";
        }
        std::cout << '\n';
        for (std::size_t d = 0; d < search.found.size(); d++) {
            std::cout << '\n' << (d + 1) << ". ";
            std::vector<std::vector<std::string>> forms = sentential_forms(g, search.found[d]);
            for (std::size_t i = 0; i < forms.size(); i++) {
                std::cout << (i == 0 ? "" : " ⇒ ") << form_text(g, forms[i]);
            }
            std::cout << "\n   " << search.found[d].size() << " pasos\n";
            if (trees) {
                print_tree(std::cout, tree_of(g, search.found[d]), "   ", "   ");
            }
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
predicates.hDescargar predicates.h
// Los lenguajes del capítulo, cada uno como una función de C++ que decide mirando la cadena,
// sin usar ninguna gramática. Las pruebas comparan cada gramática con su función.
#ifndef PREDICATES_H
#define PREDICATES_H

#include <algorithm>
#include <cstddef>
#include <string>

inline std::size_t count_of(const std::string& w, char c) {
    return static_cast<std::size_t>(std::count(w.begin(), w.end(), c));
}

// w = x^i y^j z^k, con las tres letras en ese orden. Devuelve false si w no tiene esa forma.
inline bool three_blocks(const std::string& w, char x, char y, char z, std::size_t& i, std::size_t& j,
                         std::size_t& k) {
    std::size_t p = 0;
    i = j = k = 0;
    while (p < w.size() && w[p] == x) {
        p++;
        i++;
    }
    while (p < w.size() && w[p] == y) {
        p++;
        j++;
    }
    while (p < w.size() && w[p] == z) {
        p++;
        k++;
    }
    return p == w.size();
}

// { 0^n 1^n : n ≥ 0 }
inline bool is_zeros_ones(const std::string& w) {
    std::size_t half = w.size() / 2;
    return w.size() % 2 == 0 && w == std::string(half, '0') + std::string(half, '1');
}

inline bool is_palindrome(const std::string& w) {
    return std::equal(w.begin(), w.end(), w.rbegin());
}

// Paréntesis balanceados: ningún prefijo cierra más de lo que abrió, y al final no queda nada abierto.
inline bool is_balanced(const std::string& w) {
    long open = 0;
    for (char c : w) {
        open += (c == '(') ? 1 : -1;
        if (open < 0) {
            return false;
        }
    }
    return open == 0;
}

inline bool has_equal_ab(const std::string& w) {
    return count_of(w, 'a') == count_of(w, 'b');
}

inline bool has_even_ones(const std::string& w) {
    return count_of(w, '1') % 2 == 0;
}

// Una lista de bloques 0^n 1^n con n ≥ 1, uno detrás de otro. La lista puede ser vacía.
inline bool is_block_list(const std::string& w) {
    std::size_t p = 0;
    while (p < w.size()) {
        std::size_t zeros = 0;
        while (p < w.size() && w[p] == '0') {
            p++;
            zeros++;
        }
        std::size_t ones = 0;
        while (p < w.size() && w[p] == '1') {
            p++;
            ones++;
        }
        if (zeros == 0 || zeros != ones) {
            return false;
        }
    }
    return true;
}

// { a^i b^j c^k : i = j o j = k }
inline bool is_abc_union(const std::string& w) {
    std::size_t i = 0, j = 0, k = 0;
    return three_blocks(w, 'a', 'b', 'c', i, j, k) && (i == j || j == k);
}

// Expresiones con a, +, *, ( y ). Se lee de izquierda a derecha sabiendo si toca un operando
// o un operador: un operando es a o un paréntesis que abre; después de un operando viene un
// operador, un paréntesis que cierra o el final.
inline bool is_expression(const std::string& w) {
    bool operand_next = true;
    long open = 0;
    for (char c : w) {
        if (c == 'a') {
            if (!operand_next) {
                return false;
            }
            operand_next = false;
        } else if (c == '(') {
            if (!operand_next) {
                return false;
            }
            open++;
        } else if (c == ')') {
            if (operand_next || open == 0) {
                return false;
            }
            open--;
        } else {  // + o *
            if (operand_next) {
                return false;
            }
            operand_next = true;
        }
    }
    return !operand_next && open == 0;
}

// Instrucciones con if y else, donde i es "if condición then", e es "else" y a es una
// instrucción simple. La cadena tiene la forma (i…i a e)…(i…i a e) i…i a, y cada e
// necesita un i anterior que todavía no tenga su else.
inline bool is_if_else(const std::string& w) {
    long free_ifs = 0;
    char previous = 'e';  // como si antes hubiera un else: lo primero es i o a
    for (char c : w) {
        if (c == 'i' || c == 'a') {
            if (previous == 'a') {
                return false;
            }
            free_ifs += (c == 'i') ? 1 : 0;
        } else {  // e
            if (previous != 'a' || free_ifs == 0) {
                return false;
            }
            free_ifs--;
        }
        previous = c;
    }
    return previous == 'a';
}

#endif
search_cost.cppDescargar search_cost.cpp
// Compara dos maneras de decidir si una gramática en forma normal de Chomsky genera una cadena:
// probar derivaciones por la izquierda con backtracking, y CYK.
//   search_cost ARCHIVO.cfg CADENA...
// Cuenta trabajo, no tiempo: pasos de derivación probados contra comprobaciones de CYK.
#include <cstddef>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>

#include "cfg.h"
#include "chomsky.h"

int main(int argc, char** argv) {
    if (argc < 3) {
        std::cerr << "uso: search_cost ARCHIVO.cfg CADENA...\n";
        return 2;
    }
    try {
        std::string path = argv[1];
        Cfg g = (path == "-") ? read_cfg(std::cin) : load_cfg(path);
        std::cout << "  n   respuesta    pasos probados   comprobaciones de CYK   cadena\n";
        for (int i = 2; i < argc; i++) {
            std::string w = argv[i];
            CykTable table = cyk(g, w);
            // En forma normal de Chomsky una derivación de w tiene 2|w| − 1 pasos: ese tope no corta nada.
            // La búsqueda para en la primera derivación que encuentra. Si la cadena no se genera, las agota todas.
            DerivationSearch search = leftmost_derivations(g, w, 2 * w.size() + 1, 1);
            bool generated = cyk_accepts(g, table);
            if (generated != !search.found.empty()) {
                throw std::runtime_error("las dos búsquedas no coinciden");
            }
            std::cout << std::setw(3) << w.size() << "   " << std::left << std::setw(13)
                      << (generated ? "genera" : "no genera") << std::right << std::setw(14) << search.explored
                      << std::setw(24) << table.checks << "   " << (w.empty() ? "ε" : w) << '\n';
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
show_cfg.cppDescargar show_cfg.cpp
// Muestra una gramática como cuádrupla y lista las cadenas más cortas que genera:
//   show_cfg ARCHIVO.cfg [LONGITUD]
// Sin LONGITUD, lista las cadenas de hasta 6 símbolos.
#include <cstddef>
#include <iostream>
#include <set>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"

int main(int argc, char** argv) {
    if (argc < 2 || argc > 3) {
        std::cerr << "uso: show_cfg ARCHIVO.cfg [LONGITUD]\n";
        return 2;
    }
    try {
        Cfg g = load_cfg(argv[1]);
        std::size_t max_length = (argc == 3) ? std::stoul(argv[2]) : 6;
        std::cout << "G = (V, Σ, R, S)\n  V = {";
        for (std::size_t i = 0; i < g.variables.size(); i++) {
            std::cout << (i == 0 ? "" : ", ") << g.variables[i];
        }
        std::cout << "}\n  Σ = {";
        for (std::size_t i = 0; i < g.terminals.size(); i++) {
            std::cout << (i == 0 ? "" : ", ") << g.terminals[i];
        }
        std::cout << "}\n  S = " << g.start << "\n  R tiene " << g.rules.size() << " reglas:\n";
        for (const Rule& rule : g.rules) {
            std::cout << "    " << rule.head << " → " << form_text(g, rule.body) << '\n';
        }
        std::vector<std::string> words = shortest_first(generated_strings(g, max_length));
        std::cout << "Cadenas de L(G) con longitud a lo sumo " << max_length << " (" << words.size() << "):\n ";
        for (const std::string& w : words) {
            std::cout << ' ' << (w.empty() ? "ε" : w);
        }
        std::cout << '\n';
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
to_chomsky.cppDescargar to_chomsky.cpp
// Convierte una gramática a forma normal de Chomsky:
//   to_chomsky ARCHIVO.cfg                        escribe el resultado en formato .cfg
//   to_chomsky ARCHIVO.cfg --pasos                muestra la gramática después de cada paso
//   to_chomsky ARCHIVO.cfg --unitarias-primero    el orden equivocado: paso 3 antes que el paso 2
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <string>

#include "cfg.h"
#include "chomsky.h"

// Las reglas de g, una línea por variable, como en el archivo pero sin el encabezado.
static void print_rules(const Cfg& g) {
    for (const std::string& name : g.variables) {
        std::string line;
        for (const Rule& rule : g.rules) {
            if (rule.head == name) {
                line += (line.empty() ? name + " -> " : " | ") + body_text(rule.body);
            }
        }
        if (!line.empty()) {
            std::cout << "  " << line << '\n';
        }
    }
}

static void report(const std::string& title, const Cfg& g) {
    std::cout << title << " (" << g.rules.size() << " reglas)\n";
    print_rules(g);
}

int main(int argc, char** argv) {
    if (argc < 2 || argc > 3) {
        std::cerr << "uso: to_chomsky ARCHIVO.cfg [--pasos | --unitarias-primero]\n";
        return 2;
    }
    try {
        Cfg g = load_cfg(argv[1]);
        std::string option = (argc == 3) ? argv[2] : "";
        if (option.empty()) {
            std::cout << "# " << argv[1] << " en forma normal de Chomsky.\n";
            write_cfg(std::cout, to_chomsky(g));
            return 0;
        }
        if (option != "--pasos" && option != "--unitarias-primero") {
            throw std::runtime_error("opción desconocida: " + option);
        }
        report("La gramática original", g);
        Cfg result = with_new_start(g);
        report("\nPaso 1: variable inicial nueva", result);
        if (option == "--pasos") {
            result = without_epsilon_rules(result);
            report("\nPaso 2: sin reglas ε", result);
            result = without_unit_rules(result);
            report("\nPaso 3: sin reglas unitarias", result);
        } else {
            result = without_unit_rules(result);
            report("\nPaso 3 antes de tiempo: sin reglas unitarias", result);
            result = without_epsilon_rules(result);
            report("\nPaso 2, tarde: sin reglas ε", result);
        }
        result = with_short_rules(result);
        report("\nPaso 4: reglas de a lo sumo dos símbolos, y terminales solos", result);
        std::string why = why_not_chomsky(result);
        if (why.empty()) {
            std::cout << "\nEstá en forma normal de Chomsky.\n";
        } else {
            std::cout << "\nNo está en forma normal de Chomsky. " << why << ".\n";
        }
    } catch (const std::exception& error) {
        std::cerr << "error: " << error.what() << '\n';
        return 1;
    }
}
machines/abc_union.cfgDescargar machines/abc_union.cfg
# { a^i b^j c^k : i = j o j = k }, como unión de dos gramáticas. Es ambigua.
variables: S X C A Y
terminals: a b c
start: S
rules:
S -> X C | A Y
X -> a X b | eps
C -> c C | eps
A -> a A | eps
Y -> b Y c | eps
machines/blocks.cfgDescargar machines/blocks.cfg
# Una lista de bloques, cada uno de la forma 0^n 1^n con n >= 1. Ejemplo de la conversión.
variables: S B
terminals: 0 1
start: S
rules:
S -> B S | eps
B -> 0 B 1 | 0 1
machines/dangling_else_fixed.cfgDescargar machines/dangling_else_fixed.cfg
# El else colgante resuelto: cada else va con el if libre más cercano.
# M genera instrucciones donde todo if tiene su else; U, las que tienen algún if sin else.
variables: S M U
terminals: i e a
start: S
rules:
S -> M | U
M -> i M e M | a
U -> i S | i M e U
machines/dangling_else.cfgDescargar machines/dangling_else.cfg
# El else colgante. i es "if condición then", e es "else", a es cualquier otra instrucción.
variables: S
terminals: i e a
start: S
rules:
S -> i S | i S e S | a
machines/equal_ab.cfgDescargar machines/equal_ab.cfg
# Cadenas con igual número de a y de b.
variables: S
terminals: a b
start: S
rules:
S -> a S b | b S a | S S | eps
machines/even_ones.cfgDescargar machines/even_ones.cfg
# Cantidad par de unos, a partir del DFA de la semana 1: una variable por estado.
variables: P I
terminals: 0 1
start: P
rules:
P -> 0 P | 1 I | eps
I -> 0 I | 1 P
machines/expr_ambiguous_chomsky.cfgDescargar machines/expr_ambiguous_chomsky.cfg
# machines/expr_ambiguous.cfg en forma normal de Chomsky.
variables: E0 E E0_1 E0_2 E0_3 E_1 E_2 E_3 U_+ U_* U_( U_)
terminals: a + * ( )
start: E0
rules:
E0 -> E E0_1 | E E0_2 | U_( E0_3 | a
E -> E E_1 | E E_2 | U_( E_3 | a
E0_1 -> U_+ E
E0_2 -> U_* E
E0_3 -> E U_)
E_1 -> U_+ E
E_2 -> U_* E
E_3 -> E U_)
U_+ -> +
U_* -> *
U_( -> (
U_) -> )
machines/expr_ambiguous.cfgDescargar machines/expr_ambiguous.cfg
# Expresiones aritméticas con sumas, productos y paréntesis. Es ambigua.
# El símbolo * es el producto: un terminal es un solo carácter.
variables: E
terminals: a + * ( )
start: E
rules:
E -> E + E | E * E | ( E ) | a
machines/expr_precedence.cfgDescargar machines/expr_precedence.cfg
# Expresiones aritméticas con un nivel por operador: E suma términos, T multiplica factores.
# Genera el mismo lenguaje que expr_ambiguous.cfg y no es ambigua.
variables: E T F
terminals: a + * ( )
start: E
rules:
E -> E + T | T
T -> T * F | F
F -> ( E ) | a
machines/palindromes.cfgDescargar machines/palindromes.cfg
# Palíndromos sobre {a, b}: las cadenas que se leen igual al derecho y al revés.
variables: S
terminals: a b
start: S
rules:
S -> a S a | b S b | a | b | eps
machines/parens_ss.cfgDescargar machines/parens_ss.cfg
# Paréntesis balanceados, con la regla S -> S S. Es ambigua.
variables: S
terminals: ( )
start: S
rules:
S -> S S | ( S ) | eps
machines/parens.cfgDescargar machines/parens.cfg
# Paréntesis balanceados.
variables: S
terminals: ( )
start: S
rules:
S -> ( S ) S | eps
machines/two_derivations.cfgDescargar machines/two_derivations.cfg
# La cadena ab tiene dos derivaciones y un solo árbol: la gramática no es ambigua.
variables: S A B
terminals: a b
start: S
rules:
S -> A B
A -> a
B -> b
machines/unit_order.cfgDescargar machines/unit_order.cfg
# Para ver por qué las reglas ε se quitan antes que las unitarias.
variables: S A B
terminals: a b
start: S
rules:
S -> A B | a
A -> a | eps
B -> b
machines/zeros_ones.cfgDescargar machines/zeros_ones.cfg
# { 0^n 1^n : n >= 0 }
variables: S
terminals: 0 1
start: S
rules:
S -> 0 S 1 | eps

Errores

Ejemplos con errores a propósito: no compilan, fallan o dan un resultado incorrecto. Los apuntes explican cada uno.

errors/glued_symbols.cfgDescargar errors/glued_symbols.cfg
# Los símbolos de una alternativa van separados por espacios: aSb es un solo nombre desconocido.
variables: S
terminals: a b
start: S
rules:
S -> aSb | eps
errors/start_not_variable.cfgDescargar errors/start_not_variable.cfg
# La variable inicial no está en V.
variables: A B
terminals: a
start: S
rules:
A -> a B | eps
B -> a A
errors/unknown_symbol.cfgDescargar errors/unknown_symbol.cfg
# El lado derecho usa c, que no es variable ni terminal.
variables: S
terminals: a b
start: S
rules:
S -> a S b | c

Pruebas

Comprueban lo que afirman los apuntes; se ejecutan con make test.

test_ambiguity.cppDescargar test_ambiguity.cpp
// Pruebas de derivaciones, árboles y ambigüedad (sesión A).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <set>
#include <string>
#include <vector>

#include "cfg.h"

static std::size_t count_leftmost(const Cfg& g, const std::string& w) {
    DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
    assert(search.complete);
    return search.found.size();
}

// Cada derivación por la izquierda da un árbol de derivación de w, con tantos nodos internos
// como pasos, y dos derivaciones por la izquierda distintas dan árboles distintos.
static void check_trees(const Cfg& g, const std::string& w) {
    DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
    assert(search.complete);
    std::set<std::string> seen;
    for (const Derivation& derivation : search.found) {
        Tree tree = tree_of(g, derivation);
        assert(is_parse_tree(g, tree));
        assert(yield_of(tree) == w);
        assert(count_inner(tree) == derivation.size());
        assert(seen.insert(bracket_text(tree)).second);
    }
}

// Toda cadena de L(G) hasta max_length tiene exactamente una derivación por la izquierda.
// No demuestra que la gramática no sea ambigua, pero una cadena corta con dos árboles la delataría.
static std::size_t check_one_tree_each(const Cfg& g, std::size_t max_length) {
    std::set<std::string> generated = generated_strings(g, max_length);
    for (const std::string& w : generated) {
        assert(count_leftmost(g, w) == 1);
    }
    return generated.size();
}

static void test_expressions() {
    Cfg ambiguous = load_cfg("machines/expr_ambiguous.cfg");
    Cfg levels = load_cfg("machines/expr_precedence.cfg");
    // El ejemplo de los apuntes: dos derivaciones por la izquierda contra una.
    assert(count_leftmost(ambiguous, "a+a*a") == 2);
    assert(count_leftmost(levels, "a+a*a") == 1);
    check_trees(ambiguous, "a+a*a");
    check_trees(levels, "a+a*a");
    // Los dos árboles de la gramática ambigua, y las dos derivaciones como salen en los apuntes.
    DerivationSearch search = leftmost_derivations(ambiguous, "a+a*a", 1000);
    assert(bracket_text(tree_of(ambiguous, search.found[0])) == "[E [E a] + [E [E a] * [E a]]]");
    assert(bracket_text(tree_of(ambiguous, search.found[1])) == "[E [E [E a] + [E a]] * [E a]]");
    // El árbol de la gramática con niveles agrupa el producto: a + (a * a).
    search = leftmost_derivations(levels, "a+a*a", 1000);
    assert(search.found[0].size() == 8);
    assert(bracket_text(tree_of(levels, search.found[0])) == "[E [E [T [F a]]] + [T [T [F a]] * [F a]]]");
    // La ambigüedad también aparece con un solo operador: (a+a)+a y a+(a+a).
    assert(count_leftmost(ambiguous, "a+a+a") == 2);
    assert(count_leftmost(ambiguous, "a+a+a+a") == 5);
    assert(count_leftmost(levels, "a+a+a+a") == 1);
    // Las dos gramáticas generan el mismo lenguaje, y en la de niveles cada cadena tiene un solo árbol.
    assert(generated_strings(ambiguous, 7) == generated_strings(levels, 7));
    check_one_tree_each(levels, 7);
}

static void test_dangling_else() {
    Cfg dangling = load_cfg("machines/dangling_else.cfg");
    Cfg fixed = load_cfg("machines/dangling_else_fixed.cfg");
    assert(count_leftmost(dangling, "iiaea") == 2);
    assert(count_leftmost(fixed, "iiaea") == 1);
    check_trees(dangling, "iiaea");
    // En la gramática corregida el else queda con el if de adentro.
    DerivationSearch search = leftmost_derivations(fixed, "iiaea", 1000);
    assert(bracket_text(tree_of(fixed, search.found[0])) == "[S [U i [S [M i [M a] e [M a]]]]]");
    assert(generated_strings(dangling, 10) == generated_strings(fixed, 10));
    check_one_tree_each(fixed, 10);
}

static void test_two_derivations_one_tree() {
    Cfg g = load_cfg("machines/two_derivations.cfg");
    assert(count_leftmost(g, "ab") == 1);
    check_trees(g, "ab");
}

static void test_union() {
    Cfg g = load_cfg("machines/abc_union.cfg");
    // Dos árboles exactamente cuando i = j = k. El caso i = j = k = 0 es ε, que también tiene dos.
    for (const std::string& w : generated_strings(g, 9)) {
        std::size_t a = 0, b = 0, c = 0;
        for (char x : w) {
            a += (x == 'a');
            b += (x == 'b');
            c += (x == 'c');
        }
        assert(count_leftmost(g, w) == ((a == b && b == c) ? 2u : 1u));
    }
}

static void test_other_grammars() {
    // Gramáticas del capítulo en las que cada cadena tiene un solo árbol.
    check_one_tree_each(load_cfg("machines/zeros_ones.cfg"), 12);
    check_one_tree_each(load_cfg("machines/palindromes.cfg"), 10);
    check_one_tree_each(load_cfg("machines/parens.cfg"), 12);
    check_one_tree_each(load_cfg("machines/even_ones.cfg"), 9);
    check_one_tree_each(load_cfg("machines/blocks.cfg"), 12);
    // Con S → SS, la cadena ()()() ya tiene más de un árbol aunque se limite la búsqueda.
    Cfg ss = load_cfg("machines/parens_ss.cfg");
    assert(leftmost_derivations(ss, "()()()", 12, 100000).found.size() >= 2);
}

int main() {
    test_expressions();
    test_dangling_else();
    test_two_derivations_one_tree();
    test_union();
    test_other_grammars();
    std::printf("test_ambiguity: ok\n");
}
test_cfg.cppDescargar test_cfg.cpp
// Pruebas de la sesión A: el formato .cfg, y que cada gramática de machines/ genera exactamente
// su lenguaje. Para cada una se comparan todas las cadenas hasta una longitud con una función
// de predicates.h que decide el mismo lenguaje sin usar la gramática.
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"
#include "predicates.h"

static bool throws(const std::function<void()>& action) {
    try {
        action();
    } catch (const std::runtime_error&) {
        return true;
    }
    return false;
}

// L(G) y el predicado coinciden en todas las cadenas de longitud a lo sumo max_length.
// Devuelve cuántas cadenas se revisaron.
static std::size_t check_language(const std::string& path, std::size_t max_length,
                                  const std::function<bool(const std::string&)>& in_language) {
    Cfg g = load_cfg(path);
    std::set<std::string> generated = generated_strings(g, max_length);
    std::vector<std::string> words = all_strings(g.terminals, max_length);
    for (const std::string& w : words) {
        assert((generated.count(w) > 0) == in_language(w));
    }
    return words.size();
}

static void test_format() {
    // El ejemplo de code/formats.md.
    Cfg g = load_cfg("machines/parens.cfg");
    assert(g.variables == std::vector<std::string>{"S"});
    assert((g.terminals == std::vector<char>{'(', ')'}));
    assert(g.start == "S");
    assert(g.rules.size() == 2);
    assert((g.rules[0] == Rule{"S", {"(", "S", ")", "S"}}));
    assert((g.rules[1] == Rule{"S", {}}));

    // Lo que se escribe se vuelve a leer igual.
    for (const char* path : {"machines/expr_precedence.cfg", "machines/abc_union.cfg", "machines/blocks.cfg"}) {
        Cfg original = load_cfg(path);
        std::ostringstream text;
        write_cfg(text, original);
        std::istringstream again(text.str());
        Cfg copy = read_cfg(again);
        assert(copy.variables == original.variables && copy.terminals == original.terminals);
        assert(copy.start == original.start && copy.rules == original.rules);
    }

    // Una variable puede tener varias líneas, y una regla repetida cuenta una vez.
    std::istringstream lines("variables: S\nterminals: a\nstart: S\nrules:\nS -> a S\n# comentario\nS -> eps | a S\n");
    Cfg joined = read_cfg(lines);
    assert(joined.rules.size() == 2);

    // Las tres descripciones de errors/ no son gramáticas.
    assert(throws([] { load_cfg("errors/unknown_symbol.cfg"); }));
    assert(throws([] { load_cfg("errors/start_not_variable.cfg"); }));
    assert(throws([] { load_cfg("errors/glued_symbols.cfg"); }));
    std::istringstream empty_alternative("variables: S\nterminals: a\nstart: S\nrules:\nS -> a |\n");
    assert(throws([&] { read_cfg(empty_alternative); }));
}

static std::size_t test_languages() {
    std::size_t total = 0;
    total += check_language("machines/zeros_ones.cfg", 12, is_zeros_ones);
    total += check_language("machines/palindromes.cfg", 12, is_palindrome);
    total += check_language("machines/parens.cfg", 12, is_balanced);
    total += check_language("machines/parens_ss.cfg", 12, is_balanced);
    total += check_language("machines/equal_ab.cfg", 10, has_equal_ab);
    total += check_language("machines/even_ones.cfg", 10, has_even_ones);
    total += check_language("machines/blocks.cfg", 12, is_block_list);
    total += check_language("machines/abc_union.cfg", 9, is_abc_union);
    total += check_language("machines/expr_ambiguous.cfg", 7, is_expression);
    total += check_language("machines/expr_precedence.cfg", 7, is_expression);
    total += check_language("machines/dangling_else.cfg", 9, is_if_else);
    total += check_language("machines/dangling_else_fixed.cfg", 9, is_if_else);
    return total;
}

// Lo que afirma la demostración de { 0^n 1^n }: la forma después de k pasos es 0^k S 1^k o,
// si ya terminó, 0^(k−1) 1^(k−1). La derivación de 0^n 1^n es una sola y tiene n + 1 pasos.
static void test_zeros_ones_proof() {
    Cfg g = load_cfg("machines/zeros_ones.cfg");
    for (std::size_t n = 0; n <= 8; n++) {
        std::string w = std::string(n, '0') + std::string(n, '1');
        DerivationSearch search = leftmost_derivations(g, w, 100);
        assert(search.complete && search.found.size() == 1);
        assert(search.found[0].size() == n + 1);
        std::vector<std::vector<std::string>> forms = sentential_forms(g, search.found[0]);
        for (std::size_t k = 0; k < forms.size(); k++) {
            std::string text = form_text(g, forms[k]);
            if (k <= n) {
                assert(text == std::string(k, '0') + "S" + std::string(k, '1'));
            } else {
                assert(n == 0 ? text == "ε" : text == w);
            }
        }
    }
}

// La búsqueda de derivaciones por la izquierda y el cálculo de L(G) hasta una longitud
// responden lo mismo. Solo con gramáticas donde la búsqueda termina sola.
static void test_search_agrees() {
    struct Case {
        const char* path;
        std::size_t max_length;
    };
    for (const Case& c : {Case{"machines/zeros_ones.cfg", 10}, Case{"machines/palindromes.cfg", 9},
                          Case{"machines/parens.cfg", 10}, Case{"machines/even_ones.cfg", 8},
                          Case{"machines/blocks.cfg", 10}, Case{"machines/expr_precedence.cfg", 5},
                          Case{"machines/dangling_else.cfg", 7}}) {
        Cfg g = load_cfg(c.path);
        std::set<std::string> generated = generated_strings(g, c.max_length);
        for (const std::string& w : all_strings(g.terminals, c.max_length)) {
            DerivationSearch search = leftmost_derivations(g, w, 1000);
            assert(search.complete);
            assert(!search.found.empty() == (generated.count(w) > 0));
        }
    }
}

// Con S → SS y S → ε la búsqueda no termina: S ⇒ SS ⇒ S ⇒ SS ⇒ … Con cualquier tope de pasos se corta.
static void test_search_can_run_forever() {
    Cfg g = load_cfg("machines/parens_ss.cfg");
    for (std::size_t steps : {5, 10, 15}) {
        DerivationSearch search = leftmost_derivations(g, "()", steps, 1000000);
        assert(!search.complete);
    }
    // Y las derivaciones de () son cada vez más al subir el tope.
    assert(leftmost_derivations(g, "()", 4, 1000000).found.size() <
           leftmost_derivations(g, "()", 8, 1000000).found.size());
}

int main() {
    test_format();
    std::size_t total = test_languages();
    test_zeros_ones_proof();
    test_search_agrees();
    test_search_can_run_forever();
    std::printf("test_cfg: ok (12 gramáticas, %zu cadenas comparadas con su predicado)\n", total);
}
test_chomsky.cppDescargar test_chomsky.cpp
// Pruebas de la conversión a forma normal de Chomsky (sesión B).
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#include "cfg.h"
#include "chomsky.h"

// Las reglas de g como texto, para comparar con lo que muestran los apuntes.
static std::set<std::string> rule_set(const Cfg& g) {
    std::set<std::string> rules;
    for (const Rule& rule : g.rules) {
        rules.insert(rule.head + " -> " + body_text(rule.body));
    }
    return rules;
}

static bool has_epsilon_rule(const Cfg& g, bool also_start) {
    for (const Rule& rule : g.rules) {
        if (rule.body.empty() && (also_start || rule.head != g.start)) {
            return true;
        }
    }
    return false;
}

static bool has_unit_rule(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        if (is_unit(g, rule)) {
            return true;
        }
    }
    return false;
}

static bool start_on_right(const Cfg& g) {
    for (const Rule& rule : g.rules) {
        for (const std::string& symbol : rule.body) {
            if (symbol == g.start) {
                return true;
            }
        }
    }
    return false;
}

struct Case {
    const char* path;
    std::size_t max_length;
};

static const std::vector<Case> GRAMMARS = {
    {"machines/zeros_ones.cfg", 12},     {"machines/palindromes.cfg", 10},    {"machines/parens.cfg", 12},
    {"machines/parens_ss.cfg", 10},      {"machines/equal_ab.cfg", 8},        {"machines/even_ones.cfg", 9},
    {"machines/blocks.cfg", 12},         {"machines/abc_union.cfg", 9},       {"machines/expr_ambiguous.cfg", 7},
    {"machines/expr_precedence.cfg", 7}, {"machines/dangling_else.cfg", 9},   {"machines/dangling_else_fixed.cfg", 9},
    {"machines/two_derivations.cfg", 4}, {"machines/unit_order.cfg", 4},
};

// Cada paso conserva el lenguaje y deja lo que promete. Al final, forma normal de Chomsky.
static void test_each_step() {
    for (const Case& c : GRAMMARS) {
        Cfg g = load_cfg(c.path);
        std::set<std::string> language = generated_strings(g, c.max_length);

        Cfg step1 = with_new_start(g);
        assert(generated_strings(step1, c.max_length) == language);
        assert(!start_on_right(step1));

        Cfg step2 = without_epsilon_rules(step1);
        assert(generated_strings(step2, c.max_length) == language);
        assert(!has_epsilon_rule(step2, false) && !start_on_right(step2));
        // La inicial conserva S0 → ε exactamente cuando ε está en el lenguaje.
        assert(has_epsilon_rule(step2, true) == (language.count("") > 0));

        Cfg step3 = without_unit_rules(step2);
        assert(generated_strings(step3, c.max_length) == language);
        assert(!has_unit_rule(step3) && !has_epsilon_rule(step3, false) && !start_on_right(step3));

        Cfg step4 = with_short_rules(step3);
        assert(generated_strings(step4, c.max_length) == language);
        assert(is_chomsky(step4));
        check_cfg(step4);
        assert(rule_set(step4) == rule_set(to_chomsky(g)));

        // Convertir una gramática que ya está en forma normal solo le agrega la variable inicial nueva.
        assert(is_chomsky(to_chomsky(step4)));
    }
}

// El ejemplo completo de los apuntes: machines/blocks.cfg, paso por paso.
static void test_blocks_example() {
    Cfg g = load_cfg("machines/blocks.cfg");
    Cfg step1 = with_new_start(g);
    assert(step1.start == "S0");
    assert((rule_set(step1) ==
            std::set<std::string>{"S0 -> S", "S -> B S", "S -> eps", "B -> 0 B 1", "B -> 0 1"}));
    assert((nullable_variables(step1) == std::set<std::string>{"S0", "S"}));
    Cfg step2 = without_epsilon_rules(step1);
    assert((rule_set(step2) ==
            std::set<std::string>{"S0 -> S", "S0 -> eps", "S -> B S", "S -> B", "B -> 0 B 1", "B -> 0 1"}));
    // Los pares unitarios, además de los (A, A): S0 llega a S y a B, y S llega a B.
    std::set<std::pair<std::string, std::string>> pairs = unit_pairs(step2);
    assert((pairs == std::set<std::pair<std::string, std::string>>{
                         {"S0", "S0"}, {"S", "S"}, {"B", "B"}, {"S0", "S"}, {"S0", "B"}, {"S", "B"}}));
    Cfg step3 = without_unit_rules(step2);
    assert((rule_set(step3) == std::set<std::string>{"S0 -> eps", "S0 -> B S", "S0 -> 0 B 1", "S0 -> 0 1",
                                                     "S -> B S", "S -> 0 B 1", "S -> 0 1", "B -> 0 B 1",
                                                     "B -> 0 1"}));
    Cfg step4 = with_short_rules(step3);
    assert((rule_set(step4) ==
            std::set<std::string>{"S0 -> eps", "S0 -> B S", "S0 -> U_0 S0_1", "S0 -> U_0 U_1", "S -> B S",
                                  "S -> U_0 S_1", "S -> U_0 U_1", "B -> U_0 B_1", "B -> U_0 U_1", "S0_1 -> B U_1",
                                  "S_1 -> B U_1", "B_1 -> B U_1", "U_0 -> 0", "U_1 -> 1"}));
    assert(step4.rules.size() == 14 && step4.variables.size() == 8);
}

// El error común: quitar las unitarias antes que las reglas ε vuelve a crear unitarias.
static void test_wrong_order() {
    Cfg g = load_cfg("machines/unit_order.cfg");
    Cfg wrong = with_short_rules(without_epsilon_rules(without_unit_rules(with_new_start(g))));
    assert(!is_chomsky(wrong));
    assert(has_unit_rule(wrong));
    assert(why_not_chomsky(wrong) == "S0 -> B: es una regla unitaria");
    // El lenguaje sigue siendo el mismo: lo que se pierde es la forma, no la equivalencia.
    assert(generated_strings(wrong, 6) == generated_strings(g, 6));
    assert(is_chomsky(to_chomsky(g)));
    // Lo mismo pasa con el ejemplo completo: S → BS con S anulable deja S → B.
    Cfg blocks = load_cfg("machines/blocks.cfg");
    assert(!is_chomsky(with_short_rules(without_epsilon_rules(without_unit_rules(with_new_start(blocks))))));
}

// Sin el paso 1, la regla ε de la variable inicial puede seguir usándose en medio de una derivación.
static void test_why_new_start() {
    Cfg g = load_cfg("machines/parens_ss.cfg");
    Cfg skipped = with_short_rules(without_unit_rules(without_epsilon_rules(g)));
    assert(generated_strings(skipped, 8) == generated_strings(g, 8));
    assert(!is_chomsky(skipped));
}

// Una regla con k apariciones de variables anulables se convierte en hasta 2^k reglas.
static void test_epsilon_blowup() {
    std::istringstream text("variables: S A\nterminals: a\nstart: S\nrules:\nS -> A A A A A A\nA -> a | eps\n");
    Cfg g = read_cfg(text);
    Cfg step2 = without_epsilon_rules(with_new_start(g));
    std::size_t rules_of_s = 0;
    for (const Rule& rule : step2.rules) {
        rules_of_s += (rule.head == "S");
    }
    // Borrar apariciones distintas de A da el mismo lado derecho: quedan A, AA, …, AAAAAA.
    assert(rules_of_s == 6);
    std::istringstream other(
        "variables: S A B C\nterminals: a\nstart: S\nrules:\nS -> A B C A B C\nA -> a | eps\nB -> a | eps\nC -> a | eps\n");
    Cfg h = read_cfg(other);
    Cfg h2 = without_epsilon_rules(with_new_start(h));
    rules_of_s = 0;
    for (const Rule& rule : h2.rules) {
        rules_of_s += (rule.head == "S");
    }
    // Las subsecuencias no vacías y distintas de ABCABC.
    assert(rules_of_s == 51);
}

// En forma normal de Chomsky, toda derivación de una cadena de longitud n ≥ 1 tiene 2n − 1 pasos.
static std::size_t test_derivation_length() {
    std::size_t checked = 0;
    for (const Case& c : GRAMMARS) {
        Cfg g = to_chomsky(load_cfg(c.path));
        std::size_t max_length = std::string(c.path).find("expr") != std::string::npos ? 5 : 6;
        for (const std::string& w : generated_strings(g, max_length)) {
            DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
            assert(search.complete && !search.found.empty());
            for (const Derivation& derivation : search.found) {
                assert(derivation.size() == (w.empty() ? 1 : 2 * w.size() - 1));
                checked++;
            }
        }
    }
    return checked;
}

int main() {
    test_each_step();
    test_blocks_example();
    test_wrong_order();
    test_why_new_start();
    test_epsilon_blowup();
    std::size_t checked = test_derivation_length();
    std::printf("test_chomsky: ok (14 gramáticas convertidas, %zu derivaciones de 2n − 1 pasos)\n", checked);
}
test_cyk.cppDescargar test_cyk.cpp
// Pruebas de CYK (sesión B): responde lo mismo que las otras dos maneras de saber si una
// gramática genera una cadena, la tabla del ejemplo es la de los apuntes, y el árbol que
// recupera es un árbol de derivación de la cadena.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

#include "cfg.h"
#include "chomsky.h"
#include "predicates.h"

struct Case {
    const char* path;
    std::size_t max_length;
    std::function<bool(const std::string&)> in_language;
};

static std::size_t binary_rules(const Cfg& g) {
    std::size_t total = 0;
    for (const Rule& rule : g.rules) {
        total += (rule.body.size() == 2);
    }
    return total;
}

// Para todas las cadenas hasta una longitud: CYK con la gramática convertida responde lo mismo
// que el predicado y que el cálculo de L(G) con la gramática original.
static std::size_t test_agreement() {
    std::vector<Case> cases = {
        {"machines/zeros_ones.cfg", 9, is_zeros_ones},     {"machines/palindromes.cfg", 8, is_palindrome},
        {"machines/parens.cfg", 9, is_balanced},           {"machines/parens_ss.cfg", 8, is_balanced},
        {"machines/equal_ab.cfg", 8, has_equal_ab},        {"machines/even_ones.cfg", 8, has_even_ones},
        {"machines/blocks.cfg", 9, is_block_list},         {"machines/abc_union.cfg", 6, is_abc_union},
        {"machines/expr_ambiguous.cfg", 5, is_expression}, {"machines/expr_precedence.cfg", 4, is_expression},
        {"machines/dangling_else.cfg", 6, is_if_else},     {"machines/dangling_else_fixed.cfg", 6, is_if_else},
    };
    std::size_t total = 0;
    for (const Case& c : cases) {
        Cfg original = load_cfg(c.path);
        Cfg g = to_chomsky(original);
        std::set<std::string> generated = generated_strings(original, c.max_length);
        for (const std::string& w : all_strings(original.terminals, c.max_length)) {
            CykTable table = cyk(g, w);
            bool answer = cyk_accepts(g, table);
            assert(answer == c.in_language(w));
            assert(answer == (generated.count(w) > 0));
            // El costo: (n³ − n)/6 pares de celdas, por la cantidad de reglas A → BC.
            std::size_t n = w.size();
            assert(static_cast<std::size_t>(table.checks) == (n * n * n - n) / 6 * binary_rules(g));
            if (answer) {
                Tree tree = cyk_tree(g, table, w);
                assert(is_parse_tree(g, tree) && yield_of(tree) == w);
                assert(count_inner(tree) == (n == 0 ? 1 : 2 * n - 1));
                assert(count_trees(g, w) >= 1);
            } else {
                assert(count_trees(g, w) == 0);
            }
            total++;
        }
    }
    return total;
}

static std::string cell_text(const Cfg& g, const CykTable& table, std::size_t i, std::size_t j) {
    std::string text;
    for (const std::string& name : g.variables) {
        if (table.cell[i][j].count(name) > 0) {
            text += (text.empty() ? "" : ",") + name;
        }
    }
    return text;
}

// La tabla de a+a*a con la gramática ambigua convertida, celda por celda, como en los apuntes.
static void test_table_of_the_notes() {
    Cfg g = load_cfg("machines/expr_ambiguous_chomsky.cfg");
    // El archivo guardado es lo que produce la conversión.
    Cfg converted = to_chomsky(load_cfg("machines/expr_ambiguous.cfg"));
    assert(g.variables == converted.variables && g.start == converted.start);
    assert(g.rules.size() == converted.rules.size());
    for (const Rule& rule : converted.rules) {
        assert(std::find(g.rules.begin(), g.rules.end(), rule) != g.rules.end());
    }
    assert(g.variables.size() == 12 && g.rules.size() == 18 && binary_rules(g) == 12);

    std::string w = "a+a*a";
    CykTable table = cyk(g, w);
    std::vector<std::vector<std::string>> expected = {
        {"E0,E", "", "E0,E", "", "E0,E"},
        {"", "U_+", "E0_1,E_1", "", "E0_1,E_1"},
        {"", "", "E0,E", "", "E0,E"},
        {"", "", "", "U_*", "E0_2,E_2"},
        {"", "", "", "", "E0,E"},
    };
    for (std::size_t i = 0; i < 5; i++) {
        for (std::size_t j = i; j < 5; j++) {
            assert(cell_text(g, table, i, j) == expected[i][j]);
        }
    }
    assert(table.checks == 240);
    assert(cyk_accepts(g, table));
    Tree tree = cyk_tree(g, table, w);
    assert(bracket_text(tree) == "[E0 [E a] [E0_1 [U_+ +] [E [E a] [E_2 [U_* *] [E a]]]]]");
    // Dos árboles, como las dos derivaciones por la izquierda de la gramática original.
    assert(count_trees(g, w) == 2);
    assert(leftmost_derivations(g, w, 9, 1000).found.size() == 2);
    assert(count_trees(to_chomsky(load_cfg("machines/expr_precedence.cfg")), w) == 1);
    // a+a+a+a tiene 5 árboles: los números de Catalan.
    assert(count_trees(g, "a+a+a+a") == 5);
    assert(count_trees(g, "a+a+a+a+a") == 14);
    assert(!cyk_accepts(g, "a+"));
    assert(!cyk_accepts(g, ""));
}

// El conteo de árboles de CYK coincide con el número de derivaciones por la izquierda.
static void test_tree_counts() {
    for (const char* path : {"machines/parens_ss.cfg", "machines/equal_ab.cfg", "machines/abc_union.cfg",
                             "machines/dangling_else.cfg"}) {
        Cfg g = to_chomsky(load_cfg(path));
        for (const std::string& w : generated_strings(g, 6)) {
            DerivationSearch search = leftmost_derivations(g, w, 1000, 100000);
            assert(search.complete);
            assert(count_trees(g, w) == search.found.size());
        }
    }
}

static void test_edge_cases() {
    // CYK rechaza una gramática que no está en forma normal de Chomsky.
    Cfg parens = load_cfg("machines/parens.cfg");
    bool thrown = false;
    try {
        cyk(parens, "()");
    } catch (const std::runtime_error&) {
        thrown = true;
    }
    assert(thrown);
    // La cadena vacía: depende solo de la regla S0 → ε.
    assert(cyk_accepts(to_chomsky(parens), ""));
    assert(!cyk_accepts(to_chomsky(load_cfg("machines/two_derivations.cfg")), ""));
    // Una gramática que no genera nada: B no termina nunca. Y C no tiene reglas.
    std::istringstream text("variables: S A B C\nterminals: a\nstart: S\nrules:\nS -> A B | A C\nA -> a\nB -> B B\n");
    Cfg nothing = read_cfg(text);
    assert(is_chomsky(nothing));
    assert(generated_strings(nothing, 8).empty());
    for (const std::string& w : all_strings(nothing.terminals, 8)) {
        assert(!cyk_accepts(nothing, w));
    }
}

int main() {
    std::size_t total = test_agreement();
    test_table_of_the_notes();
    test_tree_counts();
    test_edge_cases();
    std::printf("test_cyk: ok (12 gramáticas, %zu cadenas)\n", total);
}

Laboratorio

Archivos de partida del laboratorio de la semana.

lab/cyk_parser/MakefileDescargar lab/cyk_parser/Makefile
TIEMPO = 2
VERIFICADOR = verificador.cpp
include ../../../lab.mk
lab/cyk_parser/README.mdDescargar lab/cyk_parser/README.md
# Un parser con CYK

Un parser recibe una gramática y una cadena, decide si la gramática genera la cadena y, cuando la genera,
muestra **cómo**: un árbol de derivación. En este laboratorio escriben uno con el algoritmo CYK, que funciona
con cualquier gramática libre de contexto (CFG) que esté en forma normal de Chomsky.

Una gramática $G = (V, \Sigma, R, S)$ está en forma normal de Chomsky si cada regla es de una de estas formas:

- $A \to BC$, donde $B$ y $C$ son variables y ninguna es la variable inicial;
- $A \to a$, donde $a$ es un terminal;
- $S \to \varepsilon$, solo para la variable inicial $S$.

## Entrada

Una gramática en forma normal de Chomsky, en el formato `.cfg` de [`code/formats.md`](../../../formats.md),
seguida del bloque de cadenas del mismo documento:

```text
# { a^n b^n : n >= 0 } en forma normal de Chomsky.
variables: S0 S T A B
terminals: a b
start: S0
rules:
S0 -> A T | A B | eps
S -> A T | A B
T -> S B
A -> a
B -> b
strings: 4
aabb

aab
ab
```

- Una línea que empieza con `#` es un comentario. Puede haber comentarios en cualquier línea anterior a
  `strings:`, también entre las reglas.
- Puede haber líneas vacías antes de `rules:`. Entre `rules:` y `strings:` no hay líneas vacías.
- `variables:`, `terminals:`, `start:` y `rules:` vienen siempre en ese orden.
- Después de `rules:`, cada línea es `variable -> alternativa | alternativa…`. Una alternativa es `eps`, un
  terminal, o dos variables separadas por un espacio. Una variable puede tener varias líneas, y una regla
  puede estar repetida.
- Una variable puede no tener ninguna regla, y un terminal puede no aparecer en ninguna regla.
- `strings: k` dice cuántas cadenas siguen, una por línea. **Una línea vacía es la cadena vacía
  $\varepsilon$.** Después de `strings:` ya no hay comentarios.

## Salida

Por cada cadena, en el mismo orden:

- si la gramática no la genera, una línea con `no genera`;
- si la genera, una línea con `genera` y, en la línea siguiente, un árbol de derivación de la cadena.

El árbol se escribe en una línea. Un nodo con la variable $A$ es `[A hijo hijo]`, con un espacio antes de cada
hijo. Un hijo es otro nodo o, si es una hoja, el terminal. El árbol de la cadena vacía es `[S eps]`, con el
nombre de la variable inicial.

Para la entrada de arriba, una salida correcta es:

```text
genera
[S0 [A a] [T [S [A a] [B b]] [B b]]]
genera
[S0 eps]
no genera
genera
[S0 [A a] [B b]]
```

El primer árbol dice que $S_0 \to AT$, que $A \to \mathtt{a}$, que $T \to SB$, y así hasta las hojas, que leídas
de izquierda a derecha dan $\mathtt{aabb}$:

```text
S0
├── A
│   └── a
└── T
    ├── S
    │   ├── A
    │   │   └── a
    │   └── B
    │       └── b
    └── B
        └── b
```

**Una cadena puede tener varios árboles**, y cualquiera de ellos es una respuesta correcta. Por eso el juez no
compara su salida con `casos/NN.out` como texto. Usa un verificador, `verificador.cpp`, que comprueba tres cosas
de cada árbol: que la raíz es la variable inicial, que cada nodo con sus hijos es una regla de la gramática, y
que las hojas forman la cadena. Pueden leerlo, y `casos/NN.out` trae un árbol posible para cada cadena.

## Límites

- $1 \leq |V| \leq 30$ y $1 \leq |\Sigma| \leq 20$. La gramática tiene a lo sumo 100 reglas, contando cada
  alternativa como una regla.
- El nombre de una variable tiene entre 1 y 10 caracteres visibles, sin espacios. No empieza con `#`, no
  termina con `:`, no contiene `[` ni `]`, y no es `eps`, `->` ni `|`. Un nombre puede ser prefijo de otro (`X`
  y `X1`). Hay variables que se llaman `genera` y `no`.
- Un terminal es un solo carácter visible, distinto de `#`, `[`, `]` y `|`. Ningún terminal es a la vez el
  nombre de una variable.
- $1 \leq k \leq 100$. Cada cadena tiene a lo sumo 100 símbolos, y las longitudes suman a lo sumo 500.
- Todas las cadenas están formadas solo por terminales de `terminals:`.
- La entrada siempre es una gramática válida en forma normal de Chomsky: no tienen que detectar errores.

## Tiempo

2 segundos por caso. Se compila con `g++ -Wall -Wextra -std=c++20 -O2`.

Probar derivaciones una por una hasta encontrar la cadena es correcto y no alcanza. Con la gramática de
`casos/14.in`, la cadena `()()()…()((` tiene 100 símbolos y no se genera, y para saberlo así habría que agotar
una cantidad de derivaciones que crece exponencialmente con la longitud: el juez da `TLE`. CYK llena una tabla
de $n(n+1)/2$ celdas y, para una cadena de $n$ símbolos y una gramática con $r$ reglas $A \to BC$, prueba
$r \cdot (n^3 - n)/6$ combinaciones: con $n = 100$ y $r = 100$ son menos de 17 millones por cadena.

Esa cuenta supone que saber si una variable está en una celda cuesta un paso. Si cada celda es un
`std::set<std::string>`, cada consulta compara nombres y el programa puede pasarse del tiempo. Numeren las
variables al leerlas y guarden en cada celda un `std::vector<bool>`, o un entero donde el bit $v$ dice si la
variable número $v$ está en la celda.

## Qué se practica aquí

En `code/week-05/chomsky.h` hay una función `cyk` que llena la tabla y otra que recupera un árbol: son las que
usan los ejemplos de los apuntes, y pueden leerlas. Están escritas para que se parezcan a la definición, con
conjuntos de nombres, y no para ser rápidas. Aquí escriben su propio CYK, en un solo archivo `solution.cpp`,
**sin incluir `cfg.h` ni `chomsky.h`**: el juez compila ese único archivo, y el lector de `cfg.h` no entiende
el bloque `strings:`.

Los casos traen, entre otros: la cadena vacía con y sin la regla $S \to \varepsilon$ (también como última
línea de la entrada), una gramática que no genera nada, variables sin reglas, una variable inicial sin
reglas, una gramática que solo genera $\varepsilon$, un terminal que ninguna regla produce, reglas repetidas,
comentarios entre las reglas, y varios casos con cadenas de 100 símbolos.

## Cómo avanzar

```sh
make        # compila solution.cpp en build/
make test   # corre el juez con todos los casos
```

1. Lean la gramática y las cadenas. Lean por líneas, con `std::getline`: `>>` se salta las líneas vacías, y aquí
   una línea vacía es una cadena. Guarden las reglas separadas según su forma: las $A \to BC$, las $A \to a$ y,
   si está, la regla $S \to \varepsilon$. El esqueleto trae un `struct Cfg` con una propuesta de tipos.
2. Respondan solo `genera` o `no genera`. Llenen la tabla **por longitudes crecientes** de subcadena: primero
   las celdas de un símbolo, con las reglas $A \to a$; después las de dos, las de tres, hasta la cadena
   completa. Una celda de longitud $\ell$ solo consulta celdas de longitud menor, que ya están llenas. Con solo
   esta parte, el juez ya da `AC` en los casos donde ninguna cadena se genera (`03` y `05`).
3. Para las cadenas que se generan, recuperen un árbol. La tabla ya dice qué variables generan cada subcadena;
   para armar el nodo de la variable $A$ sobre la subcadena de $i$ a $j$, busquen otra vez una regla $A \to BC$
   y un corte $k$ con $B$ en la celda de $i$ a $k$ y $C$ en la de $k+1$ a $j$. Tiene que existir, porque por
   eso $A$ entró a la celda. Los dos hijos salen igual, de forma recursiva.
4. Pasen los casos de borde. Antes de correr el juez, respondan a mano: ¿qué tabla le toca a la cadena vacía?
   ¿Qué responde una gramática cuya variable inicial no tiene reglas? ¿Y si una variable del lado derecho no
   tiene reglas?
5. Escriban en forma normal de Chomsky la gramática de los paréntesis balanceados,
   $S \to \mathtt{(}S\mathtt{)}S \mid \varepsilon$, que está en `../../machines/parens.cfg`. Háganlo a mano, con
   los cuatro pasos de los apuntes, guárdenla en un archivo y pruébenla con su parser:

   ```sh
   { cat mi_gramatica.cfg; printf 'strings: 4\n(())()\n\n(()\n)(\n'; } | build/solution
   ```

   Debe responder `genera`, `genera`, `no genera`, `no genera`, con un árbol para cada una de las dos primeras.
   Después comparen su gramática con la que escribe `build/to_chomsky machines/parens.cfg` desde `code/week-05`: no
   tienen que ser iguales, pero sí generar las mismas cadenas.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).
Para revisar un árbol suyo fuera del juez, el verificador se puede correr a mano:

```sh
build/solution < casos/01.in > salida.txt
build/verificador casos/01.in casos/01.out salida.txt && echo correcto
```

Si algo está mal, el verificador dice en qué cadena y por qué.

## Para seguir

Opcional, sin casos en el juez.

- **Contar árboles.** Cambien la tabla para que cada celda guarde, por cada variable, **cuántos** árboles tiene
  esa variable para esa subcadena, en lugar de un sí o un no. Con la gramática de `casos/10.in`, ¿cuántos
  árboles tiene `a+a+a+a+a`? ¿Y con la de `casos/14.in`, la cadena `()()()()`? Usen un tipo de 64 bits y
  piensen qué pasa con cadenas largas.
- **Decir dónde falla.** Cuando la cadena no se genera, impriman el prefijo más largo que sí es prefijo de
  alguna cadena del lenguaje. ¿Alcanza la tabla de CYK para saberlo?
- **Convertir antes.** Escriban un segundo programa que lea una gramática cualquiera y la escriba en forma
  normal de Chomsky, con los cuatro pasos en orden, y encadénenlo con su parser.
lab/cyk_parser/solution.cppDescargar lab/cyk_parser/solution.cpp
// Un parser con CYK. Lee una gramática en forma normal de Chomsky y una lista de cadenas.
// Por cada cadena imprime si la gramática la genera y, si la genera, un árbol de derivación.
#include <iostream>
#include <string>
#include <utility>
#include <vector>

// Los cuatro componentes de G = (V, Σ, R, S), con los nombres del formato.
// Los tipos son una propuesta: cada variable se guarda por su posición en la lista, para que
// la tabla de CYK no tenga que comparar nombres, y las reglas se separan según su forma.
// Pueden cambiarlos.
struct Cfg {
    std::vector<std::string> variables;          // V: los nombres, en el orden de la entrada
    std::vector<char> terminals;                 // Σ
    std::vector<std::vector<int>> binary;        // R, las reglas A → B C: {A, B, C} como posiciones en variables
    std::vector<std::pair<int, char>> terminal;  // R, las reglas A → a: (A, a)
    bool start_to_eps = false;                   // R, la regla S → ε, si está
    int start = 0;                               // S, como posición en variables
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    Cfg g;
    std::string line;
    // Por hacer: leer la gramática línea por línea con std::getline, hasta la línea strings:.
    // Después, leer las cadenas (una línea vacía es ε), llenar la tabla de CYK para cada una
    // y responder. Para las que se generan, recuperar un árbol de la tabla.
    while (std::getline(std::cin, line)) {
    }
    // Este esqueleto no imprime nada, así que el juez da WA en todos los casos.
    return static_cast<int>(g.variables.size());
}
lab/cyk_parser/verificador.cppDescargar lab/cyk_parser/verificador.cpp
// Verificador del laboratorio: verificador CASO.in CASO.out SALIDA
// Una cadena puede tener varios árboles de derivación, así que la salida no se compara con
// CASO.out como texto. De CASO.out solo se toma si cada cadena se genera o no. Para cada cadena
// que se genera, se comprueba que el árbol entregado es un árbol de derivación de esa cadena:
// la raíz es la variable inicial, cada nodo con sus hijos es una regla de la gramática, y las
// hojas, de izquierda a derecha, forman la cadena.
// Termina con 0 si la salida es correcta. Si no, escribe la razón y termina con 1.
#include <cstddef>
#include <fstream>
#include <iostream>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

struct Cfg {
    std::set<std::string> variables;
    std::set<std::pair<std::string, std::vector<std::string>>> rules;  // (A, lado derecho); A → ε tiene lado derecho vacío
    std::string start;
};

static std::vector<std::string> split_words(const std::string& text) {
    std::istringstream in(text);
    std::vector<std::string> words;
    std::string word;
    while (in >> word) {
        words.push_back(word);
    }
    return words;
}

static int fail(std::size_t string_number, const std::string& message) {
    std::cout << "cadena " << string_number << ": " << message << '\n';
    return 1;
}

// La salida como lista de palabras. Los corchetes son palabras por sí solos.
static std::vector<std::string> tokens_of(std::istream& in) {
    std::vector<std::string> tokens;
    std::string current;
    char c = 0;
    while (in.get(c)) {
        bool space = (c == ' ' || c == '\n' || c == '\t' || c == '\r');
        if (space || c == '[' || c == ']') {
            if (!current.empty()) {
                tokens.push_back(current);
                current.clear();
            }
            if (!space) {
                tokens.push_back(std::string(1, c));
            }
        } else {
            current += c;
        }
    }
    if (!current.empty()) {
        tokens.push_back(current);
    }
    return tokens;
}

// Lee un árbol [A hijo hijo …] a partir de tokens[at] y comprueba cada nodo contra las reglas.
// Agrega sus hojas a leaves y deja en root la variable de la raíz. Si algo falla, deja la razón en error.
static bool read_tree(const Cfg& g, const std::vector<std::string>& tokens, std::size_t& at, std::string& root,
                      std::string& leaves, std::string& error, int depth) {
    if (depth > 100000) {
        error = "el árbol es demasiado profundo";
        return false;
    }
    if (at >= tokens.size() || tokens[at] != "[") {
        error = "se esperaba [ al empezar un árbol";
        return false;
    }
    at++;
    if (at >= tokens.size() || g.variables.count(tokens[at]) == 0) {
        error = "después de [ va una variable" + (at < tokens.size() ? ", y hay " + tokens[at] : std::string());
        return false;
    }
    root = tokens[at];
    at++;
    std::vector<std::string> body;
    bool eps = false;
    while (at < tokens.size() && tokens[at] != "]") {
        if (tokens[at] == "[") {
            std::string child;
            if (!read_tree(g, tokens, at, child, leaves, error, depth + 1)) {
                return false;
            }
            body.push_back(child);
        } else if (tokens[at] == "eps") {
            eps = true;
            at++;
        } else {
            // Una hoja es un terminal: un solo carácter que no es una variable.
            if (tokens[at].size() != 1 || g.variables.count(tokens[at]) > 0) {
                error = "una hoja debe ser un terminal, y hay " + tokens[at];
                return false;
            }
            body.push_back(tokens[at]);
            leaves += tokens[at];
            at++;
        }
    }
    if (at >= tokens.size()) {
        error = "falta ] para cerrar el árbol de " + root;
        return false;
    }
    at++;
    if (eps && !body.empty()) {
        error = "eps solo puede ser el único hijo de un nodo";
        return false;
    }
    if (g.rules.count({root, body}) == 0) {
        std::string text;
        for (const std::string& symbol : body) {
            text += " " + symbol;
        }
        error = "el nodo " + root + " ->" + (body.empty() ? " eps" : text) + " no es una regla de la gramática";
        return false;
    }
    return true;
}

int main(int argc, char** argv) {
    if (argc != 4) {
        std::cout << "uso: verificador CASO.in CASO.out SALIDA\n";
        return 2;
    }
    std::ifstream input(argv[1]);
    std::ifstream expected(argv[2]);
    std::ifstream output(argv[3]);
    if (!input || !expected || !output) {
        std::cout << "no se pudo abrir alguno de los archivos\n";
        return 2;
    }

    // La gramática y las cadenas del caso.
    Cfg g;
    std::vector<std::string> strings;
    std::string line;
    while (std::getline(input, line)) {
        if (!line.empty() && line[0] == '#') {
            continue;
        }
        std::vector<std::string> words = split_words(line);
        if (words.empty() || words[0] == "terminals:" || words[0] == "rules:") {
            continue;
        }
        if (words[0] == "variables:") {
            g.variables.insert(words.begin() + 1, words.end());
        } else if (words[0] == "start:") {
            g.start = words[1];
        } else if (words[0] == "strings:") {
            int count = std::stoi(words[1]);
            for (int s = 0; s < count; s++) {
                std::string w;
                std::getline(input, w);
                strings.push_back(w);
            }
            break;
        } else {
            std::vector<std::string> body;
            for (std::size_t i = 2; i <= words.size(); i++) {
                if (i < words.size() && words[i] != "|") {
                    if (words[i] != "eps") {
                        body.push_back(words[i]);
                    }
                    continue;
                }
                g.rules.insert({words[0], body});
                body.clear();
            }
        }
    }

    // Qué cadenas se generan, según la respuesta esperada. El árbol de CASO.out no se usa.
    std::vector<bool> generated;
    while (std::getline(expected, line)) {
        std::vector<std::string> words = split_words(line);
        if (words.size() == 1 && words[0] == "genera") {
            generated.push_back(true);
        } else if (words.size() == 2 && words[0] == "no" && words[1] == "genera") {
            generated.push_back(false);
        }
    }
    if (generated.size() != strings.size()) {
        std::cout << "el archivo de respuestas no corresponde al caso\n";
        return 2;
    }

    std::vector<std::string> tokens = tokens_of(output);
    std::size_t at = 0;
    for (std::size_t s = 0; s < strings.size(); s++) {
        const std::string shown = strings[s].empty() ? "la cadena vacía" : strings[s];
        if (at >= tokens.size()) {
            return fail(s + 1, "falta la respuesta");
        }
        if (tokens[at] == "no" && at + 1 < tokens.size() && tokens[at + 1] == "genera") {
            at += 2;
            if (generated[s]) {
                return fail(s + 1, "dice no genera, y la gramática sí genera " + shown);
            }
            continue;
        }
        if (tokens[at] != "genera") {
            return fail(s + 1, "se esperaba genera o no genera, y hay " + tokens[at]);
        }
        at++;
        if (!generated[s]) {
            return fail(s + 1, "dice genera, y la gramática no genera " + shown);
        }
        std::string root, leaves, error;
        if (!read_tree(g, tokens, at, root, leaves, error, 0)) {
            return fail(s + 1, error);
        }
        if (root != g.start) {
            return fail(s + 1, "la raíz del árbol es " + root + ", y debe ser la variable inicial " + g.start);
        }
        if (leaves != strings[s]) {
            return fail(s + 1, "las hojas del árbol forman " + (leaves.empty() ? std::string("la cadena vacía") : leaves) +
                                   ", y la cadena es " + shown);
        }
    }
    if (at != tokens.size()) {
        std::cout << "sobra salida después de la última respuesta: " << tokens[at] << '\n';
        return 1;
    }
    return 0;
}

Compilación

Cómo se compilan y ejecutan los ejemplos.

MakefileDescargar Makefile
# Semana 5: gramáticas libres de contexto, forma normal de Chomsky y CYK.
# Se usa dentro del entorno del curso.
#
#   make           compila los programas de la clase en build/
#   make test      corre las pruebas de los ejemplos, con sanitizers
#   make clean     borra lo generado
#
# Las pruebas leen las gramáticas de machines/ y de errors/, así que se corren desde esta carpeta.
# El laboratorio está en lab/cyk_parser y tiene su propio Makefile: estas reglas no lo tocan.

CXX = g++
CXXFLAGS = -Wall -Wextra -std=c++20 -g -fsanitize=address,undefined
BUILD = build
PROGRAMS = show_cfg derive to_chomsky cyk search_cost
TESTS = test_cfg test_ambiguity test_chomsky test_cyk
HEADERS = cfg.h chomsky.h predicates.h

.PHONY: all test clean

all: $(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%)

$(PROGRAMS:%=$(BUILD)/%) $(TESTS:%=$(BUILD)/%): $(BUILD)/%: %.cpp $(HEADERS) | $(BUILD)
	$(CXX) $(CXXFLAGS) $< -o $@

$(BUILD):
	mkdir -p $@

test: $(TESTS:%=$(BUILD)/%) $(PROGRAMS:%=$(BUILD)/%)
	@for t in $(TESTS); do $(BUILD)/$$t || exit 1; done
	@echo "Todas las pruebas pasaron."

clean:
	rm -rf $(BUILD)