Algoritmo CYK
O algoritmo de Cocke-Younger-Kasami (CYK) determina se unha cadea pode ser xerada por unha gramática libre de contexto e, se é posible, como pode ser xerada. Este proceso é coñecido como análise sintáctico da cadea. O algoritmo é un exemplo de programación dinámica.
A versión estándar de CYK recoñece linguaxes definidas por unha gramática libre de contexto escrita na forma normal de Chomsky (CNF). Calquera gramática libre de contexto pode ser convertida a CNF sen moita dificultade, CYK pode usarse para recoñecer calquera linguaxe libre de contexto. É posible estender o algoritmo CYK para que traballe sobre algunhas gramáticas libre de contexto non escritas como CNF. Isto pode facerse para mellorar a execución, aínda que fai o algoritmo máis difícil de entender.
O peor caso asintótico a complexidade temporal de CYK é Θde (n3), onde n é a lonxitude da cadea analizada. Isto fai a este algoritmo un dos máis eficientes (nestes termos) no recoñecemento das linguaxes libres de contexto. Con todo, existen outros algoritmos cun mellor funcionamento para certos subconjuntos das linguaxes libres de contexto.
O algoritmo
[editar | editar a fonte]O algoritmo de CYK é un algoritmo de análise ascendente. e a súa importancia teórica vén dada ao poder usarse para probar que o problema de pertenza ás linguaxes libres de contexto é decidible.
O algoritmo de CYK para o problema de pertenza é o seguinte:
Let O String de entrada consiste en n caracteres, a1... an.
Let a gramática conten r símbolos terminais e non-terminais R1... Rr.
A gramática conten o subconxunto Rs que é o conxunto de símbolos iniciais.
Let P[n,n,r] un array de booleans. Inicialice todos os valores de P a falso.
For each i = 1 to n
For each produción unitaria aj → ai, set P[i,1,j] = true.
For each i = 2 to n -- Lonxitude do arco
For each j = 1 to n-i+1 -- Comezo do arco
For each k = 1 to i-1 -- Partición do arco
For each producion RA -> RB RC
If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
If calquera P[1,n,x] is true (x é iterado sobre o conxunto s, onde s son todos os índices para Rs)
Then string pertence á linguaxe
Else string non pertence á linguaxe
Informalmente
[editar | editar a fonte]En termos informais, este algoritmo considera todas as posibles subsecuencias dunha secuencia de palabras e establece P[i,j,k] a verdadeiro se a subsecuencia de palabras que empezan desde i de lonxitude j pode ser xerada desde Rk. Unha vez consideradas as subsecuencias de lonxitude 1, continúase coas de lonxitude 2, e así sucesivamente. Para subsecuencias de lonxitude 2 ou maior, considérase cada posible partición da subsecuencia en dous partes, e compróbase se existe algunha regra P → Q R na que Q concuerda coa primeira parte e R coa segunda. Se é así, establécese que P concuerda coa subsecuencia completa. Unha vez que este proceso complétese, a frase é recoñecida pola gramática se a subsecuencia que contien a frase completa concuerda co símbolo inicial.
| S | ||||||
| VP | ||||||
| S | ||||||
| VP | PP | |||||
| S | NP | NP | ||||
| NP | V, VP | Det. | N | P | Det | N |
| she | eats | a | fish | with | a | fork |
Extensión do algoritmo
[editar | editar a fonte]É fácil estender o algorimo paraque non só determine se unha frase pertence a unha linguaxe, senón que tamén constrúa unha árbore sintáctica, gardando os nodos da árbore como elementos dun array, no canto de como booleanos. Posto que as gramáticas poden ser ambiguas, é necesario gardar unha lista de nodos para cada unha das posibles árbores sintácticas. Así, o resultado final é un bosque con todos as posibles árbores sintácticas.
Tamén é posible estender o algoritmo CYK para analizar cadeas usando gramáticas libres de contexto con pesos e gramáticas libres de contexto probabilísticas. Os pesos ou probabilidades serán gardados na táboa P no canto dos valores booleanos. Deste xeito P[i,j,A] conterá o mínimo peso (máxima probabilidade) de que a subcadena desde i ata j poida ser derivada por A. Outras extensións permiten ao algoritmo enumerar todos as posibles análises dunha frase ordenándoos de menor a maior peso (maior a menor probabilidade).
Notas
[editar | editar a fonte]- John Cocke e Jacob T. Schwartz (1970). Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University.
- 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.
- Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n3. Information and Control 10(2): 189–208.
