# 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.
