--- title: Ayrıştırma Ağacı slug: ayristirma-agaci-03365 url: /detay/ayristirma-agaci-03365 type: article language: Türkçe entity: primary: Ayrıştırma Ağacı type: article disambiguation: Ayrıştırma Ağacı: Biçimsel dil kuramında, dizgelerin üretim kurallarına göre hiyerarşik gösterimi. Bilgisayar bilimlerinde kullanılır. categories: - name: Bilişim Ve İletişim Teknolojileri slug: bilisim-ve-iletisim-teknolojileri url: /kategori/bilisim-ve-iletisim-teknolojileri - name: Yazılım Ve Yapay Zekâ slug: yazilim-ve-yapay-zeka url: /kategori/yazilim-ve-yapay-zeka tags: - LL(1) ve LR(1) Ayrıştırıcılar - Gramer Belirsizliği - Türetim Türleri - Biçimsel Dil Kuramı - Ayrıştırma Ağacı author: Beyza Nur Türkü created_at: 2025-07-08T00:47:22.157843+03:00 updated_at: 2025-07-21T21:56:12.169515+03:00 image: https://cdn.t3pedia.org/media/uploads/2025/07/07/eHaUJZUKVhlPI2MoitpYfNQ6BGYNs3Wx.png --- # Ayrıştırma Ağacı ## Article Content **Ayrıştırma ağacı (*parse tree*)**, [biçimsel dil kuramının](/tr/detay/formal-diller-ve-otomata-teorisi-67ebc/llms.txt) temel kavramlarından biri olup bir dilin üretim kurallarına ([gramer](/tr/detay/dil-bilimi/llms.txt)) 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. ### **Biçimsel Dil Teorisi Bağlamında Ayrıştırma Ağacı** 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ının Yapısı** 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](/tr/detay/ibare-sozluk/llms.txt) 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ç](/tr/detay/ucgen-f9564/llms.txt) dallanır. ![Image](https://cdn.kureansiklopedi.com/media/uploads/2025/07/07/tNwvZQ7I5JpFT1zICH1Qgzsp1Y165LOw.png) *Ayrıştırma ağacı yapısı örneği (Yapay zeka ile oluşturulmuştur.)* ### **Türetim Türleri: Sol-Öncelikli ve Sağ-Öncelikli** Bir ayrıştırma ağacı, birden fazla farklı türetimden doğabilir. [Türetim](/tr/detay/derivasyon-9af02/llms.txt) 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 *belirsiz*dir. ### **Belirsizlik (Ambiguity)** 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. ### **Ayrıştırma Ağaçları ve BNF Gösterimi** 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şası: Algoritma** [Ayrıştırma ağacının](/tr/detay/decision-trees-3a4bc/llms.txt) inşası, biçimsel dil kuramının temel işlemlerinden biridir. Özellikle tam [parantezlenmiş](/tr/detay/parantez-6b778/llms.txt) (*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ı Değerlendirme** 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](/tr/detay/algoritma-6/llms.txt). 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) ve LR(1) Ayrıştırıcılar** #### **LL(1) Ayrıştırıcı** 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ı** [LR(1) ayrıştırıcı](/tr/detay/formal-languages-and-automata-theory-80010/llms.txt), *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](/tr/detay/dil-bilgisi/llms.txt), 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. ## Academic Sources and References 1. Critchlow, Carol ve Eck, David J. "Parsing and Parse Trees". Engineering LibreTexts. Erişim Tarihi: 8 Temmuz 2025. Erişim Adresi. 2. Runestone Academy. "Parse Tree". Erişim Tarihi: 8 Temmuz 2025. Erişim Adresi. 3. Stanford InfoLab. "Parse Trees". Erişim Tarihi: 8 Temmuz 2025. Erişim Adresi. 4. The University of North Carolina at Chapel Hill. "Parse Trees". Erişim Tarihi: 8 Temmuz 2025. Erişim Adresi. 5. Şeker, Şadi Evren. "Parçalama Ağacı (Parse Tree)". 2008. Erişim Tarihi: 8 Temmuz 2025. Erişim Adresi.