Algorytm CYK (Cocke’a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomskiego. Algorytm działa w czasie gdzie jest długością słowa, a jest rozmiarem gramatyki.
Algorytm Pseudokod algorytmu: Tworzymy tablicę dla zaś przebiega wszystkie nieterminale (czy też równoważnie ich numery), wszystkie jej wartości ustawiając na 0 Dla każdego znaku na pozycji i dla każdego takiego, że w gramatyce jest produkcja ustawiamy w tablicy Dla każdej długości od 2 do Dla każdego początku od 1 do Dla każdego podziału od 1 do Jeśli w tablicy są ustawione i a w gramatyce mamy produkcję ustawiamy Słowo należy do języka, jeśli gdzie to symbol startowy gramatyki
Przykład Dana jest gramatyka bezkontekstowa w postaci normalnej Chomskiego:
Formalnie:
Pytanie: ?
Inicjalizacja tabeli:
1 2 3 4 5 a a b b b 1 2 3 4 5
Wyrazy długości 1: pola z racji istnienia reguły pola z racji istnienia reguły
1 2 3 4 5 a a b b b 1 2 3 4 5
Wyrazy długości 2: pole ponieważ nie istnieje żadne reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych
1 2 3 4 5 a a b b b 1 2 – 3 4 5
pole z racji produkcji
1 2 3 4 5 a a b b b 1 2 – 3 4 5
pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych
1 2 3 4 5 a a b b b 1 2 – – 3 4 5
pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych
1 2 3 4 5 a a b b b 1 2 – – – 3 4 5
Wyrazy długości 3:
pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych lub tylko
1 2 3 4 5 a a b b b 1 2 – – – 3 – 4 5 1 2 3 4 5 a a b b b 1 2 – – – 3 – 4 5
pole z racji reguły
1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 5 1 2 3 4 5 a a b b b 1 2 – – – 3 – 4 5
pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol
1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 5 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 5
Wyrazy długości 4: pole z racji reguły
1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 5 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5
pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol lub ciąg symboli nieterminalnych
1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5
Wyrazy długości 5: pole z racji reguły
1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5 – 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5 – 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5 – 1 2 3 4 5 a a b b b 1 2 – – – 3 – – 4 – 5
Ponieważ symbol startowy nie jest podzbiorem zbioru w polu czyli wyraz nie jest elementem gramatyki
Zobacz też algorytm Earleya
Bibliografia
CYK Kategoria:Parsery Kategoria:Programowanie dynamiczne