Compiler Tasarımı

Compiler Tasarımı Niçin Compiler Tasarımı ? Compiler tasarımı bilgisayar mimarisi ve automata teorisinin temel uğraşlarından biridir. Şayet iyi bir yazılım mühendisi olmak istiyorsanız yazdığınız kodların compiler mutfağında nasıl pişirildiğini bilmelisiniz. Böylelikle kod yazarken muhtemel hataları sezebilir, en optimum verimliliğe sahip kodlar yazabilirsiniz. Bence compiler tasarımı çok önemlidir. Evet mutfak da nasıl piştiğini bilmesek de yemek yiyebiliriz ama bir gün mutfağa girme zorunluluğuz olursa ne yapacaksınız ? Bilgisayar bilimi matematik temellidir. Matematikse basit ve kesin kabullerden oluşur. Biz 1 i 1 olarak, tam daireyi 360 derece olarak, sin 90" ı 1 olarak 2 X 2 = 4 olarak basit ve temel kabullerle matematiği oluşturduk. Bilgisayar bilimindeki en basit kabuller dil kurallarıdır (syntax). Örneğim C++ da int değişken; bildirimi ram’de 32 bitlik (int) bir değişken tanımlar ama bunun nerede ve nasıl olduğu bizi ilgilendirmez. Oysaki bu yazdığımız programın verimi acısından çok önemlidir. Çünkü biz ne yaparsak yapalım compiler ’ın ram-disk-güvenlik verimliğinden bağımsız programlar oluşturamayız. Dolayısıyla compiler ’ın başarısı bizim programımızın başarısını direk etkiler. Bu konuda en bariz örnek tüm yazılımcılar tarafından bilinen Basic kodlarının yavaş C++ kodlarının hızlı olduğudur. Peki ama neden ? Cevap compiler tasarımlarıdır. Basic, program içerisinde kullanılan tüm değişkenleri program başladığında tanımlar ve tek bir değişken uzayında saklar. Basic ram yönetimi acısından oldukça basit bir yol izlemektedir ama bu gereksiz değişkenlerin tüm program boyunca (life time) ram’de yer kaplamasına ve gereksiz yavaşlığa sebep olur. Dolayısıyla basic ’de kod yazan tasarımcı basic compiler ’ın bu özelliklerini biliyorsa her iş için yeni değişkenler tanımlamaktan kaçınacaktır. C++ değişken tanımlama ve ram yapısı: C++ da ise 2 farklı ram alanı vardır. Genel değişkenlerin listesi management head "de özel değişkenler stack" de saklanır. Küçük boyutlu değişkenler (int, byte, char gibi) direk management head "de saklanır. Bu değişkenlere değer tipli değişken denir. Büyük boyutlu değişkenlerde (array, string, struct, class vb.) ise sadece değişkenin bir işaretçisi (pointer ’ı) management head ’de saklanır. Büyük boyutlu veri veya değişkenlerin kendisi programın data segment ’inde saklanır. Dolayısıyla bu değişken tipi, ilişkili bir data segment alanı ve bir pointer ’dan oluşur. Bu değişkenlere de referans tipli değişkenler denir. (Ben bu yazıyı yazdığımda .NET ile ilk tanıışma dönemleri idi. Aslında .NET ile adını cok duyduğumuz Management code, Referans Type, Value Type gibi kavramlar gökten inmedi onlar hep vardı.) Burada C++ ‘da başvuru olarak bilinen kavram ortaya çıkmaktadır. Başvuralar aslında aynı isme sahip iki değişkenden oluşur. Birincisi data segment ‘de tanımlı gerçek veriyi saklayan değişken, ikincisi data segment deki veriyi işaret eden management head "de tanımlı (bir pointer) değişken. Yani başvuru aynı isme ait biri referans, diğeri değer tipli iki değişken tanımlar. Başvurular sayesinde compiler değer ve referans tipler arasında ki farkları ortadan kaldıra bilmekte çalışma anında hangisinin kullanılacağına kendisi karar vermektedir. Gelişmiş ram yönetimi sayesine c++ scope ‘lar geliştirmiş ve değişkenlerin ram deki hayat zamanlarını (life time) bu scope larla belirlemiştir. Bir programın (veya sınıfın) genel değişkenleri ve ana scope da ki değişkenler direk management head de saklanırken, fonksiyonlara giden parametreler ve alt scope da ki değişkenler stack de saklanmaktadır. Böylelikle C++ (Java ve .NET) programları bir anda mümkün olan en az ram alanını kapsamakda pointer"lar ile verimliliği sağlamaktadır. Yukarıda bahsedilen tartışma göstermiştir ki compiler"lar yazdığımız programın mutfağında aslında programın en önemli özeliği olan verimliği sağlamaktadır. Yazdığımız programın karakteristik özelliklerini aslında compiler"lar belirlemektedir. Nasıl Compiler Tasarlarım ? Klasik compiler tasarımına geçmeden önce bir bilgisayar dili (computer language) nedir, hangi bileşenlerden oluşur. Yazdığımız kod orta seviyede hangi elemanlarla temsil edilir. Açıkça diller düzenli değildir. Noam Chomsky düzenli ve diğer dilleri şu şekilde kategorize etmiştir: Dil Sınıfı Gramer Automaton 3 Regular NFA ve DFA 2 Context-Free Push-Down Automaton 1 Context-Sensitive Linear-Bounded Automaton 0 Sınırsız (Unresticted-Free) Turing Machine Burada durup küçük bir kaç noktayı vurgulayalım. Üst seviye diller alt seviye dilleri kapsamaksakdadır. Dolayısıyla yeni bir dil yazacaksak mutlaka en azından dil kurallarının düzenli ifadelerce tanımlanabilir olması gerekmektedir. Biz automata teorisinden tüm ifadelerin düzenli ifadeler tarafından temsil edilemediğini bilmekteyiz. Sonuç olarak tüm bilgisayar dillerinin (ve dolayısıyla programlarının) sınırı düzenli ifadelerce temsil edilebilmektir. Biz farkında olmasakda aslında yazdığımız program kodlarının arka alanda compiler tarafından tanınmasında kullandığımız dil sınıfına göre NFA,DFA, Push-Down automata veya Linear-Bounded automata"lar kullanılmaktadır. Dolayısıyla NFA,DFA gibi automata yapıların nasıl çalıştığını anlayarak yazdığımız kodun neye dönüşeceğini ve ne ifade ettiğini daha iyi anlarız. Bu dillerin karşılığı olan makina sistemlerine göre yapılabilecek cıkarımlar: Context-Sensitive dillerin Context-Free dillerden daha güçlü olduğu görülmektedir. Dolayısıyla C++, Java, C# gibi (Context-Sensitive) bir dil, yapısı itibariyle Pascal, Delphi, Basic gibi (Context-Free) bir dilden daha güçlüdür.  Şu an da  kullandığımız popüler yazılım dilleri olan C++, Java, C#"ın sonu ne olur sorusuna cevaptır. Yazılım dilleri gelişimini düşündüğümüzde regular bir dil olan ADA  ile başlayan üst seviye yazılım dili gelişimi context-free diller olan Basic ve Cobol ile devam etmiş daha sonra context-sensitive C dilli ile sürmüştür. OOP ‘in yazılım dilerine girmesi ile context-sensitive diller olan, sıra ile C++, Java ve C# dilleri üretilmiştir. Biz bu gelişimden bir sonra ki dillerin Free diller olacağı sonucunu çıkarabiliriz. Free dillerin geliştirilmesinin kolay olmayacağı kesindir. Çünkü free gramerler hiç bir gramer sınırlamasına sahip değildir. Düzenli fakat sınırlamasız bir gramer yapısına ait bir dilin geliştirilmesi ve öğrenilmesi son derece zor alacağı kesindir. Fakat gün geçtikçe daha zor hale giren yazılım problemlerinin çözülmesinde Context-Sensitive dillerin yetersiz kaldığı durumların artması bizleri Free dil tasarımlarına yönelteceği kesindir. Bu yazıda automata teorisine ait konular olan automata’lara değilinmeyecektir. Bunun iki sebebi var. Bu automata"ların çalışma şekilleri ve yapıları çok önemli olmasına rağmen, yapmaya çalıştığımız şey compiler tasarlamaktır. Dolayısıyla bu yazının okuyucuları uzman yazılımcılardır ve bu konuları zaten bilinmektedir.  İkincisi automata teorisi buraya sığmayacak kadar önemli ve büyük bir teoridir. Kısaca dil yapılarına bir bakış yaptıktan sonra şimdi compiler tasarım modelini inceleye biliriz. Klasik compiler tasarımı 7 kademeden oluşur ve yapısı aşağıda ki şekilde gösterilmiştir. Compiler katmanlarını anlatmaya başlamadan önce bu tasarım modelinin tek compiler modeli olmadığının bilinmesi gerekir. Bu tasarım modeli özellikle C++, Java gibi nesne dayalı programlama (OOP) dilerine ait compiler tasarım modelidir. Basic gibi script dillerde tablo yönetimi ve bütünleşik hata  yakalama sistemi bulunmamaktadır. Ayrıca Java ve .NET dilleri gibi platformdan bağımsız dillerde compiler"lar sadece orta seviye kod üretimi yapmaktadır. Diğer aşamalar JIT (Just In Time) derleyicileri tarafından çalışma anında gerçekleştirilmektedir. Lexical Analiz: Bu seviyede kod "token"lara ayrılır. Token kodun mantıklı en küçük parçasıdır .Örneğim “int”, “byte” gibi tip isimleri, değişken, fonksiyon ve sınıf isimleri birer token ile ifade edilirler. Burada kaynak kodu regular ifadeler haline çevrilir. Her bir değişken tanımıyla dinamik olarak büyüyen bir NFA kullanılır. Bu NFA token da ki her bir karakterle eğer varsa uygun state değişimini yapar yoksa hata üretir . Token bittiğinde NFA bir “final state” ise NFA “final state” ait token değerini döndürür. Token bittiğinde NFA bir “final state” de değilse hata üretir. Bu kısımda yazım hatalarının ayıklanır. Syntax Analiz : Elde edilen ifadelerin dil kurallarına uyun olup olamadığı kontrol edilir. Örneğim “fonksiyon_ismi ( parametre_ismi ) ;” şeklinde olması gereken ifade “fonksiyon_ismi ( tip_ismi );” şeklinde ise parametre_ismi yanlış ve yanlış tip tanımlaması hataları üretilecektir. Bir çok compiler hataları sınıflandırmıştır ve önemli hatalarla karşılaşılmadığı sürece kesilmez. Böylelikle bir derleme işleminde birden çok hata yakalanmaktadır. Aynı zamanda ifadeler postfix halinden mikro işlemci için daha anlamlı olan prefix haline dönüştürülür. Burada bir tam ifade oluşturulur. Yani “d = a / b * c ;” ifadesi “ = d / a * b c ”ifadesine döner. Bu ifadeyi parser tree olarak gösterirsek.   Tablo Yönetimi: Yazının en başında bahsedilen değişken ve kod ömürlerinin takip edildiği katmandır. Orta Seviye Kod Üretimi: Bilgisayar mimarisine uygunluğu sağlamak için işlemler bu seviyede üç adresli kod şekline çevriliyor. Yani bir adımda sadece bir işlemci komutunun gerçekleşmesi sağlanıyor. Örneğim “= d / a * b c ” ifadesi “T1 = b * c, T2 = a / T1,d = T2 “ şekline çevrilir. Bilgisayar mimarisinden haberi olan insanlar olarak biz T1 ve T2 in aslında mikro işlemcinin registerlerini temsil ettiğini söyleyebiliriz. Hata Yakalama: Derleme işlemi sırasında oluşabilecek her türlü hatanın yakalandığı yerdir. Kod Optimizasyonu: Gereksiz mikroişlemci adımlarının araştırılıp optimizme edildiği yerdir. Örneğim “a = b + c + d ; e = b + c + f ” komutu “ T1 = b + c; a = T1 + d; e = T1 + f” şekline çevrilir. Kod  Üretimi: Burada mikro işlemcinin anlayabileceği çalıştırılabilir kod üretilmektedir.  

Döküman Arama

Başlık :

Kapat