Yazan : Şadi Evren ŞEKER
Bu yazının amacı, özellikle derleyici tasarımı (compiler design) konusunda sıkça kullanılan parçalama algoritmalarından (parse algorithm) birisi olan SLR(1) algoritmasını açıklamaktır.
Algoritma, klasik LR algoritmalarından LR(1) algoritmasının basitleştirilmiş halidir. Bu anlamda Simplified LR(1) şeklinde okunabilir.
LR(1) algoritması hatırlanacak olursa, bu algoritma Left to Right parsing ve Rightmost derivation terimlerinin baş harflerinden oluşmaktadır ve anlam olarak soldan sağa parçalama ve sağdan azaltma olarak anlaşılabilir.
LR(1) algoritmasının problemi, bu algoritmada çizilen DFA şeklinin oldukça karmaşık olmasıdır. Yani LR(0) algoritmasında, sadece anlık olarak durumlar incelenirken, LR(1) algoritmasında buna ilave olarak sonraki terimler de incelenmektedir. İşte bu sonraki durum incelemesinin getirdiği karmaşıklığı azaltmak için LR(0) kadar basit bir DFA kullanan ancak sonraki terime de bakan (yani look ahead 1 olan) bir algoritma geliştirilmiştir. SLR(1) bu algoritmanın ismidir.
Algoritma ayırca parçalama algoritmaları arasındaki, aşağıdan yukarıya (bottom-up) ve yukarıdan aşağıya (top-down) sınıflandırmalarından, aşağıdan yukarıya (bottom-up) sınıfındadır.
Algoritmanın çalışmasını basit bir örnek üzerinden izleyelim. Örneğin aşağıdaki gramer verilmiş olsun:
S→S$
S→DE
D→DP
D→aP
P→b
E→c
Bu grammer için öncelikle LR(0) seviyesinde DFA çizerek işe başlıyoruz:
Yukarıdaki DFA çıkarılırken, başlangıç durumuna dilimizin ilk başta ulaşabileceği bütün kurallar yazlır. Ardından gelebilecek her alternatif ve gelen her alternatif için dilimizde yapılacak işlemler ayrı birer durum ile gösterilir. Yukarıdaki gösterimde kullanılan nokta işaretleri o ana kadar yapılan parçalamayı temsil etmektedir.
Yukarıdaki durumlardan sadece 0 durumu bitişi ifade etmektedir ve makinemiz bir şekilde 0 durumu ile sonlanırsa bu girdiyi kabul edeceğiz.
Şimdi yukarıdaki DFA oluşturulduktan sonra örnek olarak “abc” girdisini parçalamayı deneyelim. Buna göre SLR(1) algoritması bize bu girdiyi kabul edip etmeyeceğini bildirecektir. Ayırca bu girdinin anlamına göre bir durumda da çalışmasını sonlandıracaktır.
1 durumunda girdinin ilk kelmesi olan a ile başlıyoruz. Girdimiz gereği 5 numaralı duruma geçiş yapıyoruz. Bu durumda, iki ihtimal bulunuyor ve bu ihtimallerin ikisi de shift durumu olarak görülüyor. Aslında tek durum var diye de düşünülebilir. Yani D->a.P durumunda, bir sonraki gelen terim bir devamlı (non-terminal) olduğu için bu durum da açılarak yazılmıştır.
5. durumdayken gelen ikinci girdi harfi olan b ile ilerlemeye devam ediyoruz (shift) ve gidilen durum 8. durum oluyor. Burada bir ikame (yerine koyma, reduce) işlemi ile karşılaşıyoruz (noktanın sonda olması durumlarının birer ikame olduğunu hatırlayınız) ve gelen b terimini, 5. durumdaki P terimi ile ikame ediyoruz.
Kısaca geldiğimiz durumlar aşağıdaki şekildedir:
a b -> a P
5. durumdaki a P ise D’nin ikamesidir bu durumda geçişlerimiz, aşağıdaki hali alacaktır:
a b -> a P -> D
şimdi başa dönerek (1. durum) D geçişini çalıştırıyoruz. Bu geçiş bizi 3. duruma götürüyor. 3. durumdaki bütün kurallar birer kaydırma (shift) işlemidir. O halde biz de girdiden bir sonraki harfi alarak ilerliyoruz ve 3. durumdan c geçişi ile 4. duruma geliyoruz. 4. durumda karşımıza bir ikame (reduce) işlemi çıkıyor. Buna göre c harfi yerine E devamlısı (non-terminal) koymamız gerekiyormuş. Şimdiye kadar olan geçişleri hatırlayalım:
a b -> a P -> D -> D c -> D E
3. duruma geri döndük ve DE geçişi bizi 7. duruma götürdü. Burada da bir ikame yapılıp DE yerine S koyuyoruz ve başa geri dönüyor ve mutlu sonla parçalamayı bitiriyoruz:
a b -> a P -> D -> D c -> D E -> S
Görüldüğü üzere abc girdisi, bu dil tarafından kabul edilmekte olup herhangi bir hata ile karşılaşılmamıştır.
Örnek 2 :
Bu sefer farklı bir dil aşağıdaki şekilde verilmiş olsun:
S → X | ay
X → xXy | Y
Y → a
Bu dilin DFA çizilimi aşağıdaki şekilde olacaktır:
Şimdi bu dilde xay girdisini nasıl parçalayacağımızı görelim. Öncelikle başlangıç durumu olan S0’dan başlıyoruz. İlk girdimiz x olduğu için bu yolu izleyerek S6 durumuna devam ediyoruz. Burada gelen x terimi işlendikten sonra X->x.Xy kuralı gereği bir sonraki terim bir devamlı (non-terminal) olduğu için bu terimin açılımına ulaşıp gelen a terimi ile S10 durumuna geçiyoruz. S10 durumu bir ikame durumu (reduce) olduğu için bir önceki S6 durumunda a yerine Y koyarak işleme devam ediyoruz. Bu haliyle şimdiye kadar olan geçişleri görelim:
X->x.Xy
X->Y
Y->a
Dolayısıyla
x a için x Y ve sonrasında da xX.y durumuna gelindiği söylenebilir. Zaten bu geçiş bizi S7 durumuna getirmektedir. Devamında son girdi olarak y gelecek ve bu durumda da S8 durumuna geçilerek yeni bir ikame yapılacaktır. Burada X->xXy. kuralı ile S0 durumuna dönüyor ve S->X. İşleyerek S3 durumundan ikame ediyoruz. Sonuçta ise S1 ve S2 durumları ile işlemi tamamlayarak girdiyi kabul ediyoruz.
Örnek 3
Farklı bir dil olarak aşağıdaki dili ele alalım:
S → S ( S ) | ɛ .
Bu dil için ( ( ) ( ) ) şeklinde verilen girdiyi parçalamak istiyor olalım:
Yukarıdaki şekilde görüldüğü üzere oldukça basit bir DFA çizimine sahip olan dilimizde verilen girdinin işlenmesi halinde, aşağıdaki adımları içeren bir yığın sürecine girilecektir:
