Algoritmus Cocke-Younger-Kasami

Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti O(n^3) 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 T[i,j,x], pro 1 \le i \le j \le n, kde x jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0 :Pro každý znak a na pozici i, a pro každé X takové, že v gramatice existuje pravidlo X \rightarrow a, nastavíme v poli T[i,1,X] := 1 :Pro každou délku podslova i od 2 do n: ::Pro každý začátek podslova j od 1 do n-i+1: :::Pro každou délku první poloviny podslova k od 1 do i-1: ::::Jestliže v poli mají jedničkovou hodnotu T[j,k,X] i T[j+k,i-k,Y], a v gramatice existuje pravidlo Z \rightarrow XY, nastavíme v poli T[j,i,Z] := 1 :Slovo náleží do jazyka, jestliže T[1,n,S] = 1, kde S 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