Algoritmus CYK (Cocke–Younger–Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti vzhledem k délce slova. Bezkontextový jazyk musí být zapsán gramatikou v Chomského normální formě.
Algoritmus vypadá takto: Vytvoříme pole , pro , kde jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0 Pro každý znak na pozici , a pro každé takové, že v gramatice existuje pravidlo , nastavíme v poli Pro každou délku podslova od 2 do : Pro každý začátek podslova od 1 do : Pro každou délku první poloviny podslova od 1 do : Jestliže v poli mají jedničkovou hodnotu i , a v gramatice existuje pravidlo , nastavíme v poli Slovo náleží do jazyka, jestliže , kde je vstupní neterminál gramatiky.
Jiné algoritmy jsou Earlyho parser a packrat parser.
Související články Dynamické programování
Kategorie:Algoritmy syntaktické analýzy