Yazan : Şadi Evren ŞEKER
Bu yazının amacı, derleyici tasarımı (compiler design) konusunda çok kullanılan parçalayıcılardan (parser) birisi olan LL1 parçalayıcısını (LL1 parser) açıklamaktır.
LL(1) kelimesi, 3 konunun baş harflerinden oluşur.
- İlk L harfi, Left-to-Right scan, yani soldan sağa doğru tarama yaklaşımından,
- ikinci L harfi, Leftmost Derivation, soldan eksiltme yaklaşımından,
- 1 sayısı ise sadece 1 değer ileri bakılmasından ( look ahead token)
Gelmektedir. Bu kavramların aynı anda kullanıldığı parçalama algoritması aşağıda adım adım anlatılacaktır.
Konuyu bir örnek üzerinden anlatmaya çalışalım. Öncelikle ileri bakma tablosunun (look ahead table) nasıl oluşturulduğunu anlatalım.
ÖRNEK 1:
Örneğin parçalama işlemini yapmak istediğimiz gramer aşağıdaki şekilde CFG yapısında verilmiş olsun:
S → E$
E → int
E → (E Op E)
Op → +
Op → *
LL(1) algoritmasının ilk aşamasında, parçalama tablomuzu (parse table) oluşturuyoruz. Yukarıdaki dilbilgisi (grammer) için oluşturulan tablo aşağıda verilmiştir:
Tabloda, dikkat edileceği üzere dilimizdeki nihayi elemanlar (terminal, sonlular) tablonun kolon başlıklarında ve devamlılar (non-terminal) elemanlar ise satır başlarında yazılmıştır. Bu tabloda, her devamlı (non-terminal) için kabul edilen sonlular gösterilmiş ve hangi kural ile devam edileceği belirlenmiştir.
Bu tip tabloların çizimi sırasında öncelikle basitten başlamak kolaylık sağlar. Dil bilgisi tanımımızda en basit öğe, Op olarak gösterilen operatördür ve + veya * sembollerinden birisini alabilir. Bu durumda, tabloda, Op ile + ve *’nın çakıştığı yerlere ilgili kuralları yazmak yeterlidir. Ardından E devamlısına (non-terminal) bakacak olursak, bu devamlı için de iki farklı kural tanımı dilbilgisinde yapılmıştır. Ayrıca bu iki kural da birer sonlu (terminal) ile başlamaktadır. Demek ki bizim E devamlısında bulunduğumuz durumdayken bir sonlu gelirse hangi kurala devam edeceğimiz bellidir. Nitekim tabloda da “int” gelmesi durumunad ve “(“ sembolü gelmesi durumunda tanımlı işlemler yerleştirilmiştir.
Gelelim S ile tanımlı olan kurala. Bu kural S–>E dönüşümünden dolayı, doğrudan E için tanımlı olan bütün durumları kendisine kopyalamıştır. Çünkü S durumundayken “int” veya “(“ sonluları gelirse kabul edilir ve hangi kuralın uygulanacağı bellidir.
Yukarıdaki tabloda, bazı hücrelerde bilgi varken bazılarında ise hiçbirşey yazmamaktadır. Bunun anlamı, parçalama işlemi sırasında yukarıda geçen durumlardayken, karşılığı boş olan kolondan bir sonlu (terminal) gelmesi halinde hata olduğudur.
Örneğin S devamlısı için sadece “int” ve “(“ sonluları tanımlıdır. Demek ki * veya + ile başlayan bir girdiyi (input) kabul etmemiz hatadır. Hiç sorgulamadan S durumundayken * gelmesi halinde hata verebiliriz.
Benzer şekilde kabul edeceğimiz bir girdi (input) geldiğinde de her adımda, sonraki adımı kesin (deterministic) bir şekilde nereye gideceğimizi biliyoruz.
Yukarıdaki tablonun, aşağıdaki şekilde de yazılması mümkündür:
Yeni tabloda, sadece dilbilgimizdeki her kural için bir sayı kullanılmıştır. Bu tablonun kesin (deterministic) olarak bir girdiyi nasıl işlediğini şimdi anlatmaya çalışalım:
Örneğin girdi olarak “(int + ( int * int )) “ dizgisini alalım. Bu dizginin işlenmesi aşağıda verilmiştir:
Şekilde görüldüğü üzere, S durumundan başlayarak bütün adımlar teker teker sonunca kadar tablodan çıkarılarak işlenmiştir. İlk satırda, girdinin ilk sembolü olan ( işareti için E geçişi kullanılmış, buradan E durumundayken bir parantez gelmesinde yapılacak tek ihtimal olan 3. geçiş kullanılmıştır. Ardından iki taraftaki ( işaretleri birbirini yok etmiş ve E durumundayken gelen int sonlusu için işleme başlanmıştır. Yukarıdaki adımlar bu şekilde devam eder. Yani solda bulunan ve S ile başlayan parçalama işlemi, sağda bulunan girdiyi parçalamak için kullanılmaktadır. Bu sırada soldaki terimlerin en solunda bulunan sonluya karşılık sağdaki girdide aynı sonlu bulunuyorsa bunlar birbirini yok etmektedir. Şayet soldaki listenin en solunda bir devamlı (non-terminal) varsa bu durumda, sağdaki listenin en solunda bulunan sembole göre ilgili açma işlemi tablodan yapılır.
Yukarıdaki tabloda bulunan değerler aslında LL(1) algoritmasının ilk kümesini (First set) de içermektedir. Örneğin S kümesi için kabul edilen ilk değerler
İlk (S) = { ‘(‘, ‘int’ }
olarak yukarıdaki tabloda gösterilmektedir. Bunun anlamı S durumundayken sadece bu kümedeki elemanların kabul edildiği ve bu elemanlar dışında bir eleman gelmesi durumunda hata verileceğidir.
ÖRNEK 2
Yukarıdaki örneğe benzer şekilde daha gerçekçi bir örneğin tablosunu oluşturmaya çalışalım.
Yukarıdaki örnekte verilen dilbilgisinin tablosunu oluşturalım. Tablonun satır başlıklarına, dilbilgisinde bulunan devamlıları (non-terminal) ve kolon başlıklarına da dilbilgisinde bulunan sonluları (terminal) yerleştirdik ve yukarıdaki boş tablonun nasıl doldurulduğunu adım adım işleyelim.
Şimdiki adımda tablodaki her hücreye gelecek değeri bulmamız gerekiyor. Basitten başlayarak karmaşığa doğru tabloyu dolduracağız. En basit tanım, TERM için yapılmış ve iki adet terminal ile tanımlanmıştır. Bu durumda tablonun ilgili hücreleri aşağıdaki şekilde doldurulur:
Ardından ikinci karışıklık derecesine sahip EXPR teriminin tanımını tabloda işaretleyelim. EXPR teriminin tanımına bakıldığında 5 farklı ihtimal bulunmaktadır. Bunlardan 4 tanesi zaten sonlu (terminal) ile tanımlıdır. Bunları doğrudan işaretleyebiliriz:
Ayrıca ilave bir satırda EXPR devamılsının tanımının TERM devamlısı ile yapıldığı belirtilmiş. Bu tanıma göre EXPR durumundayken, TERM durumundan bir terim ile devam etmemiz söz konusu olabilir. Bu durumda TERM için geçerli olan bilgiler, EXPR için de kopyalanmalıdır. Yani TERM satırını odluğu gibi EXPR satırına kopyalıyoruz:
Yeni halinde tablomuza bakıldığında EXPR durumundayken gelebilecek sonlu terimler aşağıdaki küme ile ifade edilebilir:
İLK (EXPR) : { zero?, not, ++, — , id, const}
Son olarak STMT devamlısını tablomuzda işaretleyelim. STMT tanımının iki satırında sonlu ile başlamaktadır. Bu durumları aşağıdaki şekilde tabloya işaretleyelim.
STMT tanımının bir satırında ise EXPR tanımı bulunmaktadır. Bu durumda EXPR satırının aynısının STMT için de kopyalanması gerekir:
Yukarıdaki tablonun son halinde, örneğin bir STMT tanımının id veya const kabul edeceği görülmektedir. Ancak “;” veya “do” sonlularının STMT tanımında bulunması bir hata olarak kabul edilebilir.
Tanımda epsilon bulunması durumu
CFG tanımında bulunan özel bir durum da, tanımın herhangi birisinde epsilon sembolünün (ε, bazı kaynaklarda lambda (λ) olarak da geçer) bulunması durumudur. Bu durum özel olarak ele alınmalıdır çünkü bahsi geçen terimin yokluğu söz konusudur. Bu durumda uygulanabilecek en kolay yaklaşım epsilon terimi yokmuş gibi davranmak ve herşeyi işledikten sonra epsilon durumunu özel olarak ele almaktır.
ÖRNEK 3:
Epsilon durumunu içeren aşağıdaki örneği ele alalım:
Yukarıdaki bu durum için tablomuzu oluşturuyoruz:
| 0-9 | + | – | |
| Number | |||
| Sign | |||
| Digits | |||
| Digit |
Yukarıdaki tabloda dikkat edilirse epsilon ihtimali gösterilmemektedir. Zaten böyle bir ihtimal gösterilemez çünkü epsilon durumu yokluğu temsil eder. Tablomuzu sanki epsilon hiç yokmuş gibi dolduruyoruz:
| 0-9 | + | – | |
| Number | |||
| Sign | Sign-> + | Sign -> – | |
| Digits | |||
| Digit | Digit -> 0|1… |9 |
Yukarıdaki hali ile tabloda sonlu durumlar (terminal) işaretlenmiştir. Sıra devamlı (non-terminal) durumları işaretlemeye geldi:
| 0-9 | + | – | |
| Number | Number->Signt Digits | Number -> Sign Digits | |
| Sign | Sign-> + | Sign -> – | |
| Digits | Digits -> DigitDigits -> Digit | Digits | ||
| Digit | Digit -> 0|1… |9 |
Yukarıdaki haliyle bütün durumlar işaretlendi. Şimdi epsilonu çalıştırabiliriz. Buna göre bir Sign devamlısının (non-terminal) epsilon yani boşluk olabilme ihtimali bulunmaktadır. Bu durumda Sign ile başlayan bir tanımda Sign terimi yokmuş gibi davranılabilir.
Number->Sign Digits
Satırını, normalde Sign ile başlıyor diye kabul etmiş ve Sign ile başlayan bütün terimleri buraya yerleştirmiştik. Epsilon durumu Sign terimi olmaması halini de düşünmemizi gerektirir çünkü Sign terimi boş olup Number devamlısı, Digits devamılsı ile başlayabilir. Bu durumda Digits satırı aynen Number satırına kopyalanmalıdır.
| 0-9 | + | – | |
| Number | Digits -> DigitDigits -> Digit | Digits | Number->Sign Digits | Number -> Sign Digits |
| Sign | Sign-> + | Sign -> – | |
| Digits | Digits -> DigitDigits -> Digit | Digits | ||
| Digit | Digit -> 0|1… |9 |
Yukarıdaki tabloda, son durum görülmektedir. Yukarıdaki tabloya göre Number terimi herhangi bir sonlu ile başlayabilir.
Yukarıdaki tabloda özel bir durum, verilen CFG’nin LL(1) olarak yazılmaya uygun olmamasıdır. Bunun sebebi bir hücrede birden fazla tanımın bulunmasıdır.
Takip Kümeleri (Follow Sets)
LL(1) algoritmasının önemli adımlarından birisi de takip kümelerini oluşturmaktır. Bu yazıda, buraya kadar İlk kümelerinin (First set) nasıl oluşturulduğunu ve nasıl kullanıldığını anlattık. Yani bir durumdayken gelen ilk girdi (input) bilgisine göre hangi adıma geçeceğimiz veya hata verip vermeyeceğimizi nasıl anlayacağımızı gördük. Bu noktadan sonra Takip Kümelerini (Follow Set) göreceğiz ve dildeki herhangi bir durumdan sonra hangi sonluların (terminal) gelebileceğini takip edeceğiz.
Takip kümeleri, basitçe dildeki herhangi bir bilgiden sonra hangi bilginin gelebileceğidir. Örneğin daha önce açıklanan örnek 2’de while kelimesinden sonra do kelimesi gelebilir mi gelemez mi? Sorusuna ancak takip kümesi ile cevap verilebilir.
Takip kümeleri nasıl oluşturulur sorusunu yine bir örnek ile açıklayalım:
Örnek 4:
A –>Ax | yB
B –> zA | Cz
C –>y | z
Yukarıda verilen dil tanımı için İlk (First) ve Takip (follow) kümelerini oluşturmaya çalışalım. Öncelilke ilk kümeleri aşağıdaki şekilde oluşturulabilir:
Basitten başlarsak, C -> y ve C-> z zaten verilmiş:
| x | y | z | |
| A | |||
| B | |||
| C | C->y | C->z |
İkinci adımda B için tablonun ilgili satırını dolduralım:
| x | y | z | |
| A | |||
| B | B->z | ||
| C | C->y | C->z |
B için tanımlı olan kurallardan birisi tabloya yazılmıştır. Ancak ikinci tanımda B->Cz şeklinde ilk eleman bir devamlı (non-terminal) olduğu için C satırı aynen kopyalanır:
| x | y | z | |
| A | |||
| B | B->Cz | B->zB->Cz | |
| C | C->y | C->z |
Ardından A ile ilgili satıra geçelim:
| x | y | z | |
| A | A->yB | ||
| B | B->Cz | B->zB->Cz | |
| C | C->y | C->z |
Sonlu (terminal) ile başlayan kuralı tablomuza yerleştirdikten sonra devamlı (non-terminal) ile başlayan durumu inceleyelim:
A->Ax olduğu için burada hem sol döngü (left recursion) problemi bulunmakta hem de A ile başlayan bütün durumları ilk (first) kümesine almamız gerekmektedir. A zaten kendi tanımı olduğu için yeni bir eleman alınması söz konusu değildir. Yani tablomuz y elemanına iki durumdan erişebilir ve ikisi de aşağıdaki şekilde gösterilmiştir:
| x | y | z | |
| A | A->yBA->Ax | ||
| B | B->Cz | B->zB->Cz | |
| C | C->y | C->z |
Tabloya hızlıca bakınca, x ile başlama durumu hiçbir devamlı (non-terminal) için söz konusu değildir.
Ayrıca tablodaki bir hücrede birden fazla kural tanımı bulunduğu için (iki ayır hücrede) bu dilbilgilsinin (grammer) LL(1) algoritması ile parçalanması mümkün değildir.
Gelelim takip (follow) kümelerinin oluşturulmasına. Bu kümelerin oluşturulması sırasında izlenecek en kolay yol iki aşamada dili incelemektir. Birinci adımda, dil tanımındaki eşitliklerin sağ tarafına bakılır. Buna göre herhangi bir terimden sonra gelen terimler, takip (follow) kümesine alınır.
1. Adım
Dilbilgisi tanımının sağ tarafını alıntılayacak olursak:
Ax | yB
zA | Cz
y | z
Yukarıdaki tanımlardan yola çıkarsak aşağıdaki kümeleri oluşturmamız mümkündür:
Takip (x) : {$}
Bunun sebebi dilin herhangi bir yerinde x’ten sonra bir sembol gelmemesidir.
Takip (y) : { $, B }
takip kümelerinde, devamlı (non-terminal)eleman bulunmaması gerekir. Bu durumda yukarıdaki kümede bulunan B terimini açmamız gerekiyor. Herhangi bir şekilde devamlı eleman kümeye eklenmişse aşağıdaki dönüşümü yapabiliriz:
Takip (y) : { $, İlk(B) }
Yani bir takip kümesinde bir devamlı (non-terminal) bulunması durumunda bu elemanın ilk kümesini yerine yazmamız mümkündür. İlk (B) ise tablodan çıkarılabileceği üzere {y,z} olarak yazılabilir:
Takip (y) : { $, y, z} olarak yazılması mümkündür.
Takip (z) : { $, A} yine devamlı (non-terminal) olduğu için bu elemanı da açıyoruz
Takip (z) : { $, y } , A devamlısının ilk kümesi yerine yazılmıştır.
Takip (A) : { x, $ }
Takip (B) : { $ }
Takip (C) : { z }
2. Adım
Bir önceki adımda atlanan bir nokta, herhangi bir terimin tanımında bulunan elemanın son eleman olması durumunda, tanımı yapılan elemanın sonrasına gelen terimlerin aslında bu son elemanın da sonrasına gelmesi durumudur.
Örneğin dil tanımımızı hatırlayalım:
A –>Ax | yB
B –> zA | Cz
C –>y | z
Buna göre C–>z durumu için, C’nin tanımının son elemanı olan z teriminden sonra gelen elemanlar aslında C’den sonra gelen elemanları da içermelidir. Çünkü C’den sonra gelen herhangi bir eleman z’nin sonrasına eklenebilir. Benzer durum B–>Cz tanımı için de geçerlidir. Burada da z sondaki eleman olduğu için B’nin sonrasına gelen her eleman aslında z’nin de sonrasına gelebilir.
İşte ikinci adımda bu durumaları kümelere ekliyoruz.
Yine en alttan başlayarak yukarı doğru çıkalım:
Takip (x) : {$} şeklinde bulmuştuk. Bu elemanın (yani x’in) sonda olduğu bir tanım var mı?
Evet var A–>Ax tanımı bu şartı sağlıyor. Öyleyse kümemizi aşağıdaki şekilde güncelliyoruz:
Takip(x) : {$ , Takip(A)} , bunun sebebi x teriminin A’nın tanımının sonunda bulunması ve A’yı takip eden bir elemanın x’i takip edebilecek olmasıdır.
Takip (y) : { $, y, z} şeklinde bulmuştuk. Bu elemanın (yani y’nin) sonda olduğu bir tanım var mı?
Evet var C–> y bu şartı sağlıyor. O halde kümemizi aşağıdaki şekilde güncelliyoruz:
Takip (y) : { $, y, z, Takip(C) }
Takip (z) : { $, y} şeklinde bulmuştuk. Bu elemanın (yani y’nin) sonda olduğu bir tanım var mı?
Evet var C–> z bu şartı sağlıyor. O halde kümemizi aşağıdaki şekilde güncelliyoruz:
Takip (z) : { $, y, Takip(C) }
Takip (C) : { z } şeklinde bulmuştuk. Bu elemanın (yani C’nin) sonda olduğu bir tanım var mı?
Hayır yok. Bu durumda Takip (C) yukarıdaki şekilde bulunmuştur. Bu takip kümesinin geçtiği önceki örnekleri son haline eriştirebiliriz.
Takip (y) : { $, y, z, z} ancak bir kümede bir eleman bir kere geçebileceği için
Takip (y) : { $, y, z} olarak bulunur
Takip (z) : { $, y, z} olarak bulunur.
Takip (B) : { $ } şeklinde bulmuştuk. Bu elemanın (yani B’nin) sonda olduğu bir tanım var mı?
Evet var, A–>yB bu şartı sağlayan bir kural. Öyleyse takip kümemiz aşağıdaki şekilde olur:
Takip (B) : { $, Takip(A)}
Takip (A) : { x, $ }şeklinde bulmuştuk. Bu elemanın (yani A’nın) sonda olduğu bir tanım var mı?
Evet var, B–>zA bu şartı sağlayan bir kural. Öyleyse takip kümemiz aşağıdaki şekilde olur:
Takip (A) : { x, $ , Takip(B)}
Şimdiye kadar bulduğumuz kümeleri toplu olarak yazarsak:
Takip(x) : {$ , Takip(A)}
Takip (y) : { $, y, z}
Takip (z) : { $, y, z}
Takip (C) : { z }
Takip (B) : { $, Takip(A)}
Takip (A) : { x, $ , Takip(B)}
şeklinde bir listeye erişiriz. Burada dikkat edilirse, Takip(A) ile Takip(B) arasında birbirini içeren (recursive) bir tanım bulunmaktadır. Diğer bir deyişle, A’dan sonra gelen bütün elemanlar B’den sonra ve B’den sonra gelen bütün elemanlar da A’dan sonra gelebilmektedir. Bu durumda bu iki küme birleştirilir.
Takip (B) : { $, x}
Takip (A) : { x, $}
şeklinde iki küme de nihayete erdirilmiş olur.
Takip(x) : {$ , Takip(A)} ise aşağıdaki şekilde güncellenir:
Takip(x) : {$ , x}
Netice olarak özellikle seçilmiş bu zor örnekteki bütün takip kümeleri bulunmuştur.
Son bir örnek üzerinden dilimizde epsilon bulunması durumunda nasıl işleyeceğimizi anlatmaya çalışalım.
Örnek 5:
Aşağıdaki şekilde verilmiş grameri ele alalım:
A –> BxC | Cy
B –>zC
C –>xA | ε
Buna göre tablomuzu ve takip kümelerini (follow set) çıkarmaya ve dilin LL(1) olup olmadığına karar vermeye çalışalım. Bu dilin özelliği, epsilon elemanını içeriyor olmasıdır bu yüzden dilimizde sanki epsilon yokmuş gibi çalışıp ardından epsilon durumunu özel olarak ele alacağız.
Öncelikle sonlulara olan geçişleri işaretleyelim:
| x | y | z | |
| A | |||
| B | B–>zC | ||
| C | C–> xA |
Şimdi devamlılara (non-terminal) olan geçişleri işaretleyelim:
| x | y | z | |
| A | A–>Cy | A–>BxC | |
| B | B–>zC | ||
| C | C–> xA |
Epsilonu dilimizden çıkarmamız halinde, parçalama tablomuz yukarıdaki halini alır. Epsilonu tablomuza eklersek (daha önce nasıl olduğunu Örnek 3’te görüştük) aşağıdaki tabloyu elde ederiz:
| x | y | z | |
| A | A–>Cy | A–>Cy | A–>BxC |
| B | B–>zC | ||
| C | C–> xA |
Bu aşamadan sonra geriye takip kümelerini oluşturmak kalıyor (follow set) ve yine sistemde epsilon yokmuş gibi işlem yapıyoruz (adımlar örnek 4’te detaylı olarak anlatılmıştır).
Takip(x) : { ilk(A) }
Takip (x) : {x,y,z}
Takip (y) : { $ , Takip (A)}
Takip (z) : { ilk(C) }
Takip (z) : { x }
Takip (A) : { $ , Takip (C) }
Takip (B) : { x }
Takip (C) : {y , $ , Takip (B) , Takip (A) }
Şayet epsilon durumunu değerlendirirsek, C değeri yok olabilir. Bu durum, aşağıdaki kurallar için sorun oluşturur:
A –> BxC
B –> zC
bunun sebebi C teriminin sonda bulunması ve aslında son terimin kaldırılması halinde
A –> Bx
B –> z
şeklinde kuralların çalışabileceğidir. Bu durumda Takip(x) kümesine Takip(A) ve Takip(B) kümesine Takip(z) eklenmelidir. Son durum aşağıdaki şekildedir:
Takip (x) : {x,y,z, Takip(A)}
Takip (y) : { $ , Takip (A)}
Takip (z) : { x }
Takip (A) : { $ , Takip (C) }
Takip (B) : { x , Takip(z) }
Takip (C) : {y , $ , Takip (B) , Takip (A) }
Şimdi takip kümelerini açarak yerine yazarsak:
Takip (x) : {x ,y ,z ,$ }
Takip (y) : { $ , x, y}
Takip (z) : { x }
Takip (A) : { $ , x, y }
Takip (B) : { x }
Takip (C) : {y , $ , x }
şeklinde son haliyle takip kümelerini (follow set) elde etmiş oluruz.
Son söz olarak, LL(1) parçalama algoritmasının, verilen bir girdi için, hangi terimden sonra hangi terimlerin gelmesi gerektiğini takip etmede hız sağladığı kesindir. Yazı zaten çok uzadığı için (şu anda 10. sayfadayım) LL(1) kullanılmaması durumunda aynı parçalama işleminin ne kadar uzun sürdüğünü ve hatta hata yaptığını göstermiyorum. Ancak okuyucu bunu kendisi de deneyebilir. Örneğin geri izleme algoritması (back tracking algorithm) kullanarak verilen bir CFG (içerikten bağımsız dil) ile bir dizgiyi parçalamayı deneyebilir. Yine de yazıya gelen yorumlara göre lüzum görülürse bu şekilde bir örnek eklemeye çalışırım.