Algoritmo CYK

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O algoritmo Cocke-Younger-Kasami (CYK) determina se uma cadeia de caracteres pode ser gerada por uma determinada gramática livre de contexto e, se ela puder, como ela pode ser gerada. Esse processo é conhecido como a análise sintática da cadeia, no caso, ascendente.

A versão padrão do algoritmo opera em gramáticas livres de contexto expressadas através da Forma Normal de Chomsky (CNF). No pior caso, o algoritmo possui complexidade \theta(n^3), em que n é o comprimento da cadeia de caracteres. Isso o torna um dos algoritmos mais eficientes no reconhecimento geral de linguagens livres de contexto. Entretanto, algoritmos mais rápidos e especializados existem para certos subconjuntos de linguagens livres de contexto.

Definição[editar | editar código-fonte]

Segue abaixo uma definição do algoritmo em pseudocódigo:

ROTINA CYK(
    Texto:a[1 \ldots n],     -- cadeia de caracteres a ser testada
    Gramatica:R[1 \ldots r], -- gramática contendo símbolos terminais e não-terminais
    Vetor<Simbolo>:R_s,      -- símbolos de início da gramática
    Vetor<Booleano>:P[n,n,r] -- vetor de booleanos inicializado em Falso
    )
    PARA CADA i DE 1 A n FAÇA
        PARA CADA Producao:R_j \to a_i FAÇA
            P[i,1,j] \gets Verdadeiro
    PARA CADA i DE 2 A n FAÇA
        PARA CADA j DE 1 A n-i+1 FAÇA
            PARA CADA k DE 1 A i-1 FAÇA
                PARA CADA Produção(R_A \to R_B R_C) FAÇA
                    SE P[j,k,B] \and P[j+k,i-k,C] ENTÃO
                        P[j,i,A] \gets Verdadeiro
    PARA CADA x EM Indices:R_s FAÇA
        SE P[1,n,x] = Verdadeiro ENTÃO
            RETORNE "membro da linguagem"
        SENÃO
            RETORNE "não-membro da linguagem"

Extensões[editar | editar código-fonte]

É trivial estender o algoritmo para determinar não somente se uma sentença pertence a uma linguagem, mas também a árvore de análise sintática, armazenando-se os nós como elementos do vetor ao invés de somente valores booleanos.Como o reconhecimento das gramáticas pode ser ambíguo, é necessário armazenar uma lista de nós, resultando numa floresta de árvores possíveis. Também é possível estender o algoritmo para lidar com algumas linguagens livres de contexto que não são escritas em CNF.

Ver também[editar | editar código-fonte]