Yazan : Şadi Evren ŞEKER

Bu yazının amacı, bilgisayar bilimlerinde özellikle derleyici tasarımı (compiler design) konusu altında geçen Earley Parçalama Algoritmasını (Earley Parsing Algorithm) açıklamaktır. Bu algoritmanın amacı, verilen bir gramer ile verilen bir girdiyi parçalayarak varsa bu girdideki hatayı bulmak, veya anlamsal olarak bir gösterim elde etmektir.

Algoritmanın çalışması için bir girdi ve bir de dil tanımı yapılması gerekir. Bu yazı kapsamında konunun anlaşılması için örnek üzerinden açıklama yapılacaktır. Konuyu anlamaya aşağıdaki dil tanımını (CFG) ele alarak başlayalım:

S → E

E → bEb | aEa | ɛ

Amacımız bu dil için baab şeklinde verilen bir girdiyi parçalamak olsun.

Earley algoritması, öncelikle parçalanacak olan girdinin her elemanının öncesinde ve sonrasında bierer durum analizi yapacak şekilde çalışmaya başlar.

Örneğimizde geçen baab girdisi için aşağıda gösterildiği gibi bir durum tablosu oluşturuyoruz:

b a a b
@1 @2 @3 @4 @5

Yukarıdaki tabloda görüldüğü üzere her girdi elemanından önce ve sonrasına gelecek şekilde 5 farklı durumu işaretledik.

Algoritmanın amacı bu işaretlenen adımları doğru bir şekilde doldurabilmek. Başlangıç durumunda, dilimizde bulunan ve başlangıçta (S başlangıç kabul edilirse) erişilebilen bütün kural tanımlarını ilk duruma yazarak algoritmamıza başlıyoruz.

b a a b
@1

S →.E

@ 1

E→.bEb @ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2 @3 @4 @5

Yukarıdaki gösterimden anlaşılacağı üzere kurallarımız arasında yer alan bütün durumlar ulaşılabilir kabul edilmiş ve bu durumların tamamı listelenmiştir. Ayrıca bu durumların tamamı 1. adımda gelen kurallar olduğu için her kuralın altına bu durumu belirten @1 sembolü eklenmiştir.

Algoritmamızın devamında ikinci adıma geçmek için gelen girdi sembolünü işletiyoruz.

Bu aşamada sorumuz, acaba girdimiz olan b sembolü geldiğinde bu kurallardan hangileri ilerler?

Noktaların konumuna dikkat edilirse, sırada b sembolü bekleyen tek kural, E->.bEb şeklinde ifade edilen kuraldır.

Bir sonraki adıma bu kuralda bulunan b sembolünü ilerleterek devam ediyoruz:

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E → b.Eb

@ 1

@3 @4 @5

Yeni halinde, noktayı bir sembol ilerlettik. Bu durumda noktadan sonra beklenen sembol E devamlısı (non-terminal) olmuş oluyor. O halde dilimizde bulunna E kuralının tanımını bu adıma ekliyoruz.

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa

@ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

@3 @4 @5

Görüldüğü üzere dil tanımımızda bulunan bütün E kuralları ikinci adımda eklenmiştir. Bu kuralların eklendiği adımı ifade etmek için kuralların altına @2 işareti yerleştirilmiştir.

Tam bu noktada dikkat edilecek önemli bir husus, E teriminin boşluk olabileceğidir. O halde E terimini bekleyen bütün sembollerin atlatılması da söz konusudur. Yani hiçbir girdi gelmese bile E terimini ilerleterek bir sonraki terime devam edebiliriz. Bu yüzden listemizin başında bulunan kuralın E harfi ilerletilmiş halini de listenin sonuna ekliyoruz.

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3 @4 @5

Bir sonraki adımda gelen a girdisini bekleyen kurallar işletilecektir.

Şu anda a girdisini bekleyen tek kural E->.aEa kuralıdır. Bu kuralı işleterek sonraki adıma devam ediyoruz:

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

@4 @5

Yeni durumda, görüldüğü üzere nokta yine bir devamlı (non-terminal) sembolden önceyi göstermektedir. Bu durumda yine bu devamlı sembolün dil tanımında bulunan kuralları eklenmelidir:

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

@4 @5

Eklenen yeni kurallar, eklendikleri adımı göstermek için bu defa @3 sembolü ile işaretlenmiştir.

Daha önce de belirtildiği üzere kurallarımız arasında E’nin boş olabilme ihtimali olduğu için listemize E’nin işletilmiş halini de ekliyoruz:

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E → b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4 @5

Algoritmamızı çalıştırmaya devam ediyoruz ve sıradaki girdi sembolü bir a harfi olduğu için, 3. adımda a harfi bekleyen kuralları ilerletiyoruz. Bu kural sadece E->.aEa kuralıdır ve bir a harfi kadar ilerler:

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4

E → a.Ea

@ 3

E → .bEb

@ 4

E → .aEa

@ 4

E → .

@ 4

E → aEa.

@ 2

@5

Yeni durumda, yine beklenen bir devamlı (non-terminal) olduğu için, bu adıma kadar alıştığımız üzere yine terimin açılımını listeye ekliyoruz.

İlave olarak E teriminin boş olabilme ihtimalini de listemizin sonuna ekliyoruz.

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4

E → a.Ea

@ 3

E → .bEb

@ 4

E → .aEa

@ 4

E → .

@ 4

E → aEa.

@ 2

E → aE.a

@ 3

@5

Yukarıda dikkat edilecek bir durum da E → aEa. şeklinde sonunda nokta olan bir kurala ulaşmış olmamızdır. Bu tip noktanın sonda olduğu kurallara ikame (reduce) kuralları ismi verilmektedir. Bu kuralın gereği olarak aEa değerinin yerine E değeri konulabilir. Yukarıdaki tabloda görüldüğü üzere ikame edilecek değer (reduce) 2. adımdan gelmektedir. Dolayısıyla 2. adıma geri dönerek buradaki E değerini ilerletiyor ve buraya taşıyoruz:

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa

@ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa

@ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4

E → a.Ea

@ 3

E → .bEb

@ 4

E → .aEa

@ 4

E → .

@ 4

E → aEa.

@ 2

E → aE.a

@ 3

E → bE.b

@ 1

@5

Yukarıdaki 4. adıma eklediğimiz yeni kurala göre 1. adımdan gelen ve bu aşamada tamamlanan devamlı (non-terminal) değerini ileretmiş olduk (shift).

Sonraki adıma geçebiliriz. Bunun için girdiden bize ulaşan sıradaki terimi yani b harfini okuyarak b harfi bekleyen bütün kurallarımızı ilerletiyoruz (shift).

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4

E → a.Ea

@ 3

E → .bEb

@ 4

E → .aEa

@ 4

E → .

@ 4

E → aEa.

@ 2

E → aE.a

@ 3

E → bE.b

@ 1

@5

E→b.Eb

@ 4

E→bEb.

@ 1

Yukarıdaki şekilde 4. adımda b harfi gelmesini bekleyen bütün kurallar ilerletildi (shift) ve oluşan yeni kurallardan ilkinde yine bir devamlı (non-terminal) terim ile karşılaştık. Burada bu terimi açarak E devamlısının kurallarını listemize ekleyebiliriz.

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4

E → a.Ea

@ 3

E → .bEb

@ 4

E → .aEa

@ 4

E → .

@ 4

E → aEa.

@ 2

E → aE.a

@ 3

E → bE.b

@ 1

@5

E→b.Eb

@ 4

E→bEb.

@ 1

E→.bEb

@ 5

E→.aEa

@ 5

E → .

@ 5

Daha önceki adımlara benzer şekilde, E tanımında boşluk olduğu için E terimini atlamış (shift) halini de kural listemize ekliyoruz:

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4

E → a.Ea

@ 3

E → .bEb

@ 4

E → .aEa

@ 4

E → .

@ 4

E → aEa.

@ 2

E → aE.a

@ 3

E → bE.b

@ 1

@5

E→b.Eb

@ 4

E→bEb.

@ 1

E→.bEb

@ 5

E→.aEa

@ 5

E → .

@ 5

E→bE.b

@ 4

Şimdi, 4. adımdan taşıdığımız ikinci kurala geçebiliriz. Bu kurala göre bir ikame (reduce) durumu ile karşılaştık çünkü nokta, kuralın sonunda bulunuyor:

E->bEb.

Kuralın gereği olarak, bEb teriminin yerine E terimi koyarak kuralın geldiği @1. adımda ilerletiyoruz. Birinci adımda E terimini bekleyen tek kuralımız S-> .E kuralıdır

b a a b
@1

S → . E

@ 1

E→.bEb

@ 1

E→.aEa @ 1

E → .

@ 1

S → E.

@ 1

@2

E→b.Eb

@ 1

E→.bEb

@ 2

E→.aEa @ 2

E → .

@ 2

E→bE.b

@ 1

@3

E → a.Ea

@ 2

E → .bEb

@ 3

E → .aEa

@ 3

E → .

@ 3

E → aE.a

@ 2

@4

E → a.Ea

@ 3

E → .bEb

@ 4

E → .aEa

@ 4

E → .

@ 4

E → aEa.

@ 2

E → aE.a

@ 3

E → bE.b

@ 1

@5

E→b.Eb

@ 4

E→bEb.

@ 1

E→.bEb

@ 5

E→.aEa

@ 5

E → .

@ 5

E→bE.b

@ 4

S → E.

@ 1

Görüldüğü üzere 5. adımda ulaştığımız durumlardan biris E yerine S ikamesi durumudur. O halde aslında bir S koşulunu tamamladığımızı ve S’nin başlangıç durumu olduğunu hatırlarsak, aslında başlangıç şartını tamamladığımızı ve dolayısıyla da kabul durumuna ulaştığımızı söyleyebiliriz.

Bu duruma kadar olan geçişleri tekrar edecek olursak:

S->E @1

E->.bEb @2

E->.aEa @3

E->. @3

E->aE.a @3

E->aEa. @4

E->bE.b @4

E->bEb. @5

S->E @1

şeklinde adımları tamamlayarak başlangıç durumunu sağlamış oluyoruz. Kısacası bu verilen girdi değeri, bu verilen dil kuralları tarafından tanınmış ve kabul edilebilir.

 

Yorumlar

  1. erdo

    merhaba hocam;
    bu örnekte geçişleri daha ayrıntılı bir şekilde nasıl yapıldığını açıklayabilirseniz sevinirim.
    iyi çalışmalar.

  2. erdo

    hocam merhaba;
    neden reduce işlemi olunca sadece olduğu seviyedekileri alıyoruz. Derste işlenen yansılarda sadece olduğu seviyeyi değil tüm seviyedekileri alıyor. biz hangisine göre yapacağız.
    iyi çalışmalar.

  3. Şadi Evren ŞEKER Article Author

    Tam olarak neyi kast ettiğinizi anlayamadım (olduğu seviye ve tüm seviyeler ile) ancak sizin için yansılara ve yazıya tekrar baktım (acaba hata mı yapıyorum diye) sanırı bir yanlış anlama var çünkü yukarıdaki örnek doğru, yansılar da doğru ve ikisi için de yapılan işlem aynı. Ya ben ya da siz birşeyi kaçırıyoruz ancak tam olarak neyi kast ettiğinizi yazarsanız belki yardımcı olabilirim. Örneğin yukarıdaki örnekte reduce edilen ve yansılara göre reduce edilmesi gerektiğini düşündüğünüz kısım nedir?

    Başarılar

  4. cbasaranoglu Article Author

    erdo Bey öncelikle ilk üç process’i anlatmaya çalıştım kalan processlerde bu şekilde yapılmaktadır.
    Bu duruma kadar olan geçişleri tekrar edecek olursak:
    S->E @1
    /*Öncelikle S terimini baslangiç değeri olarak kabul ediyoruz
    *Daha sonra E terimini ( yani non-terminak terimimizi) tanımlıyoruz
    *Burada dikkat edilmesi gereken nokta baab’ta verilen @1 girdi sembolünün işletilmesidir( ya da bir process’e tabi tutulmasıdır)
    *process’imiz b sembolüne geldiğinde çözülmesi gereken yeni sorumuz hocamızında belirttiği üzere
    *”girdimiz olan b sembolü geldiğinde bu kurallardan hangileri ilerler?”
    *yani işlemin devamlılığı için kurallardan hangisinin kullanılacağına/ilerletileceğine karar vermemiz gerek
    *Bu aşamada b sembolünün konumu göz önüne alınarak elimizdeki diğer kural olan E->.bEb kuralını kullanıyoruz.
    *Bir sonraki aşamımızda görüldüğü üzere b sembolümüzü process/işlem’e tabi tutuyoruz.
    *son olarak E kuralının tanımını ekleyip bir sonraki adıma geçiyoruz.*/
    E->.bEb @2
    /*Dilin tanımında bulunan bütün E Kuralları ikinci adımda eklendiği için bu adımı ifade etmek için @2 girdi sembölünü
    *kullanıyoruz.
    *Burada dikkat edilmesi gereken nokta E teriminin ya da kuralının boşluk değeri alabileceği/boş olabileceği ya da bütün sembollerin atlatılması olasılığıdır.(bkz:hocamızın anlatım notları)
    *Bu olasılıkları göz önünde bulundurarak E teriminin ilerletilmiş/process edilmiş halini listemizin sonuna ekliyoruz.
    *Görüldüğü üzere baab tablosunda sıradaki girdimiz a girdisi
    *Bu aşamada a girdisini bekleyen tek kural E->.aEa
    *bu kuralı process ederek devam ediyoruz.(bkz:tablolar da ayrıntılı bir biçimde gösterilmiş)*/
    E->.aEa @3
    /*Yeni durumumuzda .aEa terimi non-terminal sembolden önceyi göstermektedir.
    *Bu yüzden yine dil tanımlarımızı eklememiz gerekmektedir.
    *Yeni eklenen kuralların eklendikleri adımı göstermek için @3 terimi kullanmıştır.
    *ve E teriminin alabileceği değerlerin olasılıkları göz önünde bulundurularak
    *E teriminin processten sonraki halini de ekliyoruz.
    E->. @3
    E->aE.a @3
    E->aEa. @4
    E->bE.b @4
    E->bEb. @5
    S->E @1

Bir cevap yazın

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