Soyut sözdizimi ağacı - Abstract syntax tree

Dilbilimde kullanılan ağaçlar için bkz. Somut sözdizimi ağacı.
Aşağıdaki kod için soyut sözdizimi ağacı Öklid algoritması:
süre b ≠ 0
  Eğer a> b
    a: = a - b
  Başka
    b: = b - a
dönüş a

İçinde bilgisayar Bilimi, bir soyut sözdizimi ağacı (AST), ya da sadece sözdizimi ağacı, bir ağaç Temsili soyut sözdizimsel yapısı kaynak kodu bir Programlama dili. Ağacın her düğümü, kaynak kodda meydana gelen bir yapıyı belirtir.

Sözdizimi, gerçek sözdiziminde görünen her ayrıntıyı değil, sadece yapısal veya içerikle ilgili ayrıntıları temsil etmesi anlamında "soyut" dur. Örneğin gruplama parantez ağaç yapısında örtüktür, bu nedenle bunların ayrı düğümler olarak temsil edilmesi gerekmez. Benzer şekilde, bir if-koşulu-o zaman ifadesi gibi bir sözdizimsel yapı, üç dallı tek bir düğüm aracılığıyla gösterilebilir.

Bu, soyut sözdizimi ağaçlarını geleneksel olarak belirlenen somut sözdizimi ağaçlarından ayırır. ağaçları ayrıştırmak. Ayrıştırma ağaçları tipik olarak bir ayrıştırıcı kaynak kod çevirisi sırasında ve derleme süreç. Oluşturulduktan sonra, sonraki işlemler aracılığıyla AST'ye ek bilgiler eklenir, örn. bağlamsal analiz.

Soyut sözdizimi ağaçları da kullanılır program analizi ve program dönüşümü sistemleri.

Derleyicilerde uygulama

Soyut sözdizimi ağaçları veri yapıları yaygın olarak kullanılan derleyiciler program kodunun yapısını temsil etmek. Bir AST genellikle sözdizimi analizi bir derleyicinin aşaması. Genellikle, derleyicinin gerektirdiği birkaç aşamada programın ara bir temsili olarak hizmet eder ve derleyicinin son çıktısı üzerinde güçlü bir etkiye sahiptir.

Motivasyon

Bir AST, derleme işleminin sonraki adımlarına yardımcı olan birkaç özelliğe sahiptir:

  • Bir AST, içerdiği her öğe için özellikler ve ek açıklamalar gibi bilgilerle düzenlenebilir ve geliştirilebilir. Bu tür bir düzenleme ve açıklama, bir programın kaynak kodu ile imkansızdır, çünkü değiştirmeyi gerektirecektir.
  • Kıyasladığımızda kaynak kodu AST, gereksiz noktalama işaretlerini ve sınırlayıcıları (kaşlı ayraçlar, noktalı virgüller, parantezler vb.) içermez.
  • Bir AST, derleyicinin birbirini izleyen analiz aşamalarından dolayı genellikle program hakkında ek bilgi içerir. Örneğin, kaynak kodda her bir öğenin konumunu saklayarak derleyicinin yararlı hata mesajları yazdırmasına izin verebilir.

Programlama dillerinin doğası ve dokümantasyonu nedeniyle AST'lere ihtiyaç vardır. Diller genellikle doğası gereği belirsizdir. Bu belirsizliği önlemek için, programlama dilleri genellikle bir bağlamdan bağımsız gramer (CFG). Bununla birlikte, programlama dillerinin genellikle bir CFG'nin ifade edemediği, ancak dilin bir parçası olan ve belirtiminde belgelenen yönleri vardır. Bunlar, geçerliliğini ve davranışını belirlemek için bir bağlam gerektiren ayrıntılardır. Örneğin, bir dil yeni türlerin bildirilmesine izin veriyorsa, bir CFG bu türlerin adlarını veya bunların nasıl kullanılacağını tahmin edemez. Bir dilin önceden tanımlanmış bir türü olsa bile, uygun kullanımı zorunlu kılmak genellikle bir miktar bağlam gerektirir. Başka bir örnek ördek yazarak, bir öğenin türü bağlama göre değişebilir. Operatör aşırı yükleme yine bağlama göre doğru kullanımın ve nihai işlevin belirlendiği başka bir durumdur. Java, '+' operatörünün dizelerin hem sayısal olarak eklenmesi hem de birleştirilmesi olduğu mükemmel bir örnek sağlar.

Başka olmasına rağmen veri yapıları Bir derleyicinin iç işleyişinde yer alan AST benzersiz bir işlevi yerine getirir. İlk aşamada, sözdizimi analizi sahne, bir derleyici bir ayrıştırma ağacı üretir. Bu ayrıştırma ağacı, sözdizimi yönlendirmeli çeviri yoluyla bir derleyicinin neredeyse tüm işlevlerini gerçekleştirmek için kullanılabilir. Bu yöntem daha verimli bir derleyiciye yol açsa da, yazılım mühendisliği programları yazma ve sürdürme ilkelerine aykırıdır.[kaynak belirtilmeli ]. AST'nin bir ayrıştırma ağacına göre sahip olduğu diğer bir avantaj, boyut, özellikle AST'nin daha küçük yüksekliği ve daha az sayıda eleman olmasıdır.

Tasarım

Bir AST'nin tasarımı genellikle bir derleyicinin tasarımı ve beklenen özellikleriyle yakından bağlantılıdır.

Temel gereksinimler şunları içerir:

  • Değişken türlerinin yanı sıra her bildirimin kaynak kodundaki konumu korunmalıdır.
  • Yürütülebilir ifadelerin sırası açıkça temsil edilmeli ve iyi tanımlanmalıdır.
  • İkili işlemlerin sol ve sağ bileşenleri depolanmalı ve doğru bir şekilde tanımlanmalıdır.
  • Tanımlayıcılar ve atanmış değerleri, atama ifadeleri için saklanmalıdır.

Bu gereksinimler, AST için veri yapısını tasarlamak için kullanılabilir.

Ekleme için iki terim gibi bazı işlemler her zaman iki öğe gerektirir. Bununla birlikte, bazı dil yapıları, programlardan programlara aktarılan bağımsız değişken listeleri gibi, keyfi olarak çok sayıda çocuk gerektirir. komut kabuğu. Sonuç olarak, böyle bir dilde yazılmış kodu temsil etmek için kullanılan bir AST, bilinmeyen sayıda çocuğun hızla eklenmesine izin verecek kadar esnek olmalıdır.

Derleyici doğrulamasını desteklemek için bir AST'yi kaynak kodu formuna ayırmak mümkün olmalıdır. Üretilen kaynak kodu, yeniden derleme sırasında orijinaline görünüş olarak yeterince benzemeli ve yürütmede aynı olmalıdır.

Kullanım

AST, yoğun olarak kullanılır. anlamsal analiz, derleyicinin program öğelerinin ve dilin doğru kullanımını kontrol ettiği yer. Derleyici ayrıca oluşturur sembol tabloları anlamsal analiz sırasında AST'ye dayanır. Ağacın tam geçişi, programın doğruluğunun doğrulanmasını sağlar.

Doğruluğu onayladıktan sonra, AST, kod üretimi için temel görevi görür. AST, bazen bir ara temsil (IR) oluşturmak için kullanılır, bazen bir ara dil, kod üretimi için.

Ayrıca bakınız

Referanslar

daha fazla okuma

  • Jones, Joel. "Soyut Sözdizimi Ağacı Uygulama Deyimleri" (PDF). Alıntı dergisi gerektirir | günlük = (Yardım) (çeşitli dil ailelerinde AST uygulamasına genel bakış)
  • Neamtiu, Iulian; Foster, Jeffrey S .; Hicks, Michael (17 Mayıs 2005). Soyut Sözdizimi Ağacı Eşleştirmesini Kullanarak Kaynak Kodu Evrimini Anlama. MSR'05. Saint Louis, Missouri: ACM. CiteSeerX  10.1.1.88.5815.
  • Baxter, Ira D .; Yahin, Andrew; Moura, Leonardo; Sant 'Anna, Marcelo; Bier, Lorraine (16-19 Kasım 1998). Soyut Sözdizimi Ağaçlarını Kullanarak Klon Algılama (PDF). ICSM'98 Tutanakları. Bethesda, Maryland: IEEE.
  • Fluri, Beat; Würsch, Michael; Pinzger, Martin; Gall, Harald C. "Damıtmayı Değiştirin: İnce Taneli Kaynak Kodu Değişikliği Çıkarma için Ağaç Farklılaştırma" (PDF). Alıntı dergisi gerektirir | günlük = (Yardım) (PDF'ye doğrudan bağlantı )
  • Würsch, Michael. Soyut Sözdizimi Ağacı tabanlı Kaynak Kodu Değişikliği Algılamasını İyileştirme (Diploma tezi).
  • Falleri, Jean-Rémy; Morandat, Floréal; Blanc, Xavier; Martinez, Matias; Monperrus, Martin. İnce Taneli ve Doğru Kaynak Kodu Farklılığı (PDF). ASE 2014 Tutanakları. doi:10.1145/2642937.2642982.
  • Lucas, Jason. "Görsel C ++ Soyut Sözdizimi Ağacı (AST) Üzerine Düşünceler".

Dış bağlantılar