Zobrazení zdroje stránky Algoritmus Cocke-Younger-Kasami

'''Algoritmus CYK''' (''Cocke-Younger-Kasami'') je [[algoritmus]], který určuje, zda [[slovo (formální jazyky)|slovo]] náleží do [[Bezkontextový jazyk|bezkontextového jazyka]], a to v [[Složitost algoritmů|časové složitosti]] <math>O(n^3)</math> vzhledem k délce slova. Bezkontextový jazyk musí být zapsán [[Formální gramatika|gramatikou]] v [[Chomského normální forma|Chomského normální formě]].

Algoritmus vypadá takto:
:Vytvoříme [[pole (informatika)|pole]] <math>T[i,j,x]</math>, pro <math>1 \le i \le j \le n</math>, kde <math>x</math> jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0
:Pro každý znak <math>a</math> na pozici <math>i</math>, a pro každé <math>X</math> takové, že v gramatice existuje pravidlo <math>X \rightarrow a</math>, nastavíme v poli <math>T[i,1,X] := 1</math>
:Pro každou délku podslova <math>i</math> od 2 do <math>n</math>:
::Pro každý začátek podslova <math>j</math> od 1 do <math>n-i+1</math>:
:::Pro každou délku první poloviny podslova <math>k</math> od 1 do <math>i-1</math>:
::::Jestliže v poli mají jedničkovou hodnotu <math>T[j,k,X]</math> i <math>T[j+k,i-k,Y]</math>, a v gramatice existuje pravidlo <math>Z \rightarrow XY</math>, nastavíme v poli <math>T[j,i,Z] := 1</math>
:Slovo náleží do jazyka, jestliže <math>T[1,n,S] = 1</math>, kde <math>S</math> je vstupní neterminál gramatiky.

Jiné algoritmy jsou [[Earlyho parser]] a [[packrat parser]].

== Související články ==
* [[Dynamické programování]]
{{Pahýl}}
{{Autoritní data}}

[[Kategorie:Algoritmy syntaktické analýzy]]