El algoritmo Cocke -Younger- Kasami , el algoritmo CYK o CKY , es un algoritmo que le permite determinar si es posible mostrar una cadena dada en una gramática libre de contexto determinada y, de ser así, proporcionar su salida. En otras palabras, es un algoritmo de análisis de cadenas . El algoritmo implementa el análisis de abajo hacia arriba y se basa en el método de programación dinámica . sus descubridores: John Cock, Daniel Younger, Tadao Kasami y Jacob T. Schwartz. Utilizaron análisis de abajo hacia arriba y programación dinámica.
La versión estándar de CYK solo funciona con gramáticas libres de contexto dadas en forma normal (CNF). Sin embargo, cualquier gramática libre de contexto se puede convertir (después de la conversión) a una gramática CNF que exprese el mismo lenguaje ( Sipser 1997 ).
Es uno de los algoritmos de análisis sintáctico más eficientes en términos de complejidad asintótica en el peor de los casos , aunque existen otros algoritmos con mejores tiempos de ejecución promedio en muchos escenarios prácticos [1] .
El algoritmo funciona de la siguiente manera: en el primer paso, se escribe una palabra en la primera línea y cada carácter no terminal se agrega a la línea, debajo de la cual se muestran los caracteres terminales. Después de eso, para cada celda de la cuadrícula, es necesario ir verticalmente de arriba a abajo hasta la celda marcada, y la segunda celda hacia arriba en diagonal. Para cada uno de estos pasos, las celdas se combinan y verifican para encontrar la combinación en la gramática. Si se encuentra, el no terminal izquierdo se agrega a la celda de la cuadrícula. Si, después de todos los pasos, el carácter inicial está contenido en la última línea, la palabra se puede obtener de la gramática dada [2] .
El algoritmo de programación dinámica requiere que la gramática independiente del contexto se convierta a la forma normal de Chomsky (CNF) porque verifica si la secuencia actual se puede dividir en dos secuencias más pequeñas. Cualquier gramática libre de contexto que no produzca una cadena vacía se puede representar en CNF usando reglas de producción [3] .
En pseudocódigo , el algoritmo se ve así:
Algoritmo CYK: dada una cadena S de n caracteres: a 1 ... a n . dada una gramática que contiene r símbolos no terminales R 1 ... R r . Contiene un subconjunto R s de caracteres iniciales. def array P [ n , n , r ] de valores booleanos inicializados en False. para cada i = 1 : n para cada producción R j -> a i asigne P [ 1 , i , j ] = Verdadero para cada i = 2 : n es la longitud del intervalo para cada j = 1 : n - i +1 - - el comienzo del intervalo para cada k = 1 : i -1 es la partición del intervalo para cada producción R A -> R B R C si P [ k , j , B ] y P [ i - k , j + k , C ] luego asigne P [ i , j , A ] = True si para alguna x del conjunto s P [n, 1 , x ] = True, donde s son todos índices de R s entonces devuelva S pertenece al lenguaje de lo contrario, devuelve S no pertenece al idioma| Lenguajes formales y gramáticas formales | |
|---|---|
| Conceptos generales | |
| tipo 0 | |
| Tipo 1 |
|
| Tipo 2 | |
| tipo 3 |
|
| analizando | |