Algoritmo CYK

El algoritmo de Cocke-Younger-Kasami (CYK) determina si una cadena puede ser generada por una gramática libre de contexto y, si es posible, cómo puede ser generada. Este proceso es conocido como análisis sintáctico de la cadena. El algoritmo es un ejemplo de programación dinámica.

La versión estándar de CYK reconoce lenguajes definidos por una gramática libre de contexto escrita en la forma normal de Chomsky (CNF). Cualquier gramática libre de contexto puede ser convertida a CNF sin mucha dificultad, CYK puede usarse para reconocer cualquier lenguaje libre de contexto. Es posible extender el algoritmo CYK para que trabaje sobre algunas gramáticas libre de contexto no escritas como CNF. Esto puede hacerse para mejorar la ejecución, aunque hace el algoritmo más difícil de entender.

En el peor caso asintótico la complejidad temporal de CYK es de Θ(n³), donde n es la longitud de la cadena analizada. Esto hace a éste algoritmo uno de los más eficientes (en estos términos) en el reconocimiento de los lenguajes libres de contexto. Sin embargo, existen otros algoritmos con un mejor funcionamiento para ciertos subconjuntos de los lenguajes libres de contexto.

El algoritmo

El algoritmo de CYK es un algoritmo de análisis ascendente. y su importancia teórica viene dada al poder usarse para probar que el problema de pertenencia a los lenguajes libres de contexto es decidible.

El algoritmo de CYK para el problema de pertenencia es el siguiente:

Let the input string consist of n letters, a1... an.
Let the grammar contain r terminal and nonterminal symbols R1... Rr. 
This grammar contains the subset Rs which is the set of start symbols.
Let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
For each i = 1 to n
  For each unit production Rj → ai, set P[i,1,j] = true.
For each i = 2 to n -- Length of span
  For each j = 1 to n-i+1 -- Start of span
    For each k = 1 to i-1 -- Partition of span
      For each production RA -> RB RC
        If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
If any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs)
  Then string is member of language
  Else string is not member of language

Informalmente

En términos informales, este algoritmo considera todas las posibles subsecuencias de una secuencia de palabras y establece P[i, j, k] a verdadero si la subsecuencia de palabras que empiezan desde i de longitud j puede ser generada desde R_k. Una vez consideradas las subsecuencias de longitud 1, se continúa con las de longitud 2, y así sucesivamente. Para subsecuencias de longitud 2 o mayor, se considera cada posible partición de la subsecuencia en dos partes, y se comprueba si existe alguna regla P → Q R en la que Q concuerda con la primera parte y R con la segunda. Si es así, se establece que P concuerda con la subsecuencia completa. Una vez que este proceso se complete, la frase es reconocida por la gramática si la subsecuencia que contien la frase completa concuerda con el símbolo inicial.

Extensión del algoritmo

Es fácil extender el algoritmo para que no sólo determine si una frase pertenece a un lenguaje, sino que también construya un árbol sintáctico, guardando los nodos del árbol como elementos de un array, en vez de como booleanos. Puesto que las gramáticas pueden ser ambiguas, es necesario guardar una lista de nodos para cada uno de los posibles árboles sintácticos. Así, el resultado final es un bosque con todos los posibles árboles sintácticos.

También es posible extender el algoritmo CYK para analizar cadenas usando gramáticas libres de contexto con pesos y gramáticas libres de contexto probabilísticas. Los pesos o probabilidades serán guardados en la tabla P en vez de los valores booleanos. De esta manera P[i, j, A] contendrá el mínimo peso (máxima probabilidad) de que la subcadena desde i hasta j pueda ser derivada por A. Otras extensiones permiten al algoritmo enumerar todos los posibles análisis de una frase ordenándolos de menor a mayor peso (mayor a menor probabilidad).

Referencias

• John Cocke and Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
• T. Kasami (1965). An efficient recognition and syntax-analysis algorithm for context-free languages. Scientific report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA.
• Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n³. Information and Control 10(2): 189–208.