Algoritmo CYK

El algoritmo en pseudocódigo es el siguiente:

Sea la entrada una cadena I que consta de n caracteres: a 1 ... a n . Sea la gramática que contiene r símbolos no terminales R 1 ... R r , con símbolo inicial R 1 . Sea P [ n , n , r ] un arreglo de booleanos. Inicialice todos los elementos de P a falso. Sea back [ n , n , r ] un arreglo de listas de triples de backpointing. Inicialice todos los elementos de back a la lista vacía. para cada s = 1 a n para cada unidad de producción R v → a s establecer P [ 1 , s , v ] = verdadero para cada l = 2 a n -- Longitud del intervalo para cada s = 1 a n - l +1 -- Inicio del intervalo para cada p = 1 a l -1 -- Partición del intervalo para cada producción R a → R b R c si P [ p , s , b ] y P [ l - p , s + p , c ] entonces establecer P [ l , s , a ] = verdadero, agregar <p,b,c> al reverso [ l , s , a ] Si P [n, 1 , 1 ] es verdadero, entonces I es miembro del lenguaje. Devuelve el resultado anterior ; al recorrer los pasos anteriores, se pueden construir fácilmente todos los árboles de análisis sintáctico posibles de la cadena. De lo contrario, devuelve "no es miembro del lenguaje".

Sea la entrada una cadena I que consta de n caracteres: a 1 ... a n . Sea la gramática que contiene r símbolos no terminales R 1 ... R r , con símbolo inicial R 1 . Sea P [ n , n , r ] un arreglo de números reales. Inicialice todos los elementos de P a cero. Sea back [ n , n , r ] un arreglo de triples de backpointing. para cada s = 1 a n para cada unidad de producción R v → a s establecer P [ 1 , s , v ] = Pr( R v → a s ) para cada l = 2 a n -- Longitud del intervalo para cada s = 1 a n - l +1 -- Inicio del intervalo para cada p = 1 a l -1 -- Partición del intervalo para cada producción R a → R b R c prob_splitting = Pr( R a → R b R c ) * P [ p , s , b ] * P [ l - p , s + p , c ] si prob_splitting > P [ l , s , a ] entonces establecer P [ l , s , a ] = prob_splitting establecer de nuevo [ l , s , a ] = <p,b,c> Si P [n, 1 , 1 ] > 0, entonces encuentra el árbol de análisis retrocediendo a través de y devuelve el árbol de análisis ; de lo contrario, devuelve "no es miembro del lenguaje".

En términos informales, este algoritmo considera cada subcadena posible de la cadena de entrada y establece${\displaystyle P[l,s,v]}$ser cierto si la subcadena de longitud${\displaystyle l}$a partir de${\displaystyle s}$puede generarse desde el no terminal${\displaystyle R_{v}}$Una vez que ha considerado las subcadenas de longitud 1, pasa a las subcadenas de longitud 2, y así sucesivamente. Para las subcadenas de longitud 2 o mayor, considera cada partición posible de la subcadena en dos partes y comprueba si hay alguna producción.${\displaystyle A\to B\;C}$de tal manera que${\displaystyle B}$coincide con la primera parte y${\displaystyle C}$coincide con la segunda parte. Si es así, registra${\displaystyle A}$como coincidencia de toda la subcadena. Una vez completado este proceso, la gramática genera la cadena de entrada si la subcadena que contiene toda la cadena de entrada coincide con el símbolo de inicio.

El algoritmo anterior es un reconocedor que solo determina si una oración pertenece al idioma. Es sencillo extenderlo a un analizador sintáctico que también construya un árbol de análisis , almacenando los nodos del árbol como elementos de la matriz, en lugar del valor booleano 1. El nodo se vincula a los elementos de la matriz que se utilizaron para producirlo, de modo que se construye la estructura del árbol. Solo se necesita un nodo de este tipo en cada elemento de la matriz si solo se va a producir un árbol de análisis. Sin embargo, si se van a conservar todos los árboles de análisis de una oración ambigua, es necesario almacenar en el elemento de la matriz una lista de todas las formas en que se puede obtener el nodo correspondiente en el proceso de análisis. Esto a veces se hace con una segunda tabla B[n,n,r] de los llamados punteros inversos . El resultado final es entonces un bosque compartido de posibles árboles de análisis, donde las partes comunes de los árboles se factorizan entre los distintos análisis. Este bosque compartido puede leerse convenientemente como una gramática ambigua que genera solo la oración analizada, pero con la misma ambigüedad que la gramática original y los mismos árboles de análisis hasta un simple cambio de nombre de los no terminales, como lo muestra Lang (1994) .

Como señalan Lange y Leiß (2009) , el inconveniente de todas las transformaciones conocidas a la forma normal de Chomsky es que pueden provocar un aumento indeseable del tamaño de la gramática. El tamaño de una gramática es la suma de los tamaños de sus reglas de producción, donde el tamaño de una regla es uno más la longitud de su lado derecho.${\displaystyle g}$para denotar el tamaño de la gramática original, el aumento de tamaño en el peor de los casos puede variar desde${\displaystyle g^{2}}$a${\displaystyle 2^{2g}}$, dependiendo del algoritmo de transformación utilizado. Para su uso en la enseñanza, Lange y Leiß proponen una ligera generalización del algoritmo CYK, "sin comprometer la eficiencia del algoritmo, la claridad de su presentación ni la simplicidad de las demostraciones" ( Lange y Leiß 2009 ) .

También es posible extender el algoritmo CYK para analizar cadenas utilizando gramáticas libres de contexto ponderadas y estocásticas . En lugar de valores booleanos, los pesos (probabilidades) se almacenan en la tabla P, de modo que P[i,j,A] contendrá el peso mínimo (probabilidad máxima) con el que se puede derivar la subcadena de i a j a partir de A. Otras extensiones del algoritmo permiten enumerar todos los análisis de una cadena desde el peso más bajo hasta el más alto (de la probabilidad más alta a la más baja).

El tiempo de ejecución en el peor de los casos de CYK es${\displaystyle \Theta (n^{3}\cdot |G|)}$donde n es la longitud de la cadena analizada y | G | es el tamaño de la gramática CNF G. Esto lo convierte en uno de los algoritmos más eficientes para el reconocimiento de lenguajes libres de contexto generales en la práctica. Valiant (1975) presentó una extensión del algoritmo CYK. Su algoritmo calcula la misma tabla de análisis que el algoritmo CYK; sin embargo, demostró que se pueden utilizar algoritmos para la multiplicación eficiente de matrices con entradas binarias (0-1) para realizar este cálculo.

Utilizando el algoritmo de Coppersmith-Winograd para multiplicar estas matrices, se obtiene un tiempo de ejecución asintótico en el peor de los casos de${\displaystyle O(n^{2.38}\cdot |G|)}$Sin embargo, el término constante oculto por la notación Big O es tan grande que el algoritmo Coppersmith-Winograd solo vale la pena para matrices demasiado grandes para manejar en las computadoras actuales ( Knuth 1997 ) , y este enfoque requiere resta y, por lo tanto, solo es adecuado para el reconocimiento. La dependencia de la multiplicación eficiente de matrices no se puede evitar por completo: Lee (2002) ha demostrado que cualquier analizador sintáctico para gramáticas libres de contexto que funcione en tiempo${\displaystyle O(n^{3-\varepsilon }\cdot |G|)}$puede convertirse eficazmente en un algoritmo que calcule el producto de${\displaystyle (n\times n)}$-matrices con entradas 0-1 en el tiempo${\displaystyle O(n^{3-\varepsilon /3})}$, y esto fue extendido por Abboud et al. ^{[ 4 ]} para aplicarse a una gramática de tamaño constante.