# Un grep pequeño

`grep` recibe un patrón y un texto, y dice qué líneas del texto coinciden con el patrón. En este laboratorio
escriben la parte central de esa herramienta: reciben una expresión regular y una lista de líneas, y dicen por
cada línea si la expresión la describe **completa**.

Son las tres construcciones de la sesión A, una detrás de otra: el árbol de la expresión, el NFA de Thompson
y la simulación con el conjunto de estados activos.

## Entrada

La primera línea es la expresión regular. Después viene el bloque de cadenas de
[`code/formats.md`](../../../formats.md): una línea `strings: k` y $k$ líneas, una cadena por línea.

```text
(a|b)*abb
strings: 5
abb
babb

ab
abba
```

La expresión se escribe con la sintaxis del código de la semana, sin $\varepsilon$ ni $\emptyset$:

- Un **símbolo** es una letra minúscula de `a` a `z` o un dígito de `0` a `9`.
- La **unión** es `|`, la **concatenación** no se escribe y la **estrella** es `*`.
- Los **paréntesis** agrupan.
- **Precedencia:** primero la estrella, después la concatenación, al final la unión. `ab|cd*` es
  $(\mathtt{ab}) \cup (\mathtt{c}(\mathtt{d}^*))$.

Con más precisión, la expresión sigue esta gramática, y no tiene espacios:

```text
unión         →  concatenación ( '|' concatenación )*
concatenación →  estrella estrella*
estrella      →  átomo '*'*
átomo         →  símbolo  |  '(' unión ')'
```

Entonces una estrella puede llevar otra encima, `a**`, y puede haber paréntesis de más, `((a))`. No hay
alternativas vacías ni paréntesis vacíos: `a||b`, `(a|)` y `()` no aparecen.

Sobre las cadenas:

- **Una línea vacía es la cadena vacía $\varepsilon$**, y también hay que responder por ella.
- Las cadenas están formadas solo por letras minúsculas y dígitos. Pueden tener símbolos que no aparecen en
  la expresión: una cadena así nunca coincide.
- En esta entrada no hay comentarios: ninguna línea empieza con `#`.

## Salida

Una línea por cada cadena, en el mismo orden: `acepta` si la expresión describe la cadena completa, y
`rechaza` si no.

Un `grep` de verdad imprimiría las líneas que coinciden. Aquí se imprime un veredicto por línea por una razón
práctica: el juez compara la salida palabra por palabra, sin mirar los saltos de línea, y una línea vacía que
coincide no dejaría ninguna huella en la salida. Con un veredicto por cadena, la respuesta a la cadena vacía
se ve, y un programa que no imprime nada falla siempre.

## Límites

- La expresión tiene entre 1 y 200 caracteres, y siempre está bien formada: no tienen que detectar errores.
- $1 \leq k \leq 20\,000$.
- Las longitudes de las cadenas suman a lo sumo 100 000. Una sola cadena puede tener esa longitud.

## Ejemplo

Para la entrada de arriba, la salida es:

```text
acepta
acepta
rechaza
rechaza
rechaza
```

La expresión describe las cadenas de letras `a` y `b` que terminan en `abb`. La tercera cadena es la vacía. La
última contiene `abb`, pero no termina ahí: la expresión tiene que describir la línea completa, como con
`grep -x`.

## Tiempo

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

El NFA de Thompson de una expresión de 200 caracteres tiene a lo sumo 400 estados. Simularlo con el conjunto
de estados activos cuesta, por cada símbolo de la cadena, una pasada por los estados activos: en total, del
orden de $100\,000 \cdot 400$ pasos en el peor caso, que entra con holgura.

Lo que **no** entra es el backtracking: probar una alternativa y, si falla, volver atrás y probar la otra. Uno
de los casos es la expresión `(a|a)*b` contra una línea de 50 000 letras `a`. No hay ninguna `b`, así que la
respuesta es `rechaza`, y una búsqueda con backtracking la encuentra después de probar las $2^{50\,000}$
maneras de elegir una rama para cada letra. Otros casos tienen estrellas dentro de estrellas, como
`(a*b*)*c`, que hacen lo mismo.

Dos cuidados más:

- **Los ciclos de transiciones $\varepsilon$.** Una estrella sobre algo que puede ser vacío, como `(a*)*`, da
  un NFA en el que se puede volver al mismo estado sin leer nada. La clausura $\varepsilon$ tiene que marcar
  los estados ya visitados, o no termina.
- **No construyan el DFA completo.** Uno de los casos es "el símbolo que está 38 posiciones antes del último
  es una `a`", y su DFA tiene más de $2^{38}$ estados. El NFA tiene menos de 400.

## Qué se practica aquí

En `code/week-03` están `regex.h`, `thompson.h` y `nfa.h`, que hacen estos tres pasos para los ejemplos de los
apuntes, y pueden leerlos cuanto quieran. `solution.cpp` se escribe **sin incluirlos**: el juez compila ese
único archivo. Tampoco conviene copiarlos tal cual. Están escritos para parecerse a las definiciones, con los
estados guardados por su nombre en un `std::set`, y así la simulación no alcanza a pasar el caso más grande.

El trabajo del laboratorio es escribir los tres pasos de forma que el tercero cueste lo que dice el análisis:

- Los estados son **números** de 0 a $m - 1$, y $\delta$ son arreglos indexados por el estado. En el NFA de
  Thompson, de cada estado sale una flecha con un símbolo, o una o dos transiciones $\varepsilon$, o nada: no
  hace falta ninguna estructura más complicada.
- El conjunto de estados activos es una **lista** de estados más un arreglo de marcas, que dice si un estado
  ya está en la lista. Así agregar un estado y preguntar si ya está cuestan tiempo constante. Un
  `std::set<int>` también pasa, más justo.

## Cómo avanzar

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

Los cuatro casos grandes no están guardados: `make test` los genera con los programas `casos/gen_NN.cpp`.

1. **Leer la entrada.** El esqueleto ya lee la expresión, la línea `strings:` y las cadenas, con
   `std::getline`: una línea vacía es una cadena, y `>>` se la saltaría.
2. **El árbol de la expresión.** Escriban el parser con una función por cada línea de la gramática:
   `parse_union` llama a `parse_concat`, que llama a `parse_star`, que llama a `parse_atom`. Cada función
   devuelve el nodo que construyó. El esqueleto trae un `struct Node` como propuesta. Antes de seguir,
   comprueben a mano el árbol de `ab|cd*` y el de `(a|b)*abb`.
3. **El NFA de Thompson.** Recorran el árbol de las hojas a la raíz. Cada nodo devuelve su pieza: el estado de
   entrada y el de salida. Un símbolo crea dos estados y una flecha. La unión y la estrella crean dos estados
   y cuatro transiciones $\varepsilon$. La concatenación no crea estados: une las dos piezas con una
   transición $\varepsilon$.
4. **La simulación.** Empiecen con la clausura $\varepsilon$ del estado inicial. Por cada símbolo de la línea,
   armen la lista siguiente: para cada estado activo que tenga una flecha con ese símbolo, agreguen el destino
   y su clausura $\varepsilon$. Al final, la respuesta es si el estado de aceptación está entre los activos.
   Si la lista queda vacía a mitad de la línea, ya pueden responder `rechaza`.
5. **Los casos de borde.** Antes de correr el juez, respondan a mano: ¿qué responde `a*` con la línea vacía?
   ¿Y `a`? ¿Qué pasa en su clausura $\varepsilon$ con `(a*)*`?
6. **El caso grande.** Corran `casos/11.in`, que es `(a|a)*b` con líneas de unas decenas de letras, y después
   el juez completo.

Para probar una expresión propia sin escribir un archivo:

```sh
printf '(0|1)*1\nstrings: 3\n011\n\n010\n' | build/solution
```

Debe imprimir `acepta`, `rechaza`, `rechaza`.

Mientras desarrollan, compilen con sanitizers, como explica [`labs/README.md`](../../../../labs/README.md).

## Para seguir

Opcional, sin casos en el juez.

- Agreguen las abreviaturas `+` y `?` al parser, sin agregar tipos de nodo: `R+` es $RR^*$ y `R?` necesita
  una pieza para $\varepsilon$.
- Hagan que el programa busque como `grep` sin `-x`: que acepte una línea si la expresión describe **alguna
  subcadena** suya. No hace falta cambiar la simulación: basta cambiar el autómata. ¿Cómo?
- Guarden cada conjunto de estados activos la primera vez que aparece, con un número, y también a qué
  conjunto lleva con cada símbolo. Es la construcción de subconjuntos de la semana pasada hecha sobre la
  marcha. Midan cuántos conjuntos distintos aparecen en `casos/14.in`.
