O algoritmo Cocke-Younger-Kasami (CYK, ou CKY) é um algoritmo de análise sintática para gramáticas livres de contexto em ciência da computação. Foi publicado pela primeira vez por Itiroo Sakai em 1961 e posteriormente redescoberto por John Cocke, Daniel Younger, Tadao Kasami e Jacob T. Schwartz, após os quais recebeu esse nome. O algoritmo emprega análise ascendente e programação dinâmica para determinar se uma determinada string pode ser gerada por uma determinada gramática, e também pode construir árvores de análise sintática. Seu tempo de execução no pior caso é O(n^3 · |G|), onde n é o comprimento da string de entrada e |G| é o tamanho da gramática na forma normal de Chomsky, tornando-o um dos algoritmos de análise sintática mais eficientes em termos de complexidade assintótica no pior caso, embora outros algoritmos possam ter melhor desempenho médio na prática.
O algoritmo CYK é amplamente utilizado em processamento de linguagem natural e projeto de compiladores, onde a análise sintática é uma etapa fundamental. É particularmente valorizado por sua simplicidade e tempo polinomial garantido, mesmo para gramáticas ambíguas. A dependência do algoritmo em programação dinâmica permite que ele lide sistematicamente com todas as análises possíveis, o que é útil em aplicações como análise sintática em linguagens de programação e análise sintática em sistemas de inteligência artificial.
Histórico
O algoritmo foi descrito pela primeira vez por Itiroo Sakai em 1961, mas ganhou destaque por meio de redescobertas independentes por John Cocke, Daniel Younger e Tadao Kasami no final da década de 1960. Jacob T. Schwartz também contribuiu para seu desenvolvimento. O nome do algoritmo reflete essas redescobertas, com o acrônimo CYK derivado de Cocke, Younger e Kasami. O algoritmo tornou-se um tópico padrão no ensino de ciência da computação, particularmente em cursos sobre linguagens formais e teoria dos autômatos. Seu desenvolvimento precede as abordagens modernas de aprendizado de máquina e redes neurais para análise sintática, mas permanece relevante como técnica fundamental.
Forma Padrão: Forma Normal de Chomsky
A versão padrão do algoritmo CYK exige que a gramática livre de contexto esteja na forma normal de Chomsky (FNC). Na FNC, todas as regras de produção são da forma A → BC (onde B e C são não terminais) ou A → α (onde α é um símbolo terminal). Além disso, o símbolo inicial S pode ter uma produção S → ε para permitir a string vazia. Qualquer gramática livre de contexto que não gere a string vazia pode ser transformada em uma gramática FNC equivalente, como demonstrado por Sipser em 1997. Essa transformação é algorítmica e preserva a linguagem gerada pela gramática. O requisito da FNC simplifica o processo de análise sintática porque limita as maneiras pelas quais uma substring pode ser dividida em duas partes, permitindo programação dinâmica eficiente.
Descrição do Algoritmo
O algoritmo CYK opera preenchendo uma tabela tridimensional P[l, s, v], onde l é o comprimento de uma substring, s é a posição inicial dessa substring e v é um não terminal. A entrada P[l, s, v] é definida como verdadeira se a substring de comprimento l começando na posição s pode ser derivada do não terminal R_v. O algoritmo procede em ordem crescente de comprimento da substring, começando com comprimento 1.
Para cada substring de comprimento 1, o algoritmo verifica produções unitárias da forma R_v → a_s, onde a_s é o terminal na posição s. Para substrings de comprimento 2 ou maior, considera-se cada partição possível da substring em duas partes, e para cada produção A → BC, verifica-se se a primeira parte pode ser derivada de B e a segunda parte de C. Se sim, marca-se a substring como derivável de A. O algoritmo também mantém uma tabela de ponteiros de retorno para permitir a reconstrução das árvores de análise sintática.
No final, a string de entrada é reconhecida como membro da linguagem se P[n, 1, 1] for verdadeiro, significando que o símbolo inicial R_1 pode derivar a string inteira. Os ponteiros de retorno podem então ser usados para construir todas as árvores de análise sintática possíveis.
Exemplo
Considere a seguinte gramática na FNC:
- S → NP VP
- VP → VP PP
- VP → V NP
- VP → eats
- PP → P NP
- NP → Det N
- NP → she
- V → eats
- P → with
- N → fish
- Det → the
Esta gramática pode analisar frases como "she eats the fish with the fork". O algoritmo CYK preencheria a tabela marcando primeiro substrings de uma palavra: "she" como NP, "eats" como VP ou V, "the" como Det, "fish" como N, "with" como P e "fork" como N. Em seguida, combina substrings: "the fish" como NP (Det N), "eats the fish" como VP (V NP), e assim por diante. Eventualmente, determina que a frase inteira pode ser derivada de S, e os ponteiros de retorno revelam a estrutura da árvore de análise sintática.
Aplicações e Significância
O algoritmo CYK é significativo na teoria e prática da análise sintática. É usado em processamento de linguagem natural para análise sintática, no projeto de compiladores para análise sintática de linguagens de programação e em bioinformática para previsão de estrutura secundária de RNA. Sua complexidade de tempo no pior caso de O(n^3) é ótima para análise sintática geral de gramáticas livres de contexto no pior caso, embora algoritmos especializados como o parser Earley possam ser mais eficientes para certas gramáticas. A abordagem de programação dinâmica do algoritmo também o torna adequado para gramáticas ambíguas, pois pode enumerar todas as análises possíveis. Na inteligência artificial moderna, o algoritmo CYK foi adaptado para uso em gramáticas livres de contexto probabilísticas e análise sintática estatística, onde calcula a árvore de análise sintática mais provável dada uma distribuição de probabilidade sobre as produções.
Limitações e Extensões
Uma limitação do algoritmo CYK padrão é seu requisito de FNC, que pode aumentar o tamanho da gramática e afetar a eficiência. Existem extensões para gramáticas que não estão na FNC, como o algoritmo Earley, que lida diretamente com gramáticas livres de contexto arbitrárias. Além disso, o algoritmo CYK foi estendido para lidar com gramáticas ponderadas e gramáticas probabilísticas, onde cada produção tem um peso ou probabilidade, e o objetivo é encontrar a análise com o peso ou probabilidade máxima. Essas extensões são usadas em reconhecimento de fala e tradução automática. O algoritmo também forma a base para técnicas de análise sintática mais avançadas em modelos baseados em aprendizado profundo, embora esses frequentemente usem abordagens de redes neurais em vez de regras gramaticais explícitas.