Cocke -Younger- Kasami - algoritmen , CYK- eller CKY - algoritmen , är en algoritm som låter dig bestämma om det är möjligt att visa en given sträng i en given kontextfri grammatik , och i så fall tillhandahålla dess utdata. Med andra ord är det en stränganalysalgoritm . Algoritmen implementerar bottom-up-parsning och är baserad på den dynamiska programmeringsmetoden . dess upptäckare: John Cock, Daniel Younger, Tadao Kasami och Jacob T. Schwartz. De använde sig av bottom-up-analys och dynamisk programmering.
Standardversionen av CYK fungerar endast med kontextfria grammatiker som ges i normal form (CNF). Men vilken kontextfri grammatik som helst kan konverteras (efter konvertering) till en CNF-grammatik som uttrycker samma språk ( Sipser 1997 ).
Det är en av de mest effektiva analysalgoritmerna när det gäller asymptotisk komplexitet i värsta fall , även om det finns andra algoritmer med bättre genomsnittliga exekveringstider i många praktiska scenarier [1] .
Algoritmen fungerar enligt följande: i det första steget skrivs ett ord på den första raden och varje icke-terminaltecken läggs till på raden, under vilken terminaltecknen visas. Därefter, för varje cell i rutnätet, är det nödvändigt att gå vertikalt från topp till botten till den markerade cellen och den andra cellen upp diagonalt. För varje sådant steg kombineras cellerna och kontrolleras för att hitta kombinationen i grammatiken. Om den hittas läggs den vänstra icke-terminalen till i rutnätscellen. Om det initiala tecknet efter alla steg finns på sista raden kan ordet hämtas från den givna grammatiken [2] .
Den dynamiska programmeringsalgoritmen kräver att den kontextfria grammatiken konverteras till Chomsky Normal Form (CNF) eftersom den kontrollerar om den aktuella sekvensen kan delas upp i två mindre sekvenser. All kontextfri grammatik som inte producerar en tom sträng kan representeras i CNF med hjälp av produktionsregler [3] .
I pseudokod ser algoritmen ut så här:
CYK-algoritm: givet en sträng S med n tecken: a 1 ... a n . ges en grammatik som innehåller r icke-terminala symboler R 1 ... R r . Innehåller en delmängd R s av initiala tecken. def array P [ n , n , r ] av booleska värden initierade till False. för varje i = 1 : n för varje produktion R j -> a i tilldela P [ 1 , i , j ] = Sant för varje i = 2 : n är intervalllängden för varje j = 1 : n - i +1 - - början av intervallet för varje k = 1 : i -1 är uppdelningen av intervallet för varje produktion RA -> R B R C om P [ k , j , B ] och P [ i - k , j + k , C ] tilldela sedan P [ i , j , A ] = Sant om för några x från mängden s P [n, 1 , x ] = Sant, där s är alla index för R s så återkommer S tillhör språket annars hör retur S inte till språket| Formella språk och formella grammatiker | |
|---|---|
| Allmänna begrepp | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 |
|
| analysera | |