Universidad de Córdoba

Escuela Politécnica Superior

Ingeniería en Informática

Métodos Universales de
Análisis Sintáctico
Algoritmo CYK

Profesor:
Nicolás Luis Fernández García

Alumnos:
Miguel Ángel Cid García
Carlos García García

Fecha:
02/05/2011

1
INDICE DE CONTENIDOS

1. INTRODUCCIÓN____________________________________________________1
1.1. EL ANALIZADOR SINTÁCTICO_______________________________________________________1
1.2. EL ALGORITMO CYK______________________________________________________________3
1.2.1. Características______________________________________________________________3

2. DESCRIPCIÓN______________________________________________________5
2.1. PREPROCESO____________________________________________________________________5
2.2. IDEA BÁSICA DEL ALGORITMO CYK__________________________________________________6
2.4. PSEUDOCÓDIGO DEL ALGORITMO CYK_______________________________________________9
2.4. RECONSTRUCCIÓN DEL ÁRBOL SINTACTICO____________________________________________9
2.5. ALGORITMO CYK PREDICTIVO_____________________________________________________10

3. EJEMPLO__________________________________________________________11
3.1. RECONOCIMIENTO DE UNA CADENA_________________________________________________11

I
INDICE DE TABLAS

Tabla 1.1 Ejemplo del método de selección de la Ruleta. ______________________ 47

Tabla 4.2 Ejemplo del método de selección de Jerarquías ______________________ 51

II
INDICE DE ILUSTRACIONES

Figura 1.1: Distribución de una planta de usando curvas de llenado de espacios. _____ 5

III
5
__________1 Introducción_
1.1. El analizador sintáctico

Un analizador sintáctico (en inglés parser) es uno de los componentes más

importante de un compilador el cual tiene como objetivo realizar un análisis sintáctico
que convierte el texto de entrada en otras estructuras (comúnmente árboles), que son
más útiles para el posterior análisis, y capturan la jerarquía implícita de la entrada. En
otras palabras, el análisis sintáctico se puede considerar como una función que toma
como entrada la secuencia de componentes léxicos producida por el análisis léxico y
produce como salida el árbol sintáctico. En la realidad, el análisis sintáctico hace una
petición al análisis léxico del componente léxico siguiente en la entrada (los símbolos
terminales), a medida que lo va necesitando en el proceso de análisis, conforme se
mueve a lo largo de la gramática.

Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los
lenguajes libres de contexto. Cabe notar que existe una justificación formal que
establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata
de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de
contexto es equivalente en capacidad computacional a un autómata de pila.

Los analizadores sintácticos fueron extensivamente estudiados durante los años 70,
detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la
creación de programas generadores de analizadores sintéticos a partir de una
especificación de la sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales y
1
como Yacc, GNU Bison y JavaCC. Estos lenguajes de programación tienden a basarse
en gramáticas libres de contexto, debido a que se pueden escribir analizadores rápidos y
eficientes para éstas.

Figura 1.1: Estructura de un analizador

Existen tres grandes clases de métodos de análisis sintáctico [1] que son los siguientes:

 Métodos universales: como los algoritmos de Cocke-Younger-Kasami (CYK)

y el método de Early son lo más conocidos, pueden analizar cualquier gramática
pero son bastante ineficientes desde un punto de vista computacional.

 Métodos de análisis descendente: se parte del símbolo de inicio de la gramática

que se coloca en la raíz y se va construyendo el árbol desde arriba hacia abajo
hasta las hojas, eligiendo la derivación que da lugar a una concordancia con la
cadena de entrada. Se basa en la idea de predice una derivación y establece una
concordancia con el símbolo de la entrada (predict/match). El análisis sintáctico
descendente corresponde con un recorrido prefijo del árbol de análisis
sintáctico(primero expandimos el nodo que visitamos y luego procesamos los
hijos).

 Métodos de análisis ascendente: se construye el árbol de análisis sintáctico

desde las hojas hasta la raíz. En las hojas está la cadena a analizar y se intenta
reducirla al símbolo de inicio de la gramática que está en la raíz. Se trata de
desplazar-se en la cadena de entrada y encontrar una subcadena para aplicar una
reducción (una regla de producción a la inversa), (shift-reduce). El análisis
sintáctico ascendente corresponde con un recorrido postorden del árbol (primero
reconocemos los hijos y luego mediante una reducción reconocemos el padre).

1.2. El algoritmo CYK

2
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

Dentro de los métodos universales esta el algoritmo de Cocke-Younger-Kasami

(CYK) para análisis sintáctico de gramáticas independientes del contexto en forma
normal de Chomsky (FNC)  fue descubierto por J. Cocke[1], pero fue publicado
independientemente por Younger [3] y Kasami [2], de ahí su nombre. Es un método
universal de análisis sintáctico que 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 FNC. Cualquier gramática libre de contexto puede ser convertida
a FNC 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 en FNC. Esto puede hacerse para mejorar la
ejecución, aunque hace el algoritmo más difícil de entender.

1.2.1. Características

Las principales características del algoritmo de CYK que definen este algoritmo se
muestra a continuación:

 Es aplicable a cualquier gramática de contexto libre. En el caso de que la

gramática no sea de contexto libre se puede transformar para que cumpla este
requisito. Por lo cual, es aplicable si interesan todos los árboles de derivación
posibles (G. ambiguas)

 Es un método de análisis universal pero existen versiones de análisis

descendente y ascendentes sobre este algoritmo.

 Es un método tabular, es decir, está basado en tablas.

 Utiliza  técnicas de programación dinámica.

 El problema se divide en subproblemas que son tratados de forma independiente.

 Las soluciones a dichos subproblemas se combinan para obtener la solución al

problema inicial.

 Simula de forma eficiente una búsqueda paralela de la estructura de análisis.

3
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

 No son aplicables para lenguajes de programación convencionales.

 Tiene poca aplicabilidad, ya que son bastante ineficientes.

 Tiene complejidad espacial proporcional a Θ(n2).

 En el peor caso asintótico la complejidad temporal de CYK es de Θ(n3), 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.

4
___________2 Descripción_
2.1. Preproceso

Para usar este algoritmo CYK, en cualquiera de sus formas, las reglas de
la gramática de contexto libre que tengamos, son necesarias transformarlas en
FNC sin cadena vacía. Para ello, las reglas deben tener uno de los dos siguientes
formatos:

A -> B C
A -> a__

donde A, B y C son símbolos no terminales, y donde a es un símbolo terminal. Las

reglas que inicialmente, no tengan uno de estos formatos habrá que transformarlas,
mediante el algoritmo que se muestra en la figura. Hay que dejar claro, que no todas las
gramáticas, pueden ser puestas en FNC sin cadena vacía y sin eliminar reglas unitarias
del tipo A ->B.

Es obvio, que esta conversión multiplicará el número de reglas aplicables, lo cual no

lleva consigo un ‘parsing’ linealmente más lento, ya que las reglas serán muchas más
pero su uso será mucho más sencillo, sin necesidad de recorrer los símbolos de su parte
derecha ya que sólo tiene dos. Eso sí, es necesario ordenar las reglas por su parte
derecha, y guardar con cada símbolo, cuál es la primera regla que contiene dicho
símbolo como primero en su parte derecha (si no, la velocidad dependen directamente

5
del número medio de reglas, multiplicándose por veinte o treinta el tiempo de
reconocimiento de una frase).

Figura 2.1: Algoritmo que pasa una gramática en formato FNC

Como las reglas de los dos tipos permitidos, no se aplican conjuntamente, una extensión
regular de las reglas originales (las que permiten paréntesis...) disminuye el número de
reglas en FNC creadas.

Los símbolos generados durante el proceso de transformación de las reglas serán,

totalmente transparentes al usuario, no apareciendo en los árboles, ni en pantalla.

2.2. Idea básica del algoritmo CYK

La idea del algoritmo es explorar todas las posibles formas de derivar la

palabra, para demostrar que puede ser reconocida por la gramática. Para ello, se
parte de una gramática en FNC, ya que esta tiene mejores propiedades a la hora
de calcular la eficiencia, y de una cadena.
6
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

Como antes se ha mencionado, los datos de entrada del algoritmo son los siguientes:

 Gramática G = (Vn, VT, P, S) en FNC

 Una cadena w = a1a2 …an cuya pertenencia a L(G) se quiere reconocer

La versión original de este algoritmo hace uso de una tabla bidimensional triangular,
que recibe el nombre de ‘chart’, la cual contiene las posiciones de la cadena de entrada
donde se almacena los resultados parciales obtenidos. Para rellenar la tabla, se colocará
los símbolos no terminales que pueden generar dicha letra o símbolo terminal (Reglas
del tipo A->a). De esta manera, para una cadena o palabra de entrada formada por 6
letras, la tabla chart tomará la siguiente forma:

0 1 2 3 4 5 6
1 a1 {A}
2 a2 {A}
3 a3 {A}
4 a4 {C}
5 a5 {C}
6 a6 {C,B
}

Primero, se aplicaran las reglas que llevan a los símbolos terminales. Estos, como se
muestra en la tabla, se colocaran en las celdas chart[n,n-1], donde es n va desde 1 a 6.
Los símbolos no terminales que los generan se ubicarán en la diagonal de la tabla, es
decir, en las celdas chart[n,n]. Como se ilustra, puede suceder que en una gramática
pueda haber reglas de producción que genere el mismo símbolo terminal, entonces para
dicho caso tan solo hay que colocar el conjunto de símbolos no terminales en la celda
correspondiente. Para la generación de las celdas restante, se irá rellenando las celdas
desde la columna la derecha hacia la izquierda y desde abajo hacia arriba. La siguiente
tabla muestra el orden para la tabla chart del ejemplo anterior.

0 1 2 3 4 5 6
1 a1 {A} 1 3 6 10 15
2 a2 {A} 2 5 9 14
3 a3 {A} 4 8 13
4 a4 {C} 7 12
5 a5 {C} 11
6 a6 {C,B
}

7
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

En estas celdas de la tabla se realizarán las posibles combinaciones para ver si alguna
genera alguna regla de producción contenida en la gramática, aplicando tan solo las
reglas de producción del tipo A -> CB. Las celdas que se deben mirar para las posibles
combinaciones dependen de la celda en que se esté trabajando y sigue este paso:

Para la celda chart[i,j], mirar las posibles combinaciones de chart[i, k] y

chart [k+1, j], donde i indica la fila, j la columna y k un valor
comprendido ente i ≤ k ≤ j

Hay que tener en cuenta que si en alguna de las celdas tiene un conjunto de símbolos
no terminales habrá que realizar la combinación de cada uno de los símbolos con el
símbolo de la otra celda. También, es importante mencionar que el orden establecido en
este paso no puede ser alterado, por ejemplo, si en la celda chart[i, k] = {C} y en la
celda chart[k+1, j] = {C,B}, las combinaciones serán CB y CC, dando lugar, la primera
combinación, a introducir en la celda chart[i, j] = {A}, pero no generará la combinación
BC ya que no este no es el orden preestablecido. Por último, para una misma celda
siempre se dará el caso de que tomará un valor ya que de todas las combinaciones que
se han hecho para esa celda solo se podrá aplicar una regla para la cadena que se está
reconociendo. La siguiente figura, muestra las posibles combinaciones de los símbolos
no terminales para la celda chart[1,6].

Figura 2.2: Introducción de una regla en una celda de la tabla chart

El algoritmo reconocerá la cadena en el caso que en la celda superior izquierda de la

tabla se obtenga el axioma. Un adecuado ordenamiento de las reglas y de los símbolos
equivalentes (o un preprocesamiento de los mismos en forma de nuevas reglas) permite
acelerar el proceso.

8
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

2.4. Pseudocódigo del algoritmo CYK

El siguiente pseudocódigo simula el algoritmo CYK estándar, el cual se ha

definido en el apartado anterior, de la forma más clara posible.

2.4.1. Extensión del algoritmo para reconstruir del árbol

sintáctico

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.

Este proceso se desarrollará para cada árbol sintáctico a partir del axioma, es decir, que
va a desarrollar los árboles sintácticos de aquellas cadenas que pertenecen al lenguaje.
Este análisis se llevará a cabo deshaciendo las reducciones, esto es, siguiendo el camino
opuesto al de reconocimiento. Al crear todos los posibles árboles, podremos ver todos
los caminos que llevan al análisis de la cadena.

La reconstrucción de todos los árboles de análisis posibles (o secuencias de reglas

aplicables para construir la cadena de entrada), requiere recursión múltiple, dado que
además de invertir el proceso de análisis (el backtraking típico de los procesos basados
en programación dinámica como es CYK), debemos multiplicar el número de árboles
cada vez que detectamos una ambigüedad (dos maneras distintas de rellenar una misma
casilla de análisis).

9
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

El siguiente pseudocódigo simula la reconstrucción del árbol sintáctico.

2.5. Algoritmo CYK predictivo

También sería especialmente interesante, que se dispusiera de un
algoritmo con el que fuese posible predecir, tras haber aplicado todas las reglas a
cada palabra que se va leyendo, y a la combinación de ésta con las que la
preceden, cuáles son las posibles siguientes.

Para ello, es necesario precompilar la gramática, y saber para cada símbolo no terminal
de la gramática en FNC, cuáles son los símbolos terminales que los pueden encabezar.
El procedimiento para la predicción de símbolos se muestra a continuación.

10
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

El procedimiento anterior sería el que está desarrollado e integrando en el

procedimiento de CYK y se tendría como resultado el algoritmo del cuadro.

11
______________3 Ejemplo_
3.1. Reconocimiento de una cadena

Tenemos el siguiente conjunto de producciones de una gramática que genera la

llamada a una función:

P={
S -> DS
S -> Ɛ

13
 D -> T id(P);
T -> int
P -> TL
P -> Ɛ
L -> ,TL
L -> Ɛ
}

Lo primero que debemos hacer es poner la gramática en FNC, para ello aplicaremos lo
siguiente pasos:

- Eliminación de las producciones épsilon

- Eliminación de las reglas unitarias
- Conversión a la gramática FNC
1. Eliminación de las producciones epsilon

Para eliminar las producciones épsilon se duplicaran las reglas que contienen
epsilon, quedando de la siguiente manera:

P={
S -> D
S -> DS
D -> T id();
D -> T id(P);
T -> int
P -> T
P -> TL
L -> ,T
L -> ,TL
}

2. Eliminación de las reglas unitarias

Después de limpiar la gramática para que no queden reglas ninguna regla épsilon
se pasará a eliminar las reglas unitarias (A ->B), para poder realizar esta eliminación
sustituirá el símbolo terminal por la regla a las que deriva. A continuación se muestra la
gramática después de realizar este paso.

P={
S -> T id();
S -> T id(P);
S -> DS
D -> T id();
D -> T id(P);

14
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

T -> int
P -> int
P -> TL
L -> ,T
L -> ,TL
}

Como se puede apreciar esto produce aumento el número de reglas de producción, para
simplificar aun más y que quede la gramática más simple, se puede eliminar la reglas
producidas por el símbolo no terminal D, ya que las reglas que produce este está
contenido dentro del axioma S. Al aplicar esta simplificación la gramática quedaría de
la siguiente manera.

P={
S -> T id();
S -> T id(P);
S -> SS
T -> int
P -> int
P -> TL
L -> ,T
L -> ,TL
}

3. Conversión a la gramática a FNC

Para convertir la gramática a la FNC, primero se pasa los símbolos terminales a

una regla unitaria, quedando la gramática de cómo se muestra.

P={
S -> TABCD
S -> TABPCD
S -> SS
A -> id
B -> (
C -> )
D -> ;
T -> int
P -> int
P -> TL
L -> ET
L -> ETL
E -> ,

15
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

Finalmente se transforma las reglas que contengas más de dos símbolos terminales. La
gramática en FNC que se obtiene es la siguiente.

16
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

P={
S -> TSI
SI-> ASII
SII -> BSIII
SII -> BSIV
SIII -> CD
SIV -> PSIII
S -> SS
A -> id
B -> (
C -> )
D -> ;
T -> int
P -> int
P -> TL
L -> ET
L -> EP
E -> ,
}

La cadena que se quiere que sea reconocida por el algoritmo es la siguiente:

int h(int,int);

17
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

Para empezar a realizar el algoritmo, primero se pondrán los símbolos terminales a

modo de referencia y en la diagonal se podrán las reglas unitarias que llevan a esos
símbolos terminales.

0 1 2 3 4 5 6 7 8

1 int {T,P
}
2 h {A}

3 ( {B}

4 int {T,P
}
5 , {E}

6 int {T,P
}
7 ) {C}

8 ; {D}

Después de rellenar la diagonal principal de la tabla se pasa a rellenar el resto de celdas.

Si se sigue la idea que se ha expuesto, a continuación se pasará a rellenar la tabla como
anteriormente se especifico. La primera celda que se rellena de la tabla es chart(5, 6), la
combinación de la celda chart(5, 5) y chart(6, 6) produce la regla L -> ET y L ->EP.
Aplicando esta regla, la tabla se queda como se muestra a continuación.

0 1 2 3 4 5 6 7 8

1 int {T,P
}
2 h {A}

3 ( {B}

4 int {T,P
}
5 , {E} {L}

6 int {T,P
}
7 ) {C}

8 ; {D}

18
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

La siguiente celda en la que se obtiene una regla de producción es chart (4, 6). La
combinación viene dada por las celdas chart(4, 4) y chart(5, 6) y produce la regla P ->
TL Entonces en esta celda se coloca el conjunto formado por P.
0 1 2 3 4 5 6 7 8

1 int {T,P {S}

}
2 h {A} {SI}

3 ( {B} {SII}

4 int {T,P {P} {SIV}

}
5 , {E} {L}

6 int {T,P {SIV}

}
7 ) {C} {SIII}

8 ; {D}

Luego el algoritmo se sitúa en la celda chart(7,8) y con la única combinación posible

produce la regla SIII ->CD.

0 1 2 3 4 5 6 7 8

1 int {T,P
}
2 h {A}

3 ( {B}

4 int {T,P {P}

}
5 , {E} {L}

6 int {T,P
}
7 ) {C} {SIII}

8 ; {D}

19
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

A continuación, las celdas chart(6, 8) y chart(4, 8) se rellenan de la misma forma pero

de forma sucesiva. En ella se coloca el símbolo no terminal SIV producido por la unión
de los símbolos no terminales P y SIII .

0 1 2 3 4 5 6 7 8

1 int {T,P
}
2 h {A}

3 ( {B}

4 int {T,P {P} {SIV}

}
5 , {E} {L}

6 int {T,P {SIV}

}
7 ) {C} {SIII}

8 ; {D}

La siguiente celda a rellenar es chart(3, 8) que viene dada por la unión de las celdas
chart(3,3) y chart(4,8). Esta unión produce la regla SII -> BSIV, por lo tanto colocamos
en dicha celda el símbolo no terminal SII.

0 1 2 3 4 5 6 7 8

1 int {T,P
}
2 h {A}

3 ( {B} {SII}

4 int {T,P {P} {SIV}

}
5 , {E} {L}

6 int {T,P {SIV}

}
7 ) {C} {SIII}

8 ; {D}

20
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

La celda chart(2, 8) es la siguiente que pasa a ser rellenada. En ella se colocará el

símbolo no terminal SI, esto viene dado por la combinación de la celda chart(2, 2) y
chart(3, 8), es decir, la unión de A y SII produce la regla que lleva al símbolo SI.

0 1 2 3 4 5 6 7 8

1 int {T,P
}
2 h {A} {SI}

3 ( {B} {SII}

4 int {T,P {P} {SIV}

}
5 , {E} {L}

6 int {T,P {SIV}

}
7 ) {C} {SIII}

8 ; {D}

Para terminar el análisis, se realiza las posibles combinaciones de la celda chart(1,8),

en ella se debería de obtener el axioma. Como se muestra en la tabla, finalmente si se
consigue el símbolo S (axioma), este viene dado por la unión de la celda chart (1,1) y
chart (2,8)

0 1 2 3 4 5 6 7 8

1 int {T,P {S}

}
2 h {A} {SI}

3 ( {B} {SII}

4 int {T,P {P} {SIV}

}
5 , {E} {L}

6 int {T,P {SIV}

}
7 ) {C} {SIII}

8 ; {D}

21
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

Como se ha podido comprobar, el algoritmo si es capaz de reconocer la cadena de

entrada que se ha introducido en el compilador.

Otro ejemplo

Este es un ejemplo sencillo del uso del algoritmo de Chomsky sobre una
gramática que está en la FNC.

P={
S -> AB
A -> CD
A -> CF
B -> EB
F -> AD
B -> c
C -> a
D -> b
E -> c
}

Si se quiere reconocer la cadena aaabbbcc, el algoritmo rellenará la tabla de la

siguiente manera.

22
 Métodos Universales de Análisis Sintáctico: Algoritmo CYK

Bibliografía
[1]  Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman(1990): Compiladores, Principios,
Técnicas Y Herramientas. Pearson Educación, Stanford University. ISBN:
9684443331. http://books.google.es/books?
id=yG6qJBAnE9UC&pg=PA164&lpg=PA164&dq=M
%C3%A9todos+universales+de+an%C3%A1lisis+Sint
%C3%A1ctico.&source=bl&ots=rrVJTV8ZmN&sig=iDgwaKVdmPF9y0xOsA
L2r5CCfBI&hl=es&ei=EC2kTZflHIO1hAeO1vjLCQ&sa=X&oi=book_result&c
t=result&resnum=1&ved=0CBgQ6AEwAA#v=onepage&q=M%C3%A9todos
%20universales%20de%20an%C3%A1lisis%20Sint%C3%A1ctico.&f=false

[2]   John Cocke and Jacob T. Schwartz (1970). Programming languages and their
compilers: Preliminary notes. Technical report, Courant Institute of
Mathematical Sciences, New York University.

[3]  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.

[4]    Daniel H. Younger (1967). Recognition and parsing of context-free languages

in time n3. Information and Control 10(2): 189–208.

http://ants.dif.um.es/staff/juanbot/traductores/files/20022003/tema3.pdf

http://lorien.die.upm.es/juancho/pfcs/DPF/capitulo5.pdf

http://ocw.unican.es/ensenanzas-tecnicas/teoria-de-automatas-y-lenguajes-
formales/material-de-clase-nuevo/nuevo/4-4CYK.pdf

http://coleweb.dc.fi.udc.es/cole/library/ps/Alo2000a_B.pdf

http://www.ecst.csuchico.edu/~juliano/Computing/CYKalgorithm.pdf

http://jones.ling.indiana.edu/~mdickinson/09/645/slides/10-parsing/10a-cyk-2x3.pdf

Ejemplo Java: http://www.marco-maniscalco.de/?p=229

Ejemplo: http://www.diotavelli.net/people/void/demos/cky.html

23
Métodos Universales de Análisis Sintáctico: Algoritmo CYK

24