2 + 3 × 4 neden 14 eder?

2 + 3 * 4 ifadesini soldan sağa hesaplarsak 20 buluruz. Bildiğimiz aritmetik kurallarıyla sonuç 14 olur. Bir parser yazarken, alışık olduğumuz bu kuralı açıkça tarif etmemiz gerekir.

Sıra değil, yapı

İfade bir liste gibi görünse de anlamını bir ağaçla gösterebiliriz:

Kök düğüm toplama işlemidir. Sol çocuğu 2, sağ çocuğu ise çarpma ifadesidir. Sağ çocuğun değerini bulmadan toplamayı tamamlayamayız: 3 * 4 = 12, ardından 2 + 12 = 14.

AST, yani abstract syntax tree, dilin anlamlı yapısını temsil eder. Her kaynak karakteri ağaçta yer almak zorunda değildir. Parantezler yapıyı belirlerken ayrı düğümler olarak tutulmayabilir.

Bu önceliği nasıl tarif ederiz?

Toplama ve çarpma için ayrı gramer katmanları yazabiliriz:

expression → product (("+" | "-") product)*
product    → unary   (("*" | "/") unary)*
unary      → ("-" | "+") unary | primary
primary    → NUMBER | IDENT | "(" expression ")"

Buradaki sondaki *, programdaki çarpma işareti değildir: gramer gösteriminde “sıfır veya daha çok tekrar” anlamındadır. Tırnak içindeki "*" ise gerçek çarpma operatörüdür.

Toplamayı okuyan fonksiyon, her bir parçayı okumak için çarpma katmanını çağırır. Böylece çarpma ifadesi toplamanın bir parçasına dönüşür.

Öncelik ile birleşme yönü farklıdır

10 - 3 - 2 ifadesinde iki operatörün de önceliği aynıdır. Bu kez birleşme yönüne ihtiyacımız var.

(10 - 3) - 2 = 5
10 - (3 - 2) = 9

Bu deneyde çıkarma soldan birleşir. Gramerin tekrarını bir döngüyle okuyup önceki sonucu yeni düğümün sol çocuğu yaparak bunu sağlıyoruz.

Öncelik, farklı operatörlerin nasıl gruplanacağını; birleşme yönü, aynı öncelikteki operatörlerin nasıl gruplanacağını belirler.

Kendin dene

print 2 + 3 * 4; ile print (2 + 3) * 4; ifadelerinin ağaçlarını kâğıda çizip karşılaştır. Ardından print 10 - 3 - 2; için aynı alıştırmayı yap. Sonucu hesaplamadan önce ağacın yapısını düşün.

İngilizce köşesi

Precedence: işlem önceliği. Associativity: birleşme yönü.

Multiplication has higher precedence than addition. Subtraction is left-associative in this small language.

Kaynak okuma: Crafting Interpreters — Parsing Expressions.