Bu doküman, derleyici (compiler) tasarımında kullanılan parser (ayrıştırıcı) tekniklerinin temelini ve önemini anlatmak için hazırlanmıştır. Parser'lar, kaynak kodun sözdizimsel olarak doğru olup olmadığını kontrol eder ve kodu anlamlı parçalara (AST - Soyut Sözdizim Ağacı) dönüştürerek derleyicinin sonraki aşamalarında (ör. analiz, optimizasyon, kod üretimi) kullanılmasını sağlar. Farklı grammar kuralları ve birleşme yönleri (left/right associativity) ile parser yazmak, hem dilin kurallarını doğru uygulamak hem de karmaşık ifadeleri doğru şekilde çözümlemek için kritik öneme sahiptir.
Bu repo, derleyici (compiler) ve parser konularında öğrendiğim temel bilgileri ve örnekleri paylaşmak için hazırlanmıştır. Özellikle context-free grammar (CFG) kuralları, left/right associativity (sol/sağ birleşmeli) kavramları ve soyut sözdizim ağacı (AST) oluşturma örnekleri içerir.
Bir grammar, bir dilin cümlelerinin nasıl oluşturulacağını tanımlayan kurallar bütünüdür. Özellikle context-free grammar (CFG), her kuralın sol tarafında tek bir değişken (non-terminal) bulunur ve sağ tarafında ise terminal ve/veya non-terminal semboller yer alabilir.
Örnek CFG kuralı:
<expr> ::= <expr> "+" <pow> | <pow> ; '+' sol birleşmeli (left-associative)
<pow> ::= <number> "^" <pow> | <number> ; '^' sağ birleşmeli (right-associative)
<number> ::= [0-9]+ ; basit sayılar
Bir işlem sol birleşmeli ise, aynı öncelikteki işlemler soldan sağa doğru gruplanır. Örneğin toplama işlemi:
1 + 2 + 3 → (1 + 2) + 3
Yani önce sol taraftaki işlemler yapılır.
Sol birleşmeli işlemlerde, AST (soyut sözdizim ağacı) oluşturulurken her yeni işlemde yeni bir node üretilir ve bu node'un soluna, daha önce oluşturulan tüm işlemler (ve operandlar) yerleştirilir. Yani işlemler soldan sağa doğru zincirlenir ve her + gördüğümüzde, mevcut ağacın tamamı yeni node'un soluna bağlanır.
Adım adım örnekle açıklayalım:
Örneğin 2 + 3 + 4 ifadesi için AST şöyle oluşur:
-
İlk olarak
2ve3işlenir, bir+node'u oluşturulur:+- sol:
2 - sağ:
3
-
Sonra
+ 4geldiğinde, yeni bir+node'u oluşturulur ve mevcut ağaç (ilk + node'u) sol tarafa bağlanır:+- sol: (önceki + node'u)
- sağ:
4
Bunu recursive kodda şöyle yazarız:
// Left-associative parser for + (recursive)
Node *parseExprHelper(const std::string &s, Node *left) {
if (peek(s) == '+') {
consume();
Node *right = parsePow(s);
Node *node = new Node("+");
node->left = left; // Tüm önceki işlemler sol tarafta birikir
node->right = right; // Sağda sadece yeni operand
// Eğer daha fazla + varsa, yeni node'u tekrar recursive olarak işliyoruz
return parseExprHelper(s, node);
}
return left;
}
Node *parseExpr(const std::string &s) {
Node *left = parsePow(s);
return parseExprHelper(s, left);
}Yani: Her + işlemi için yeni bir node oluşturulur ve mevcut ağaç sol çocuğa bağlanır. Bu sayede AST'de işlemler soldan sağa zincirlenmiş olur (left-associative).
Bir işlem sağ birleşmeli ise, aynı öncelikteki işlemler sağdan sola doğru gruplanır. Örneğin üs alma işlemi:
2 ^ 3 ^ 4 → 2 ^ (3 ^ 4)
Yani önce sağ taraftaki işlemler yapılır.
Sağ birleşmeli bir parser yazarken, önce recursive çağrı yapılır, sonra node oluşturulur. Yani önce sağ taraf tamamen çözülür, sonra node üretilir:
// Right-associative parser for ^
Node *parsePow(const std::string &s) {
Node *left = parseNumber(s);
if (peek(s) == '^') {
consume();
Node *right = parsePow(s); // önce recursion, sonra node
Node *node = new Node("^");
node->left = left;
node->right = right;
return node;
}
return left;
}Burada önce sağ taraf tamamen çözülür (recursive çağrı), ardından node oluşturulur. Bu sayede sağ birleşmeli işlemler AST'de sağdan sola gruplanır.
Yukarıdaki grammar'da:
+işlemi sol birleşmeli (left-associative) olarak tanımlanmıştır.^işlemi sağ birleşmeli (right-associative) olarak tanımlanmıştır.
Bu repo altında, hem sol hem sağ birleşmeli işlemler için örnek parser kodları ve AST çıktıları bulabilirsiniz.
Örneğin aşağıdaki ifadeyi grammar kurallarımızla nasıl türeteceğimizi adım adım gösterelim:
Örnek ifade:
2 ^ 3 ^ 4 + 5 + 6
<expr>
<expr> → <expr> + <pow>
<expr> → (<expr> + <pow>) + <pow>
<expr> → (<pow> + <pow>) + <pow>
<pow> → <number> ^ <pow>
<pow> → <number> ^ <pow>
<pow> → <number>
((2 ^ (3 ^ 4)) + 5) + 6
Aşağıda, yukarıdaki ifadenin AST çıktısı örneği verilmiştir:
+
+
^
2
^
3
4
5
6
- Her satırdaki girinti (boşluk) bir derinlik seviyesini gösterir. Girinti arttıkça, o node bir üsttekinin çocuğudur (child).
- Aynı girinti seviyesindeki node'lar, aynı parent'ın (üstteki node'un) child'larıdır.
- En üstteki
+en dıştaki işlemdir (root/parent). Altındaki her şey onun alt ağacıdır. - Örneğin, en üstteki
+'nın iki child'ı var: bir altındaki+ve en alttaki6. - Bir altındaki
+'nın da iki child'ı var:^ve5. ^node'u ise, solunda2, sağında ise başka bir^node'u (yani 2 ^ (3 ^ 4)) barındırır.
Bu şekilde AST çıktısı, işlemlerin hangi sırayla ve nasıl gruplanacağını görsel olarak gösterir. Her parent node, altındaki child node'ları ile birlikte bir işlemi temsil eder.
- Terminal: Grammar'da, dilin en küçük yapıtaşı olan ve daha fazla açılmayan sembollerdir. Örneğin: '+', '^', '(', ')', '5', 'a' gibi doğrudan çıktıda görünen karakterler.
- Non-Terminal: Grammar kurallarında tanımlanan ve başka kurallarla açılabilen sembollerdir. Örneğin:
<expr>,<pow>,<number>gibi.
Bir grammar kuralı şu şekilde yazılır:
<non-terminal> ::= <ifade>
Örneğin:
<expr> ::= <expr> "+" <pow> | <pow>
Bu, bir <expr>'in ya <expr> + <pow> ya da sadece <pow> olabileceğini belirtir.
Bir non-terminal, tanımının en solunda kendisini tekrar çağırıyorsa buna left recursion (sol özyineleme) denir. Örnek:
<expr> ::= <expr> "+" <pow> | <pow>
Bu kuralda <expr> kendisini en başta çağırıyor.
Left recursion soldan kendini çağırır.
Recursive descent parser ilk olarak soldan açmayı dener.
Terminale ulaşmadan recursion devam eder → infinite loop.
Bu repodaki ast_parcer.cpp de recursive descent parser yaklaşımı kullanılmıştır. Left recursion (sol özyineleme) klasik haliyle recursive descent ile çalışmaz, sonsuz döngüye girer. Kodlarda left recursion'ı sağ özyinelemeye çevirerek (yardımcı fonksiyonlarla) nasıl çözdüğümü ve AST'nin doğru şekilde üretildiğini doğrudan inceleyebilirsiniz.
Sol özyinelemeyi sağ özyinelemeye çevirerek çözebiliriz. Yani kuralı şu şekilde dönüştürebiliriz:
<expr> ::= <pow> <expr'>
<expr'> ::= "+" <pow> <expr'> | ε
Burada <expr'> yeni bir non-terminaldir ve ε (epsilon) boş üretimi temsil eder. Bu dönüşüm, parser'ın sonsuz döngüye girmesini engeller.
Son Not: Grammar kurallarına ve kodun yapısına dikkat ederseniz, C++ kodunda çağırılan parse fonksiyonlarının sırası (ör.
parseExpr,parsePow,parseNumber), grammar kurallarındaki üretim sırasıyla birebir aynıdır. Yani kodun akışı, grammar'ın tanımladığı dilin yapısını doğrudan takip eder. Bu, parser yazarken kodun okunabilirliğini ve doğruluğunu artırır.