Öznitelik dilbilgisi - Attribute grammar

Bir özellik grameri bir ek resmi bir yoldur biçimsel dilbilgisi anlamsal bilgi işleme ile. Semantik bilgi, dilbilgisinin terminal ve terminal olmayan sembolleriyle ilişkili niteliklerde depolanır . Niteliklerin değerleri, dilbilgisinin üretimleriyle ilişkili nitelik değerlendirme kurallarının sonucudur. Nitelikler, soyut sözdizimi ağacındaki herhangi bir yerden başka herhangi bir yere kontrollü ve resmi bir şekilde bilgi aktarımına izin verir .

Her semantik fonksiyon, sadece bir üretim kuralında meydana gelen sembollerin nitelikleriyle ilgilenir: hem semantik fonksiyon parametreleri hem de sonucu, belirli bir kuraldan gelen sembollerin nitelikleridir. Anlamsal bir işlev, kuralın sol tarafındaki sembolün bir özniteliğinin değerini tanımladığında, öznitelik sentezlenmiş olarak adlandırılır ; aksi halde kalıtsal olarak adlandırılır . Böylece, sentezlenen nitelikler, anlamsal bilgiyi ayrıştırma ağacından yukarı iletmeye hizmet ederken, miras alınan nitelikler, değerlerin ana düğümlerden aşağı ve sözdizimi ağacından geçirilmesine izin verir.

Aritmetik ifadelerin değerlendirilmesi gibi basit uygulamalarda, öznitelik dilbilgisi, doğrudan ayrıştırmanın yanı sıra gerçekleştirilecek tüm görevi tanımlamak için kullanılabilir; karmaşık sistemlerde, örneğin, bir derleyici gibi bir dil çeviri aracı oluştururken, sözdizimi tanımı tarafından açıkça verilmeyen bir dilin kurallarını temsil eden bir dilbilgisi ile ilişkili anlamsal kontrolleri doğrulamak için kullanılabilir. Ayrıştırıcılar veya derleyiciler tarafından sözdizimi ağacını doğrudan belirli bir makinenin koduna veya bazı ara dillere çevirmek için de kullanılabilir .

Tarih

Nitelik gramerleri Donald Knuth ve Peter Wegner tarafından icat edildi . Donald Knuth genel konsept için kredilendirilirken, Peter Wegner, Knuth ile bir konuşma sırasında miras alınan özellikleri icat etti. Bazı embriyonik fikirler, IMP'nin yazarı Edgar T. "Ned" Irons'ın çalışmasına kadar uzanır .

Örnek

Aşağıdaki, tamsayıların çarpması ve eklenmesinden oluşan bir dili tanımlayabilen, bağlamdan bağımsız basit bir dilbilgisidir .

 Expr → Expr + Term
 Expr → Term
 Term → Term * Factor
 Term → Factor
 Factor → "(" Expr ")"
 Factor → integer

Aşağıdaki öznitelik dilbilgisi, dilbilgisinde yazılmış bir ifadenin sonucunu hesaplamak için kullanılabilir. Bu dilbilgisinin yalnızca sentezlenmiş değerleri kullandığını ve bu nedenle S'ye atfedilen bir dilbilgisi olduğunu unutmayın .

 Expr1 → Expr2 + Term [ Expr1.value = Expr2.value + Term.value ]
 Expr → Term [ Expr.value = Term.value ]
 Term1 → Term2 * Factor [ Term1.value = Term2.value * Factor.value ]
 Term → Factor [ Term.value = Factor.value ]
 Factor → "(" Expr ")" [ Factor.value =  Expr.value ]
 Factor → integer [ Factor.value = strToInt(integer.str) ]

Sentezlenen nitelikler

Sentezlenmiş bir nitelik, çocukların niteliklerinin değerlerinden hesaplanır. Önce çocukların değerlerinin hesaplanması gerektiğinden, bu aşağıdan yukarıya yayılmaya bir örnektir. Sentezlenmiş bir niteliği resmi olarak tanımlamak için, resmi bir dilbilgisi olsun, burada ${\displaystyle G=\langle V_{n},V_{t},P,S\rangle }$

• ${\görüntüleme stili V_{n}}$ terminal olmayan semboller kümesidir
• ${\görüntüleme stili V_{t}}$ terminal sembolleri kümesidir
• ${\görüntüleme stili P}$üretimler kümesidir
• ${\görüntüleme stili S}$ seçkin veya başlangıç ​​sembolüdür

Daha sonra, terminal olmayan sembollerin bir dize verilen ve özellik adında , bu koşullardan üçü yerine getirilmesi halinde sentezlenmiş niteliktir: ${\görüntüleme stili A}$${\görüntüleme stili bir}$${\görüntüleme stili Aa}$

• ${\displaystyle A\rightarrow \alpha \in P}$(yani gramerdeki kurallardan biridir)${\displaystyle A\sağ ok \alfa }$
• ${\displaystyle \alpha =\alpha _{1}\ldots \alpha _{n},\forall i,1\leq i\leq n:\alpha _{i}\in (V_{n}\cup V_{ T})}$ (yani, kuralın gövdesindeki her sembol, ya terminal değildir ya da terminaldir)
• ${\displaystyle Aa=f(\alpha _{j_{1}}.a_{1},\ldots ,\alpha _{j_{m}}.a_{m})}$, burada (yani özniteliğin değeri , kuralın gövdesindeki sembollerden bazı değerlere uygulanan bir fonksiyondur )${\displaystyle \{\alpha _{j_{1}},\ldots ,\alpha _{j_{m}}\}\subseteq \{\alpha _{1},\ldots ,\alpha _{n}\ }}$${\görüntüleme stili f}$

devralınan özellikler

Bir kalıtsal özellik ayrıştırma ağacındaki bir düğüm ana veya kardeş de nitelik değerleri kullanılarak tanımlanır. Devralınan öznitelikler, bir programlama dili yapısının göründüğü bağlama bağımlılığını ifade etmek için uygundur. Örneğin, adresin veya tanımlayıcının değerinin gerekli olup olmadığına karar vermek için bir tanımlayıcının atamanın solunda mı yoksa sağında mı göründüğünü takip etmek için devralınan bir özniteliği kullanabiliriz. Sentezlenen özniteliklerin aksine, miras alınan öznitelikler ebeveynden ve/veya kardeşlerden değerler alabilir. Aşağıdaki üretimde olduğu gibi,

S → ABC

burada A, S, B ve C'den değerler alabilir. B, S, A ve C'den değerler alabilir. Aynı şekilde, C de S, A ve B'den değerler alabilir.

Özel nitelik dilbilgisi türleri

• L'ye atfedilen dilbilgisi : devralınan nitelikler , soyut sözdizimi ağacının bir soldan sağa geçişinde değerlendirilebilir
• LR ile ilişkilendirilen dilbilgisi : devralınan öznitelikleri aşağıdan yukarıya ayrıştırmada da değerlendirilebilen L ile ilişkilendirilen bir dilbilgisi .
• ECLR'ye atfedilen dilbilgisi : kalıtsal niteliklerin değerlendirmesini optimize etmek için eşdeğerlik sınıflarının kullanılabileceği, LR'ye atfedilen dilbilgilerinin bir alt kümesi.
• S-attributed dilbilgisi : yalnızca sentezlenmiş nitelikleri kullanan , ancak kalıtsal nitelikler içermeyen basit bir nitelik dilbilgisi türü

Ayrıca bakınız

• dilbilgisi ekle
• Van Wijngaarden dilbilgisi
• Sözdizimine yönelik çeviri

Referanslar

Dış bağlantılar

• Özellik Gramerleri Matter Neden , Monad Okuyucu, Sayı 4, 5 Temmuz nitelik gramerlerinin biçimciliği getiriyor nasıl 2005. (Bu makale anlatıyor boy odaklı programlama için işlevsel programlama yazma yardım ederek catamorphisms düzensel . Bu ifade eder Utrecht Üniversitesi Özellik Dilbilgisi system (ayrıca bkz. Lrc: A Purely Functional, High-Sıradan Nitelikli Dilbilgisi tabanlı Sistem ) örneklerde kullanılan uygulama olarak.)
• Haskell ve işlevsel programlama ile ilgili olarak nitelik dilbilgisi .
• Atfedilen gramerleri tanıtan orijinal makale: Knuth, Donald E. (1968). "Bağlamdan bağımsız dillerin anlamı" (PDF) . Matematiksel Sistemler Teorisi . 2 (2): 127–145. doi : 10.1007/BF01692511 . S2CID  5182310 .
• Jukka Paakki: Nitelikli gramer paradigmaları—dil uygulamasında üst düzey bir metodoloji . ACM Bilgi İşlem Anketleri 27 :2 (Haziran 1995), 196–255.
• Silver , Minnesota Üniversitesi'nden genişletilebilir bir öznitelik dilbilgisi belirtim dili ve sistemidir. (Ayrıca GitHub deposuna bakın .)