LR(1) Parçalama Algoritması

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, LR(1) algoritmasını açıklamaktır. Algoritma, özellikle derleyici tasarımı konusunda sık kullanılan parçalama algoritmalarından birisidir. Algoritmanın ismi, iki kelimenin kısaltmasından gelmektedir. Buna göre ilk L harfi, left to right parsing (soldan sağa doğru parçalama) ve ikinci R harfi ise rightmost derivation (sağdan eksiltmeli) anlamındadır. Parantez içerisinde yer alan 1 sayısı ise, 1 look ahead, yani 1 sembol ilerisine bak anlamındadır. Bu durumda algoritma LR(0) algoritmasının bir seviye gelişmişi olarak düşünülebilir. LR(0) algoritması ile tek farkı, ileri bakış değerinin 1 olması ve bu sayede LR(0) tarafından parçalanamayan bazı gramerleri parçalayabilmesidir.

Bu yazı kapsamında, öncelikle örnek bir gramerin DFA çizimini göreceğiz. Algoritmada, bu DFA çiziminin ardından gelen herhangi bir girdiyi (input) DFA üzerinde dolaşarak parçalamak gelir. Bunun için de örnek bir girdi vererek nasıl çalıştığını göstereceğiz. Son olarak LR(1) algoritmasının kısıtlarını ve yapamayacaklarını inceleyeceğiz.

Örnek:

S-> aAd

S-> bBd

S-> aBe

S-> bAe

A-> c

B-> c

Yukarıdaki şekilde verilen gramer ( CFG şeklinde verilmiştir ve daha detaylı bilgi için CFG başlıklı yazı okunabilir) için DFA çizimi aşağıdaki şekilde yapılır.

Öncelikle başlangıç durumunu ele alıyoruz. Gramer tanımı itibariyle S, başlanıgıcı ifade etmektedir. O halde aşağıdaki şekilde başlayabiliriz:

Yukarıda görüldüğü üzere, öncelikle S gelmesi ve sonrasında $ sembolü olan girdinin bitmesi (end of input) halinde bu kabul anlamına gelmektedir. Dolayısıyla S->.S$ kuralı bizim bitişimizi ifade etmektedir. Burada . işareti, o ana kadar olan parçalama durumunu gösterir. Yani o ana kadar parçalanan sembolleri ve o anda sıradaki sembolü göstermektedir.

Yukarıdaki ilk kurala bakacak olursak, S->.S$ ifadesi, sırada S sembolü olduğunu göstermektedir. Bu durum aslında özel olarak ele alınması gereken bir durumdur. Buna göre sıradaki beklenen terim bir devamlı (non-terminal) olarak görülmektedir. Böyle özel bir halde, bu devamlının (non-terminal) tanımını içeren kurallar da DFA çizimindeki duruma eklenmelidir. Yukarıdaki durumda bulunan diğer 4 kuralın geliş sebebi işte budur.

Şimdi yukarıda çizdiğimiz 1 numaralı durumdan sonra devam için gelebilecek sembolleri inceleyelim. İlk kural itibariyle bir S, ikinci ve 4. kurallar itibariyle bir a ve üçüncü ve beşinci kurallar itibariyle de bir b sembolü beklenmektedir. Bütün bu semboller için çizdiğimiz durumdan devam yollarını çizmemiz gerekiyor:

Yukarıdaki şekilde gösterildiği üzere, 1 numaralı durumdan çıkan 3 ayrı ok, 3 ayrı duruma geçişi temsil etmektedir. Bunlardan ilki olan 2 numaralı durumda, bir kaydırma (shift) işlemi gerçekleşmiş ve noktanın yeri bir kaydırılmıştır. S->S.$ gösterimi, S gelmesi halinde, 1 numaralı durumdan gidebileceğimiz ve gittiğimizde gramerimizde olacak değişikliği göstermektedir. Burada dikkat edilecek bir husus, sıradaki sembolün $ olmasıdır. Yani bir şekilde girdinin (input) sonuna ulaşıldıysa, artık bu girdi kabul edilmiş demektir. Bu anlamda, 2 numaralı duruma bir kabul durumu denilebilir.

Şimdi, diğer durumları doldurmaya çalışalım:

Yukarıda, her sembolün gelmesi durumunda yapılması gereken kaydırma işaretleri tutulmaktadır. Dikkat edilirse, yine sıradaki sembolün devamlı (non-terminal) olduğu koşullar ile karşı karşıyayız. Bu sembollerin açılımını yapıyoruz:

Gösterimimizde, 3. ve 4. durumlar için karşılaşılan devamlı (non-terminal) sembollerin tanımları yerleştirilmiştir. Örneğin 3. durumda, S->a.Ad,$ koşulu, bize a teriminin işlendiği sıradaki terimin A olduğu ve virgülden sonra $ geldiği için look ahead (bakış) değerinin $ olduğunu göstermekteydir. Burada, sıradaki terimin A olmasından dolayı A teriminin açılımını yaparak A->c kuralını, duruma ekliyoruz. Bu eklemede dikkat edilecek iki husus bulunuyor. Birincisi eklenen yeni kuralda, henüz c sembolü işlenmediği için A->.c şeklinde noktanın c sembolünden önce yerleştirilmesi, ikincisi ise virgülden sonraki terim olarak d sembolünün yerleştirilmesidir. Yani S->a.Ad,$ kuralında A gelmesi halinde sıradaki beklenecek olan sembol d olacağı için A->.c kuralında da bakış değerimiz (look ahead) d sembolü olacaktır.

Burada LR(1) algoritmasının, LR(0) algoritmasından farkını görebiliriz, yani durumların içerisine yazılan kurallarda, bakış değerine göre aynı kural, farklı satırlar halinde yazılabilir. Örneğin A->.c,d ile A->.c,e aynı kural olan A->c kuralından gelmesine karşılık, devamında beklenen terimlerin farklı olmasından dolayı durumun içerisinde yer alır. Biz DFA çizmimize devam edelim, 3. durumda beklenen semboller ve bu sembollerin gelmesi durumunda gidilecek durumlar aşağıdaki şekilde çizilebilir:

Yukarıda, yeni eklenen 3 farklı durum bulunmaktadır. Burada özel olarak birşeyi belirtmek istiyorum, klasik birer kaydırma durumu olan 5. ve 6. durumların aksine 7. durum oldukça önemlidir ve iyi anlaşılması gerekir. 7. durumda iki adet ikame(reduce) işlemi bulunmaktadır. Yani bir c sembolü geldiğinde yerine A devamlısı veya B devamlısı (non-terminal) konulabilir. Aslında bu durum, LR(0) tam bir problemdir ve böyle bir durumu içeren LR(0) algoritması, hemen bu grameri parçalayamayacağını söyleyebilir. Ancak burada dikkat ederseniz c sembolünün A mı B mi olacağı devamında gelen d veya e sembolüne göre belirlenebilmektedir. O halde algoritmamız devamında gelecek olan sembole göre karar verebilir ve klasik ikame / ikame (reduce / reduce) problemi olan problemin üstesinden gelebilir. Bu durumu bir örnek girdiyi işlerken daha net göreceğiz. Sıradaki 4. durumu açalım:

Görüldüğü üzere, bir önceki adıma benzer şekilde 3 durum çıktı ve bu durumlardan 10. durum, 7. duruma benzer şekilde bir ikame / ikame (reduce / reduce) durumudur. Buradan sonra hızlanarak bütün DFA‘in çizilmiş halini verelim:

Son haliyle DFA çizimimizi tamamladık. Şimdi bu DFA’in bir örnek girdi üzerinde nasıl çalıştığını görelim. Örnek girdimiz “acd” olsun ve bu girdiyi nasıl parçaladığımızı görelim.

Öncelikle başlangıç durumundan başlıyoruz:

Bu durumdayken, ilk gelen girdi sembolümüz a olduğu için ilgili yolu izliyoruz:

Buraya 1 numaralı düğümden geldik ve sıradaki sembol bir c dolayısıyla sıradaki yolu izleyerek 7 nuaralı düğüme geçiyoruz:

Şimdi artık bir ikame (reduce) durumu ile karşılaştığımız için, c yerine bir devamlı (non-terminal) koyabiliriz. Ancak sorun A veya B devamlılarından (non-terminal) hangisinin geleceğidir.

Girdimiz “acd” olduğuna göre ve biz c sembolünü işlediğimize göre sıradaki terime bakıp d olduğunu görebiliriz. O halde şu anda bulduğumuz c sembolü yerine sıradaki terim d olduğu için A konulması sonucuna varmak gayet kolaydır.

“13|.Ad” şeklinde girdimizi güncelliyoruz, yani 1. ve 3. durumları aştık ve sırada A terimini işlemek var.

Bu bizi, 5. duruma götürür. Girdimiz, “135|A.d” şeklini almıştır ve sıradaki girdimiz de d sembolüdür.

Şimdi yeni bir ikame (reduce) durumu olan 11. duruma ulaştık. Yapmamız gereken işlem aAd yerine S koymaktır. Girdimiz buraya geldikten sonra “ 1,3,5,11 | d. “ şeklini aldı. O halde sıradaki işlem 3,5,11 terimlerinin yerine (yani a,A,d terimleri olduğu görülebilir) S koymaktır:

“1.S” durumuna dönmüş oluruz ki bu da bizim 1. durumdan başlayarak S işletmemiz gerektiğini ifade eder:

Şeklindeki başlangıç durumundan S sembolü işletilirse, kabul durumu olan 2. duruma ulaşılır ve bu girdinin kabul edildiği ve hatasız olduğu anlamına gelir.

LR(1) algoritması başarıyla çalışmıştır ve LR(0) için problem olan bir reduce/reduce durumunu başarıyla çözmüştür.

Peki LR(1) algoritmasının limitleri var mıdır? Bütün gramerler LR(1) ile işletilip girdiler başarıyla çözülebilir mi?

Bu sorunun cevabı ne yazık ki hayırdır. Yani LR(1) de bazı limitlere sahiptir. Örneğin aşağıdaki şekilde bir reduce / reduce durumu LR(1) için de problem oluşturur.

Görüldüğü üzere burdaki ikame / ikame (reduce /reduce) problemi ne yazık ki takip eden karaktere bakılarak çözülememektedir. Yani tek bir sembole bakmak yeterli olmaz. Belki ikinci bir sembol, yani sıradaki sembolden sonra gelen sembol de tutularak çözülebilir:

Şayet gramer bize ikinci sembolde bir farklılık yakalama imkanı tanıyorsa o zaman çözüm bulunabilir denilebilir. Zaten bu şekilde 2 sonraki terime kadar bakan algoritmaya LR(2) ve daha fazla terime bakan algoritmalara da LR(n) şeklinde isim verilir (buradaki n herhangi bir sayı olabilir , örneğin LR(3) veya LR(15) gibi). Ancak dikkat edilecek bir husus, buradaki sayı arttıkça DFA çiziminin karmaşıklaştığı ve algoritmanın işletilmesinin zorlaştığıdır.