Derleyiciler (Compilers) Nasıl Çalışır

Derleyicilerin nasıl çalıştığını ve bir derleyicinin adımlarını açıklamadan önce bir derleyicinin ne olduğunu ve ne işe yaradığını açıklamakta fayda var.

Derleyici; kaynak dosyada(.java, .cpp, .cs, vb. dosyalar) bulunan insan tarafından okunabilir kodları, bilgisayarın anlayabileceği makine kodlarına dönüştüren bir programdır.

Bir derleyici 3 ana adımdan oluşur.
Bu adımlar Front-End, Optimizer ve Back-End’dir. Ayrıca bu adımlar da kendi içlerinde alt adımlardan oluşur.

Front-End

Bu aşamada kaynak dosyadaki kodu (.c, .java, .cs gibi kaynak dosyalar) bir metin belgesindeki (.txt veya .docx dosyası gibi) sıradan bir metin gibi düşünebilirsiniz. Derleyici, bu aşamada koddaki karakterleri bir metinden karakter okur gibi tek tek okur ve bunlardan belirli tapılar kurar.

Bu aşama Scanning Analyzer, Syntactic Analyzer ve Semantic Analyzer alt adımlarından oluşmaktadır.

Scanning Analyzer (Lexer)

Lexer, ‘+’, ‘=’, ‘;’, boşluk gibi karakterleri tespit edene kadar kaynak dosyadaki karakterleri tek tek okur ve okuduğu karakterlerle Token adında özel bir nesne oluşturur.

Aşağıda bazı kodlar ve bu kodların token nesnelerine dönüşmesiyle ilgili örnekler yer almaktadır.

# Token Code Example;
x1 = a3 + 5;
x'2;

# Tokens of the code example;

x1  is a  Token (identifier)
=   is a  Token (assignment operator)
a3  is a  Token (identifier)
+   is a  Token (adding operator)
5   is a  Token (number)
;   is a  Token (end of statement)

x'2 is an Invalid Token
;   is a  Token (end of statement)

Syntactic Analyzer (Parser)

Parser, tıpkı insanların kelimelerle cümle kurması gibi token’lar ile ifadeler(statements) oluşturur. Bir önceki bölümde(Lexer bölümü) elde edilen token’lar, ifadeler oluşturmak için kullanılır. Oluşturulan bu ifadeler daha sonra Abstract Syntax Tree (A.S.T.) adı verilen özel bir veri yapısına dönüştürülür.

Parser’ın amacı oluşturulan ifadenin gramer açısından doğru olup olmadığını anlamak ve A.S.T.’de hata ayıklaması yapmaktır.

Gramer, derleyicinin geçerli bir ifadeye sahip olması için programcıya verilen kurallardır.

Her bir token’ın doğru kullanıldığı ancak gramerin yanlış olduğu kod örneği aşağıda verilmiştir.

# Invalid Grammar Example;
num = a*b +/;

Grammar açısından doğru kod örneği aşağıdadır.

# Valid Grammar Example;
num = a*b + y/z;

Grammar açısından doğru kodun A.S.T. grafiği.

Semantic Analyzer

Semantic Analyzer kaynak dosyada yazılan kodun gramer açısından doğru olsa bile kaynak dosyada yazılan kodun anlamlı olup olmadığını kontrol eder.

Gramer olarak doğru olsa bile bir ifadenin ve kodun anlamsız olabileceği örnekler aşağıda verilmiştir.

# İfade örneği; 
Ahmet'in evi Ahmet'e gidiyor.

Açıklama: Bu cümle gramer açısından doğru, ancak anlamsızdır.

-----------------
# Kod örneği;
5 = x;

Açıklama: 5 değeri, saf bir gerçek değerdir ve
x, yerel bir değerdir(x bellek adresini temsil eder).
Yerel bir değişkene gerçek bir değer atanabilir,
ancak tersi bir durum anlamsızdır.

Bir kodun gramer açısından doğru olsa bile anlamsız olabileceği anlaşıldığına göre, gerçek hayattan bir örnek verelim.

Person p;
Computer c;
int x;
x = p - c;

Gerçek hayatta bir kaynak dosyaya kod yazdığımızda her bir bildirimimiz ve değişkenimiz için Symbol Table çağrılır.

Anlaşılacağı üzere kaynak kodumuzdaki bildirimlerin ve değişkenlerin kapsam alanları, tipleri, vb. bilgileri Symbol Table’da mevcuttur.

Derleyici yukarıdaki örneğin anlamsız kodlar içerdiğini derleme esnasında Semantic Analyzer aşamasında Symbol Table’ı kontrol ederek anlayabilir.

Optimizer

Optimizer, hedef makineden bağımsız olarak (x86, arm, GPU vb. mimariler) derleyicinin front-end aşaması sonunda elde edilen A.S.T. veri yapısını optimize etmeye çalışır.

Derleyicinin amacı optimizasyon ile kodu daha hızlı hale getirmeyi ummaktır.

Bu optimizasyon işlemleri için farklı yöntem ve yaklaşımlar vardır. Bunlardan en yaygın olanı Command Subexpression Elimination(CSE)’dir. C.S.E. yaklaşımını kabaca özetlemek ve basit bir örnek vermek gerekirse, birden fazla tekrar eden işlem varsa, bu işlemler bir değişkene atanır. Bu işlemlere ihtiyaç duyulduğunda, atandıkları değişkenlerden kullanılırlar.

Optimizer’ın çözümleri bir nevi sezgisel algoritmalardır.

Back-End

Optimizer aşamasından farklı olarak, Derleyici bu aşamada kodumuzu hedef makinemizin özelliklerine (x86 veya arm mimarisi, çekirdek sayısı vb.) göre optimize etmeye çalışır.

Bu aşama Instruction Selection, Instruction Scheduling ve Register Allocation alt adımlarından oluşur.

Derleyici, Back-End kısmında kodumuzu optimize etmek için Optimizer kısmından elde ettiği AST veri yapısını, Abstract Assembly Model’ine dönüştürür.

Abstract Syntax Tree = Üst Düzey Ara Gösterim
Abstract Assembly Model = Düşük Seviyeli Ara Gösterim

Abstract Assembly Model olarak oluşturulan “num = a*b + y/z “ örneği aşağıdadır.

# Abstract Assembly Model of "num = a*b + y/z";

load a -> r1 
load b -> r2 
mult r1, r2 -> r3
load y -> r4 
load z -> r5 
div r4, r5 -> r6
add r3, r6 -> r7
store r7 -> num

Instruction Selection

Günümüzde farklı işlemleri farklı şekillerde gerçekleştirebilen farklı işlemciler bulunmaktadır.

Bazı işlemciler bellekten değerleri tek tek alıp register’lara tek tek yazarken (yukarıdaki örnekteki soyut assembly modeli gibi), diğer bazı işlemciler bellek operasyonları gibi işlemlerle bellekteki verilere doğrudan erişip işleyebilmektedir.

Örneğin; bir derleyici
a load -> r1
b load -> r2
mult r1, r2 -> r3
yerine mult[a], [b] -> r1 komutunu seçebilir.

Derleyici, Instruction Selection aşamasında hedef makinemiz için mevcut seçenekler arasından en performanslı seçeneği seçmeye çalışır.

Instruction Scheduling

Derleyici, Instruction Scheduling aşamasında komutların gecikme sürelerini, hedef makinenin register sayısını ve benzeri parametreleri dikkate alarak programımızın en verimli şekilde çalışabilmesi için komutları yeniden düzenler.

Örnek olarak, instruction selection kısmındaki abstract assembly modelinin daha verimli çalışması için aşağıdaki şekilde yeniden düzenlendiğini düşünebiliriz.

# Reorganized Abstract Assembly Model of "num = a*b + y/z";

load a -> r1
load b -> r2
load y -> r4
load z -> r5
mult r1, r2 -> r3
div r4, r5 -> r6
add r3, r6 -> r7
store r7 -> num

# Latencies of Operations
#   load   = 2 cycle
#   store  = 3 cycle
#   mult   = 4 cycle
#   div    = 5 cycle
#   add    = 1 cycle

Yukarıdaki örnekte mikroişlemcinin pipelining yapabildiği varsayılmaktadır.

Register Allocation

Derleyici, Register Allocation aşamasına kadar virtual register adı verilen sonsuz sayıda register’a sahipmiş gibi davranır. Ayrıca, bu virtual register’lar ile önceki adımlardaki abstract assembly modeli oluşturulur. Yukarıdaki örneklerde gösterilen r1, r2 ve benzeri register’ların hepsi birer virtual register’dır ve iki virtual register ile yapılan işlem sonucu ortaya çıkan register’lar da temporary virtual register’dır.

Örneğin; mult r1, r2 -> r3
burada r3 bir temporary virtual register’dır.

Derleyici, önceki adımlarda oluşturulan abstract assembly modelinden virtual register’ları alır ve Register Allocation aşamasında bunları hedef makinedeki gerçek register’larla eşleştirir.

Tahmin edebileceğiniz gibi, bir hedef makinenin resgister sayısı sonsuz değildir. Derleyici, eşleme için en yüksek önceliğe sahip virtual register’ları hedef makinedeki gerçek register’lar ile eşler ve gerçek register’lar ile eşlenemeyen virtual register’daki veriler bu aşamada tekrar bellekte saklanır.

Özetle, kaynak dosyadaki kod bu üç adımı ve bunların alt adımlarını başarıyla tamamladığında, bir bilgisayarın anlayabileceği makine koduna dönüşmüş olur.

Buraya kadar okuduğunuz için teşekkür ederim.

Kod örneklerini buradan takip edebilirsiniz:

GitHub - KeremTAN/Compiler-Lecture: The aim of this repository is to keep the applications in the…

Derleyici Teorsini daha detaylı öğrenmek için buradaki video’ya gidebilirsiniz: