Ayrıştırma Ağacı

Ayrıştırma ağacı (parse tree), biçimsel dil kuramının temel kavramlarından biri olup bir dilin üretim kurallarına (gramer) uygun biçimde bir dizgenin (string) nasıl üretildiğini hiyerarşik bir yapı olarak gösteren grafiksel temsildir. Ayrıştırma ağaçları, bilgisayar bilimlerinde özellikle derleyici tasarımında, doğal dil işleme (NLP) alanında, matematiksel ifadelerin çözümlemesinde ve cümle analizlerinde yaygın biçimde kullanılmaktadır.

Temelde bir ayrıştırma ağacı, bir bağlamdan bağımsız gramer (context-free grammar) yardımıyla belirli bir giriş dizgesinin o gramer tarafından üretilip üretilemeyeceğini ve eğer üretilebiliyorsa, hangi adımlarla üretileceğini görsel bir yapı olarak ifade eder. Bu yapı, üretim kurallarının uygulama sırasını ve ara aşamaları da içerir.

Ayrıştırma ağaçlarının temeli biçimsel dil kuramına dayanır. Bir gramer G=(V,Σ,R,S) dört ögeden oluşur:

• V: Tüm sembolleri (terminal ve non-terminal) içerir.
• Σ: Terminal semboller kümesidir.
• R: Üretim kuralları kümesidir.
• S: Başlangıç sembolüdür.

Bir ayrıştırma ağacı:

• Kök düğüm (root) olarak başlangıç sembolünü barındırır.
• İç düğümler (non-terminal düğümler) üretim kurallarının sol tarafını temsil eder.
• Yapraklar (leaves) terminal semboller (veya boşluk sembolü ϵ) içerir.
• Her bir iç düğümün çocukları, ilgili üretim kuralının sağ tarafındaki sembolleri gösterir.

Ayrıştırma ağacı bir kök düğümden dallanan dallar aracılığıyla terminal sembollere ulaşır. Düğümler ikiye ayrılır:

• İç düğümler (non-terminal): Üretim kuralı uygulandığını gösterir.
• Yaprak düğümler (terminal): Üretim sona ermiş, artık sembol terminaldir.

Her düğüm bir etikete sahiptir. Örneğin, (x + y) * z ifadesi için bir ayrıştırma ağacı kökünde E bulunur. Üretim kurallarının hangi sırayla uygulandığına bağlı olarak ağaç dallanır.

^{Ayrıştırma ağacı yapısı örneği (Yapay zeka ile oluşturulmuştur.)}

Bir ayrıştırma ağacı, birden fazla farklı türetimden doğabilir. Türetim sırasında:

• Sol-öncelikli türetim (leftmost derivation): Her adımda en soldaki non-terminal değiştirilir.
• Sağ-öncelikli türetim (rightmost derivation): Her adımda en sağdaki non-terminal değiştirilir.

Örnek: x + y *z

• Sol - öncelikli: E⇒E+E⇒x+E⇒x+E∗E⇒x+y∗E⇒x+y∗z
• Sağ - öncelikli: E⇒E∗E⇒E+E∗E⇒x+E∗E⇒x+y∗E⇒x+y∗z

Burada farklı türetimler aynı ifadeyi üretebilir. Eğer farklı türetimlere karşılık gelen farklı ayrıştırma ağaçları varsa, gramer belirsizdir.

Bir gramer, bir dizge için birden fazla farklı ayrıştırma ağacı üretilebiliyorsa belirsizdir. Örneğin, a + b * c ifadesi hem çarpmanın hem de toplamanın öncelik kuralına göre farklı şekillerde ayrıştırılabilir. Bu durum, derleyiciler için istenmeyen bir durumdur. Bu nedenle çoğu programlama dili grameri, öncelik kurallarını açıkça belirten belirsiz olmayan grammarlardır.

Örnek:

Belirsiz gramer: E→E+E, E→E∗E, E→a∣b∣c

Bu gramer a + b *c ifadesini hem (a+b)*c hem de a +(b*c) şeklinde ayrıştırabilir.

Backus-Naur Formu (BNF) ayrıştırma ağaçlarının tanımlanmasında yaygın biçimde kullanılır. BNF’de üretim kuralları genellikle şu biçimde yazılır:

Örnek: 4 + 8 * (2 - 3) ifadesinin ayrıştırma ağacı;

Ayrıştırma ağacının inşası, biçimsel dil kuramının temel işlemlerinden biridir. Özellikle tam parantezlenmiş (fully parenthesized) matematiksel ifadelerin ayrıştırılması, kuramsal anlatımı somut bir uygulamaya dönüştürür. Bir ifade ayrıştırılırken her sembol bir token olarak ele alınır ve ayrıştırma işlemi bu token dizisi üzerinde adım adım yürütülür.

Ayrıştırma ağacının inşası için dört temel kural tanımlanır:

1. Sol Parantez ((): Yeni bir alt ifade başlatıldığı anlamına gelir. Bu durumda mevcut düğümün sol çocuğu olarak yeni bir düğüm eklenir ve algoritma bu yeni düğüme iner.
2. Operatör (+, -, *, / gibi): Mevcut düğüme bu operatör atanır. Ardından mevcut düğümün sağ çocuğu olarak yeni bir düğüm açılır ve algoritma sağ alt düğüme iner.
3. Operand (sayı): Bu durumda mevcut düğüme sayısal değer atanır. Daha sonra bir üst düğüme geri dönülür.
4. Sağ Parantez ()): Alt ifade tamamlanmıştır; algoritma bir üst düğüme çıkarak bir üst düzeye geri döner.

Bu işlem zincirleme biçimde devam eder ve ayrıştırma tamamlanana dek ağaç dallanır. Ebeveyn-düğüm ilişkilerini kaybetmemek için yığın (stack) kullanımı zorunludur. Her alt düğüme inişte mevcut düğüm yığına eklenir; üst düğüme dönüşte yığından çekilir.

Uygulama Örneği:

( 3 + ( 4 * 5 ) ) ifadesi için:

• ( 3 + ( 4 * 5 ) ) ifadesi ['(', '3', '+', '(', '4', '*', '5', ')', ')'] biçiminde tokenlara ayrılır.
• İlk '(' ile kök düğüm oluşturulur.
• '3' sayısı eklenir.
• '+' operatörü yerleştirilir.
• Yeni '(' ile alt ifade başlatılır.
• '4' eklenir, '*' operatörü atanır, '5' eklenir.
• Kapanan ')' ile üst düğüme çıkılır.
• Son ')' ile tüm yapı tamamlanır.

Bu işlem sonunda tam bir ayrıştırma ağacı oluşur. Her dal, parantezli alt ifadeye karşılık gelir.

Ayrıştırma ağacının inşa edilmesi yalnızca dizgeyi yapısal olarak çözümlemeyi değil, aynı zamanda ifadenin sayısal değerinin hesaplanmasını da mümkün kılar. Bu bağlamda, ayrıştırma ağacının değerlendirilmesi (evaluation) bir tür ağaç tabanlı hesaplama algoritmasıdır.

Değerlendirme algoritması özyinelemeli (recursive) bir yapıdadır:

• Temel Durum (Base Case): Eğer düğüm bir yaprak (operand) ise, doğrudan değeri döndürülür.
• Özyinelemeli Durum: Eğer düğüm bir operatör içeriyorsa, sol ve sağ çocuk düğümler üzerinde özyinelemeli olarak değerlendirme yapılır. Ardından düğümdeki operatör, alt düğümlerden dönen değerler üzerine uygulanır.

Örneğin (3 + (4 * 5)) için:

1. 4 * 5 = 20 hesaplanır.
2. 3 + 20 = 23 elde edilir.

Bu yöntem, karmaşık ifadelerde bile doğru işlem sırasını otomatik olarak korur; çünkü ayrıştırma ağacı zaten işlemlerin öncelik ilişkisini yapısal olarak saklamaktadır.

LL(1) ayrıştırıcı, top-down parsing yöntemidir.

• İlk L (Left-to-right): Girdiyi soldan sağa okur.
• İkinci L (Leftmost derivation): Sol-öncelikli türetim uygular.
• (1): Bir karakter ileri bakış (lookahead) yeterlidir.

LL(1) gramerlerinde, her adımda uygulanacak üretim kuralı yalnızca sıradaki karaktere bakılarak belirlenebilir. Bu özellik, insan tarafından kolayca anlaşılır gramerlerin tasarımını mümkün kılar. G2 grameri örneğinde olduğu gibi, aritmetik işlemlerde işlem önceliği açıkça belirlenir ve belirsizlik ortadan kaldırılır.

LR(1) ayrıştırıcı, bottom-up parsing yöntemidir.

• İlk L (Left-to-right): Girdiyi soldan sağa okur.
• R (Rightmost derivation): Sağ-öncelikli türetim adımlarını ters sırayla çıkarır.
• (1): Bir karakter ileri bakış yeterlidir.

LR(1) gramerleri, LL(1) gramerlerine göre daha karmaşık dil yapılarını tanımlayabilir. G3 gramerinde olduğu gibi, bazı dil yapılarında hangi kuralın seçileceğine karar vermek için yalnızca sembolün yerini değil, işlem önceliklerini de göz önünde bulundurmak gerekir. Bu nedenle LR(1) ayrıştırıcılar, shift/reduce algoritmasını kullanarak girişte ilerler ve hangi üretim kuralının uygulanacağını belirler.

Örneğin (x + y) * z ifadesi LR(1) algoritmasında:

• Cursor başlangıçta en soldadır.
• Shift işlemiyle semboller biriktirilir.
• Reduce işlemiyle tanımlı alt kalıplar tanınarak daha üst düzey sembole dönüştürülür.
• Bu işlemler adım adım, sağ-öncelikli türetimin tersine yürütülür.