Sintaxis para ordenadores: el algoritmo de CYK en clase de lengua

Tiempo de lectura: 11 min

[Este texto fue originalmente concebido como parte del capítulo Aplicaciones tecnológicas de la Lingüística del libro Avances de la Lingüística y su aplicación didáctica editado por Andrea Ariño Bizarro, Bárbara Marqueta y Natalia López Cortés. Por motivos de espacio, esta sección se quedó en el tintero. La recupero aquí por si tuviera interés para alguien.]

La sintaxis es una parte central de los contenidos escolares de lengua. Habitualmente, nos la encontramos en el aula en forma de ejercicio de análisis sintáctico de cajitas o árboles, de esos que se pintan con tiza en la pizarra. En esta entrada propongo llevar a clase de lengua dos artefactos que, si bien son plenamente sintácticos, son un tanto particulares: las gramáticas de contexto libre y el algoritmo de CYK. Son dos formalismos que tienen poco que ver con la sintaxis escolar; ambos son desarrollos de la lingüística computacional que buscan representaciones y estrategias puramente formales para que los ordenadores puedan hacer análisis sintáctico.

Disclaimer: El objetivo del ejercicio es asomarse a otras formas de mirar la sintaxis y a plantearse cuestiones fundamentales sobre las facultades lingüísticas de los humanos, la naturaleza de la ambigüedad y los posibles caminos formales que nos permiten analizar y reconocer las oraciones que nos encontramos. Pero no soy profe, no he dado clase nunca a chavales en edad escolar. Muy posiblemente este ejercicio sea irrelevante, excesivo o inasequible para estudiantes pre-universitarios, no lo sé. Yo creo que hay un encanto y una belleza en mirar la sintaxis desde esta perspectiva un tanto inusual que quizá resuene con algunos alumnos desconectados de lo que normalmente se enseña en clase de lengua.

Gramáticas de contexto libre

En el campo de la lingüística computacional, se entiende como gramática de contexto libre a un conjunto de reglas que representan fenómenos sintácticos. Las reglas de una gramática de contexto libre representan la manera en que se combinan elementos sintácticos para formar otros elementos sintácticos. Así, por ejemplo, una regla podría tener la siguiente forma:

Oración ➝ Sintagma Nominal    Sintagma Verbal

Esta regla gramatical indica que una oración es un elemento que está formado por un sintagma nominal seguido de un sintagma verbal. Las reglas de una gramática se formulan siguiendo esta estructura, en la que el elemento a la izquierda de la flecha es el elemento que se construye (o que se puede reescribir) combinando los dos elementos de la derecha. Una gramática sería pues un conjunto de estas reglas de reescritura; el objetivo de una gramática es ser capaz de reconocer las oraciones sintácticamente válidas de una lengua y formalizar las relaciones sintácticas entre los elementos de una oración.

Vamos a ver un ejemplo con una gramática de juguete. Por comodidad, usaremos las siguiente abreviaturas: O (oración), SN (sintagma nominal), SV (sintagma verbal), Det (determinante), N (nombre común), V (verbo).

O ➝ SN SV

SN ➝ Det N

SV ➝ V

Det ➝ el

N ➝ niño

V ➝ escribe

V ➝ lee

Esta gramática nos dice que una oración (O) se construye con un sintagma nominal (SN) seguido de un sintagma verbal (SV). Asimismo, nos dice que el sintagma nominal está formado por un determinante seguido de un nombre y que un sintagma verbal está formado básicamente por un verbo. Por último, nuestra mini gramática incluye unas reglas finales que son un poco distintas a las anteriores: estas reglas contienen el léxico que contempla nuestra gramática: el como determinante, niño como sustantivo, escribe y lee como verbos. 

Esta gramática podría producir o aceptar como válidas las oraciones El niño escribe, El niño lee. Es decir, nuestra gramática contiene las reglas tanto sintácticas como léxicas para poder analizar esas oraciones. Sin embargo, otras oraciones (como El chico escribe o El niño lee un libro) no serían contempladas por nuestra gramática. Si quisiéramos incluir otras oraciones, necesitaríamos ampliar nuestra gramática, bien incluyendo nuevas reglas de reescritura (para que contemple objetos directos), bien incluyendo más elementos a nuestro léxico (chico). 

Incorporar nuevas palabras a nuestra gramática es sencillo, basta con incorporar las reglas correspondientes al léxico: 

O ➝ SN SV

SN ➝ Det N

SV ➝ V

Det ➝ el

N ➝ niño

N ➝ chico

V ➝ escribe

V ➝ lee

Con esta adición, ya habríamos incluido El chico escribe y El chico lee al repertorio de frases contempladas por nuestra gramática. 

Vamos ahora a añadir ahora añadir a nuestra gramática un complemento directo: 

O ➝ SN SV

SN ➝ Det N

SV ➝ V SN

Det ➝ el

N ➝ niño

N ➝ chico

V ➝ escribe

V ➝ lee

Una simple regla ha bastado para que nuestra gramática incluya complementos directos: hemos añadido a nuestra regla del sintagma verbal (que hasta ahora solo decía que un sintagma verbal está formado por un verbo) la condición de que el verbo vaya necesariamente seguido de un sintagma nominal. Como la regla para el sintagma nominal ya estaba formulada antes (SN ➝ Det N), nuestra gramática ya contiene la información para interpretar los SN. Con esta simple enmienda ya tendríamos incluidos complementos directos. Vamos a añadir también algunas reglas más a nuestro léxico que nos permitan sacarle partido a nuestra gramática.

O ➝ SN SV

SN ➝ Det N

SV ➝ V SN

Det ➝ el

Det ➝ un

N ➝ niño

N ➝ chico

N libro

N cuento

V ➝ escribe

V ➝ lee

Con estas adiciones, nuestra gramática ya reconoce oraciones como El niño lee un libro, El chico escribe un cuento, pero también Un chico escribe el libro, El niño lee el libro. 

Añadamos ahora algún verbo intransitivo, como dormir o reír:

O ➝ SN SV

SN ➝ Det N

SV ➝ V SN

Det ➝ el

Det ➝ un

N ➝ niño

N ➝ chico

N libro

N cuento

V ➝ escribe

V ➝ lee 

V ➝ duerme

V ➝ ríe 

¡Horror! Tal como está formulada en este punto, nuestra gramática no reconocería una oración como El niño duerme o El chico ríe: nuestra gramática solo contempla la posibilidad de que un sintagma verbal esté formado por un verbo seguido de un sintagma nominal (SV ➝ V SN). Técnicamente, nuestra gramática permitiría una oración como El niño ríe un cuento, pero rechazaría El niño ríe. Necesitamos manipular las reglas de nuestra gramática para que contemple la posibilidad de incluir construcciones intransitivas. 

O ➝ SN SV

SN ➝ Det N

SV ➝ V SN

SV ➝ V

Det ➝ el

Det ➝ un

N ➝ niño

N ➝ chico

N libro

N cuento

V ➝ escribe

V ➝ lee 

V ➝ duerme

V ➝ ríe 

Con esta nueva regla, damos dos posibilidades de sintagma verbal: bien como sintagma verbal transitivo (con el V seguido necesariamente de un SN), bien como un sintagma verbal intransitivo (V solo, como teníamos al principio). Con esta solución, nuestra gramática ya aceptaría la frase El niño duerme o El niño ríe y podríamos darnos por satisfechos. Sin embargo, nuestra gramática seguiría dando por buenas oraciones un tanto anómalas sintácticamente como El niño ríe un cuento. Podemos refinar nuestra gramática y nuestro léxico para que solo se permitan construcciones intransitivas con verbos intransitivos y solo se permitan construcciones transitivas con verbos transitivos.  

O ➝ SN SV

SN ➝ Det N

SV ➝ VT SN

SV ➝ VI

Det ➝ el

Det ➝ un

N ➝ niño

N ➝ chico

N libro

N cuento

VT ➝ escribe

VT ➝ lee 

VI ➝ duerme

VI ➝ ríe 

En esta ocasión, no hemos añadido reglas nuevas, sino que hemos modificado ligeramente las que ya teníamos: hemos añadido la restricción de que la regla para las construcciones transitivas solo permita verbos transitivos (VT). Del mismo modo, la construcción intransitiva solo puede darse con verbos intransitivos (VI). Por último, nuestro léxico ya no contempla verbos a secas (V), sino que distingue entre verbos transitivos (VT: escribe, lee) e intransitivos (VI: ríe, duerme).

El algoritmo de CYK

Las gramáticas como la que vimos en el apartado anterior permiten representar formalmente las construcciones sintácticas permitidas en una lengua (o, planteado de una manera menos ambiciosa, dar cuenta de algunas de ellas) y ser utilizadas de forma computacional para producir y reconocer patrones sintácticos. ¿Pero cómo puede un ordenador aplicar una gramática como la que vimos anteriormente a una oración no vista previamente? En este ejercicio proponemos llevar el algoritmo de CYK como actividad al aula. 

El algoritmo de CYK (del apellido de sus creadores: Cocke–Younger–Kasami) es un conjunto de pasos sistemáticos (un algoritmo) que, dada una gramática (como la del ejercicio anterior) y una oración cualquiera, nos permite concluir si dicha oración es analizable o no por nuestra gramática. Dicho de otro modo, el algoritmo CYK es el conjunto de pasos que permiten a un ordenador aplicar las reglas de una gramática de contexto libre a una oración cualquiera para determinar si la oración es o no aceptable según esa gramática. Podríamos decir que el algoritmo de CYK es la forma en que los ordenadores pueden hacer análisis sintáctico. La actividad consiste en ejecutar a mano este algoritmo, es decir, vamos a reproducir con papel y lápiz cada una de los pasos del algoritmo (como si nosotros fuésemos el ordenador que ejecuta) y ver qué resultado obtenemos.

Partiremos de la siguiente gramática: 

O ➝ SN SV

SN ➝ Det N

SN ➝ N Adj

SN ➝ NP

SV ➝ V

SV ➝ V SN

SV ➝ V Adj

Det ➝ el

NP ➝ Carlos

N ➝ vino

V ➝ vino

Adj ➝ blanco

Nuestra gramática considera que una oración está formada por un sintagma nominal (SN) seguido de sintagma verbal (SV). Asimismo, considera que un sintagma nominal puede estar formado por un nombre propio, por un sustantivo seguido de un adjetivo o por un determinante seguido de un sustantivo. Por otro lado, un sintagma verbal puede estar formado solo por un verbo o por un verbo y un adjetivo. En cuanto al léxico, esta gramática incluye el nombre propio Carlos, el adjetivo blanco y una palabra que puede ser intepretada tanto como sustantivo como verbo: vino

La oración que vamos a analizar siguiendo el algoritmo de CYK y aplicando esta gramática es: Carlos vino blanco.

Para ejecutar el algoritmo vamos necesitar un casillero como este: 

En la base del casillero, pondremos las palabras de nuestra oración:

La filosofía del algoritmo es la siguiente: iremos desde las casillas de abajo hacia la cúspide. En cada casilla, iremos aplicando las reglas de nuestra gramática que correspondan. Los elementos gramaticales de una casilla serán el resultado de combinar los elementos gramaticales de casillas inferiores. El objetivo es llegar a la cúspide del casillero (casilla 1). Si al llegar a la cúspide del casillero hemos obtenido una O (es decir, una oración), quiere decir que nuestro sistema ha podido analizar sintácticamente la oración de partida (siguiendo el ejemplo se verá todo más claro). 

El primer paso consiste en rellenar las casillas de la fila inferior con la categoría gramatical que nuestra gramática asigne a cada una de las palabras. Es decir, rellenaremos las casillas 4, 5 y 6 con la categoría gramatical que nuestra gramática asigne a las palabras de la oración:

Primera fila rellenada. Merece la pena fijarse que la palabra vino tiene dos categorías posibles: verbo y sustantivo. Para un hablantes puede ser evidente que en “Carlos vino blanco”, la palabra “vino” es una forma del verbo “venir”. Pero ese análisis que para nosotros es evidente como hablantes no lo es para un ordenador. Lo que el algoritmo de CYK permite precisamente es que un ordenador analice sintácticamente de forma adecuada la oración deshaciendo las posibles ambigüedades sintácticas que encuentre amparándose exclusivamente en las reglas de la gramática que le hemos dado. 

A continuación hacemos un segundo repaso de las categorías del casillero y vemos si podemos aplicar ya en este punto alguna regla más de nuestra gramática. Así, por ejemplo, nuestra gramática estipula que un SN puede estar constituido por un NP (sin necesidad de combinarlo con ningún otro elemento). Igualmente, un SV puede estar constituido por un V solamente. Aplicamos pues las reglas de la gramática a los elementos de nuestra primera fila:

Lo que tenemos en el casillero en este punto son las distintas etiquetas sintácticas que nuestra gramática permite asignar a cada una de las palabras de la oración: Carlos puede ser un NP o ya directamente un SN. Vino puede ser un V, un N o incluso un SV por sí mismo. Por ahora, blanco solo puede ser analizado como un Adj según nuestra gramática.  

El siguiente paso consiste en rellenar la segunda fila de casillas combinando los elementos de las casillas inferiores dos a dos. Es decir, vamos a comprobar si hay alguna regla en nuestra gramática que nos permita combinar los elementos de las casillas 4 y 5 y, si la hay, escribiremos el resultado en la casilla 2. Dicho de otro modo, vamos a comprobar de qué maneras nuestra gramática permite combinar las casillas 4 y 5 (correspondientes a “Carlos” y “vino”) para construir un elemento sintáctico que englobe a ambos. De esta manera, el elemento sintáctico resultante de combinar 4 y 5 lo anotaremos en la casilla 2.  A continuación, haremos lo mismo con las casillas 5 y 6, y anotaremos el resultado en la casilla 3. 

Tenemos una regla que nos permite combinar el SN de la casilla 4 con el SV de la casilla 5: O ➝ SN SV. Así que apuntamos O en la casilla 2. Lo que estamos diciendo es que, con los elementos que tenemos y ateniéndonos a las reglas de nuestra gramática, técnicamente nuestra gramática permite combinar el SN de la casilla 4 con el SV de la casilla 5 para obtener una oración (O). Es decir, nuestro algoritmo está considerando la posibilidad de que el análisis sintáctico de nuestra oración sea simplemente que Carlos es el sujeto y que vino es el sintagma verbal y que ambos forman una oración, dejando de lado blanco. Nosotros como hablantes sabemos que esa interpretación tiene poco sentido, porque blanco no puede quedar colgando fuera del análisis sintáctico. Sin embargo, precisamente esa es la gracia del algoritmo: explorar todos los caminos sintácticos posibles permitidos por nuestra gramática y descartar aquellos que nos llevan a callejones sin salida hasta dar con el bueno. Así que, aunque nos parezca un sinsentido, aplicamos la regla y anotamos O en la casilla 2: 

No hay más reglas que nos permitan combinar los elementos de la casilla 4 con los de la casilla 5, así que vamos a explorar ahora de qué maneras podemos combinar las casillas 5 (vino) y 6 (blanco) para formar otros elementos sintácticos. Atendiendo a nuestra gramática, hay dos reglas que podemos aplicar: que V se combine con Adj para formar un SV (SV ➝ V Adj) o que N se combine con Adj para formar un SN (SN ➝ N Adj). Es decir, nuestro algoritmo está explorando ahora las posibles maneras de combinar “vino” con “blanco” y encuentra 2 posibilidades: que formen un sintagma nominal (como si vino blanco hiciera referencia a la bebida) o que formen un sintagma verbal. Es decir, en este punto del proceso, el algoritmo no sabe si debe interpretar “vino blanco” como un sintagma nominal o un sintagma verbal. Mantenemos pues las dos hipótesis con la esperanza de que la gramática nos permita desambiguarlo en pasos posteriores del algoritmo. Anotamos ambas posibilidades en la casilla 3: 

Llegamos al último punto del algoritmo. Ahora tenemos dos posibles caminos: combinar un elemento de la casilla 2 (que es la suma de 4 y 5) con un elemento de la casilla 6; o bien combinar un elemento de la casilla 4 con un elemento de la casilla 3. Ojo: las casillas que podemos combinar son esas (la 4 con la 3 o la 2 con la 6); en ningún caso podemos combinar la 2 y la 3. Esto puede parecer contraintuitivo, pero tiene lógica: la casilla 2 representa el elemento sintáctico resultante de unir a 4 y 5 (Carlos vino). La casilla 3 representa el elemento sintáctico resultante de unir a 5 y 6 (vino blanco). Si intentásemos combinar las casillas 2 y 3 estaríamos intentando combinar a la vez Carlos vino y vino blanco. Y eso no puede ser, porque vino tiene que estar o bien con Carlos, o bien con blanco, pero no puede estar formando parte de los dos elementos sintácticos a la vez. Así que las combinaciones posibles son combinar 4 y 3 (Carlos con vino blanco) o 2 y 6 (Carlos vino con blanco). 

La opción de combinar las casillas 2 y 6 no nos lleva a ningún lado: la gramática no incluye ninguna regla que nos permita combinar una O con un Adj (como es razonable). En cambio la gramática sí contempla una regla que permite unir el SN de la casilla 4 con el SV de la casilla 3. En concreto, la regla  O ➝ SN SV. Es decir, si nos quedamos con la interpretación que dice que Carlos es un SN (casilla 4) y que vino blanco es un SV (casilla 3), podemos formar una O. Así que lo apuntamos en la casilla 1. ¡Hemos llegado a la cúspide del casillero y hemos conseguido llegar formando una oración (O)! ¡Nuestra oración ha sido analizada por el algoritmo! Para recuperar el análisis sintáctico solo tendríamos que recuperar las reglas gramaticales aplicadas que nos han llevado al camino que termina con una O en la cúspide, en este caso: 

O ➝ SN SV

SV ➝ V Adj

SN ➝ NP

NP -> Carlos

V -> vino

Adj -> blanco

Tras haber recorrido el algoritmo, no solo hemos obtenido el análisis de la oración, sino que además sabemos que ese vino de la oración de partida es necesariamente un verbo en ese contexto. Y lo que es más importante: el proceso ha sido exclusivamente formal y en ningún momento hemos dependido de nuestro conocimiento interno como hablantes. El resultado obtenido (incluyendo que vino en este caso era un verbo y no un sustantivo) es producto exclusivo de haber ido aplicando las reglas de nuestra gramática.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.