Yazan : Şadi Evren ŞEKER

CYK parçalama algoritması (parse algorithm), verilen girdinin (input), bir içerikten bağımsız dil (context free language) için nasıl parçalanabileceğini gösterir. CYK algoritmasının ismi, algoritmayı bulan kişilerin baş harflerinden oluşur: Cocke–Younger–Kasami.

Algoritmadaki amaç, içerikten bağımsız dilin üretebileceği parçalama ağaçlarını veya alternatif parçalama yöntemlerini gösterebilmektir.

[flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/cyk.flv /]

Bu durumu bir örnek üzerinden anlatmaya çalışalım:

Örnek olarak aşağıdaki içerikten bağımsız dili ele alalım:

S -> AB | SA

A -> BA | CB | a

B -> CC | b

C -> SS | AC|a

Yukarıdaki bu dil için örnek girdimiz (input) : “ababa” olsun ve biz bu girdiyi CYK algoritmasına göre parçalamaya çalışalım:

Bu durumu bir tablo yardımıyla yapıyoruz.

Tablomuz, girdimizin uzunluğu 5 olduğu için, 5×5 boyutlarında oluyor:

a b a b a

Yukarıda görüldüğü üzere bir tablo oluşturduk ve bu tablonun her sütunun altına, girdimizdeki bir harfi yerleştirdik.

CYK algoritması, bu tablo üzerinde bir merdivenin basamaklarını tırmanır gibi sırasıyla her seviyede, altında kalan kelimeyi bulacaktır.

Bu durum aşağıdaki tabloda gösterilmiştir:

ababa
abab baba
aba bab aba
ab ba ab ba
a b a b A
a b a b a

Görüldüğü üzere, tablodaki en üst satırda bütün girdinin parçalanmış hali yer alacaktır. Bunun altında girdi boyutunun bir eksiği, onun altında iki eksiği … nihayet en altta tek boyutlu girdiler yer alacaktır.

CYK algoritmasının amacı bu tek boyutlu girdilerden yukarı doğru girdinin tamamını oluşturmaktır.

Şimdi CYK algoritması ile çalışmaya hazırız, önce her sonlu (terminal) için dilimizde tanımlı devamlıları (non-terminal) yerleştiriyoruz.

Örneğin a harfi için A ve b harfi için B devamlılarını yazabiliriz:

A,C B A,C B A,C
a b a b a

Ardından iki uzunluğundaki kelimelere geçiyoruz.

Örneğin aşağıdaki tabloda gösterilen renkli hücreye gelen değer, bu hücrenin hemen altındaki iki hücrede bulunan terminallerden üretilen değerdir.

A,C B A,C B A,C
a b a b a

Bu hücreye, altında kalan ab girdisinin değeri yazılacaktır. Bu girdiyi belirleyen değer ise a girdisi ve b girdisi için yazılan bir alt satırdaki değerlerdir.

O halde ab girdisi için CFL üzerinde AB, CB aranacak. Bu değerlerden, AB’ye S, CB’ye A’dan ulaşılabiliyor o halde bu hücreye S,A yazıyoruz.

Diğer hücreler de benzer şekilde hesaplanır:

S,A A S,A A
A,C B A,C B A,C
a b a b a

Bir üst satırı da benzer şekilde hesaplayalım. Burada ilk sütuna aba girdisinin sonucu yazılacak. Bu girdi ab + a veya a+ab şeklinde yazılabilir. O halde bir önceki satırlardan hesapladığımız değerleri bu denkleme yazacak olursak:

ab -> S,A

a -> A,C

ba -> A

b -> B

ihtimaller şunlar olacaktır:

SA,SC,AA,AC,AB

Bu ihtimalleri içeren devamlılar sırasıyla aşağıda verilmiştir:

S , X, X, C ,S

Yukarıdaki satırda bulunan X değerlerine geçiş olmadığı gösterilir. Yani CFL üzerinde SC veya AA sonucuna ulaşılan bir devamlı yoktur.

Diğer hücreleri de aşağıdaki şekilde doldurabiliriz:

S,C S,A S,C
S,A A S,A A
A,C B A,C B A,C
a b a b a

Bir üst satırda ilk hücre için bakılacak alternatifler aşağıdadır:

aba+b veya a + bab

bu alternatiflerden aba + b için : S,C + B -> SB, CB

diğer alternatif olan a +bab için A,C + S,A -> AS, CS, AA, CA

Toplamda alternatiflerimiz : SB, CB, AS, CS, AA, CA

Bu alternatiflerin dilimizdeki tanımlarına bakarsak : X, A, X, X, X, X

Sadece A sonucu çıkar.

A
S,C S,A S,C
S,A A S,A A
A,C B A,C B A,C
a b a b a

Bir yanındaki sütun için alternatiflerimiz : BS, BC, SA, SC, AA, AC

Bu alternatiflerin dilimizdeki tanımları: X, X, S, X, X, C

Sonuç olarak S,C bulunur:

A S,C
S,C S,A S,C
S,A A S,A A
A,C B A,C B A,C
a b a b a

Son satırımızdaki ihtimaller ise:

a+baba : AS, AC, CS, CC

abab+a : AA, AC

Bütün ihtimaller bu durumda: AS, AC, CS, CC, AA

Bu ihtimallerin dilde tanımları : X, C, X, B, X

Dolayısıyla bu hücrenin değeri CB olarak bulunur.

C,B
A S,C
S,C S,A S,C
S,A A S,A A
A,C B A,C B A,C
a b a b a

Yukarıdaki bu tablo bize, örnek girdinin parçalanması için alternatif yolları göstermektedir.

Örneğin girdimiz ababa ise, bu girdi için C veya B’den başlanarak parçalama yapılmalıdır. Örneğin dilimiz, S ile başlamak zorundaysa bu girdi parçalanamaz.

Yukarıdaki bu tablonun bir parçalama ağacı (parse tree) şeklinde çizimi aşağıdadır:

Yukarıdaki şekilde C veya B ile başlayan iki ayrı parçalama ağacı (parse tree) örneği gösterilmiştir.

İki taraftan da ababa sonucuna ulaşıldığı görülebilir. Elbette bu parçalama işlemi sırasında farklı alt dallardan da dolaşılması söz konusu olabilir. Örneğin turuncu renke gösterilen A düğümünü ele alalım. Bu düğüm A->AB şeklinde açılmıştır. Oysaki aynı düğümün CB şeklinde açılıp buradan da “ab” girdisine indirilmesi mümkün olabilirdi.

Yorumlar

  1. sare

    Hocam cyk parsing algoritması ile verilen bir string ayrıştırılarak stringin bu gramer tarafından oluşturulabilecegi sonucunu cıkarıyoruz peki bu algoritma kullanılarak o gramer a ait tum kelimelerin bulunması mumkun mu bu konuda bilgi verebilir misiniz ?

  2. Şadi Evren ŞEKER Article Author

    Kısaca evet.

    Sadece CYK değil, bütün parçalama (parsing) algoritmaları verilen bir girdinin (input) verilen kurala (gramer) uygun olup olmadığını kontrol etmeyi ve uygun şekilde parçalamayı amaçlar. Ancak siz verilen kurala uygun bütün olası girdileri üretmek istiyorsanız bunun için de çeşitli yöntemler bulunuyor. En basiti kaba kuvvet yöntemi (brute force) kullanarak bir dildeki üretilebilecek bütün kelimeleri üretmek ve verilen kurala (gramer) uygun olmayanları elemektir.

    Ayrıca bazı diller (örneğin PROLOG) bu özelliği doğrudan desteklemektedir (fonksiyonlar çift yönlü olarak çalışır, yani bir input ve bir regular expression vererek parçalamak yerine, input kısmını bağımsız değişken (unbounded variable) olarak kullanmanız ve bütün olası sonuçları almanız mümkündür). Örnek olması açısından , aşağıdaki bağlantıda verilen ilk örnekte, 100 lira maaşı olan herkes listelenmiştir:

    http://www.bilgisayarkavramlari.com/2010/12/28/prolog-ile-fonksiyon-ve-liste-yonetimi/

    Benzer şekilde istediğiniz kuralı bir sonlu durum makinesi (finite state machine) çevirerek (örneğin thomson inşası (thomson’s construction) kullandığımızı düşünelim) bu makinedeik her durumu ve her geçişi dolaşan bir dolaşma algoritması (traverse algorithm) yazabilirsiniz.

  3. Cüneyt

    Hocam iyi günler.
    En alt kısımda parse tree oluştururken B den uzayan ağacın son kısmında A->AB dönüşümü üstte verilen kurallarda mevcut değil. A->BA ,A->CB şeklinde verilmiş. Doğru çözümde de ababa stringine ulaşamadık. Çözümünüz var mıdır?

  4. Tolga

    Hocam, en son elde ettiğimiz tablo sadece parse ağacının başlangıç düğümünü mü bize gösteriyor yoksa daha aşağı dallanmalarda da tablodan yararlanıyor muyuz?

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir