A análise CKY (também chamada de CYK, de Cocke-Younger-Kasami) é um algoritmo de análise sintática para gramáticas livres de contexto que utiliza análise ascendente e programação dinâmica. Foi publicado pela primeira vez por Itiroo Sakai em 1961 e posteriormente redescoberto de forma independente por John Cocke, Daniel Younger, Tadao Kasami e Jacob T. Schwartz, após os quais recebeu o nome. O algoritmo determina se uma determinada string pode ser gerada por uma gramática e, se puder, pode construir todas as árvores de análise possíveis para essa string.
A versão padrão do CKY opera apenas em gramáticas livres de contexto na forma normal de Chomsky (CNF), onde toda regra de produção é da forma A → BC (dois não terminais) ou A → a (um terminal). Qualquer gramática livre de contexto que não gere a string vazia pode ser transformada algoritmicamente em uma gramática CNF equivalente, então essa restrição não limita a aplicabilidade do algoritmo em princípio. Para gramáticas que geram a string vazia, pode-se permitir explicitamente uma regra S → ε, onde S é o símbolo inicial.
A importância da análise CKY decorre de sua complexidade de tempo no pior caso de O(n^3 · |G|), onde n é o comprimento da string de entrada e |G| é o tamanho da gramática CNF. Isso a torna um dos algoritmos de análise sintática mais eficientes em termos de comportamento assintótico no pior caso, embora outros algoritmos possam ter tempos médios de execução melhores em cenários práticos.
Visão Geral do Algoritmo
O algoritmo funciona preenchendo uma tabela tridimensional P[l, s, v], onde cada entrada é um valor booleano que indica se a substring de comprimento l começando na posição s pode ser gerada a partir do não terminal R_v. A tabela é preenchida em ordem crescente de comprimento da substring, começando com substrings de comprimento 1.
Para cada símbolo terminal na entrada, o algoritmo verifica todas as produções unitárias da forma R_v → a_s e marca as entradas correspondentes da tabela como verdadeiras. Para substrings mais longas, ele considera cada partição possível da substring em duas partes e verifica se existe uma produção A → BC tal que B gere a primeira parte e C gere a segunda parte. Se tal produção existir, a entrada para A é definida como verdadeira.
Pseudocódigo
que a entrada seja uma string I consistindo de n caracteres: a1 ... an.
que a gramática contenha r símbolos não terminais R1 ... Rr, com símbolo inicial R1.
que P[n,n,r] seja um array de booleanos. Inicialize todos os elementos de P como falso.
que back[n,n,r] seja um array de listas de triplas de retroapontamento. Inicialize todos os elementos de back como a lista vazia.
para cada s = 1 a n
para cada produção unitária Rv → as
defina P[1,s,v] = verdadeiro
para cada l = 2 a n -- Comprimento do intervalo
para cada s = 1 a n-l+1 -- Início do intervalo
para cada p = 1 a l-1 -- Partição do intervalo
para cada produção Ra → Rb Rc
se P[p,s,b] e P[l-p,s+p,c] então
defina P[l,s,a] = verdadeiro,
acrescente <p,b,c> a back[l,s,a]
se P[n,1,1] for verdadeiro então
I é membro da linguagem
retorne back -- ao refazer os passos através de back, pode-se facilmente construir todas as árvores de análise possíveis da string.
senão
retorne "não é membro da linguagem"
Exemplo
Considere a seguinte gramática em CNF:
S → NP VP
VP → VP PP
VP → V NP
VP → eats
PP → P NP
NP → Det N
NP → she
V → eats
P → with
Det → the
N → fish
Para analisar a string "she eats the fish with the fish", o algoritmo primeiro marca todas as substrings de comprimento 1. Por exemplo, P[1,1,NP] é definido como verdadeiro porque NP → she, e P[1,2,VP] é definido como verdadeiro porque VP → eats. Em seguida, ele processa substrings de comprimento 2, como "she eats", que pode ser derivada como S → NP VP, então P[2,1,S] torna-se verdadeiro. O processo continua para substrings mais longas, considerando todas as partições. No final, se P[n,1,S] for verdadeiro, a string é reconhecida como parte da linguagem, e os retroapontadores permitem a reconstrução da árvore de análise.
Aplicações e Variantes
A análise CKY é amplamente utilizada em processamento de linguagem natural e linguística computacional, particularmente para análise com gramáticas livres de contexto probabilísticas. Variantes do algoritmo foram desenvolvidas para lidar com gramáticas ponderadas e para melhorar o desempenho no caso médio. A abordagem de programação dinâmica do algoritmo também a conecta a outros métodos de análise, como o analisador Earley, que lida com gramáticas livres de contexto arbitrárias sem conversão CNF, mas tem uma complexidade de pior caso semelhante.
Em sistemas modernos de Artificial intelligence, a análise CKY foi amplamente substituída por abordagens baseadas em Neural network, particularmente modelos Transformer (architecture) usados em Large language models. No entanto, o algoritmo permanece uma técnica fundamental importante na teoria de linguagens formais e ainda é ensinado em currículos de ciência da computação. Seus princípios de programação dinâmica e análise ascendente também aparecem em outras áreas, como modelos Sequence-to-Sequence (Seq2Seq) e decodificação Beam Search.
A eficiência e clareza do algoritmo o tornaram um exemplo padrão em livros didáticos sobre análise sintática e Machine learning. Instituições de pesquisa como MIT CSAIL e Stanford AI Lab contribuíram para seu estudo e aplicação, e ele permanece relevante em campos que exigem análise exata de dados estruturados, como bioinformática e projeto de compiladores.
Limitações
A análise CKY requer que a gramática esteja na forma normal de Chomsky, o que pode aumentar o número de regras de produção e o tamanho da gramática. A complexidade de tempo de pior caso O(n^3) pode ser proibitiva para strings de entrada muito longas, especialmente em aplicações em tempo real. Além disso, a complexidade de espaço do algoritmo é O(n^2 · r), que pode ser grande para gramáticas com muitos não terminais. Apesar dessas limitações, a análise CKY permanece um referencial para algoritmos de análise exata e um conceito-chave no estudo de linguagens livres de contexto.