Derleyici tasarımı, uzun zamandır kendimi geliştirmek için uğraştığım bir konu. Bu konu ile ilgili çok kitaplar ve makaleler okudum ve araştırmalar yaptım. Ama ne yazık ki, bu konuda kendimi ciddi manada ilerleyebilmiş olarak hissetmiyorum. Şimdi ise bu araştırma ve notlarımı burada toplamayı düşünüyorum. Böylece kendimi bu konuda geliştirmeyi ve bununla beraber bu notları sizlerle paylaşmayı düşünüyorum.

Bu yazı serisi, önceden yazdığım makaleler gibi tecrübe ve bilgiye dayalı olmayacak. Okuduğum kitap ve makalelerden ve denemelerimden oluşacak. Bu yüzden bu makale serisinin hedeflediği kitle, sadece bu işin meraklılarına hitap ediyor. Derleyici-yorumlayıcı yazmak isteyenlere faydalı bir konu özeti olacağını düşünüyorum. Ayrıca bu işe yeni başlayacak olanlara veya başlamış ama bir sebepten dolayı yarım bırakmış kimselere de bir fihrist, bir yol haritası olacağını düşünüyorum. Tabi bu notları çıkarmakla ben de kendimi bu konuda geliştirmeyi düşünüyorum.

BaÅŸlarken..

İlk derleyici yazma merakım, bir işletim sistemi yazma merakım olduğunda başladı Gerçi işletim sistemi olarak sadece disketten boot edilebilir ve dos benzeri bir şeyler yazabildim ancak. Fakat bu gayretim bana çok şeyler kazandırdı. Öncelikle bilgisayar ve işletim sisteminin çalışma mantığını çok iyi bir şekilde sindirdim. Ayrıca assembler ve diğer programlama dilleri noktasında da çok faydası oldu. Ayrıca derleyicilerin işletim sistemleri için ne kadar önemli ve vazgeçilmez bir şey olduğunu da gördüm. Bütün o kodları assembler ile yazmak bir yana, herhangi bir hata olduğunda kafayı yememek bir yana. Bu tabiki ilk başlarda derleyici yazma merakından çok, derleyici yazma ihtiyacını doğurdu.

Tabi bunlar çok öncelerde kaldı. Artık eskisi gibi işletim sistemi yazmak gibi uçuk bir düşüncenin altına girmeyi düşünmüyorum. Fakat derleyici yazmak o kadar da uçuk, ütopik olan bir şey değil. Zira en ünlü programalama dillerine baktığınızda hemen hemen hepsinin ilk başlarda bir veya iki kişi ile yazıldığını görürsünüz. Bu konu ile ilgili araştırma yaptıkça, bu konunun anlaşılmasının çok zor olmadığını fakat teoriden pratiğe, uygulamaya dökmenin zorluğunu gördüm. Son zamanlarda derleyici tasarım teknolojisinin gelişmesiyle beraber uygulamaya dökme işlemi de artık -eskisi gibi- çok zor değil. Zamanı geldiğinde bu teknolojilerden bahsetmeye çalışacağım.

Bu Makale Serisi Kime Hitap Ediyor

Ä°lk baÅŸlarda da dediÄŸim gibi öncelikle bu iÅŸe meraklı olmalısınız. Bu konu sadece derleyici veya yorumlayıcı yazmaktan ibaret deÄŸil tabiki. EÄŸer yabancı bir dilden (mesala Ä°ngilizce’den) Türkçe çeviri yapan veya tam tersi iÅŸlemi yapan bir çeviri programı yapmak istiyorsanız, yine bu konu iyi bilmeniz gerekiyor.

Bir derleyici, yorumlayıcı yazabilmek için bir programlama diline iyi hakim olmanız da gerekmektedir. Bu yüzden bu makaleyi okuyabilmeniz için en az bir adet programlama dilini iyi bilmeniz gerekiyor. Üstelik nesne tabanlı programlamayı da bilmeniz işinizi daha da kolaylaştıracaktır.

Ayrıca şunu da belirtmek isterim. Bu konuda Türkçe kaynak yok denecek kadar az. Bu konuda kendinizi geliştirmek istiyorsanız ilk başta İngilizce ile başlasanız fena etmezsiniz.

Kitaplar ve Kaynaklar

Piyasada bu konu ilgili bir çok kitap mevcut. Kimi çok eski ve şu anki teknolojiye hitap etmiyor, kimisi de çok teoride kalıp pratikte hiç bir kullanımından bahsetmiyor. Onca kitap arasından kendimize referans kabul edebileceğimiz kitabı seçmek zor olabiliyor. Ben bunlardan beğendiğim ve gerçekten kaliteli kitapları tavsiye edeceğim. Bu kitaplar genel yorumlarda da iyi gözle bakılan ve günümüz derleyici teknolojilerine de uygun kitaplardır.

Benim tavsiye edebileceÄŸim kitaplar ÅŸunlar:

Compilers, Principles, Techniques and Tools; 2nd Edition: Bu kitap, derleyici tasarımının temel ve vazgeçilmez kitabı olarak kabul edilir. Derleyici tasarımcıları arasında ilk baskısının kapağındaki ejder figüründen dolayı “Dragon Book” ismiyle anılmaktadır. Kitabın ilk baskısı yanılmıyorsam 1986 yılında yayınlanmış. Fakat benim tavsiye edeceÄŸim 2. baskısıdır. 2. baskısı 2006′da çıktı ve deÄŸiÅŸen bir çok derleyici teknolojisini barındırmaktadır. Ä°yi bir baÅŸlangıç yapmak isteyen ve yanı başında referans kitap olarak bulundurmak isteyenlere tavsiye ediyorum.

Engineering a Compiler (Cooper, Torczon): Bu kitabı çok aramama rağman ancak ebay üzerinde bulabildim. Sıfır almak isteyenler için amazonda da mevcut. Ebook olarak bulmayı niyetlenenlere söyleyeceğim şey şu ki, bu kitabın internet üzerindeki ebookları eksik. Daha doğrusu draft, yani yazarın kitap çıkmadan çok önceki taslak metinlerinden oluşuyor. Şu ana kadar incelediğim kitaplar arasında işe yarar, teori ve pratik bilgisi iyi olan ve yeni derleyici teknolojilerine hitap eden nadir kitaplardan birisi.

The Definitive ANTLR Reference: İleride bahsedeceğim derleyici derleyicilerinden birisi olan ANTLR ile ilgili yazılmış güzel bir kitap. ANTLR derleyici derleyicisini tasarlayan ve yazan Terence Parr tarafından yazılmış olan kitapta, sadece ANTLR ile ilgili bilgi bulunmamakta. Bu kitapta derleyici tasarımının temel bilgileri yanında gramer oluşturma, lexer, parser çalışma mantıkları ve LL çakışmaları gibi bir çok konuda bilgi de bulunmakta. Önceki iki kitap, her ne kadar pratikte kullanılabilecek bilgiler içerse de genelde teoriyi hedefleyen kitaplardır. Fakat bu kitap, öğrendiğimiz teoriyi uygulumaya nasıl dökebilceğimizi ayrıntısı ile anlatmakta.

Derleyici-yorumlayıcı yazmak isteyen herkese bu üç kitabı ÅŸiddetle tavsie ediyorum. Bunlar dışında yardımcı olabilecek ÅŸu kitaplara da göz atabilirsiniz.Â

Bu kitaplarla beraber bir sorununuz olduğunda, internet üzerinde ANTLR ve Coco/R mail listeleri sizlere yardımcı olacaktır.

Ayrıca sourcefoge.net gibi bir çok sitede bulabileceğiniz açık kaynak kodlu derleyici projeleri bulunmaktadır. Özellikle Tiny C benzeri bir çok açık kaynak kodlu ve küçük (yani incelenebilir) derleyicilere ulaşabilirsiniz. Gcc, freepascal gibi büyük projeleri de inceleyebilirsiniz. Fakat bu projeler çok büyük olduklarından pek öğretme/öğrenme amaçlı değiller. Bunun yerine daha çok küçük ve deneysel projeleri bulup incelemekte yarar var.

Ben yeri geldikçe bu tarz projeleri bulup sizlerle paylaşacağım. Ayrıca yeni çıkmış olan veya benim yeni keşfettiğim güzel kitapları da burada yeri geldikçe tanıtmaya çalışacağım.

Bir sonraki bölümde derleyiciler hakkında temel teorik bilgiler bulacaksınız. Bir sonraki bölümde anlamadığınız yerler olursa burada verdiğim kitap ve kaynaklardan istifade edererek araştırırsınız. Çünkü bunlar temel konulardır ve sonrasında gelecek olan bölümler bu temel bilgiler üzerine inşa edilecektir.

Bölüm 1: Derleyiciler ve Çalışma Mantığı

Derleyici tasarımı, bilgisayar biliminde önemli bir sahayı oluşturmaktadır. En basit olarak bir derleyici, büyük bir bilgisayar programıdır. Bir derleyici, kaynak kodu alır ve belli bir bilgisayar mimarisine uygun çalıştırılabilir bir hedefe çevirir. Bu çevirimin bir parçası da girilen kaynak kodun imla analizini yani syntax analizini yapmaktır. Bu imla analizi sonucunda, kaynak kodlarda hata tespiti yapılır ve kaynak kodun derleyici içindeki karşılıklarına çevrilir. Derleyeci, daha sonra, bu çevrilmiş olan kaynaklara bir mânâ, anlam yükler. Bu anlam yüklemesi sonucunda, derleyici anlam hatalarını araştırır. Bu işlemden sonra da kaynak kodun derleyicide ifade ettiği anlama göre hedeflenen çıktı üretilir. Tabi bu açıklama çok yüzeysel bir açıklama ve adeta bu bölümde göreceklerimizin bir özeti hükmünde oldu.

Derleyici tasarımı, bir mühendislik çalışmasıdır ayrıca. Derleyici yazarı, bu yolda kendisine bol alternatifi olan, masrafı, avantajları ve zorluğu belirgin olan bir tasarım ortamı oluşturmak zorundadır. Her bir karar, oluşturulacak olan derleyiciyi etkileyecektir. Oluşturulacak olan ürünün kalitesi bu alınan kararlara bağlıdır.

Derleyici tasarımı, çok eski olmamasına rağmen, tatmin edici seviyelere kadar gelişmiş bir konudur. Bu konuda bir çok başarılara imza atılmıştır. Piyasada olan bir çok derleyici ve binlerce çeşit programalama dili ile beraber, bu konudaki bilgiler kullanılarak geliştirilmiş bir çok program, bunun ispatıdır. Bir problemi çözmek için bir çok yöntem geliştirilmiştir. Ben burada en güncel ve popüler tekniklerden bahsetmeye çalışacağım. Ama bilinki, bahsedeceğimiz her bir konu ve teknik için alternatifler mevcuttur. Bu alternatifleri araştırmak size kalmış.

Derleme İşlemine Genel Bakış

Bir program çalıştırılabilir olmadan önce, bir çok çevirim iÅŸlemlerine tabi tutularak hedef çalıştırılabilir kodlar oluÅŸturulurlar. Bu çevirim iÅŸlemini yapan programın özel adına derleyici (compiler) diyoruz. Derleyici, kendisinin anlayacağı bir dilde kaynak kodlarını alır ve çıkışta çalıştırılabilir kodlar üretir. Bu çalıştırılabilir kodlar Windows’da exe, dll, Linux’de elf, so gibi dosyalar olabilceÄŸi gibi, .net, java gibi sanal makinalar için çalıştırılabilir kodlar da üretebilir.

Ayrıca çalıştırılabilir kodlar, direk olarak işleme de tabi tutulabilirler. Yani javascript, vbscript gibi direk olarak derleme anında çalışan derleyiciler de mevcuttur. Bu tip derleyicilerin özel adına ise yorumlayıcı (interpreter) denilir. Her ne kadar bazı eski kaynaklarda yorumlayıcılar ve derleyiciler iki farklı şeylermiş gibi gösterilse de çalışma mantıkları aynı olduğu için hepsine genel olarak derleyici demeyi uygun buluyorum. Çünkü derleme işleminde, ileride ayrıntısı ile göreceğimiz gibi, ilk safha yorumlama, ikinci safha ise kod üretmedir. Yorumlayıcıların tek farkı, kod üretme safhası bulunmamasıdır.

Ayrıca yorumlayıcı kodları, çalışabilmek için bir yorumlayıcıya ihtiyaç duyarlar. Mesela php kodları php derleyicisine, basic kodları basic derleyicisine, javascript kodları ecmascript destekli bir browser’a ihtiyaç duyarlar. Bu kodlar, yorumlayıcı olmadan çalıştırılamazlar. Fakat C++, Delphi gibi derleyicilerin ürettiÄŸi kodları, direk olarak iÅŸletim sistemi üzerinden iÅŸlemci çalıştırmaktadır, daha sonradan derleyiciye ihtiyaçları yoktur.

Bir de günümüz teknolojisinde yorumlayıcı olan ama temelde derleyiciler gibi kod üretebilen derleyiciler de mevcuttur. Mesela php derleyicisi, yorumlayıcı gibi ayrı bir dosyaya iÅŸletim sistemine uygun bir kod üretmeden, hemen çalışmaya baÅŸlar. Fakat yorumlayıcılardan farklı olarak “kod üretir”. Bu kod tabiki ayır bir dosya deÄŸil, IIS, Apache gibi server’lara uygun yapıda opcode’lardır.

Günümüzde derleme iÅŸlemi yapan bir programı, yorumlayıcı, derleyici olarak kesin bir ÅŸekilde ayırmak zorlaÅŸmıştır. Bunun yerine hepsine derleyici demek ve derleme iÅŸlemindeki ilk bölüme yorumlayıcı demek daha doÄŸru olacaktır. Ve bu mantığın kavram karmaÅŸasını da önleyeceÄŸini düşünüyorum. Ve herhangi bir yorumlayıcıya derleyici demeyi de yanlış bulmuyorum. (Php yorumlayıcısı yerine, php derleyicisi demek bana daha uygun geliyor…)

Peki, kaynak kodumuz, derleyici ile tanıştıktan sonra hangi aşamalardan ve safhalardan geçiyor? Bu konuyu ayrıntısı ile ilerleyen bölümlerde göreceğiz. Burada özet mahiyetinde şöyle bahsedebiliriz:

Derleyici İşleyiş Diagramı

Genel manada bu şekilde olsa da hem arka planda, hemde görüntüde bir çok safha değişebilmektedir.

Kaynak kod derleyicimize geldiÄŸi vakit, ilk olarak, kaynak kodun harfleri teker teker iÅŸlenir ve tanımlanarak token dediÄŸimiz nesnelere dönüştürülürler. Bu iÅŸlemi gerçekleÅŸtiren parçaya Lexer denilir. Lexer’ın görevi, imla (syntax) analizi yapıp sonuç olarak bir token listesi oluÅŸturmaktır. Bu imla analizi sırasında kaynak kodda hatalar da bulunabilir. Bu hatalar Lexer tarafından tespit edilir ve imla hatası (syntax error) olarak bildirilir. Lexer, kaynak kodun ifade ettiÄŸi, edeceÄŸi anlam ile uÄŸraÅŸmaz. Hangi token’nın hangisinden sonra geldiÄŸi ile ilgilenmez.

Mesela aşağıdaki karakter katarına bakalım.

Lexer, bu karakter katarındaki her bir karakteri ayrıştırır. “width” kelimesini bir token, “:=” atama operatörünü bir token, 2 sayısını bir token ve “;” iÅŸaretini bir baÅŸka token olarak belirler. EÄŸer gramere göre bu karakter katarında hata mevcut deÄŸilse token listesini üretir. Burada ayrıca her bir boÅŸluk da, kimi lexer’lar tarafından, birer token olarak kabul edilmektedir. Ä°leride ayrıntısını göreceÄŸimiz token’ı Delphi’deki bir record veya C++’daki bir struct yapısına benzetebilirsiniz. Bu record ya da struct içinde, token’nın türü, bulunduÄŸu pozisyon gibi deÄŸerler bulunur.

Lexer, token listesini oluşturduktan sonra işlemini tamamlamıştır. Artık bu token listesini, Parser dediğimiz başka bir derleyici parçasına iletir.

Parser, bu token listesini alır ve bir aÄŸaç yapısı üretir. Bu oluÅŸturulan aÄŸaca, Parse AÄŸacı denilir. Token listesinden oluÅŸturulmuÅŸ olan parse aÄŸacı, yine tokenlardan oluÅŸmuÅŸ bir yapıdır ve derleyicinin tanıdığı gramere göre oluÅŸturulur. Parser eÄŸer aÄŸacı oluÅŸtururken gramere uygun olmayan bir token ile karşılaşırsa bunu hata olarak bildirir. Parserın ürettiÄŸi bu hataya “Gramer Hatası” yada “Parse Hatası” (Parse Error) denilir.

Parser, token içinde bulunan ve tokenın ifade ettiği text ile uğraşmaz. Tokenın karakter katarında hangi pozisyonda bulunduğu ile ilgilenmez. Ayrıca parser, lexer gibi, tokenın ifade ettiği anlam ile uğraşmaz. Parser sadece token listesinin dizilişine göre gramere uygunluğu kontrol eder. Bunun sonucunda da bu token listesinden oluşan bir parse ağacı üretir.

Misal olarak aÅŸağıdaki karakter katarından, Lexer ve Parser’ın ürettiÄŸi çıktılara bakalım:

Â

Lexer ve Parser Ä°ÅŸleyiÅŸi

Bu ağacın oluşturulmasının amacına daha sonra değineceğiz.

Parse aÄŸacı oluÅŸtuktan sonra bu aÄŸaç, Semantik Analiz’e (Semantic Analysis) tabi tutulur. AÄŸacın her bir yaprağında bulunan tokenlar, bu aÅŸamada derleyici için bir mânâ ifade etmeye baÅŸlarlar. Yani artık integer olan bir token, derleyici tarafından integer, deÄŸiÅŸken olan token ise deÄŸiÅŸken olarak anlam verilir. Bunun sonucunda ise, anlam olarak belli hatalar oluÅŸabilir. Bu aÅŸamada oluÅŸabilecek hatalara Semantik Hatalar (Semantic Errors) denilir. Mesela integer olan bir deÄŸiÅŸken, string olan bir deÄŸiÅŸkene direk olarak eÅŸitlenemez! Tabi bu örnek programlama dillerine göre farklılık da gösterebilir. Fakat genel manada integer bir deÄŸeri string bir deÄŸere direk olarak eÅŸitleyemezsiniz. Çünkü bunların token tipleri farklıdır. Bu tarzdaki, yani anlam bakımından yanlış olan iÅŸlemler semantik hataları oluÅŸtururlar.

Semantik analiz sonucunda herhangi bir hata oluşmamış ise parse ağacı yardımı ile intermediate code ya da intermediate representation dediğimiz ara bir kod oluşturulur. Tabi bu safha her derleyicide bulunmayabilir. Bu ara kod oluşturulduktan sonra kodlar optimize edilir ve tekrar son çıktı için kod üretilir. Bazı derleyiciler ara kod oluşturmadan direk olarak kod oluşturabilmektedir.

Bu iÅŸlemlerden bizi en çok zorlayan kısım lexer ve parser kısımlarıdır. Çünkü bu parçalar, programlama dilinin gramerini ifade eden, tanımlanmasında hata kabul etmeyen, hamaliyesi çok olan parçalardır. Bu zorluklardan dolayı bir çok “derleyici derleyicisi” denilen yardımcı programlar geliÅŸtirilmiÅŸtir. Her büyük derleyicide bu derleyici derleyicisi kullanılmaktadır. Bunu daha sonra ayrıntısı ile göreceÄŸiz.

Burada bahsettiÄŸimiz tabirler yabancı gelse de, ileride bunları daha iyi ve ayrıntısı ile bahsedeceÄŸiz. Ama genel olarak “Derleyici Tasarım Notları” baÅŸlıklı bu yazı serimiz bunlardan bahsedecektir. Burada bir nevi, anlatacaklarımızı özetlemiÅŸ olduk. Fakat ayrıntıda gizli, çok farklı teknikler ve yöntemler mevcut. Bunlara yeri geldikçe bahsedeceÄŸiz.

Â

________________________________

Birinci bölüm henüz bitmiÅŸ deÄŸil. Devamını bir baÅŸka zamana atıyorum.Â

Kolay gelsin.

Fatih Tolga Ata © 2009