Tamaño de letra
Tema
Ancho de lectura
Tipografía

Apuntes · Capítulo 5Lenguajes libres de contexto

Gramáticas libres de contexto

Gramáticas libres de contexto

La primera parte del curso terminó con un límite. Un autómata finito tiene una cantidad fija de estados, y con eso no puede contar sin tope: en la semana 4 demostramos que { 0n1n:n≥0 }\{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\} no es regular. Ni un DFA, ni un NFA, ni una expresión regular lo describen.

Ese lenguaje no es una curiosidad. Tiene la forma de casi todo lo que escribimos para una computadora: algo que se abre y después se cierra, con más cosas del mismo tipo adentro. Un paréntesis que abre exige uno que cierre. Una llave { de C++ exige su }, y entre las dos hay instrucciones que traen sus propias llaves. Una lista de JSON contiene valores, y un valor puede ser otra lista. A eso se le llama estructura anidada, y para reconocerla hay que recordar cuántas cosas quedaron abiertas, sin límite.

Esta semana empieza la segunda parte del curso, con una manera nueva de describir un lenguaje. Un autómata reconoce: recibe una cadena y responde sí o no. Una gramática hace lo contrario: da reglas para generar las cadenas del lenguaje, y la estructura anidada sale sola porque las reglas pueden ser recursivas. Las gramáticas libres de contexto describen todos los lenguajes regulares y además {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}, los paréntesis balanceados, las expresiones aritméticas y la sintaxis de los lenguajes de programación.

La semana tiene dos mitades. En la primera definimos las gramáticas, aprendemos a diseñarlas y a demostrar que generan lo que decimos, y encontramos un problema que los autómatas no tenían: una misma cadena puede tener dos estructuras distintas. En la segunda resolvemos la pregunta que un compilador se hace con cada programa: dada una gramática y una cadena, ¿la gramática genera la cadena? La respuesta pasa por una forma ordenada de escribir las gramáticas, la forma normal de Chomsky, y por un algoritmo de programación dinámica, CYK.

Ruta de lectura.

Antes de clase (15–20 minutos): la introducción, Lo que las expresiones regulares no alcanzan y La definición formal de una gramática. Antes de la sesión B, El problema de la pertenencia. Con eso llegan con la definición y con la pregunta de la segunda sesión ya planteada.

En clase: Sesión A, de Lo que las expresiones regulares no alcanzan a Ambigüedad. Sesión B, de El problema de la pertenencia a El costo de CYK.

Después de clase: el Resumen y los Ejercicios, para repasar. Antes del laboratorio, El algoritmo CYK otra vez y El código de la semana. Para ampliar, las lecturas de apoyo del recuadro siguiente.

Lectura. Sipser, sec. 2.1 (Context-Free Grammars), que incluye la ambigüedad y la parte Chomsky Normal Form, y de la sec. 7.2 el teorema de que todo lenguaje libre de contexto está en P, que es el algoritmo CYK. Erickson, Models of Computation, nota 5 (Context-free languages). Son apoyo: estos apuntes se pueden estudiar solos.

Código. Los programas de este capítulo están en code/week-05. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. El laboratorio está en lab/cyk_parser.

Lo que las expresiones regulares no alcanzan

Tres lenguajes que aparecen en cualquier programa, y que ningún autómata finito reconoce.

Paréntesis balanceados. Las cadenas sobre {(,)}\{\mathtt{(}, \mathtt{)}\} en las que cada paréntesis que abre tiene uno que cierra después, como (())()\mathtt{(())()}, y no como )(\mathtt{)(} ni (()\mathtt{(()}. El argumento de la semana 4 se repite casi igual: después de leer (n\mathtt{(}^n hay que recordar nn para saber cuántos )\mathtt{)} faltan, y nn no tiene tope.

Expresiones aritméticas. a+a×a\mathtt{a+a\times a} o (a+a)×a\mathtt{(a+a)\times a}, donde a\mathtt{a} representa un número o una variable. Contienen a los paréntesis balanceados, y además tienen algo que los paréntesis solos no muestran: la cadena tiene una estructura que decide qué significa. En a+a×a\mathtt{a+a\times a} el producto se hace primero, aunque esté escrito después.

JSON. Un valor es un número, o una lista de valores entre corchetes, separados por comas. La definición se nombra a sí misma, y eso es lo que da listas dentro de listas, como [1, [2, 3], []].

Las tres descripciones tienen la misma forma: dicen cómo se arma una cadena del lenguaje a partir de cadenas más cortas del mismo lenguaje. Una expresión es una expresión, un signo más y otra expresión. Una lista es un corchete, valores, y un corchete. Una gramática es esa descripción escrita con precisión. La del valor de JSON, simplificada, donde n\mathtt{n} representa un número, queda así:

V→n∣[ ]∣[ L ]L→V∣V , L\begin{aligned} V &\to \mathtt{n} \mid \mathtt{[\,]} \mid \mathtt{[}\,L\,\mathtt{]} \\ L &\to V \mid V\,\mathtt{,}\,L \end{aligned}

Se lee: un valor VV es un número, o una lista vacía, o un corchete, una lista de valores LL y un corchete. Una lista de valores es un valor solo, o un valor, una coma y otra lista de valores. La barra ∣\mid separa las alternativas.

En la práctica. La sintaxis de casi todos los lenguajes de programación y de los formatos de datos se publica como una gramática de este tipo. El estándar de C++, la referencia de Python y la especificación de JSON traen sus reglas escritas con una flecha y alternativas. El programa que lee un texto y encuentra su estructura según una gramática se llama parser, y está en todo compilador, en todo intérprete y en toda biblioteca que lee JSON.

La definición formal de una gramática

Una gramática libre de contexto (context-free grammar, CFG) es una cuádrupla G=(V,Σ,R,S)G = (V, \Sigma, R, S), donde:

  1. VV es un conjunto finito de variables (variables);
  2. Σ\Sigma es un conjunto finito de terminales (terminals), que no comparte elementos con VV;
  3. RR es un conjunto finito de reglas (rules), cada una de la forma A→uA \to u, donde AA es una variable y uu es una cadena de variables y terminales, es decir, u∈(V∪Σ)∗u \in (V \cup \Sigma)^*;
  4. S∈VS \in V es la variable inicial.

Los terminales son los símbolos de las cadenas que la gramática genera: son el alfabeto del lenguaje. Las variables no aparecen en esas cadenas. Son nombres para las partes que todavía falta escribir: “aquí va una expresión”, “aquí va una lista”. Escribimos las variables con mayúsculas, AA, BB, SS, y los terminales como los símbolos de siempre, 0\mathtt{0}, a\mathtt{a}, (\mathtt{(}. Las letras uu, vv, xx, yy nombran cadenas que pueden mezclar variables y terminales, y ww queda para las cadenas de terminales.

El lado derecho de una regla puede ser la cadena vacía: A→εA \to \varepsilon es una regla válida, y se llama regla ε\varepsilon. Varias reglas con el mismo lado izquierdo se abrevian con la barra: A→u∣vA \to u \mid v son las dos reglas A→uA \to u y A→vA \to v.

El primer ejemplo es la gramática G1G_1 del lenguaje que cerró la semana 4:

S→0S1∣εS \to \mathtt{0}S\mathtt{1} \mid \varepsilon

Es G1=({S},{0,1},R,S)G_1 = (\{S\}, \{\mathtt{0}, \mathtt{1}\}, R, S), con las dos reglas S→0S1S \to \mathtt{0}S\mathtt{1} y S→εS \to \varepsilon. Cuando una gramática se da solo con sus reglas, como aquí, se entiende que las variables son los símbolos que aparecen a la izquierda de alguna flecha, que los terminales son los demás símbolos, y que la variable inicial es la de la primera regla.

Las gramáticas como archivos

Las gramáticas del curso se escriben en archivos .cfg, con el formato de code/formats.md. Los campos son los cuatro componentes de la definición, con su nombre en palabras: variables, terminals, start y rules. Este es machines/zeros_ones.cfg:

# { 0^n 1^n : n >= 0 }
variables: S
terminals: 0 1
start: S
rules:
S -> 0 S 1 | eps

Cada línea después de rules: tiene una variable, la flecha -> y sus alternativas separadas por |. Los símbolos de una alternativa van separados por espacios, porque el nombre de una variable puede tener varias letras. La alternativa vacía se escribe eps. El programa show_cfg lee un archivo, lo muestra como cuádrupla y lista las cadenas más cortas que genera:

$ build/show_cfg machines/zeros_ones.cfg
G = (V, Σ, R, S)
  V = {S}
  Σ = {0, 1}
  S = S
  R tiene 2 reglas:
    S → 0S1
    S → ε
Cadenas de L(G) con longitud a lo sumo 6 (4):
  ε 01 0011 000111

Todavía no dijimos qué significa que una gramática genere una cadena. Eso es la sección siguiente.

Error común. Escribir S -> 0S1 en el archivo. Sin espacios, 0S1 es un solo nombre, que no es variable ni terminal. La carpeta errors/ tiene ese caso, y el lector lo rechaza diciendo por qué:

$ build/show_cfg errors/glued_symbols.cfg
error: errors/glued_symbols.cfg: la gramática no es válida: en una regla de S aparece aSb, que no es variable ni terminal

En C++. El struct Cfg de cfg.h tiene los cuatro componentes con los nombres del formato: variables, terminals, rules y start. Una regla es un struct Rule con head, la variable de la izquierda, y body, un std::vector<std::string> con los símbolos de la derecha. La regla A→εA \to \varepsilon tiene el body vacío: un vector con cero elementos, igual que ε\varepsilon es la cadena con cero símbolos.

Derivaciones y el lenguaje de una gramática

Una gramática se usa así: se escribe la variable inicial y se repite un paso hasta que no queden variables. El paso es elegir una variable de lo que está escrito, elegir una de sus reglas, y reemplazar la variable por el lado derecho de la regla. Con G1G_1:

S⇒0S1⇒00S11⇒000S111⇒000111S \Rightarrow \mathtt{0}S\mathtt{1} \Rightarrow \mathtt{00}S\mathtt{11} \Rightarrow \mathtt{000}S\mathtt{111} \Rightarrow \mathtt{000111}

Los tres primeros pasos usan la regla S→0S1S \to \mathtt{0}S\mathtt{1}, y el último usa S→εS \to \varepsilon: la SS se reemplaza por nada.

Con precisión. Sean uu, vv, xx cadenas de variables y terminales, y sea A→xA \to x una regla de GG. Decimos que uAvuAv deriva en un paso uxvuxv, y escribimos

uAv⇒uxv.uAv \Rightarrow uxv.

Decimos que uu deriva vv, y escribimos u⇒∗vu \Rightarrow^* v, si se llega de uu a vv con cero o más pasos: u=vu = v, o hay cadenas u1,…,uku_1, \ldots, u_k con

u⇒u1⇒u2⇒⋯⇒uk=v.u \Rightarrow u_1 \Rightarrow u_2 \Rightarrow \cdots \Rightarrow u_k = v.

Esa secuencia es una derivación (derivation) de vv a partir de uu, y kk es su número de pasos. Cada cadena que aparece en una derivación que empieza en SS se llama una forma: puede tener variables y terminales.

El lenguaje de la gramática es el conjunto de las cadenas de terminales que se derivan de la variable inicial:

L(G)={ w∈Σ∗:S⇒∗w }.L(G) = \{\, w \in \Sigma^* : S \Rightarrow^* w \,\}.

Si w∈L(G)w \in L(G) decimos que GG genera ww. Un lenguaje es libre de contexto (context-free language) si alguna gramática libre de contexto lo genera.

Dos cosas de la definición que conviene mirar despacio.

Solo cuentan las cadenas sin variables. 00S11\mathtt{00}S\mathtt{11} se deriva de SS, pero no está en L(G1)L(G_1): es una forma, un trabajo a medio hacer. Una derivación que nunca logra deshacerse de sus variables no genera nada.

En cada paso hay elecciones. Qué variable reemplazar y con cuál de sus reglas. Una gramática no es un procedimiento con un solo camino: es un conjunto de reglas, y L(G)L(G) junta lo que sale por todos los caminos. En eso se parece a un NFA, que acepta si algún camino acepta.

Por qué se llaman libres de contexto

La regla A→xA \to x se puede aplicar a una AA esté donde esté. En la definición del paso, uu y vv son cualesquiera: lo que rodea a la variable, su contexto, no importa. De ahí salen dos propiedades que usaremos en casi todas las demostraciones del capítulo.

Lema (del contexto). Si x⇒∗yx \Rightarrow^* y, entonces uxv⇒∗uyvuxv \Rightarrow^* uyv para todas las cadenas uu, vv.

Demostración. Cada paso de x⇒∗yx \Rightarrow^* y reemplaza una variable por el lado derecho de una regla. El mismo reemplazo se puede hacer con uu escrita a la izquierda y vv a la derecha, porque la definición del paso permite cualquier cosa alrededor. Haciendo los mismos pasos en el mismo orden se va de uxvuxv a uyvuyv. ∎

Lema (de separación). Sean X1,…,XkX_1, \ldots, X_k símbolos, variables o terminales, y ww una cadena de terminales. Si X1X2⋯Xk⇒∗wX_1X_2 \cdots X_k \Rightarrow^* w con nn pasos, entonces ww se parte en w=w1w2⋯wkw = w_1w_2 \cdots w_k de modo que Xi⇒∗wiX_i \Rightarrow^* w_i con nin_i pasos para cada ii, y n1+⋯+nk=nn_1 + \cdots + n_k = n.

Con palabras: lo que sale de cada símbolo es un trozo de la cadena final, los trozos quedan en el mismo orden que los símbolos, y cada símbolo trabaja por su cuenta.

Demostración. Por inducción sobre nn.

Caso base: n=0n = 0. Entonces X1⋯Xk=wX_1 \cdots X_k = w, todos los XiX_i son terminales, y sirve wi=Xiw_i = X_i con ni=0n_i = 0.

Paso inductivo: el primer paso de la derivación reemplaza alguna variable XjX_j con una regla Xj→Y1⋯YmX_j \to Y_1 \cdots Y_m. Queda la cadena

X1⋯Xj−1  Y1⋯Ym  Xj+1⋯Xk,X_1 \cdots X_{j-1}\; Y_1 \cdots Y_m\; X_{j+1} \cdots X_k,

que deriva ww con n−1n - 1 pasos. Por la hipótesis de inducción, ww se parte en un trozo por cada símbolo de esa cadena. Los trozos de X1,…,Xj−1X_1, \ldots, X_{j-1} y de Xj+1,…,XkX_{j+1}, \ldots, X_k sirven tal cual. Sea wjw_j la concatenación de los trozos de Y1,…,YmY_1, \ldots, Y_m. Entonces Xj⇒Y1⋯Ym⇒∗wjX_j \Rightarrow Y_1 \cdots Y_m \Rightarrow^* w_j: el primer paso es la regla, y el resto se arma derivando cada YY en su trozo, uno después de otro, lo que el lema del contexto permite. Esa derivación tiene un paso más que la suma de los pasos de los YY, así que los números de pasos de todos los XiX_i suman (n−1)+1=n(n - 1) + 1 = n. Si m=0m = 0, la regla es Xj→εX_j \to \varepsilon, y wj=εw_j = \varepsilon con un paso. ∎

Idea clave. En una gramática libre de contexto, lo que una variable genera no depende de lo que tiene alrededor. Por eso una derivación se puede partir en derivaciones independientes, una por símbolo, y por eso tiene sentido preguntar “¿qué cadenas genera la variable AA?” para cada variable por separado.

Derivaciones por la izquierda

Cuando una forma tiene varias variables, el orden en que se reemplazan no cambia lo que se puede generar: por el lema de separación, cada una trabaja por su cuenta. Para no contar como distintas dos derivaciones que solo difieren en ese orden, se fija uno.

Una derivación por la izquierda (leftmost derivation) es una derivación en la que cada paso reemplaza la variable que está más a la izquierda en la forma. Con la gramática S→ABS \to AB, A→aA \to \mathtt{a}, B→bB \to \mathtt{b}, la cadena ab\mathtt{ab} tiene dos derivaciones:

S⇒AB⇒aB⇒abS⇒AB⇒Ab⇒abS \Rightarrow AB \Rightarrow \mathtt{a}B \Rightarrow \mathtt{ab} \qquad\qquad S \Rightarrow AB \Rightarrow A\mathtt{b} \Rightarrow \mathtt{ab}

Solo la primera es por la izquierda. La segunda reemplaza BB cuando todavía hay una AA antes.

Toda cadena de L(G)L(G) tiene al menos una derivación por la izquierda. Sale del lema de separación: si A⇒X1⋯Xk⇒∗wA \Rightarrow X_1 \cdots X_k \Rightarrow^* w, se deriva primero todo el trozo de X1X_1, después todo el de X2X_2, y así, y dentro de cada trozo se hace lo mismo.

El programa derive busca todas las derivaciones por la izquierda de una cadena, probando reglas con backtracking:

$ build/derive machines/zeros_ones.cfg 000111
w = 000111
derivaciones por la izquierda: 1

1. S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 000111
   4 pasos
   S
   ├── 0
   ├── S
   │   ├── 0
   │   ├── S
   │   │   ├── 0
   │   │   ├── S
   │   │   │   └── ε
   │   │   └── 1
   │   └── 1
   └── 1

Debajo de la derivación, el programa dibuja un árbol. Es el tema de la sección siguiente.

Árboles de derivación

Una derivación dice qué reglas se usaron y en qué orden. El orden es un accidente: lo que importa es qué regla se le aplicó a cada variable. Un árbol guarda eso y nada más.

Un árbol de derivación (parse tree) de una gramática GG es un árbol ordenado en el que:

  • cada nodo interno lleva una variable, y cada hoja lleva un terminal o ε\varepsilon;
  • si un nodo lleva la variable AA y sus hijos, de izquierda a derecha, llevan X1,X2,…,XkX_1, X_2, \ldots, X_k, entonces A→X1X2⋯XkA \to X_1X_2 \cdots X_k es una regla de GG;
  • una hoja lleva ε\varepsilon solo si es el único hijo de su padre, y entonces la regla es A→εA \to \varepsilon.

La cadena que el árbol deriva se lee en sus hojas, de izquierda a derecha, saltando las ε\varepsilon. El árbol de arriba tiene raíz SS y deriva 000111\mathtt{000111}. El programa lo dibuja acostado: los hijos de un nodo son las líneas que cuelgan de él, de arriba hacia abajo en lugar de izquierda a derecha.

Animación de la derivación de 000111 con la gramática S → 0S1 | ε. A la izquierda crece el árbol y debajo se muestra la forma actual; a la derecha se escribe la derivación, con la regla de cada paso. Al comienzo el árbol es solo la raíz S y la forma es S. Paso 1, regla S → 0S1: a la raíz le cuelgan tres hijos, 0, S y 1, y la forma es 0S1. Paso 2, la misma regla sobre la S nueva: la forma es 00S11. Paso 3, otra vez: la forma es 000S111, y cada 0 queda emparejado con el 1 de su misma regla. Paso 4, regla S → ε: a la última S le cuelga una sola hoja ε, y la forma queda sin variables. Las hojas del árbol, de izquierda a derecha y saltando ε, dan 000111; fueron 4 pasos, uno por cada nodo internoAnimación de la derivación de 000111 con la gramática S → 0S1 | ε. A la izquierda crece el árbol y debajo se muestra la forma actual; a la derecha se escribe la derivación, con la regla de cada paso. Al comienzo el árbol es solo la raíz S y la forma es S. Paso 1, regla S → 0S1: a la raíz le cuelgan tres hijos, 0, S y 1, y la forma es 0S1. Paso 2, la misma regla sobre la S nueva: la forma es 00S11. Paso 3, otra vez: la forma es 000S111, y cada 0 queda emparejado con el 1 de su misma regla. Paso 4, regla S → ε: a la última S le cuelga una sola hoja ε, y la forma queda sin variables. Las hojas del árbol, de izquierda a derecha y saltando ε, dan 000111; fueron 4 pasos, uno por cada nodo interno
La derivación y el árbol crecen juntos: cada paso le cuelga a una variable los símbolos de la regla, y la forma es lo que se lee en la frontera del árbol.

Los árboles y las derivaciones cuentan la misma historia:

  • De una derivación sale un árbol. La raíz es la variable inicial, y cada paso uAv⇒uxvuAv \Rightarrow uxv le cuelga a esa AA un hijo por cada símbolo de xx.
  • De un árbol salen derivaciones, en general varias: una por cada orden en que se pueden recorrer los nodos internos de modo que cada uno venga después de su padre. Todas tienen el mismo número de pasos, porque cada nodo interno es exactamente un paso.
  • De un árbol sale una sola derivación por la izquierda. Es la que recorre los nodos internos en preorden: primero el nodo, después sus hijos de izquierda a derecha. Y dos árboles distintos dan derivaciones por la izquierda distintas, porque de la lista de reglas en preorden se reconstruye el árbol.

Por eso un árbol y una derivación por la izquierda son dos maneras de escribir lo mismo. Las dos derivaciones de ab\mathtt{ab} de la sección anterior tienen el mismo árbol:

$ build/derive machines/two_derivations.cfg ab
w = ab
derivaciones por la izquierda: 1

1. S ⇒ AB ⇒ aB ⇒ ab
   3 pasos
   S
   ├── A
   │   └── a
   └── B
       └── b

En adelante usaremos una forma equivalente de decir que una variable genera una cadena: A⇒∗wA \Rightarrow^* w si y solo si hay un árbol de derivación con raíz AA que deriva ww.

Idea clave. El árbol de derivación es la estructura de la cadena según la gramática: qué trozo salió de qué variable. Un compilador no quiere saber solo que el programa está bien escrito. Quiere el árbol, porque el árbol dice qué operación se aplica a qué.

En C++. En cfg.h, un árbol es un struct Tree con symbol y children, un std::vector<Tree>. Un struct puede tener un vector de sí mismo, y así el árbol se arma y se destruye sin punteros, sin new y sin delete. La función tree_of construye el árbol de una derivación por la izquierda, y yield_of lee sus hojas.

Cómo diseñar una gramática

Diseñar un DFA era decidir qué recordar. Diseñar una gramática es describir cómo se arma una cadena del lenguaje a partir de otras más cortas. Tres preguntas ayudan:

  1. ¿Cuáles son las cadenas más cortas del lenguaje? Son los casos base: reglas sin variables a la derecha.
  2. ¿Cómo se obtiene una cadena más larga a partir de una o dos más cortas? Son las reglas recursivas.
  3. ¿Toda cadena del lenguaje se arma así? Si quedan cadenas afuera, faltan reglas.

Cuatro ejemplos, del más simple al menos obvio.

Ceros y después la misma cantidad de unos

L={ 0n1n:n≥0 }L = \{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}. La más corta es ε\varepsilon. Una cadena más larga es 0\mathtt{0}, una cadena del lenguaje, y 1\mathtt{1}: la recursión agrega un símbolo en cada extremo a la vez, y así las dos cantidades crecen juntas.

S→0S1∣εS \to \mathtt{0}S\mathtt{1} \mid \varepsilon

Esa es la idea que un DFA no puede imitar: la regla S→0S1S \to \mathtt{0}S\mathtt{1} deja la variable en medio, y lo que se escribe a su izquierda queda emparejado con lo que se escribe a su derecha.

Palíndromos

Un palíndromo es una cadena igual a su reverso: w=wRw = w^R. Sobre {a,b}\{\mathtt{a}, \mathtt{b}\}, los más cortos son ε\varepsilon, a\mathtt{a} y b\mathtt{b}. Uno más largo empieza y termina con el mismo símbolo, y lo que queda en medio es otro palíndromo.

S→aSa∣bSb∣a∣b∣εS \to \mathtt{a}S\mathtt{a} \mid \mathtt{b}S\mathtt{b} \mid \mathtt{a} \mid \mathtt{b} \mid \varepsilon
$ build/show_cfg machines/palindromes.cfg 4
G = (V, Σ, R, S)
  V = {S}
  Σ = {a, b}
  S = S
  R tiene 5 reglas:
    S → aSa
    S → bSb
    S → a
    S → b
    S → ε
Cadenas de L(G) con longitud a lo sumo 4 (13):
  ε a b aa bb aaa aba bab bbb aaaa abba baab bbbb

Los casos base a\mathtt{a} y b\mathtt{b} dan los palíndromos de longitud impar, y ε\varepsilon los de longitud par.

Paréntesis balanceados

Una cadena de paréntesis está balanceada si ningún prefijo tiene más )\mathtt{)} que (\mathtt{(}, y la cadena completa tiene tantos de uno como de otro. La más corta es ε\varepsilon. Para una más larga, miren su primer símbolo: es un (\mathtt{(}, que se cierra en algún )\mathtt{)}. Lo que hay entre los dos está balanceado, y lo que sigue después también.

S→(S)S∣εS \to \mathtt{(}S\mathtt{)}S \mid \varepsilon
$ build/show_cfg machines/parens.cfg 6
G = (V, Σ, R, S)
  V = {S}
  Σ = {(, )}
  S = S
  R tiene 2 reglas:
    S → (S)S
    S → ε
Cadenas de L(G) con longitud a lo sumo 6 (9):
  ε () (()) ()() ((())) (()()) (())() ()(()) ()()()

Hay otra gramática para el mismo lenguaje, quizá más natural: una cadena balanceada es dos balanceadas seguidas, o una balanceada entre paréntesis, o nada.

S→SS∣(S)∣εS \to SS \mid \mathtt{(}S\mathtt{)} \mid \varepsilon

Está en machines/parens_ss.cfg, y genera lo mismo. Las dos gramáticas se comportan muy distinto, como veremos en El problema de la pertenencia y en los ejercicios.

Igual número de a y de b

L={ w∈{a,b}∗:w tiene tantas a como b }L = \{\, w \in \{\mathtt{a}, \mathtt{b}\}^* : w \text{ tiene tantas } \mathtt{a} \text{ como } \mathtt{b} \,\}. Aquí las a\mathtt{a} y las b\mathtt{b} van en cualquier orden: abba\mathtt{abba} y bbaa\mathtt{bbaa} están en LL. La gramática es

S→aSb∣bSa∣SS∣εS \to \mathtt{a}S\mathtt{b} \mid \mathtt{b}S\mathtt{a} \mid SS \mid \varepsilon
$ build/show_cfg machines/equal_ab.cfg 4
G = (V, Σ, R, S)
  V = {S}
  Σ = {a, b}
  S = S
  R tiene 4 reglas:
    S → aSb
    S → bSa
    S → SS
    S → ε
Cadenas de L(G) con longitud a lo sumo 4 (9):
  ε ab ba aabb abab abba baab baba bbaa

Que todo lo que genera tiene igual número de a\mathtt{a} y de b\mathtt{b} se ve en las reglas: cada una agrega una de cada o ninguna. Lo que no es obvio es la pregunta 3: ¿se obtienen todas? La cadena abba\mathtt{abba} no empieza con a\mathtt{a} y termina con b\mathtt{b}, ni al revés. Sale de la regla SSSS, como ab\mathtt{ab} seguida de ba\mathtt{ba}. Que siempre se pueda partir así hay que demostrarlo, y lo hacemos en la sección siguiente.

Error común. Olvidar el caso base. Con solo S→0S1S \to \mathtt{0}S\mathtt{1}, toda forma tiene una SS y ninguna derivación termina: la gramática genera ∅\emptyset, no {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}. Y al revés, una gramática cuya única regla es S→εS \to \varepsilon genera {ε}\{\varepsilon\}, que tiene una cadena. Es la diferencia entre ∅\emptyset y {ε}\{\varepsilon\} de la semana 1, ahora con gramáticas.

Unir gramáticas

Los lenguajes libres de contexto son cerrados bajo unión, y la construcción es de una línea. Si G1G_1 y G2G_2 generan L1L_1 y L2L_2, con variables iniciales S1S_1 y S2S_2, se renombran las variables para que las dos gramáticas no compartan ninguna, se juntan todas las reglas y se agrega una variable inicial nueva con

S→S1∣S2.S \to S_1 \mid S_2.

Una derivación desde SS elige en su primer paso con cuál de las dos gramáticas sigue. Como las variables no se comparten, desde S1S_1 solo se usan reglas de G1G_1 y se genera exactamente L1L_1, y lo mismo con S2S_2.

Sirve para diseñar: si el lenguaje es “esto o aquello”, se hace una gramática para cada parte. El lenguaje { aibjck:i=j o j=k }\{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i = j \text{ o } j = k \,\} es la unión de dos lenguajes parecidos a {0n1n}\{\mathtt{0}^n\mathtt{1}^n\}: en uno se emparejan las a\mathtt{a} con las b\mathtt{b} y las c\mathtt{c} van libres, y en el otro al revés. En machines/abc_union.cfg las dos partes ya están pegadas a la inicial:

S→XC∣AYX→aXb∣εC→cC∣εA→aA∣εY→bYc∣ε\begin{aligned} S &\to XC \mid AY \\ X &\to \mathtt{a}X\mathtt{b} \mid \varepsilon & \qquad C &\to \mathtt{c}C \mid \varepsilon \\ A &\to \mathtt{a}A \mid \varepsilon & \qquad Y &\to \mathtt{b}Y\mathtt{c} \mid \varepsilon \end{aligned}

XCXC genera las cadenas con i=ji = j, y AYAY las cadenas con j=kj = k. La misma idea con S→S1S2S \to S_1S_2 da la concatenación, y con S→S1S∣εS \to S_1S \mid \varepsilon da la estrella.

De un DFA a una gramática

Todo lenguaje regular es libre de contexto. Dado un DFA M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F), se construye una gramática con una variable por estado: la variable RqR_q va a generar las cadenas que llevan de qq a un estado de aceptación.

  • Por cada transición δ(q,a)=p\delta(q, a) = p, la regla Rq→aRpR_q \to aR_p.
  • Por cada estado de aceptación q∈Fq \in F, la regla Rq→εR_q \to \varepsilon.
  • La variable inicial es Rq0R_{q_0}.

Con el DFA de la paridad de unos de la semana 1, de estados par\mathit{par} e impar\mathit{impar}, y llamando PP e II a las dos variables, queda machines/even_ones.cfg:

P→0P∣1I∣εI→0I∣1P\begin{aligned} P &\to \mathtt{0}P \mid \mathtt{1}I \mid \varepsilon \\ I &\to \mathtt{0}I \mid \mathtt{1}P \end{aligned}

Una derivación copia la ejecución del autómata. La forma siempre es lo leído hasta ahora seguido de la variable del estado actual:

$ build/derive machines/even_ones.cfg 1001 --sin-arboles
w = 1001
derivaciones por la izquierda: 1

1. P ⇒ 1I ⇒ 10I ⇒ 100I ⇒ 1001P ⇒ 1001
   5 pasos

Los estados por los que pasa el DFA con 1001\mathtt{1001} son par\mathit{par}, impar\mathit{impar}, impar\mathit{impar}, impar\mathit{impar}, par\mathit{par}: las mismas variables, en el mismo orden. El último paso, P→εP \to \varepsilon, solo se puede dar porque par\mathit{par} es de aceptación. Lo que hay que demostrar es que Rq⇒∗wRpR_q \Rightarrow^* wR_p exactamente cuando δ∗(q,w)=p\delta^*(q, w) = p, por inducción sobre ∣w∣|w|, y queda como ejercicio.

En estas gramáticas la variable siempre queda al final de la forma. Por eso no pueden emparejar nada: no hay nada a la derecha de la variable. Lo que las gramáticas libres de contexto agregan a los lenguajes regulares es poder dejar la variable en medio.

Demostrar que una gramática genera un lenguaje

Afirmar que L(G)=LL(G) = L es afirmar la igualdad de dos conjuntos, y se demuestra con dos inclusiones:

  • L⊆L(G)L \subseteq L(G): toda cadena del lenguaje se puede derivar. La gramática no se queda corta.
  • L(G)⊆LL(G) \subseteq L: toda cadena que se deriva está en el lenguaje. La gramática no genera de más.

Cada una es una inducción, y suelen ser sobre cosas distintas. Para L⊆L(G)L \subseteq L(G) se toma una cadena de LL y se hace inducción sobre algo de la cadena, como su longitud, para construirle una derivación. Para L(G)⊆LL(G) \subseteq L se toma una derivación y se hace inducción sobre su número de pasos.

La demostración para 0ⁿ1ⁿ

Teorema. La gramática G1G_1, con reglas S→0S1∣εS \to \mathtt{0}S\mathtt{1} \mid \varepsilon, genera exactamente L={ 0n1n:n≥0 }L = \{\, \mathtt{0}^n\mathtt{1}^n : n \geq 0 \,\}.

Demostración. Por dos inclusiones.

Primera inclusión, L⊆L(G1)L \subseteq L(G_1). Demostramos por inducción sobre nn que S⇒∗0nS1nS \Rightarrow^* \mathtt{0}^nS\mathtt{1}^n para todo n≥0n \geq 0.

Caso base: n=0n = 0. 00S10=S\mathtt{0}^0S\mathtt{1}^0 = S, y S⇒∗SS \Rightarrow^* S con cero pasos.

Paso inductivo: supongamos S⇒∗0nS1nS \Rightarrow^* \mathtt{0}^nS\mathtt{1}^n. Aplicando la regla S→0S1S \to \mathtt{0}S\mathtt{1} a la única variable de esa forma:

S⇒∗0nS1n⇒0n 0S1 1n=0n+1S1n+1.S \Rightarrow^* \mathtt{0}^nS\mathtt{1}^n \Rightarrow \mathtt{0}^n\,\mathtt{0}S\mathtt{1}\,\mathtt{1}^n = \mathtt{0}^{n+1}S\mathtt{1}^{n+1}.

Con eso, para cualquier nn se tiene S⇒∗0nS1n⇒0n1nS \Rightarrow^* \mathtt{0}^nS\mathtt{1}^n \Rightarrow \mathtt{0}^n\mathtt{1}^n, donde el último paso usa S→εS \to \varepsilon. Luego 0n1n∈L(G1)\mathtt{0}^n\mathtt{1}^n \in L(G_1).

Segunda inclusión, L(G1)⊆LL(G_1) \subseteq L. Demostramos por inducción sobre kk la siguiente afirmación: si S⇒∗uS \Rightarrow^* u con exactamente kk pasos, entonces

u=0kS1kok≥1 y u=0k−11k−1.u = \mathtt{0}^kS\mathtt{1}^k \qquad \text{o} \qquad k \geq 1 \text{ y } u = \mathtt{0}^{k-1}\mathtt{1}^{k-1}.

Caso base: k=0k = 0. La única forma que se deriva con cero pasos es u=S=00S10u = S = \mathtt{0}^0S\mathtt{1}^0.

Paso inductivo: supongamos la afirmación para kk, y sea S⇒∗u′⇒uS \Rightarrow^* u' \Rightarrow u, donde la primera parte tiene kk pasos. Para dar un paso más, u′u' tiene que tener una variable. Por la hipótesis, u′u' es 0kS1k\mathtt{0}^kS\mathtt{1}^k o es una cadena sin variables, así que u′=0kS1ku' = \mathtt{0}^kS\mathtt{1}^k. Su única variable es esa SS, y hay dos reglas para ella:

  • con S→0S1S \to \mathtt{0}S\mathtt{1} queda u=0k+1S1k+1u = \mathtt{0}^{k+1}S\mathtt{1}^{k+1};
  • con S→εS \to \varepsilon queda u=0k1k=0(k+1)−11(k+1)−1u = \mathtt{0}^k\mathtt{1}^k = \mathtt{0}^{(k+1)-1}\mathtt{1}^{(k+1)-1}.

Las dos son las formas que la afirmación permite para k+1k + 1.

Ahora, si w∈L(G1)w \in L(G_1), entonces S⇒∗wS \Rightarrow^* w con algún número kk de pasos, y ww no tiene variables. Por la afirmación, k≥1k \geq 1 y w=0k−11k−1w = \mathtt{0}^{k-1}\mathtt{1}^{k-1}, que está en LL. ∎

La segunda inclusión demostró más de lo que se pedía: describió todas las formas que la gramática puede producir, y no solo las cadenas finales. Es lo mismo que pasaba con los DFA en la semana 1, donde para demostrar algo sobre los estados de aceptación había que decir qué significaba cada estado. Aquí, para demostrar algo sobre las cadenas terminadas hay que decir cómo es cada forma a medio terminar. La afirmación también dice que la derivación de 0n1n\mathtt{0}^n\mathtt{1}^n es una sola y tiene n+1n + 1 pasos, como la de 000111\mathtt{000111} que imprimió derive, de 4 pasos. La misma demostración, cambiando 0\mathtt{0} por a\mathtt{a} y 1\mathtt{1} por b\mathtt{b}, sirve para S→aSb∣εS \to \mathtt{a}S\mathtt{b} \mid \varepsilon y {anbn}\{\mathtt{a}^n\mathtt{b}^n\}.

La demostración para igual número de a y de b

Esta es más interesante, porque la inclusión difícil es la otra.

Teorema. La gramática G2G_2, con reglas S→aSb∣bSa∣SS∣εS \to \mathtt{a}S\mathtt{b} \mid \mathtt{b}S\mathtt{a} \mid SS \mid \varepsilon, genera exactamente el lenguaje LL de las cadenas sobre {a,b}\{\mathtt{a}, \mathtt{b}\} con tantas a\mathtt{a} como b\mathtt{b}.

Demostración. Por dos inclusiones.

Primera inclusión, L(G2)⊆LL(G_2) \subseteq L. Demostramos que toda forma uu con S⇒∗uS \Rightarrow^* u tiene tantas a\mathtt{a} como b\mathtt{b}, por inducción sobre el número de pasos. Con cero pasos, u=Su = S tiene cero de cada una. Y cada regla reemplaza una SS por algo que tiene una a\mathtt{a} y una b\mathtt{b} (aSb\mathtt{a}S\mathtt{b} y bSa\mathtt{b}S\mathtt{a}) o ninguna de las dos (SSSS y ε\varepsilon): si las cantidades eran iguales antes del paso, lo son después. En particular, las formas sin variables, que son las cadenas de L(G2)L(G_2), están en LL.

Segunda inclusión, L⊆L(G2)L \subseteq L(G_2). Demostramos por inducción sobre ∣w∣|w| que toda w∈Lw \in L cumple S⇒∗wS \Rightarrow^* w. La inducción es fuerte: se supone el resultado para todas las cadenas de LL más cortas que ww.

Caso base: w=εw = \varepsilon. S⇒εS \Rightarrow \varepsilon por la regla S→εS \to \varepsilon.

Paso inductivo: sea w∈Lw \in L con ∣w∣≥1|w| \geq 1. Como tiene tantas a\mathtt{a} como b\mathtt{b}, su longitud es par y ∣w∣≥2|w| \geq 2. Hay tres casos, según su primer y su último símbolo.

Caso 1: ww empieza con a\mathtt{a} y termina con b\mathtt{b}. Entonces w=axbw = \mathtt{a}x\mathtt{b}, y xx tiene una a\mathtt{a} menos y una b\mathtt{b} menos que ww: está en LL y es más corta. Por la hipótesis, S⇒∗xS \Rightarrow^* x, y por el lema del contexto,

S⇒aSb⇒∗axb=w.S \Rightarrow \mathtt{a}S\mathtt{b} \Rightarrow^* \mathtt{a}x\mathtt{b} = w.

Caso 2: ww empieza con b\mathtt{b} y termina con a\mathtt{a}. Igual, con la regla S→bSaS \to \mathtt{b}S\mathtt{a}.

Caso 3: ww empieza y termina con el mismo símbolo. Digamos que es a\mathtt{a}; con b\mathtt{b} el argumento es el mismo cambiando los signos. Para cada ii de 00 a ∣w∣|w|, sea d(i)d(i) el número de a\mathtt{a} menos el número de b\mathtt{b} en el prefijo de ww de longitud ii. Sabemos que:

  • d(0)=0d(0) = 0 y d(∣w∣)=0d(|w|) = 0, porque w∈Lw \in L;
  • d(1)=1d(1) = 1, porque el primer símbolo es a\mathtt{a};
  • d(∣w∣−1)=−1d(|w| - 1) = -1, porque el último símbolo es a\mathtt{a} y con él se llega a d(∣w∣)=0d(|w|) = 0;
  • de d(i)d(i) a d(i+1)d(i + 1) el valor cambia en exactamente 11, hacia arriba o hacia abajo.

Una cantidad que va de 11 a −1-1 con pasos de tamaño 11 pasa por 00: hay un ii con 1<i<∣w∣−11 < i < |w| - 1 y d(i)=0d(i) = 0. Partimos w=xyw = xy con ∣x∣=i|x| = i. El prefijo xx tiene tantas a\mathtt{a} como b\mathtt{b} porque d(i)=0d(i) = 0, y entonces yy también, porque ww las tiene. Las dos cadenas están en LL, no son vacías y son más cortas que ww. Por la hipótesis, S⇒∗xS \Rightarrow^* x y S⇒∗yS \Rightarrow^* y, y por el lema del contexto, usado dos veces,

S⇒SS⇒∗xS⇒∗xy=w.S \Rightarrow SS \Rightarrow^* xS \Rightarrow^* xy = w.

En los tres casos S⇒∗wS \Rightarrow^* w. ∎

El caso 3 es el que justifica la regla S→SSS \to SS, y muestra una técnica que vuelve mucho: seguir una cantidad a lo largo de los prefijos de la cadena. Con abba\mathtt{abba}, los valores de dd son 0,1,0,−1,00, 1, 0, -1, 0: el cero del medio parte la cadena en ab\mathtt{ab} y ba\mathtt{ba}.

Error común. Demostrar una sola inclusión. “Toda cadena que la gramática genera tiene igual número de a\mathtt{a} y de b\mathtt{b}” también es cierto para la gramática S→aSb∣εS \to \mathtt{a}S\mathtt{b} \mid \varepsilon, que no genera ba\mathtt{ba}. Y “toda cadena del lenguaje se genera” también es cierto para una gramática de Σ∗\Sigma^*. Hacen falta las dos.

Las pruebas de la semana comprueban las dos inclusiones de otra manera: para cada gramática de machines/ calculan todas las cadenas que genera hasta cierta longitud, y las comparan una por una con una función de C++ que decide el lenguaje mirando la cadena. Eso no reemplaza la demostración, que vale para todas las longitudes, pero encuentra enseguida una regla que falta o que sobra.

Ambigüedad

Las expresiones aritméticas con suma, producto y paréntesis tienen una gramática de una línea. La llamamos G3G_3:

E→E+E∣E×E∣(E)∣aE \to E + E \mid E \times E \mid (E) \mid \mathtt{a}

En los archivos el producto se escribe *, porque un terminal es un solo carácter del teclado. La gramática está en machines/expr_ambiguous.cfg, y genera las expresiones correctas. El problema aparece al pedirle la estructura de una:

$ build/derive machines/expr_ambiguous.cfg 'a+a*a'
w = a+a*a
derivaciones por la izquierda: 2

1. E ⇒ E+E ⇒ a+E ⇒ a+E*E ⇒ a+a*E ⇒ a+a*a
   5 pasos
   E
   ├── E
   │   └── a
   ├── +
   └── E
       ├── E
       │   └── a
       ├── *
       └── E
           └── a

2. E ⇒ E*E ⇒ E+E*E ⇒ a+E*E ⇒ a+a*E ⇒ a+a*a
   5 pasos
   E
   ├── E
   │   ├── E
   │   │   └── a
   │   ├── +
   │   └── E
   │       └── a
   ├── *
   └── E
       └── a

Son dos árboles distintos para la misma cadena. En el primero la raíz es una suma, y su operando derecho es el producto: es a+(a×a)\mathtt{a} + (\mathtt{a} \times \mathtt{a}). En el segundo la raíz es un producto, y su operando izquierdo es la suma: es (a+a)×a(\mathtt{a} + \mathtt{a}) \times \mathtt{a}. Con 2+3×42 + 3 \times 4, el primer árbol vale 14 y el segundo vale 20. Un compilador que usara esta gramática no sabría cuál calcular.

Los dos árboles de derivación de a+a×a con la gramática ambigua, lado a lado, cada uno con su derivación por la izquierda. En el árbol 1 la raíz E tiene tres hijos: E, el signo + y E. La primera E deriva a, y la segunda, resaltada, tiene los hijos E, × y E, que derivan a cada una: el operando derecho de la suma es el producto, la agrupación es a + (a × a), y con 2 + 3 × 4 da 2 + 12 = 14. En el árbol 2 la raíz E tiene los hijos E, × y E. La primera E, resaltada, tiene los hijos E, + y E, y la última deriva a: el operando izquierdo del producto es la suma, la agrupación es (a + a) × a, y con 2 + 3 × 4 da 5 × 4 = 20. Las hojas de los dos árboles dicen la misma cadenaLos dos árboles de derivación de a+a×a con la gramática ambigua, lado a lado, cada uno con su derivación por la izquierda. En el árbol 1 la raíz E tiene tres hijos: E, el signo + y E. La primera E deriva a, y la segunda, resaltada, tiene los hijos E, × y E, que derivan a cada una: el operando derecho de la suma es el producto, la agrupación es a + (a × a), y con 2 + 3 × 4 da 2 + 12 = 14. En el árbol 2 la raíz E tiene los hijos E, × y E. La primera E, resaltada, tiene los hijos E, + y E, y la última deriva a: el operando izquierdo del producto es la suma, la agrupación es (a + a) × a, y con 2 + 3 × 4 da 5 × 4 = 20. Las hojas de los dos árboles dicen la misma cadena
Los dos árboles que imprimió derive, de pie. La cadena es la misma; lo que cambia es qué operación queda debajo de la otra, y con eso el resultado.

Una cadena tiene una derivación ambigua si tiene dos o más árboles de derivación distintos. Una gramática es ambigua (ambiguous) si genera alguna cadena con dos o más árboles de derivación distintos. Como cada árbol corresponde a una sola derivación por la izquierda, es lo mismo decir: alguna cadena tiene dos o más derivaciones por la izquierda distintas.

La ambigüedad de G3G_3 no viene solo de mezclar operadores. Con un solo operador ya aparece:

$ build/derive machines/expr_ambiguous.cfg 'a+a+a' --sin-arboles
w = a+a+a
derivaciones por la izquierda: 2

1. E ⇒ E+E ⇒ E+E+E ⇒ a+E+E ⇒ a+a+E ⇒ a+a+a
   5 pasos

2. E ⇒ E+E ⇒ a+E ⇒ a+E+E ⇒ a+a+E ⇒ a+a+a
   5 pasos

Una agrupa (a+a)+a(\mathtt{a} + \mathtt{a}) + \mathtt{a} y la otra a+(a+a)\mathtt{a} + (\mathtt{a} + \mathtt{a}). Para la suma el resultado es el mismo, pero para la resta no lo sería. La regla E→E+EE \to E + E no dice de qué lado se agrupa.

Error común. Llamar ambigua a una gramática porque una cadena tiene dos derivaciones. Casi toda cadena tiene muchas derivaciones: con S→ABS \to AB, A→aA \to \mathtt{a}, B→bB \to \mathtt{b}, la cadena ab\mathtt{ab} tiene dos, según se reemplace primero AA o BB, y esa gramática no es ambigua, porque las dos tienen el mismo árbol. Lo que cuenta son dos árboles distintos o, lo que es igual, dos derivaciones por la izquierda distintas. Para mostrar que una gramática es ambigua se exhibe una cadena y sus dos árboles.

La gramática de expresiones con niveles de precedencia

Para el mismo lenguaje hay una gramática que no es ambigua. La idea es darle un nivel a cada operador, con una variable por nivel:

E→E+T∣TT→T×F∣FF→(E)∣a\begin{aligned} E &\to E + T \mid T \\ T &\to T \times F \mid F \\ F &\to (E) \mid \mathtt{a} \end{aligned}
  • Una expresión EE es una suma de términos.
  • Un término TT es un producto de factores.
  • Un factor FF es una a\mathtt{a} o una expresión entre paréntesis.

Dos decisiones de diseño quitan las dos fuentes de ambigüedad.

Los niveles dan la precedencia. Un producto solo puede tener factores como operandos, y una suma no es un factor, salvo que vaya entre paréntesis. Así, en a+a×a\mathtt{a+a\times a} el producto no puede tener a la suma como operando: la única manera de leerla es como la suma de a\mathtt{a} y de a×a\mathtt{a \times a}.

La recursión de un solo lado da la asociatividad. La regla es E→E+TE \to E + T, y no E→E+EE \to E + E: a la derecha de un ++ va un término, que no puede contener otra suma sin paréntesis. Entonces a+a+a\mathtt{a+a+a} solo se puede agrupar como (a+a)+a(\mathtt{a} + \mathtt{a}) + \mathtt{a}, por la izquierda, que es como se calculan la suma y la resta.

$ build/derive machines/expr_precedence.cfg 'a+a*a'
w = a+a*a
derivaciones por la izquierda: 1

1. E ⇒ E+T ⇒ T+T ⇒ F+T ⇒ a+T ⇒ a+T*F ⇒ a+F*F ⇒ a+a*F ⇒ a+a*a
   8 pasos
   E
   ├── E
   │   └── T
   │       └── F
   │           └── a
   ├── +
   └── T
       ├── T
       │   └── F
       │       └── a
       ├── *
       └── F
           └── a

Un solo árbol, con el producto debajo de la suma. El precio es que el árbol es más alto: para llegar de EE a una a\mathtt{a} hay que bajar por TT y por FF, con las reglas E→TE \to T y T→FT \to F, que no agregan ningún símbolo. Esas reglas, de una variable a otra variable, se llaman reglas unitarias, y vuelven en la sesión B.

El único árbol de a+a×a con la gramática de niveles. La raíz E tiene tres hijos: E, el signo + y T. La E de la izquierda baja por T y por F hasta la primera a. La T de la derecha, dentro de un recuadro resaltado, tiene tres hijos: T, que baja por F hasta la segunda a; el signo ×; y F, que deriva la tercera a. A la derecha, las reglas con el color de cada variable: E → E + T | T, una expresión es una suma de términos; T → T × F | F, un término es un producto de factores; F → (E) | a, un factor es una a o una expresión entre paréntesis. Dos notas: el producto a × a es un solo término T y queda entero debajo de la suma; E → T y T → F son reglas unitarias, que bajan de nivel sin agregar símbolos. Abajo, la única derivación por la izquierda, de 8 pasosEl único árbol de a+a×a con la gramática de niveles. La raíz E tiene tres hijos: E, el signo + y T. La E de la izquierda baja por T y por F hasta la primera a. La T de la derecha, dentro de un recuadro resaltado, tiene tres hijos: T, que baja por F hasta la segunda a; el signo ×; y F, que deriva la tercera a. A la derecha, las reglas con el color de cada variable: E → E + T | T, una expresión es una suma de términos; T → T × F | F, un término es un producto de factores; F → (E) | a, un factor es una a o una expresión entre paréntesis. Dos notas: el producto a × a es un solo término T y queda entero debajo de la suma; E → T y T → F son reglas unitarias, que bajan de nivel sin agregar símbolos. Abajo, la única derivación por la izquierda, de 8 pasos
Con un nivel por operador, el producto es un término completo: no hay manera de que la suma quede debajo de él sin paréntesis.

Las dos gramáticas generan el mismo lenguaje. Son equivalentes: L(G3)L(G_3) es igual al lenguaje de la gramática con niveles. Lo que cambia es cuántos árboles tiene cada cadena. Que la gramática con niveles no es ambigua se puede demostrar, mostrando que en cada nodo la cadena deja una sola regla posible, y no lo haremos aquí. Las pruebas de la semana comprueban las dos cosas hasta donde alcanzan: que las dos gramáticas generan las mismas cadenas de hasta 7 símbolos, y que cada una de esas cadenas tiene exactamente una derivación por la izquierda en la gramática con niveles.

Idea clave. La ambigüedad es una propiedad de la gramática, no del lenguaje. El mismo lenguaje puede tener una gramática ambigua y otra que no lo es. Y la gramática no solo decide qué cadenas son correctas: decide qué árbol tiene cada una, y con el árbol, qué significa.

En la práctica. Los generadores de parsers, como yacc y bison, aceptan la gramática ambigua de una línea si se les declara aparte la precedencia y la asociatividad de cada operador. Por dentro hacen lo mismo que la gramática con niveles. La tabla de precedencia de operadores de C++, con sus más de quince niveles, es esa declaración.

El else colgante

El ejemplo más conocido de ambigüedad en un lenguaje de programación. Una instrucción puede ser un if sin else, un if con else, o cualquier otra cosa. Abreviando if (condición) como i\mathtt{i}, else como e\mathtt{e} y cualquier otra instrucción como a\mathtt{a}:

S→iS∣iSeS∣aS \to \mathtt{i}S \mid \mathtt{i}S\mathtt{e}S \mid \mathtt{a}

La cadena iiaea\mathtt{iiaea} es este fragmento de C++:

if (c1) if (c2) f(); else g();

¿De cuál de los dos if es el else?

$ build/derive machines/dangling_else.cfg iiaea
w = iiaea
derivaciones por la izquierda: 2

1. S ⇒ iS ⇒ iiSeS ⇒ iiaeS ⇒ iiaea
   4 pasos
   S
   ├── i
   └── S
       ├── i
       ├── S
       │   └── a
       ├── e
       └── S
           └── a

2. S ⇒ iSeS ⇒ iiSeS ⇒ iiaeS ⇒ iiaea
   4 pasos
   S
   ├── i
   ├── S
   │   ├── i
   │   └── S
   │       └── a
   ├── e
   └── S
       └── a

En el primer árbol el else es del if de adentro: si c1 es falso no se ejecuta nada. En el segundo es del if de afuera: si c1 es falso se ejecuta g(). Son dos programas distintos.

C, C++, Java y casi todos los lenguajes eligen el primero: el else va con el if más cercano que todavía no tiene uno. Esa convención se puede escribir en la gramática, separando las instrucciones en las que todo if tiene su else, que llamamos MM, de las que tienen algún if sin else, que llamamos UU:

S→M∣UM→iMeM∣aU→iS∣iMeU\begin{aligned} S &\to M \mid U \\ M &\to \mathtt{i}M\mathtt{e}M \mid \mathtt{a} \\ U &\to \mathtt{i}S \mid \mathtt{i}M\mathtt{e}U \end{aligned}

La regla M→iMeMM \to \mathtt{i}M\mathtt{e}M exige que lo que está entre un if y su else sea una instrucción completa, sin ningún if suelto que pudiera reclamar ese else. Con esta gramática, que está en machines/dangling_else_fixed.cfg, iiaea\mathtt{iiaea} tiene una sola derivación por la izquierda,

S⇒U⇒iS⇒iM⇒iiMeM⇒iiaeM⇒iiaea,S \Rightarrow U \Rightarrow \mathtt{i}S \Rightarrow \mathtt{i}M \Rightarrow \mathtt{ii}M\mathtt{e}M \Rightarrow \mathtt{iia}\mathtt{e}M \Rightarrow \mathtt{iiaea},

que es la salida de build/derive machines/dangling_else_fixed.cfg iiaea: el if de afuera no tiene else, y el de adentro sí.

En la práctica. Los lenguajes reales casi nunca escriben la gramática corregida, que es más difícil de leer. Dejan la ambigua y agregan la regla en palabras, y el parser la aplica: cuando puede elegir entre seguir leyendo un else o dar por terminado el if, sigue leyendo. Otros lenguajes evitan el problema desde la sintaxis: Python con la indentación, y Go y Rust exigiendo llaves en cada rama.

Lenguajes inherentemente ambiguos

En los dos ejemplos, una gramática ambigua se cambió por otra equivalente que no lo es. No siempre se puede. Un lenguaje libre de contexto es inherentemente ambiguo si todas las gramáticas que lo generan son ambiguas. Existen, y un ejemplo es el lenguaje de la sección Unir gramáticas:

{ aibjck:i=j o j=k }.\{\, \mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i = j \text{ o } j = k \,\}.

Lo enunciamos sin demostrarlo: la demostración es larga y no la necesitaremos. La intuición sí se ve en la gramática machines/abc_union.cfg. Una cadena con i=j=ki = j = k, como abc\mathtt{abc}, está en las dos mitades de la unión, y tiene un árbol por cada una:

$ build/derive machines/abc_union.cfg abc --sin-arboles
w = abc
derivaciones por la izquierda: 2

1. S ⇒ XC ⇒ aXbC ⇒ abC ⇒ abcC ⇒ abc
   5 pasos

2. S ⇒ AY ⇒ aAY ⇒ aY ⇒ abYc ⇒ abc
   5 pasos

Lo que el teorema dice es que ninguna otra gramática lo arregla: cualquier gramática de este lenguaje tiene alguna cadena con dos árboles.

Tampoco hay un algoritmo general que reciba una gramática y decida si es ambigua. Es un problema indecidible, una palabra que tendrá un sentido preciso desde la semana 9; este resultado llega en la semana 10. Para una gramática concreta se puede buscar una cadena con dos árboles, como hace derive, y si aparece, la gramática es ambigua. Si no aparece entre las cadenas cortas, eso no demuestra nada.

El problema de la pertenencia

La sesión B responde una sola pregunta, que se llama el problema de la pertenencia:

dadas una gramaˊtica G y una cadena w, ¿G genera w?\text{dadas una gramática } G \text{ y una cadena } w, \text{ ¿} G \text{ genera } w \text{?}

Con un DFA la pregunta equivalente no tenía dificultad: se sigue la única ejecución, un paso por símbolo, y se mira el estado final. Una gramática no trae un procedimiento así. La definición dice que w∈L(G)w \in L(G) si existe una derivación, y no dice cómo encontrarla.

El primer intento es buscarla: probar derivaciones, todas, hasta que alguna termine en ww. Es lo que hace derive, que además descarta un camino en cuanto los terminales ya escritos a la izquierda no coinciden con ww. Con las gramáticas de la sesión A funcionó. Con la segunda gramática de los paréntesis, S→SS∣(S)∣εS \to SS \mid \mathtt{(}S\mathtt{)} \mid \varepsilon, pasa esto:

$ build/derive machines/parens_ss.cfg '()' --pasos 5 --sin-arboles
w = ()
derivaciones por la izquierda: 4 (la búsqueda se cortó: derivaciones de hasta 5 pasos, 20 como máximo)

1. S ⇒ SS ⇒ (S)S ⇒ ()S ⇒ ()
   4 pasos

2. S ⇒ SS ⇒ S ⇒ (S) ⇒ ()
   4 pasos

3. S ⇒ (S) ⇒ (SS) ⇒ (S) ⇒ ()
   4 pasos

4. S ⇒ (S) ⇒ ()
   2 pasos

La opción --pasos 5 le pone un tope a la búsqueda: solo mira derivaciones de hasta 5 pasos. Sin tope no terminaría. La derivación 2 muestra por qué: S⇒SS⇒SS \Rightarrow SS \Rightarrow S usa S→SSS \to SS y después S→εS \to \varepsilon, y vuelve a donde empezó. Ese rodeo se puede repetir cuantas veces se quiera, así que la cadena ()\mathtt{()} tiene infinitas derivaciones por la izquierda. Con el tope en 7 pasos el programa ya encuentra 14.

Tener infinitas derivaciones de una cadena que sí se genera es incómodo. Lo grave es el otro caso: con una cadena que no se genera, como )(\mathtt{)(}, la búsqueda sigue probando rodeos sin fin, y nunca puede responder “no”. Hay dos tipos de regla que permiten dar pasos sin avanzar:

  • las reglas ε\varepsilon, A→εA \to \varepsilon, que acortan la forma: después de crecer con S→SSS \to SS, la forma vuelve a encogerse;
  • las reglas unitarias, A→BA \to B, que cambian una variable por otra sin agregar nada. Con A→BA \to B y B→AB \to A se puede dar vueltas sin fin.

Sin esas reglas, cada paso de una derivación alarga la forma o convierte una variable en terminales, y eso no se puede hacer para siempre si la cadena final tiene nn símbolos. El plan de la sesión es ese:

  1. Mostrar que toda gramática se puede reescribir sin reglas ε\varepsilon y sin reglas unitarias, en una forma muy rígida, la forma normal de Chomsky. Con ella las derivaciones tienen una longitud conocida, y la búsqueda termina siempre.
  2. Ver que aun así la búsqueda tarda un tiempo exponencial.
  3. Cambiar la búsqueda por una tabla: el algoritmo CYK, que responde en tiempo polinomial.

La forma normal de Chomsky

Una gramática G=(V,Σ,R,S)G = (V, \Sigma, R, S) está en forma normal de Chomsky (Chomsky normal form) si cada una de sus reglas tiene una de estas formas:

A→BCcon B y C variables, ninguna de las dos la variable inicialA→acon a un terminalS→εsolo para la variable inicial S\begin{aligned} A &\to BC && \text{con } B \text{ y } C \text{ variables, ninguna de las dos la variable inicial} \\ A &\to a && \text{con } a \text{ un terminal} \\ S &\to \varepsilon && \text{solo para la variable inicial } S \end{aligned}

A la derecha de una regla hay exactamente dos variables o exactamente un terminal. La única excepción es la regla S→εS \to \varepsilon, que hace falta cuando ε\varepsilon está en el lenguaje, porque ninguna de las otras dos formas puede generarla. Y como la variable inicial no aparece a la derecha de ninguna regla, esa regla ε\varepsilon solo se puede usar como el único paso de la derivación S⇒εS \Rightarrow \varepsilon: nunca en medio de otra derivación.

Ninguna gramática de la sesión A está en esta forma. S→0S1S \to \mathtt{0}S\mathtt{1} tiene tres símbolos a la derecha y mezcla terminales con variables, E→TE \to T es unitaria, y en S→(S)S∣εS \to \mathtt{(}S\mathtt{)}S \mid \varepsilon la variable inicial aparece a la derecha y tiene una regla ε\varepsilon. Una gramática en forma normal de Chomsky para { anbn:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^n : n \geq 0 \,\} es esta:

S0→AT∣AB∣εS→AT∣ABT→SBA→aB→b\begin{aligned} S_0 &\to AT \mid AB \mid \varepsilon \\ S &\to AT \mid AB \\ T &\to SB \\ A &\to \mathtt{a} \qquad B \to \mathtt{b} \end{aligned}

Es menos legible que S→aSb∣εS \to \mathtt{a}S\mathtt{b} \mid \varepsilon, y no se pretende que una persona escriba así. La forma normal es para los algoritmos y para las demostraciones, que solo tienen que considerar dos formas de regla. La primera consecuencia es esta.

Teorema (longitud de las derivaciones). Sea GG una gramática en forma normal de Chomsky y sea w∈L(G)w \in L(G) con ∣w∣=n≥1|w| = n \geq 1. Toda derivación de ww tiene exactamente 2n−12n - 1 pasos.

Demostración. Contando. Tomemos una derivación S⇒⋯⇒wS \Rightarrow \cdots \Rightarrow w. Como w≠εw \neq \varepsilon, no usa la regla S→εS \to \varepsilon: esa regla solo se le puede aplicar a la variable inicial, que solo aparece en la primera forma, y aplicarla ahí da ε\varepsilon. Entonces cada paso usa una regla A→BCA \to BC o una regla A→aA \to a. Sean pp y qq cuántas veces se usa cada tipo.

  • Un paso con A→BCA \to BC alarga la forma en exactamente un símbolo, y un paso con A→aA \to a no cambia su longitud. La forma empieza con longitud 1 y termina con longitud nn. Luego p=n−1p = n - 1.
  • Un paso con A→aA \to a escribe exactamente un terminal, los pasos con A→BCA \to BC no escriben ninguno, y un terminal ya escrito no se borra ni se cambia. La cadena final tiene nn terminales. Luego q=nq = n.

En total son p+q=(n−1)+n=2n−1p + q = (n - 1) + n = 2n - 1 pasos. ∎

Dicho con el árbol: es un árbol binario con nn hojas, que tiene n−1n - 1 nodos con dos hijos, más un nodo encima de cada hoja. La cadena vacía, cuando está en el lenguaje, tiene la derivación de un paso S⇒εS \Rightarrow \varepsilon.

El teorema arregla el primer problema de la búsqueda. Para saber si GG genera ww alcanza con probar las derivaciones de 2n−12n - 1 pasos, que son una cantidad finita: la búsqueda termina siempre, y puede responder “no”. Queda el segundo problema, que es cuántas son. El programa search_cost busca así, con una gramática en forma normal de Chomsky de los paréntesis balanceados, y cuenta cuántos pasos de derivación llega a probar. La primera línea prepara esa gramática con el programa de la sección siguiente.

$ build/to_chomsky machines/parens_ss.cfg > build/parens_ss_cnf.cfg
$ build/search_cost build/parens_ss_cnf.cfg '()((' '()()((' '()()()((' '()()()()((' '()()()()()((' '()()()()()()((' '()()()()()()()((' '()()()()()()()()'
  n   respuesta    pasos probados   comprobaciones de CYK   cadena
  4   no genera                22                      80   ()((
  6   no genera                64                     280   ()()((
  8   no genera               179                     672   ()()()((
 10   no genera               513                    1320   ()()()()((
 12   no genera              1535                    2288   ()()()()()((
 14   no genera              4792                    3640   ()()()()()()((
 16   no genera             15496                    5440   ()()()()()()()((
 16   genera                   62                    5440   ()()()()()()()()

Las siete primeras cadenas son pares ()\mathtt{()} seguidos de ((\mathtt{((}: no están balanceadas, y la búsqueda solo lo descubre al final, después de agotar todas las maneras de derivar el comienzo. Cada vez que la cadena crece en dos símbolos, los pasos probados se multiplican por cerca de 3: es un crecimiento exponencial. A ese ritmo, la cadena de 100 símbolos del laboratorio pediría más de 102010^{20} pasos. La última fila muestra que con una cadena que sí se genera la búsqueda puede tener suerte y encontrar pronto una derivación. El costo está en responder “no”.

La columna de CYK crece mucho más despacio, y no depende de la respuesta. Ese algoritmo es el final del capítulo. Antes hay que saber llevar cualquier gramática a la forma normal.

La conversión en cuatro pasos

Teorema. Todo lenguaje libre de contexto es generado por una gramática en forma normal de Chomsky.

Demostración. Por construcción. Dada una gramática GG cualquiera, se le aplican cuatro transformaciones, en este orden:

  1. agregar una variable inicial nueva;
  2. quitar las reglas ε\varepsilon;
  3. quitar las reglas unitarias;
  4. partir las reglas largas y sacar los terminales de las reglas de dos símbolos.

De cada paso hay que decir qué se construye, por qué el lenguaje no cambia, y qué queda garantizado para los pasos siguientes. Lo hacemos en las cuatro subsecciones que siguen, con un mismo ejemplo: la gramática machines/blocks.cfg, que genera listas de bloques 0n1n\mathtt{0}^n\mathtt{1}^n con n≥1n \geq 1, como 0101\mathtt{0101} o 001101\mathtt{001101}.

S→BS∣εB→0B1∣01\begin{aligned} S &\to BS \mid \varepsilon \\ B &\to \mathtt{0}B\mathtt{1} \mid \mathtt{01} \end{aligned}

El programa to_chomsky --pasos imprime la gramática después de cada paso. Su salida está repartida en las subsecciones.

$ build/to_chomsky machines/blocks.cfg --pasos
La gramática original (4 reglas)
  S -> B S | eps
  B -> 0 B 1 | 0 1

Paso 1: una variable inicial nueva

Qué se construye. Se agrega una variable nueva S0S_0, con la única regla S0→SS_0 \to S, y S0S_0 pasa a ser la variable inicial.

Paso 1: variable inicial nueva (5 reglas)
  S0 -> S
  S -> B S | eps
  B -> 0 B 1 | 0 1

Por qué el lenguaje no cambia. Toda derivación desde S0S_0 empieza con S0⇒SS_0 \Rightarrow S, el único paso posible, y sigue como una derivación de la gramática original. Y toda derivación original S⇒∗wS \Rightarrow^* w se convierte en una nueva poniéndole ese paso delante.

Qué queda garantizado. La variable inicial no aparece a la derecha de ninguna regla. S0S_0 es nueva, así que ninguna regla anterior la menciona, y los pasos siguientes no la van a poner a la derecha. En el ejemplo se ve por qué importa: la SS original aparece en S→BSS \to BS y tiene una regla ε\varepsilon, las dos cosas que la forma normal prohíbe juntas.

Paso 2: quitar las reglas ε

Una variable AA es anulable si A⇒∗εA \Rightarrow^* \varepsilon. Las variables anulables se calculan marcando, como los estados alcanzables de un autómata:

  • se marca AA si tiene la regla A→εA \to \varepsilon;
  • se marca AA si tiene una regla A→X1⋯XkA \to X_1 \cdots X_k en la que todos los XiX_i son variables ya marcadas;
  • se repite hasta que no se pueda marcar ninguna más.

Las marcadas son exactamente las anulables. Una variable marcada deriva ε\varepsilon: lo hace con la regla que la marcó, seguida de las derivaciones de las variables que estaban marcadas antes. Y una variable que deriva ε\varepsilon termina marcada, por inducción sobre el número de pasos de esa derivación: su primer paso es una regla A→X1⋯XkA \to X_1 \cdots X_k donde, por el lema de separación, cada XiX_i deriva ε\varepsilon con menos pasos, así que cada XiX_i es una variable que se marca, y entonces AA también.

En el ejemplo, SS es anulable por S→εS \to \varepsilon, y S0S_0 lo es por S0→SS_0 \to S. BB no lo es.

Qué se construye. Por cada regla A→X1⋯XkA \to X_1 \cdots X_k se ponen todas las reglas que se obtienen borrando algunas apariciones de variables anulables del lado derecho: ninguna, una, varias o todas, de todas las maneras posibles. La única que no se pone es la que queda con el lado derecho vacío. Así desaparecen todas las reglas ε\varepsilon. Al final, si la variable inicial S0S_0 es anulable, se le agrega la regla S0→εS_0 \to \varepsilon.

Paso 2: sin reglas ε (6 reglas)
  S0 -> S | eps
  S -> B S | B
  B -> 0 B 1 | 0 1

La regla S→BSS \to BS tiene una aparición de una variable anulable, la SS de la derecha. Sin borrarla queda S→BSS \to BS, y borrándola queda S→BS \to B. La regla S0→SS_0 \to S queda igual sin borrar, y borrando quedaría vacía, así que no se pone. La regla S→εS \to \varepsilon desaparece, y S0S_0 recibe la suya.

La idea es adelantar la decisión. En la gramática original, una derivación usaba S→BSS \to BS y más tarde decidía que esa segunda SS desaparecía. En la nueva, lo decide en el momento de elegir la regla: usa S→BS \to B y la SS nunca llega a escribirse.

Por qué el lenguaje no cambia. Llamemos GG a la gramática antes del paso y G′G' a la de después. Escribimos ⇒G\Rightarrow_G y ⇒G′\Rightarrow_{G'} para distinguir con cuál se deriva. Demostramos que para toda variable AA y toda cadena de terminales w≠εw \neq \varepsilon:

A⇒G∗wsi y solo siA⇒G′∗w sin usar la regla S0→ε.A \Rightarrow_G^* w \quad \text{si y solo si} \quad A \Rightarrow_{G'}^* w \text{ sin usar la regla } S_0 \to \varepsilon.

De derecha a izquierda. Cada regla A→u′A \to u' de G′G' distinta de S0→εS_0 \to \varepsilon sale de una regla A→uA \to u de GG borrando apariciones de variables anulables. En GG se puede hacer lo mismo con más pasos: A⇒GuA \Rightarrow_G u, y después cada variable borrada se deriva en ε\varepsilon, lo que el lema del contexto permite. Entonces A⇒G∗u′A \Rightarrow_G^* u', y cada paso de una derivación de G′G' se reemplaza por varios de GG.

De izquierda a derecha. Por inducción sobre el número de pasos de A⇒G∗wA \Rightarrow_G^* w. La derivación tiene al menos un paso, porque AA es una variable y ww no. Sea A→X1⋯XkA \to X_1 \cdots X_k la regla de su primer paso. Por el lema de separación, w=w1⋯wkw = w_1 \cdots w_k con Xi⇒G∗wiX_i \Rightarrow_G^* w_i, cada una con menos pasos que la derivación completa. Miramos cada XiX_i:

  • si wi=εw_i = \varepsilon, entonces XiX_i es una variable anulable, y la borramos;
  • si wi≠εw_i \neq \varepsilon y XiX_i es un terminal, entonces wi=Xiw_i = X_i, y lo dejamos;
  • si wi≠εw_i \neq \varepsilon y XiX_i es una variable, la dejamos, y por la hipótesis de inducción Xi⇒G′∗wiX_i \Rightarrow_{G'}^* w_i sin usar S0→εS_0 \to \varepsilon.

Como w≠εw \neq \varepsilon, algún wiw_i no es vacío y no se borró todo: lo que queda de X1⋯XkX_1 \cdots X_k es el lado derecho de una regla de G′G'. Con esa regla como primer paso, y derivando después cada símbolo que quedó en su wiw_i, se obtiene A⇒G′∗wA \Rightarrow_{G'}^* w.

Con A=S0A = S_0, la equivalencia dice que GG y G′G' generan las mismas cadenas no vacías: la regla S0→εS_0 \to \varepsilon no agrega ninguna, porque S0S_0 no aparece a la derecha de ninguna regla, y entonces esa regla solo sirve para la derivación S0⇒εS_0 \Rightarrow \varepsilon. Y sobre la cadena vacía: las demás reglas de G′G' tienen el lado derecho no vacío, así que sin S0→εS_0 \to \varepsilon una forma nunca se queda sin símbolos. Luego ε∈L(G′)\varepsilon \in L(G') exactamente cuando se agregó esa regla, que es cuando S0S_0 es anulable, que es cuando ε∈L(G)\varepsilon \in L(G).

Qué queda garantizado. No hay reglas ε\varepsilon, salvo quizá S0→εS_0 \to \varepsilon, y la variable inicial sigue sin aparecer a la derecha.

Este paso puede crear reglas unitarias. En el ejemplo apareció S→BS \to B, que antes no estaba. Por eso el paso siguiente va después, y no antes.

Paso 3: quitar las reglas unitarias

Una regla unitaria A→BA \to B dice que todo lo que BB puede hacer, AA también puede. La idea es darle a AA directamente las reglas de BB.

Decimos que (A,B)(A, B) es un par unitario si A⇒∗BA \Rightarrow^* B usando solo reglas unitarias. Todo (A,A)(A, A) es un par unitario, con cero pasos. Los pares se calculan marcando, igual que las variables anulables: se empieza con los (A,A)(A, A), y si (A,B)(A, B) está marcado y B→CB \to C es una regla unitaria, se marca (A,C)(A, C).

En el ejemplo, las reglas unitarias son S0→SS_0 \to S y S→BS \to B. Los pares, además de los (A,A)(A, A), son (S0,S)(S_0, S), (S,B)(S, B) y (S0,B)(S_0, B).

Qué se construye. Por cada par unitario (A,B)(A, B) y cada regla B→uB \to u que no es unitaria, se pone la regla A→uA \to u. Las reglas unitarias no se ponen.

Paso 3: sin reglas unitarias (9 reglas)
  S0 -> eps | B S | 0 B 1 | 0 1
  S -> B S | 0 B 1 | 0 1
  B -> 0 B 1 | 0 1

S0S_0 recibe sus propias reglas no unitarias, que es solo ε\varepsilon; las de SS, por el par (S0,S)(S_0, S), que es BSBS; y las de BB, por el par (S0,B)(S_0, B). SS recibe la suya y las de BB.

Por qué el lenguaje no cambia. Sean GG la gramática antes del paso y G′G' la de después. Demostramos que para toda variable AA y toda cadena de terminales ww: A⇒G∗wA \Rightarrow_G^* w si y solo si A⇒G′∗wA \Rightarrow_{G'}^* w.

De derecha a izquierda. Cada regla A→uA \to u de G′G' viene de un par unitario (A,B)(A, B) y de una regla B→uB \to u de GG. Entonces en GG se tiene A⇒G∗B⇒GuA \Rightarrow_G^* B \Rightarrow_G u, y cada paso de G′G' se reemplaza por varios de GG.

De izquierda a derecha. Por inducción sobre el número de pasos de A⇒G∗wA \Rightarrow_G^* w, que es al menos 1. Miramos la regla del primer paso.

  • No es unitaria: es A→X1⋯XkA \to X_1 \cdots X_k. Como (A,A)(A, A) es un par unitario, la misma regla está en G′G'. Por el lema de separación, w=w1⋯wkw = w_1 \cdots w_k con Xi⇒G∗wiX_i \Rightarrow_G^* w_i en menos pasos, y por la hipótesis de inducción Xi⇒G′∗wiX_i \Rightarrow_{G'}^* w_i para cada variable XiX_i. Juntando, A⇒G′X1⋯Xk⇒G′∗wA \Rightarrow_{G'} X_1 \cdots X_k \Rightarrow_{G'}^* w.
  • Es unitaria: es A→BA \to B, y entonces B⇒G∗wB \Rightarrow_G^* w con un paso menos. Por la hipótesis de inducción, B⇒G′∗wB \Rightarrow_{G'}^* w. Esa derivación tiene un primer paso, con una regla B→uB \to u de G′G', que por construcción viene de un par unitario (B,C)(B, C) y una regla no unitaria C→uC \to u de GG. Como A→BA \to B es unitaria y (B,C)(B, C) es un par, (A,C)(A, C) también es un par unitario, y entonces A→uA \to u está en G′G'. Cambiando el primer paso por A⇒G′uA \Rightarrow_{G'} u y dejando el resto igual, queda A⇒G′∗wA \Rightarrow_{G'}^* w.

Qué queda garantizado. No hay reglas unitarias. Tampoco aparecieron reglas ε\varepsilon nuevas: las reglas de G′G' son copias de lados derechos que ya estaban, y la única regla ε\varepsilon que había, S0→εS_0 \to \varepsilon, solo se le puede copiar a una variable AA con (A,S0)(A, S_0) par unitario. Como S0S_0 no aparece a la derecha de ninguna regla, el único par así es (S0,S0)(S_0, S_0). Y S0S_0 sigue sin aparecer a la derecha.

Después de este paso, cada regla es S0→εS_0 \to \varepsilon, o tiene a la derecha un solo terminal, o tiene dos o más símbolos.

Paso 4: partir las reglas largas

Quedan dos defectos: lados derechos con tres o más símbolos, y terminales mezclados en lados derechos de dos o más símbolos.

Qué se construye. Primero, cada regla A→X1X2⋯XkA \to X_1X_2 \cdots X_k con k≥3k \geq 3 se cambia por una cadena de k−1k - 1 reglas de dos símbolos, con k−2k - 2 variables nuevas A1,…,Ak−2A_1, \ldots, A_{k-2} que no se usan en ningún otro lugar:

A→X1A1,A1→X2A2,…,Ak−2→Xk−1Xk.A \to X_1A_1, \quad A_1 \to X_2A_2, \quad \ldots, \quad A_{k-2} \to X_{k-1}X_k.

La variable AiA_i significa “lo que falta de la regla”: Xi+1⋯XkX_{i+1} \cdots X_k. Después, en cada regla de dos símbolos, cada terminal aa se cambia por una variable nueva UaU_a, y se agrega la regla Ua→aU_a \to a. Hay una sola UaU_a por terminal.

Paso 4: reglas de a lo sumo dos símbolos, y terminales solos (14 reglas)
  S0 -> eps | B S | U_0 S0_1 | U_0 U_1
  S -> B S | U_0 S_1 | U_0 U_1
  B -> U_0 B_1 | 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

Está en forma normal de Chomsky.

La regla B→0B1B \to \mathtt{0}B\mathtt{1} se partió en B→0B1B \to \mathtt{0}B_1 y B1→B1B_1 \to B\mathtt{1}, y con los terminales cambiados quedó B→U0B1B \to U_0B_1 y B1→BU1B_1 \to BU_1. El programa nombra B_1 a la primera variable nueva de las reglas de B. Como S0S_0 y SS recibieron en el paso 3 una copia de esa regla, cada una tiene su propia variable nueva, S0_1 y S_1, con el mismo lado derecho.

Por qué el lenguaje no cambia. Sean GG la gramática antes del paso y G′G' la de después.

Todo lo que GG deriva, G′G' lo deriva: un paso de GG con la regla A→X1⋯XkA \to X_1 \cdots X_k se reemplaza por los pasos de la cadena de reglas nuevas, seguidos de un paso Ua⇒aU_a \Rightarrow a por cada terminal que se cambió.

Para el otro sentido, a cada variable de G′G' se le asigna lo que representa en GG: una variable original se representa a sí misma, AiA_i representa la cadena Xi+1⋯XkX_{i+1} \cdots X_k de su regla, y UaU_a representa el terminal aa. Escribimos μ(Y)\mu(Y) para lo que representa YY, y μ\mu de un terminal es él mismo. Mirando las reglas de G′G' una por una (salvo S0→εS_0 \to \varepsilon, que está igual en las dos gramáticas) se comprueba que, para cada regla Y→Z1Z2Y \to Z_1Z_2 o Y→aY \to a, se tiene μ(Y)⇒G∗μ(Z1)μ(Z2)\mu(Y) \Rightarrow_G^* \mu(Z_1)\mu(Z_2) o μ(Y)⇒G∗a\mu(Y) \Rightarrow_G^* a, con un paso si YY es una variable original (es su regla de GG) y con cero si es nueva (los dos lados son la misma cadena). De ahí, por inducción sobre el número de pasos y con el lema de separación, igual que en los pasos anteriores: si Y⇒G′∗wY \Rightarrow_{G'}^* w, entonces μ(Y)⇒G∗w\mu(Y) \Rightarrow_G^* w. Con Y=S0Y = S_0, que se representa a sí misma, todo lo que G′G' genera lo genera GG.

Qué queda garantizado. Cada regla tiene ahora a la derecha un solo terminal, o exactamente dos símbolos que son variables, o es S0→εS_0 \to \varepsilon. La variable inicial no aparece a la derecha. Eso es la forma normal de Chomsky, y como ningún paso cambió el lenguaje, la gramática final genera L(G)L(G). ∎

El resultado y lo que cuesta

Sin opciones, to_chomsky escribe el resultado como un archivo .cfg, que se puede guardar o pasar a otro programa:

$ build/to_chomsky machines/blocks.cfg
# machines/blocks.cfg en forma normal de Chomsky.
variables: S0 S B S0_1 S_1 B_1 U_0 U_1
terminals: 0 1
start: S0
rules:
S0 -> eps | B S | U_0 S0_1 | U_0 U_1
S -> B S | U_0 S_1 | U_0 U_1
B -> U_0 B_1 | 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

La gramática pasó de 2 variables y 4 reglas a 8 variables y 14 reglas. Es el precio normal de la conversión. Las pruebas de la semana convierten las catorce gramáticas de machines/ que no están ya convertidas y comprueban, después de cada paso, que la gramática sigue generando las mismas cadenas hasta cierta longitud, y que cumple lo que el paso garantiza.

Cinco bloques unidos por flechas, con la gramática de blocks.cfg después de cada paso de la conversión; las alternativas que cada paso agrega están resaltadas. Original, 4 reglas: S → BS | ε y B → 0B1 | 01. Paso 1, variable inicial nueva, 5 reglas: se agrega S0 → S, y S0 no aparece a la derecha. Paso 2, sin reglas ε, 6 reglas: S0 → S | ε y S → BS | B; las anulables son S y S0, y aparece la regla unitaria S → B. Paso 3, sin reglas unitarias, 9 reglas: S0 → ε | BS | 0B1 | 01, S → BS | 0B1 | 01 y B → 0B1 | 01; los pares unitarios son (S0, S), (S, B) y (S0, B). Paso 4, reglas de dos variables y terminales solos, 14 reglas: S0 → ε | B S | U_0 S0_1 | U_0 U_1, S → B S | U_0 S_1 | U_0 U_1, B → U_0 B_1 | U_0 U_1, las tres reglas S0_1, S_1 y B_1 → B U_1, y U_0 → 0, U_1 → 1: forma normal de ChomskyCinco bloques unidos por flechas, con la gramática de blocks.cfg después de cada paso de la conversión; las alternativas que cada paso agrega están resaltadas. Original, 4 reglas: S → BS | ε y B → 0B1 | 01. Paso 1, variable inicial nueva, 5 reglas: se agrega S0 → S, y S0 no aparece a la derecha. Paso 2, sin reglas ε, 6 reglas: S0 → S | ε y S → BS | B; las anulables son S y S0, y aparece la regla unitaria S → B. Paso 3, sin reglas unitarias, 9 reglas: S0 → ε | BS | 0B1 | 01, S → BS | 0B1 | 01 y B → 0B1 | 01; los pares unitarios son (S0, S), (S, B) y (S0, B). Paso 4, reglas de dos variables y terminales solos, 14 reglas: S0 → ε | B S | U_0 S0_1 | U_0 U_1, S → B S | U_0 S_1 | U_0 U_1, B → U_0 B_1 | U_0 U_1, las tres reglas S0_1, S_1 y B_1 → B U_1, y U_0 → 0, U_1 → 1: forma normal de Chomsky
Los cuatro pasos de un vistazo. Cada paso arregla un defecto y deja la gramática lista para el siguiente; el lenguaje es el mismo en los cinco bloques.

Error común. Quitar las reglas unitarias antes que las reglas ε\varepsilon. Quitar reglas ε\varepsilon crea reglas unitarias: de A→BCA \to BC con BB anulable sale A→CA \to C. Si las unitarias ya se quitaron, esas quedan en el resultado. Con la gramática S→AB∣aS \to AB \mid \mathtt{a}, A→a∣εA \to \mathtt{a} \mid \varepsilon, B→bB \to \mathtt{b}, y los pasos 2 y 3 intercambiados:

$ build/to_chomsky machines/unit_order.cfg --unitarias-primero
La gramática original (5 reglas)
  S -> A B | a
  A -> a | eps
  B -> b

Paso 1: variable inicial nueva (6 reglas)
  S0 -> S
  S -> A B | a
  A -> a | eps
  B -> b

Paso 3 antes de tiempo: sin reglas unitarias (7 reglas)
  S0 -> A B | a
  S -> A B | a
  A -> a | eps
  B -> b

Paso 2, tarde: sin reglas ε (8 reglas)
  S0 -> A B | B | a
  S -> A B | B | a
  A -> a
  B -> b

Paso 4: reglas de a lo sumo dos símbolos, y terminales solos (8 reglas)
  S0 -> A B | B | a
  S -> A B | B | a
  A -> a
  B -> b

No está en forma normal de Chomsky. S0 -> B: es una regla unitaria.

El lenguaje sigue siendo el mismo, porque cada paso por separado es correcto. Lo que se pierde es la forma. En el otro sentido no hay problema: quitar reglas unitarias no crea reglas ε\varepsilon, como se vio en el paso 3.

El orden de los demás pasos también tiene su razón. El paso 1 va primero porque el paso 2 necesita una variable inicial que no aparezca a la derecha, para poder dejarle su regla ε\varepsilon sin que nadie más la use. El paso 4 se puede dejar para el final porque no crea reglas ε\varepsilon ni unitarias: lo que los pasos 2 y 3 limpiaron sigue limpio.

En la práctica. El paso 2 puede multiplicar las reglas. Una regla con kk apariciones de variables anulables a la derecha tiene 2k2^k maneras de borrar, y puede dejar casi 2k2^k reglas. Con reglas cortas no importa. Un programa que convierte gramáticas grandes parte primero las reglas largas y después quita las reglas ε\varepsilon: con lados derechos de a lo sumo dos símbolos, cada regla deja a lo sumo tres. Los ejercicios piden comprobar que ese otro orden también termina en la forma normal.

El algoritmo CYK

El algoritmo se llama CYK por Cocke, Younger y Kasami, que lo encontraron cada uno por su cuenta. Recibe una gramática GG en forma normal de Chomsky y una cadena ww de longitud nn, y decide si GG genera ww.

La idea es la programación dinámica sobre intervalos que vieron en Algoritmos: en lugar de preguntar solo por la cadena completa, se pregunta por todas sus subcadenas, de las más cortas a las más largas, y cada respuesta se guarda en una tabla para no calcularla dos veces. La búsqueda de la sección anterior tardaba tanto porque volvía a derivar el mismo trozo de la cadena una y otra vez, dentro de derivaciones distintas.

La tabla y su recurrencia

Numeramos los símbolos de la cadena desde 0: w=w0w1⋯wn−1w = w_0w_1 \cdots w_{n-1}. Para 0≤i≤j<n0 \leq i \leq j < n, la subcadena de ii a jj es wi⋯wjw_i \cdots w_j, con los dos extremos incluidos. La tabla tiene una celda por cada subcadena, y la celda guarda un conjunto de variables:

T[i][j]={ A∈V:A⇒∗wi⋯wj }.T[i][j] = \{\, A \in V : A \Rightarrow^* w_i \cdots w_j \,\}.

Esa es la definición de la tabla: lo que queremos que contenga. La respuesta al problema está en una sola celda: GG genera ww si y solo si S∈T[0][n−1]S \in T[0][n-1], donde SS es la variable inicial. Lo que hace falta es una manera de calcular cada celda a partir de otras, y la forma normal de Chomsky la da.

Teorema (la recurrencia de CYK). Sea GG una gramática en forma normal de Chomsky. Para toda cadena ww de longitud n≥1n \geq 1 y todos los 0≤i≤j<n0 \leq i \leq j < n:

T[i][i]={ A:A→wi es una regla }T[i][i] = \{\, A : A \to w_i \text{ es una regla} \,\}

y, si i<ji < j,

T[i][j]=⋃k=ij−1{ A:A→BC es una regla, B∈T[i][k], C∈T[k+1][j] }.T[i][j] = \bigcup_{k=i}^{j-1} \{\, A : A \to BC \text{ es una regla},\ B \in T[i][k],\ C \in T[k+1][j] \,\}.

La segunda igualdad dice: AA genera la subcadena de ii a jj si se la puede cortar en dos trozos no vacíos, de ii a kk y de k+1k + 1 a jj, de modo que alguna regla A→BCA \to BC tenga una BB que genera el primero y una CC que genera el segundo. El número kk es el punto de corte: la última posición del primer trozo.

Demostración. Antes, una observación. En forma normal de Chomsky, si BB no es la variable inicial y B⇒∗xB \Rightarrow^* x con xx una cadena de terminales, entonces x≠εx \neq \varepsilon. La razón: la única regla que acorta una forma es S→εS \to \varepsilon, y solo se le aplica a la variable inicial, que no aparece en ninguna forma derivada de BB, porque no está a la derecha de ninguna regla. Las demás reglas no acortan, así que una forma que empieza con un símbolo nunca queda vacía.

Primera igualdad. Si A→wiA \to w_i es una regla, entonces A⇒wiA \Rightarrow w_i y A∈T[i][i]A \in T[i][i]. Al revés, si A⇒∗wiA \Rightarrow^* w_i, miramos la regla del primer paso. No es S→εS \to \varepsilon, que daría la cadena vacía. No es una regla A→BCA \to BC: por el lema de separación, wiw_i se partiría en un trozo de BB y otro de CC, los dos no vacíos por la observación, y wiw_i tiene un solo símbolo. Entonces es una regla A→aA \to a, la derivación termina ahí, y a=wia = w_i.

Segunda igualdad, de derecha a izquierda. Si hay una regla A→BCA \to BC y un kk con B⇒∗wi⋯wkB \Rightarrow^* w_i \cdots w_k y C⇒∗wk+1⋯wjC \Rightarrow^* w_{k+1} \cdots w_j, entonces, por el lema del contexto,

A⇒BC⇒∗wi⋯wk C⇒∗wi⋯wk wk+1⋯wj,A \Rightarrow BC \Rightarrow^* w_i \cdots w_k\, C \Rightarrow^* w_i \cdots w_k\, w_{k+1} \cdots w_j,

y A∈T[i][j]A \in T[i][j].

Segunda igualdad, de izquierda a derecha. Sea A∈T[i][j]A \in T[i][j] con i<ji < j: AA deriva una cadena de al menos dos símbolos. La regla del primer paso no es S→εS \to \varepsilon, ni es A→aA \to a, que daría un solo símbolo. Es una regla A→BCA \to BC, y BC⇒∗wi⋯wjBC \Rightarrow^* w_i \cdots w_j. Por el lema de separación, esa subcadena se parte en xyxy con B⇒∗xB \Rightarrow^* x y C⇒∗yC \Rightarrow^* y. Como BB y CC no son la variable inicial, la observación dice que xx e yy no son vacías. Entonces x=wi⋯wkx = w_i \cdots w_k para algún kk con i≤k<ji \leq k < j, e y=wk+1⋯wjy = w_{k+1} \cdots w_j. Eso es B∈T[i][k]B \in T[i][k] y C∈T[k+1][j]C \in T[k+1][j]. ∎

La demostración usó las tres condiciones de la forma normal. Que no haya reglas ε\varepsilon garantiza que los dos trozos no son vacíos, y por eso son más cortos que la subcadena completa. Que no haya reglas unitarias garantiza que una celda no depende de sí misma. Que cada regla tenga dos variables a la derecha garantiza que alcanza con un punto de corte.

Para la cadena vacía no hay tabla, porque no hay ninguna celda. Se responde aparte: GG genera ε\varepsilon si y solo si S→εS \to \varepsilon es una de sus reglas.

El algoritmo

La recurrencia calcula una celda de una subcadena de longitud ℓ\ell a partir de celdas de subcadenas más cortas. Entonces la tabla se llena por longitudes crecientes: primero todas las celdas de longitud 1, después las de longitud 2, y así hasta la única celda de longitud nn.

algoritmo CYK(G, w)
    n ← longitud de w
    si n = 0 entonces
        devolver (S → ε es una regla de G)
    fin si
    para i desde 0 hasta n - 1
        T[i][i] ← { A : A → w[i] es una regla de G }
    fin para
    para largo desde 2 hasta n
        para i desde 0 hasta n - largo
            j ← i + largo - 1
            T[i][j] ← ∅
            para k desde i hasta j - 1
                para cada regla A → B C de G
                    si B está en T[i][k] y C está en T[k+1][j] entonces
                        agregar A a T[i][j]
                    fin si
                fin para
            fin para
        fin para
    fin para
    devolver (S está en T[0][n-1])
fin algoritmo

El algoritmo es correcto porque calcula exactamente los conjuntos del teorema: por inducción sobre el largo, cuando llega a la celda T[i][j]T[i][j] ya están calculadas las celdas T[i][k]T[i][k] y T[k+1][j]T[k+1][j] que consulta, que son de subcadenas más cortas.

Error común. Llenar la tabla por filas, i=0,1,2,…i = 0, 1, 2, \ldots, y dentro de cada fila por columnas. La celda T[0][4]T[0][4] consulta T[1][4]T[1][4], T[2][4]T[2][4], T[3][4]T[3][4] y T[4][4]T[4][4], que están en filas de abajo y todavía estarían vacías. El orden es por longitud de la subcadena. Si se prefiere recorrer por filas, hay que hacerlo de abajo hacia arriba, con ii de n−1n - 1 a 00.

La tabla, llena a mano

El ejemplo es la cadena a+a×a\mathtt{a+a\times a}, de cinco símbolos, con la gramática ambigua de expresiones G3G_3 convertida a forma normal de Chomsky. La conversión la hace to_chomsky, y el resultado está guardado en machines/expr_ambiguous_chomsky.cfg:

$ build/to_chomsky machines/expr_ambiguous.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_) -> )

Para leerla: E_1 es “un ++ y una expresión”, lo que falta de la regla E→E+EE \to E + E después de su primera EE. E_2 es “un ×\times y una expresión”, y E_3 es “una expresión y un paréntesis que cierra”. La variable inicial E0 tiene una copia de las reglas de E, con sus propias variables E0_1, E0_2, E0_3.

Los símbolos de la cadena son w0=aw_0 = \mathtt{a}, w1=+w_1 = \mathtt{+}, w2=aw_2 = \mathtt{a}, w3=×w_3 = \mathtt{\times}, w4=aw_4 = \mathtt{a}.

Longitud 1. Cada celda T[i][i]T[i][i] tiene las variables con la regla A→wiA \to w_i. Para a\mathtt{a} son E0 y E. Para +\mathtt{+} es U_+, y para ×\mathtt{\times} es U_*.

Longitud 2. Cada celda tiene un solo punto de corte.

  • T[0][1]T[0][1], la subcadena a+\mathtt{a+}: se buscan reglas A→BCA \to BC con BB en T[0][0]T[0][0], que tiene E0 y E, y CC en T[1][1]T[1][1], que tiene U_+. No hay ninguna regla con E U_+ ni con E0 U_+ a la derecha: la celda es ∅\emptyset. Ninguna variable genera a+\mathtt{a+}, que no es una expresión ni un trozo con nombre.
  • T[1][2]T[1][2], la subcadena +a\mathtt{+a}: con BB igual a U_+ y CC igual a E están las reglas E0_1 -> U_+ E y E_1 -> U_+ E. La celda tiene E0_1 y E_1.
  • T[2][3]T[2][3], la subcadena a×\mathtt{a\times}: ∅\emptyset, como T[0][1]T[0][1].
  • T[3][4]T[3][4], la subcadena ×a\mathtt{\times a}: tiene E0_2 y E_2, por las reglas con U_* E a la derecha.

Longitud 3. Dos puntos de corte por celda.

  • T[0][2]T[0][2], la subcadena a+a\mathtt{a+a}. Con k=0k = 0: BB en T[0][0]T[0][0], que tiene E0 y E, y CC en T[1][2]T[1][2], que tiene E0_1 y E_1. Las reglas E0 -> E E0_1 y E -> E E_1 sirven. Con k=1k = 1: T[0][1]=∅T[0][1] = \emptyset, nada. La celda tiene E0 y E: a+a\mathtt{a+a} es una expresión.
  • T[1][3]T[1][3], la subcadena +a×\mathtt{+a\times}. Con k=1k = 1 hace falta CC en T[2][3]T[2][3], que es ∅\emptyset. Con k=2k = 2, BB sería E0_1 o E_1 y CC sería U_*, y ninguna regla tiene ese lado derecho. La celda es ∅\emptyset.
  • T[2][4]T[2][4], la subcadena a×a\mathtt{a\times a}: con k=2k = 2 sirven las reglas E0 -> E E0_2 y E -> E E_2, y con k=3k = 3 no hay nada porque T[2][3]=∅T[2][3] = \emptyset. La celda tiene E0 y E.

Longitud 4. Tres puntos de corte por celda.

  • T[0][3]T[0][3], la subcadena a+a×\mathtt{a+a\times}: con k=0k = 0 hace falta T[1][3]T[1][3], que es ∅\emptyset; con k=1k = 1, T[0][1]=∅T[0][1] = \emptyset; con k=2k = 2, BB sería E0 o E y CC sería U_*, sin regla. La celda es ∅\emptyset.
  • T[1][4]T[1][4], la subcadena +a×a\mathtt{+a\times a}: con k=1k = 1, BB es U_+ y en T[2][4]T[2][4] está E. Las reglas E0_1 -> U_+ E y E_1 -> U_+ E sirven. Con k=2k = 2 no hay regla con E_1 o E0_1 seguida de E_2 o E0_2, y con k=3k = 3, T[1][3]=∅T[1][3] = \emptyset. La celda tiene E0_1 y E_1.

Longitud 5. La celda T[0][4]T[0][4], con cuatro puntos de corte.

  • k=0k = 0: BB en T[0][0]T[0][0], que tiene E0 y E, y CC en T[1][4]T[1][4], que tiene E0_1 y E_1. Sirven E0 -> E E0_1 y E -> E E_1. Es la lectura a\mathtt{a} más a×a\mathtt{a \times a}.
  • k=1k = 1: T[0][1]=∅T[0][1] = \emptyset.
  • k=2k = 2: BB en T[0][2]T[0][2], que tiene E0 y E, y CC en T[3][4]T[3][4], que tiene E0_2 y E_2. Sirven E0 -> E E0_2 y E -> E E_2. Es la lectura a+a\mathtt{a + a} por a\mathtt{a}.
  • k=3k = 3: T[0][3]=∅T[0][3] = \emptyset.

La celda tiene E0 y E. La variable inicial E0 está en T[0][4]T[0][4]: la gramática genera la cadena. El programa cyk llena la misma tabla:

$ build/cyk machines/expr_ambiguous_chomsky.cfg 'a+a*a'
w = a+a*a, n = 5
       j=0 a       j=1 +       j=2 a       j=3 *       j=4 a
i=0  a {E0,E}      ∅           {E0,E}      ∅           {E0,E}
i=1  +             {U_+}       {E0_1,E_1}  ∅           {E0_1,E_1}
i=2  a                         {E0,E}      ∅           {E0,E}
i=3  *                                     {U_*}       {E0_2,E_2}
i=4  a                                                 {E0,E}
E0 está en T[0][4]: genera
comprobaciones de reglas A → BC: 240
árboles de derivación: 2. Uno de ellos:
E0
├── E
│   └── a
└── E0_1
    ├── U_+
    │   └── +
    └── E
        ├── E
        │   └── a
        └── E_2
            ├── U_*
            │   └── *
            └── E
                └── a
[E0 [E a] [E0_1 [U_+ +] [E [E a] [E_2 [U_* *] [E a]]]]]

La fila ii y la columna jj tienen la celda T[i][j]T[i][j]. Solo se usa la mitad de arriba de la diagonal, porque i≤ji \leq j. La diagonal son las subcadenas de un símbolo, y la esquina de arriba a la derecha es la cadena completa. Llenar por longitudes es llenar por diagonales, desde la principal hacia esa esquina.

Animación de CYK llenando la tabla de a+a*a, una tabla triangular con una fila por i y una columna por j. Al comienzo la tabla está vacía. Longitud 1: se llena la diagonal, con {E0,E} en las tres celdas de a, {U_+} en la de + y {U_*} en la de *. Después se llena una celda por paso, resaltada en oro; para cada punto de corte k se resaltan con un mismo color la celda de su fila y la celda de su columna que se combinan, y debajo se escribe qué reglas sirven. Longitud 2: T[0][1] queda ∅ porque ninguna regla tiene ese lado derecho; T[1][2] queda con {E0_1,E_1}; T[2][3] queda ∅; T[3][4] queda con {E0_2,E_2}. Longitud 3: T[0][2] queda con {E0,E} por el corte k = 0; T[1][3] queda ∅; T[2][4] queda con {E0,E} por el corte k = 2. Longitud 4: T[0][3] queda ∅ con sus tres cortes; T[1][4] queda con {E0_1,E_1} por el corte k = 1. Longitud 5: la esquina T[0][4] queda con {E0,E} por dos cortes, k = 0 con T[0][0] y T[1][4], y k = 2 con T[0][2] y T[3][4]. La variable inicial E0 está en la esquina: la gramática genera la cadenaAnimación de CYK llenando la tabla de a+a*a, una tabla triangular con una fila por i y una columna por j. Al comienzo la tabla está vacía. Longitud 1: se llena la diagonal, con {E0,E} en las tres celdas de a, {U_+} en la de + y {U_*} en la de *. Después se llena una celda por paso, resaltada en oro; para cada punto de corte k se resaltan con un mismo color la celda de su fila y la celda de su columna que se combinan, y debajo se escribe qué reglas sirven. Longitud 2: T[0][1] queda ∅ porque ninguna regla tiene ese lado derecho; T[1][2] queda con {E0_1,E_1}; T[2][3] queda ∅; T[3][4] queda con {E0_2,E_2}. Longitud 3: T[0][2] queda con {E0,E} por el corte k = 0; T[1][3] queda ∅; T[2][4] queda con {E0,E} por el corte k = 2. Longitud 4: T[0][3] queda ∅ con sus tres cortes; T[1][4] queda con {E0_1,E_1} por el corte k = 1. Longitud 5: la esquina T[0][4] queda con {E0,E} por dos cortes, k = 0 con T[0][0] y T[1][4], y k = 2 con T[0][2] y T[3][4]. La variable inicial E0 está en la esquina: la gramática genera la cadena
La tabla de arriba, llenándose. Cada celda mira solo celdas de su fila, a su izquierda, y de su columna, debajo: todas son de subcadenas más cortas y ya están calculadas.

Idea clave. CYK no busca una derivación de la cadena. Calcula, para cada subcadena, todas las variables que la generan, de las subcadenas más cortas a las más largas. Cada celda se calcula una vez, y todas las derivaciones que pasan por esa subcadena la comparten.

Recuperar el árbol

La tabla dice que la cadena se genera, y con un poco más de trabajo dice cómo. Cada vez que una variable AA entra a la celda T[i][j]T[i][j] es por una regla A→BCA \to BC y un punto de corte kk. Esos tres datos son un nodo del árbol: AA arriba, con un hijo BB para la subcadena de ii a kk y un hijo CC para la de k+1k + 1 a jj.

Para armar el árbol se empieza en la variable inicial y la celda T[0][n−1]T[0][n-1], se busca una regla y un corte que justifiquen esa entrada, y se repite con cada hijo en su celda, hasta llegar a las celdas de la diagonal, donde el nodo es AA con un solo hijo, el terminal wiw_i. La regla y el corte se pueden guardar al llenar la tabla o, como hace chomsky.h, se vuelven a buscar al armar el árbol: para cada nodo hay que revisar a lo sumo todos los cortes y todas las reglas una vez.

El árbol que imprimió cyk salió del corte k=0k = 0 de la celda T[0][4]T[0][4], el primero que encuentra. Es la lectura a+(a×a)\mathtt{a} + (\mathtt{a} \times \mathtt{a}). Con el corte k=2k = 2 habría salido el otro. La celda T[0][4]T[0][4] tiene a E0 por dos caminos, y cada camino es un árbol: la ambigüedad de la gramática se ve en la tabla como una variable que entra a una celda de más de una manera. El programa cuenta los árboles con la misma tabla, guardando en cada celda cuántos árboles tiene cada variable en lugar de un sí o un no, y por eso informa árboles de derivación: 2, los mismos dos que encontró derive en la sesión A.

A la izquierda, la tabla de CYK de a+a*a ya llena, con resaltadas las celdas por las que pasa el árbol y, en cada una, la variable que se usa. A la derecha, el árbol que imprime cyk, con la celda de cada variable escrita debajo. La raíz es E0 en T[0][4]; sus hijos son E en T[0][0], que deriva la primera a, y E0_1 en T[1][4]. Los hijos de E0_1 son U_+ en T[1][1], que deriva +, y E en T[2][4]. Los hijos de esa E son E en T[2][2], que deriva a, y E_2 en T[3][4]. Los hijos de E_2 son U_* en T[3][3], que deriva *, y E en T[4][4], que deriva la última a. Una nota dice que E0 entra a T[0][4] por la regla E0 → E E0_1 con el corte k = 0, y que con el corte k = 2 habría salido el otro árbolA la izquierda, la tabla de CYK de a+a*a ya llena, con resaltadas las celdas por las que pasa el árbol y, en cada una, la variable que se usa. A la derecha, el árbol que imprime cyk, con la celda de cada variable escrita debajo. La raíz es E0 en T[0][4]; sus hijos son E en T[0][0], que deriva la primera a, y E0_1 en T[1][4]. Los hijos de E0_1 son U_+ en T[1][1], que deriva +, y E en T[2][4]. Los hijos de esa E son E en T[2][2], que deriva a, y E_2 en T[3][4]. Los hijos de E_2 son U_* en T[3][3], que deriva *, y E en T[4][4], que deriva la última a. Una nota dice que E0 entra a T[0][4] por la regla E0 → E E0_1 con el corte k = 0, y que con el corte k = 2 habría salido el otro árbol
Cada nodo del árbol es una variable en una celda. El punto de corte dice en qué dos celdas están sus hijos, y así se baja desde la esquina hasta la diagonal.

El árbol es de la gramática convertida, con sus variables auxiliares. Para tener el árbol de la gramática original se deshacen los pasos: un nodo E0_1 con hijos U_+ y E vuelve a ser parte de la regla E→E+EE \to E + E de su padre.

En C++. En chomsky.h la tabla es un std::vector<std::vector<std::set<std::string>>>: cell[i][j] es el conjunto de nombres de variables de T[i][j]T[i][j], tal como en la definición. Preguntar si una variable está en una celda es cell[i][k].count(B) > 0, que compara nombres. Para los ejemplos del capítulo sobra. En el laboratorio, donde importa el tiempo, conviene numerar las variables y guardar cada celda como un std::vector<bool> o como los bits de un entero.

El costo de CYK

Sea nn la longitud de la cadena y rr el número de reglas A→BCA \to BC de la gramática.

Las celdas. Hay una por cada par i≤ji \leq j: son n(n+1)/2n(n + 1)/2.

El trabajo por celda. Una celda de una subcadena de longitud ℓ\ell tiene ℓ−1\ell - 1 puntos de corte, y por cada uno se revisan las rr reglas. Hay n−ℓ+1n - \ell + 1 subcadenas de longitud ℓ\ell, una por cada posición donde puede empezar. El número total de pares de celda y punto de corte es

∑ℓ=1n(n−ℓ+1)(ℓ−1)=n3−n6.\sum_{\ell=1}^{n} (n - \ell + 1)(\ell - 1) = \frac{n^3 - n}{6}.

La suma se comprueba por inducción, o contando de otra manera: elegir una celda y un punto de corte es elegir tres posiciones i≤k<ji \leq k < j, es decir, tres números distintos i<k+1<j+1i < k + 1 < j + 1 entre 00 y nn, y hay (n+13)=(n+1)n(n−1)/6\binom{n+1}{3} = (n + 1)n(n - 1)/6 maneras. Para n=5n = 5 son 2020 pares. La gramática del ejemplo tiene r=12r = 12 reglas de dos variables, y 20⋅12=24020 \cdot 12 = 240, el número de comprobaciones que informó cyk.

El total. Cada comprobación pregunta si BB está en una celda y CC en otra. Si esa pregunta cuesta tiempo constante, CYK hace

r⋅n3−n6+n⋅tr \cdot \frac{n^3 - n}{6} + n \cdot t

pasos, donde tt es el número de reglas A→aA \to a, que se revisan una vez por cada celda de la diagonal. Si ∣G∣|G| es el tamaño de la gramática, que en forma normal de Chomsky es proporcional a su número de reglas, el costo es

O(n3⋅∣G∣).O(n^3 \cdot |G|).

Para una gramática fija es O(n3)O(n^3): polinomial en la longitud de la cadena. Recuperar un árbol agrega menos que eso: tiene 2n−12n - 1 nodos internos, y en cada uno se revisan a lo sumo n−1n - 1 cortes y rr reglas. La memoria es la tabla: n(n+1)/2n(n+1)/2 celdas con a lo sumo ∣V∣|V| variables cada una.

Comparen con la tabla de search_cost: para n=16n = 16, la búsqueda probó 15 496 pasos de derivación y CYK hizo 5440 comprobaciones. Para n=100n = 100, CYK con esa gramática de 8 reglas de dos variables hace 8⋅(1003−100)/6=1 333 2008 \cdot (100^3 - 100)/6 = 1\,333\,200 comprobaciones. La búsqueda, multiplicando por 3 cada dos símbolos, ya no termina en un tiempo razonable.

Si la gramática no viene en forma normal, primero se convierte. Eso se hace una sola vez por gramática, no una vez por cadena, y entonces el problema de la pertenencia se resuelve en tiempo polinomial para todo lenguaje libre de contexto. En el vocabulario de la última parte del curso: todo lenguaje libre de contexto está en la clase P.

Por qué hace falta la forma normal

CYK no es un algoritmo para gramáticas cualesquiera, y cada condición de la forma normal sostiene una parte.

  • Con una regla A→BCDA \to BCD haría falta partir la subcadena en tres trozos: dos puntos de corte. Cada celda revisaría del orden de n2n^2 pares de cortes en lugar de nn, y el costo subiría a n4n^4. Con reglas más largas, más todavía. El paso 4 de la conversión hace ese trabajo una vez, en la gramática, y deja el algoritmo en n3n^3.
  • Con reglas ε\varepsilon, uno de los trozos podría ser vacío y el otro sería la subcadena entera: la celda T[i][j]T[i][j] dependería de sí misma.
  • Con una regla unitaria A→BA \to B, la variable AA entra a una celda porque BB está en la misma celda. Otra vez una celda que depende de sí misma, y habría que repetir el cálculo de cada celda hasta que deje de cambiar.

Por qué los compiladores no usan CYK

O(n3)O(n^3) es polinomial, y para un compilador sigue siendo demasiado. Un archivo de código tiene decenas de miles de tokens, que son los símbolos que ve el parser. Con n=10 000n = 10\,000, n3n^3 es 101210^{12}, por cada archivo y en cada compilación.

Los compiladores no lo necesitan, porque no reciben una gramática cualquiera. Las gramáticas de los lenguajes de programación se diseñan para que el parser pueda leer la entrada una sola vez, de izquierda a derecha, y decidir qué regla aplicar mirando solo el siguiente token o unos pocos. Para esas gramáticas hay parsers que trabajan en tiempo lineal, O(n)O(n). Los niveles de precedencia de la sesión A y la regla del else son parte de ese diseño: una gramática sin ambigüedad y con una sola regla posible en cada momento. La semana próxima aparece la máquina que hay detrás, el autómata de pila.

CYK y los algoritmos de su familia quedan para cuando la gramática no se puede elegir: gramáticas ambiguas por naturaleza, como las de los idiomas, donde una oración puede tener varios árboles y se quieren todos, y herramientas que deben aceptar cualquier gramática que el usuario escriba.

El código de la semana

code/week-05/
├── cfg.h                 struct Cfg, lectura del formato .cfg, L(G) hasta una longitud,
│                         derivaciones por la izquierda y árboles
├── chomsky.h             los cuatro pasos de la conversión, CYK, el árbol y el conteo de árboles
├── predicates.h          cada lenguaje del capítulo como una función que mira la cadena
├── show_cfg.cpp          muestra un .cfg como cuádrupla y lista sus cadenas más cortas
├── derive.cpp            las derivaciones por la izquierda de una cadena, con sus árboles
├── to_chomsky.cpp            la conversión a forma normal de Chomsky, paso por paso
├── cyk.cpp               la tabla de CYK, la respuesta y un árbol
├── search_cost.cpp       pasos de la búsqueda de derivaciones contra comprobaciones de CYK
├── machines/             las gramáticas del capítulo, en formato .cfg
├── errors/               tres descripciones que no son una gramática
├── test_cfg.cpp          el formato, y cada gramática contra su predicado
├── test_ambiguity.cpp    derivaciones, árboles y cuántos árboles tiene cada ejemplo
├── test_chomsky.cpp      cada paso de la conversión conserva el lenguaje; los 2n − 1 pasos
├── test_cyk.cpp          CYK contra las otras dos maneras de decidir; la tabla del ejemplo
└── lab/cyk_parser/       el laboratorio

make compila todo, y make test corre las pruebas con ASan y UBSan. Tardan más que las de otras semanas, porque revisan muchas cadenas.

$ make test
test_cfg: ok (12 gramáticas, 328933 cadenas comparadas con su predicado)
test_ambiguity: ok
test_chomsky: ok (14 gramáticas convertidas, 280 derivaciones de 2n − 1 pasos)
test_cyk: ok (12 gramáticas, 13079 cadenas)
Todas las pruebas pasaron.

Las pruebas comprueban con assert lo que este capítulo afirma. test_cfg compara cada gramática con una función de C++ que decide el mismo lenguaje sin usar la gramática, sobre todas las cadenas hasta una longitud (entre 7 y 12 símbolos, según el tamaño del alfabeto), y revisa la forma 0kS1k\mathtt{0}^kS\mathtt{1}^k de la demostración. test_ambiguity comprueba que a+a×a\mathtt{a+a\times a} tiene dos derivaciones por la izquierda con la gramática ambigua y una con la de niveles, lo mismo para el else colgante, y que las gramáticas que llamamos no ambiguas tienen una sola derivación por la izquierda para cada cadena corta. test_chomsky convierte todas las gramáticas, comprueba que cada paso conserva el lenguaje y deja lo que promete, que el orden equivocado deja una regla unitaria, y que las derivaciones en forma normal tienen 2n−12n - 1 pasos. test_cyk comprueba que CYK responde lo mismo que el predicado y que el cálculo directo de L(G)L(G), que el número de comprobaciones es r(n3−n)/6r(n^3 - n)/6, que el árbol recuperado es un árbol de derivación de la cadena con 2n−12n - 1 nodos internos, y la tabla del ejemplo celda por celda.

Para saber qué cadenas genera una gramática, cfg.h no busca derivaciones, que como vimos puede no terminar. Calcula, para cada variable, el conjunto de las cadenas de hasta cierta longitud que genera: empieza con conjuntos vacíos y aplica las reglas hasta que ningún conjunto crece. Es la misma idea de CYK, de abajo hacia arriba, y termina siempre porque hay una cantidad finita de cadenas de esa longitud.

Los archivos de machines/ son:

Archivo Lenguaje Para qué se usa
zeros_ones.cfg {0n1n}\{\mathtt{0}^n\mathtt{1}^n\} Primer ejemplo y primera demostración
palindromes.cfg Palíndromos sobre {a,b}\{\mathtt{a}, \mathtt{b}\} Diseño
parens.cfg Paréntesis balanceados, S→(S)S∣εS \to \mathtt{(}S\mathtt{)}S \mid \varepsilon Diseño; laboratorio
parens_ss.cfg Paréntesis balanceados, con S→SSS \to SS Búsqueda que no termina
equal_ab.cfg Igual número de a\mathtt{a} y de b\mathtt{b} Segunda demostración
abc_union.cfg {aibjck:i=j o j=k}\{\mathtt{a}^i\mathtt{b}^j\mathtt{c}^k : i = j \text{ o } j = k\} Unión; lenguaje inherentemente ambiguo
even_ones.cfg Cantidad par de unos De un DFA a una gramática
two_derivations.cfg {ab}\{\mathtt{ab}\} Dos derivaciones, un árbol
expr_ambiguous.cfg Expresiones aritméticas Ambigüedad
expr_precedence.cfg Expresiones aritméticas Niveles de precedencia
dangling_else.cfg Instrucciones con if y else El else colgante
dangling_else_fixed.cfg Instrucciones con if y else El else colgante, resuelto
blocks.cfg Listas de bloques 0n1n\mathtt{0}^n\mathtt{1}^n Ejemplo de la conversión
unit_order.cfg {a,b,ab}\{\mathtt{a}, \mathtt{b}, \mathtt{ab}\} El orden de los pasos 2 y 3
expr_ambiguous_chomsky.cfg Expresiones aritméticas Ejemplo de CYK, ya en forma normal

Los programas se encadenan. Para probar CYK con cualquier gramática, se convierte y se le pasa el resultado por la entrada estándar, con - en lugar del nombre del archivo:

$ build/to_chomsky machines/blocks.cfg | build/cyk - 0101
w = 0101, n = 4
       j=0 0     j=1 1     j=2 0     j=3 1
i=0  0 {U_0}     {S0,S,B}  ∅         {S0,S}
i=1  1           {U_1}     ∅         ∅
i=2  0                     {U_0}     {S0,S,B}
i=3  1                               {U_1}
S0 está en T[0][3]: genera
comprobaciones de reglas A → BC: 110
árboles de derivación: 1. Uno de ellos:
S0
├── B
│   ├── U_0
│   │   └── 0
│   └── U_1
│       └── 1
└── S
    ├── U_0
    │   └── 0
    └── U_1
        └── 1
[S0 [B [U_0 0] [U_1 1]] [S [U_0 0] [U_1 1]]]

La última línea es el mismo árbol escrito en una línea, con un par de corchetes por nodo. Es el formato que pide el laboratorio.

El laboratorio

En lab/cyk_parser está el enunciado, un esqueleto y los casos. El problema es escribir un parser con CYK: la entrada es una gramática en forma normal de Chomsky, en formato .cfg, seguida de una lista de cadenas, y la salida dice por cada cadena genera o no genera, con un árbol de derivación para las que se generan.

cd lab/cyk_parser
make        # compila solution.cpp
make test   # corre el juez con todos los casos

Como una cadena puede tener varios árboles, el juez no compara el árbol con uno fijo. Usa un verificador que comprueba que el árbol entregado es un árbol de derivación de la cadena: que la raíz es la variable inicial, que cada nodo con sus hijos es una regla, y que las hojas forman la cadena. Los casos incluyen la cadena vacía con y sin la regla S→εS \to \varepsilon, una gramática que no genera nada, variables sin reglas, y cadenas de 100 símbolos con las que una búsqueda de derivaciones da TLE. solution.cpp se escribe sin incluir cfg.h ni chomsky.h: pueden leerlos, pero el CYK del laboratorio es el suyo, y tiene que ser más rápido que el de los ejemplos.

Resumen

  • Una gramática libre de contexto es G=(V,Σ,R,S)G = (V, \Sigma, R, S): variables, terminales, reglas A→uA \to u y una variable inicial. Describe un lenguaje diciendo cómo generar sus cadenas.
  • Un paso de derivación reemplaza una variable por el lado derecho de una de sus reglas: uAv⇒uxvuAv \Rightarrow uxv. L(G)L(G) es el conjunto de las cadenas de terminales ww con S⇒∗wS \Rightarrow^* w.
  • Lo que una variable genera no depende de lo que la rodea. Una derivación se separa en derivaciones independientes, una por símbolo: el lema de separación.
  • Un árbol de derivación guarda qué regla se aplicó a cada variable, sin el orden. Cada árbol corresponde a una sola derivación por la izquierda.
  • Diseñar una gramática es decir cómo se arma una cadena del lenguaje con otras más cortas. Dejar la variable en medio, como en S→0S1S \to \mathtt{0}S\mathtt{1}, empareja lo de la izquierda con lo de la derecha.
  • Todo lenguaje regular es libre de contexto: de un DFA sale una gramática con una variable por estado. Los lenguajes libres de contexto son cerrados bajo unión, concatenación y estrella.
  • L(G)=LL(G) = L se demuestra con dos inclusiones: toda cadena de LL se deriva, por inducción sobre la cadena, y toda cadena derivada está en LL, por inducción sobre el número de pasos, describiendo las formas.
  • Una gramática es ambigua si alguna cadena tiene dos árboles distintos, o dos derivaciones por la izquierda. Tener dos derivaciones cualesquiera no es ser ambigua.
  • La ambigüedad es de la gramática. La de las expresiones se quita con un nivel por operador, que da la precedencia, y recursión de un solo lado, que da la asociatividad. El else colgante se resuelve con la convención del if más cercano. Hay lenguajes inherentemente ambiguos.
  • El problema de la pertenencia: dadas GG y ww, ¿GG genera ww? Buscar derivaciones puede no terminar, por las reglas ε\varepsilon y las unitarias.
  • Forma normal de Chomsky: solo reglas A→BCA \to BC y A→aA \to a, más S→εS \to \varepsilon si hace falta, y la variable inicial no aparece a la derecha. Una derivación de una cadena de longitud n≥1n \geq 1 tiene exactamente 2n−12n - 1 pasos.
  • Toda gramática se convierte en cuatro pasos, en orden: variable inicial nueva, quitar reglas ε\varepsilon, quitar reglas unitarias, partir las reglas largas. Quitar reglas ε\varepsilon crea unitarias, y por eso va antes.
  • CYK llena una tabla: T[i][j]T[i][j] es el conjunto de variables que generan la subcadena de ii a jj. Las celdas de un símbolo salen de las reglas A→aA \to a, y las demás de las reglas A→BCA \to BC con un punto de corte. Se llena por longitudes crecientes, y GG genera ww si S∈T[0][n−1]S \in T[0][n-1].
  • De la tabla se recupera un árbol, y una variable que entra a una celda de dos maneras son dos árboles.
  • El costo es O(n3⋅∣G∣)O(n^3 \cdot |G|). Todo lenguaje libre de contexto se decide en tiempo polinomial. Los compiladores usan parsers lineales, porque diseñan sus gramáticas para eso.

Ejercicios

  1. Con la gramática de los palíndromos, escriban una derivación de abbba\mathtt{abbba} y dibujen su árbol. ¿Cuántos pasos tiene? ¿Cuántas derivaciones distintas tiene esa cadena, y por qué? Comprueben con build/derive machines/palindromes.cfg abbba. Después den la fórmula del número de pasos de la derivación de un palíndromo de longitud nn.
  2. Diseñen una gramática para cada lenguaje, y escríbanla como archivo .cfg para listar sus cadenas con show_cfg: (a) { anb2n:n≥0 }\{\, \mathtt{a}^n\mathtt{b}^{2n} : n \geq 0 \,\}; (b) { aibj:i≤j }\{\, \mathtt{a}^i\mathtt{b}^j : i \leq j \,\}; (c) { aibj:i≠j }\{\, \mathtt{a}^i\mathtt{b}^j : i \neq j \,\}; (d) las cadenas sobre {a,b}\{\mathtt{a}, \mathtt{b}\} que no son palíndromos. Para (c), piensen en una unión.
  3. 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 \,\} sin mirar la del capítulo, y después compárenla con machines/abc_union.cfg. Con la del capítulo: ¿qué cadenas tienen dos árboles? Demuestren que son exactamente las que tienen i=j=ki = j = k, y que ninguna cadena tiene tres.
  4. Demuestren, con las dos inclusiones, que la gramática de los palíndromos genera exactamente { w∈{a,b}∗:w=wR }\{\, w \in \{\mathtt{a}, \mathtt{b}\}^* : w = w^R \,\}. Para la segunda inclusión, describan todas las formas que se derivan de SS.
  5. Demuestren la afirmación que quedó pendiente en De un DFA a una gramática: Rq⇒∗wRpR_q \Rightarrow^* wR_p si y solo si δ∗(q,w)=p\delta^*(q, w) = p. Concluyan que la gramática genera L(M)L(M). Después construyan la gramática del DFA de la semana 1 que reconoce las cadenas que terminan en 01\mathtt{01}, y pruébenla con show_cfg.
  6. Demuestren que S→(S)S∣εS \to \mathtt{(}S\mathtt{)}S \mid \varepsilon genera exactamente los paréntesis balanceados. Para la inclusión difícil usen la cantidad d(i)d(i) de la demostración del capítulo, ahora como paréntesis abiertos menos cerrados, y el primer i>0i > 0 con d(i)=0d(i) = 0.
  7. La gramática S→SS∣(S)∣εS \to SS \mid \mathtt{(}S\mathtt{)} \mid \varepsilon es ambigua. (a) Den dos árboles para ()()()\mathtt{()()()} que no usen la regla S→εS \to \varepsilon más que debajo de un paréntesis. (b) Muestren que ()\mathtt{()} tiene infinitos árboles. ¿Qué dos reglas lo permiten? (c) Corran derive con machines/parens.cfg y varias cadenas: ¿cuántos árboles tiene cada una? Expliquen por qué S→(S)S∣εS \to \mathtt{(}S\mathtt{)}S \mid \varepsilon no deja elegir.
  8. Amplíen la gramática de expresiones con niveles para que tenga resta y división, con la precedencia y la asociatividad usuales, y un operador de potencia ^ que tenga más precedencia que el producto y asocie por la derecha: a^a^a es a^(a^a). Escríbanla como archivo y comprueben con derive que a-a-a y a^a^a tienen un solo árbol cada una, y que es el correcto.
  9. Conviertan S→aSb∣SS∣εS \to \mathtt{a}S\mathtt{b} \mid SS \mid \varepsilon a forma normal de Chomsky, a mano, mostrando los cuatro pasos. Digan cuáles son las variables anulables y los pares unitarios. Comprueben con to_chomsky --pasos: su resultado puede tener otros nombres, pero las mismas reglas.
  10. Con la gramática del ejercicio anterior ya convertida, llenen a mano la tabla de CYK para abab\mathtt{abab} y para abba\mathtt{abba}. Recuperen un árbol de la primera. ¿Cuántos árboles tiene? Comprueben con cyk.
  11. ¿Por qué CYK necesita la forma normal de Chomsky? Escriban la recurrencia que haría falta para una regla A→BCDA \to BCD y calculen cuánto costaría llenar la tabla. Después expliquen qué celda dependería de sí misma con una regla unitaria, y con una regla ε\varepsilon.
  12. El paso 2 puede multiplicar las reglas. (a) ¿Cuántas reglas deja la regla S→ABCABCS \to ABCABC si AA, BB y CC son anulables? Cuenten los lados derechos distintos y comprueben con to_chomsky --pasos. (b) Muestren que si los pasos se hacen en el orden 1, 4, 2, 3, el paso 2 a lo sumo triplica el número de reglas. (c) Demuestren que ese orden también termina en una gramática en forma normal de Chomsky: revisen qué garantiza cada paso y qué podría romper el siguiente.
  13. Para programar. Una variable es productiva si genera alguna cadena de terminales. Agreguen a cfg.h una función que calcule las variables productivas marcando, como las anulables, y con ella una que decida si L(G)=∅L(G) = \emptyset sin probar cadenas. Compárenla con shortest_lengths, que ya está en cfg.h. Úsenla con la gramática de lab/cyk_parser/casos/03.in. Este problema vuelve en la semana 9.
  14. Para programar. Modifiquen count_trees de chomsky.h, o su solución del laboratorio, para imprimir cuántos árboles tiene a+a+⋯+a\mathtt{a+a+\cdots+a} con mm sumas en la gramática ambigua convertida, para mm de 1 a 15. Busquen la secuencia que sale. ¿Crece de forma polinomial o exponencial? ¿Cuánto tarda CYK en contarlos, y por qué no es una contradicción?