Sözdizimi ağacı

Bir sözdizimi , türetme veya ayrıştırma ağacı gelen bir terimdir teorik bilgisayar bilimleri ve dilbilim . Bir metnin dağılımının hiyerarşik bir temsilini açıklar. Sözdizimi ağaçları, hem dökümün grafiksel görselleştirilmesi için bir yardımcı olarak hem de bir veri yapısı biçiminde, makine işleme için bu dökümü görüntülemek için kullanılır, örn. B. bir derleyici veya çeviricide .

Literatürde çeşitli terimler aynı şekilde kullanılmamaktadır. Sadece terim türetme ağaç vadeli dayanmaktadır türetme, bir resmi tam olarak tanımlanır . Farklı ağaç türleri için diğer isimler, gerekirse aşağıda açıklandığı gibi teknik olarak daha ayrıntılı olarak tanımlanabilir.

Dillerin teknik olanaklara göre de tanımlanabildiği bilgisayar biliminin aksine, dilbilim doğal dillerle uğraşırken daha zor önkoşullar bulur , çünkü bir cümledeki bileşenlerin sırası değişebilir.

Giriş

Türev ağacının temsili

Doğal dilde cümlelerin veya biçimsel metinlerin (örneğin, bilgisayar programları) (mekanik) analizinde , sözcüksel analizi ( simge veya sembollere ayırma ) genellikle simgelerin hiyerarşik bir özetini cümlelerin ilgili bölümlerine ( bileşenler ) veya bölümlere izler. bunun yerine resmi Metin. Tersine, bu aynı zamanda metnin bir incelemesi olarak da anlaşılabilir. Sonuç, sağda gösterilene benzer bir ağaçtır . Grafik forma ek olarak, sözdizimi ağaçları için köşeli parantezli gösterimler de kullanılır:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ top]]]].}$

Teknik olarak, soldaki ağaç , elde edilen yapıyı tam olarak somut metni kullanarak gösterdiği için somut bir türetme ağacı olarak da adlandırılır . Bununla birlikte, dilbilimde, birkaç temsil katmanı (örneğin yüzey ve derinlik yapısı ) sağlayan modeller de yaygındır .

Genellikle ağacın düğümleri niteliklerle zenginleştirilir (dilbilimde bunlar çoğunlukla morfolojik kategorilerdir ). Bu size atıfta bulunulan dilbilgisi ile ilişkilendirilmiş bir sözdizimi ağacı verir . İlk iki ağaç gösteriminde bağlamdan bağımsız bir gramer kullanılırken, ikincisinde bağlam bağımlılığı devreye girer . Bu farklılıklar Chomsky hiyerarşisine yansır . Bu gibi durumlarda, anlamsal analiz terimi derleyici yapısında kullanılır .

Derivasyon ağaçları

Bağlamdan bağımsız bir gramer düşünün . Bunun türetme ağacı , düğümleri sembollerle etiketlenen bir ağaçtır (yani terminal ve terminal olmayan semboller ve boş kelime ). Ağaç düzenlenmiştir , i. H. her düğümün alt öğelerinin sabit bir sırası vardır ve aşağıdaki etiketleme için geçerlidir: ${\ displaystyle G = \ sol (N, \ Sigma, P, S \ sağ)}$${\ displaystyle \ Sigma \ fincan N \ fincan \ {\ varepsilon \}}$

• Kök edilir etiketli başlangıç sembolüyle . Bu özellik bazen gerekli değildir. Onları tatmin eden bir ağaca tam bir türetme ağacı denir .${\ displaystyle S}$
• İle etiketlenmiş bir iç düğümün çocukları sembollerle (bu sırayla) etiketlenmişse , dilbilgisi kuralı içermelidir.${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ - z_ {1} \ ldots z_ {m}}$
• Yaprakları ağacın edilir etiketli sembollerle .${\ displaystyle \ Sigma \ fincan \ {\ varepsilon \}}$
• Bir yaprak ile işaretlenmişse, önceki düğümünün tek halefidir.${\ displaystyle \ varepsilon}$

Yalnızca terminal olmayan semboller iç düğümler olarak ve yalnızca terminal sembolleri veya yapraklar için boş kelime kullanılabilir.

Derivasyon ağaçlarının yapımı

Olası söz dizimi ağaçları / diyagramları, üretim kuralları izlenerek genellikle kısa metinler için kolayca oluşturulabilir. Daha uzun metinler için birçok mekanik yöntem mevcuttur.

Örneğin, girişte gösterilen sözdizimi diyagramı diğer şeylerin yanı sıra içerir. aşağıdaki kurallara dayanmaktadır:

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & NP \ VP \\ NP & \ rightarrow & {\ mathtt {John}} \\ NP & \ rightarrow & Det \ N \\ VP & \ rightarrow & V \ NP \\\ end {dizi}} \ quad \ quad {\ begin {dizi} {lll} V & \ rightarrow & {\ mathtt {hit}} \\ Det & \ rightarrow & {\ mathtt {the} } \\ N & \ rightarrow & {\ mathtt {top}} \ end {dizi}}}$

Bir türetme ağacı oluşturmak için, kuralın sol tarafındaki bir non-terminali sistematik olarak yalnızca terminaller kalana kadar sağ taraftaki sembollerle değiştirerek, kurallar kökten adım adım uygulanabilir:

${\ displaystyle S \ \ Rightarrow \ NP \ VP \ \ Rightarrow \ {\ mathtt {John}} \ VP \ \ Rightarrow \ {\ mathtt {John}} \ V \ NP \ \ Rightarrow \ {\ mathtt {John \ hit }} \ NP \ \ Rightarrow \ {\ mathtt {John \ hit}} \ Det \ N \ Rightarrow \ {\ mathtt {John \ hit \ the}} \ N \ Rightarrow \ {\ mathtt {John \ hit \ the \ ball}}}$

Her adımda, söz dizimi ağacının bir parçasını yukarıdan aşağıya doğru çizersiniz. Ancak kuralları tam tersi şekilde de uygulayabilir ve yazılı cümle ile başlayabilir ve ardından ağacı aşağıdan yukarıya doğru adım adım inşa edebilirsiniz.

Kesin ve belirsiz gramerler için türetme ağaçları

Bir dilbilgisi dilinde bir kelime için birden fazla türetme ağacı varsa, kişi belirsiz bir dilbilgisinden , aksi takdirde kesin olmayan bir dilbilgisinden söz eder. Örneğin, aşağıdaki dilbilgisi belirsizdir

${\ displaystyle {\ begin {dizi} {lll} S & \ rightarrow & S \ S \\ S & \ rightarrow & a \ end {dizi}}}$

çünkü "aa a" iki farklı yola bölünebilir: "[aa] a" ve "a [aa]". Bununla birlikte, yalnızca bir olası sınıflandırma aşağıdaki dilbilgisine izin verir

${\ displaystyle {\ begin {dizi} {lll} S & \ rightarrow & a \ S \\ S & \ rightarrow & a \ end {dizi}}}$

Belirsiz gramerler söz konusu olduğunda, bir ve aynı kelime için olası türetme ağaçlarının sayısı, kelimenin uzunluğu ile keskin bir şekilde artabilir. Bu durumda, türetme ağaçları artık olası türetmelerin toplamı için uygun bir temsil değildir. Biçimsel diller söz konusu olduğunda, somut (yüzey) dilbilgisi genellikle açık bir şekilde formüle edilir. Öte yandan, soyut gramerler genellikle belirsizdir, bu nedenle soyut türetme ağacının benzersizliği, analiz boyunca somuttan kaynaklanır.

Soyut sözdizimi ağaçları

Sözdizimi ağaçlarının bir bilgisayarda bir veri yapısı olarak temsili için, atama soyut sözdizimi ağacı (AST) artık oldukça düzgün bir şekilde kullanılmaktadır. B. ayrıca soyut türetme ağaçları , operatör ağaçları veya benzerleri. hakkında konuşulabilir. Literatürde soyut sözdizimi ağacı ile somut türetme ağacı arasındaki tam bir bağlantı gösterilmiştir. T. belirtti. Bununla birlikte, türetme ağacının kabalaşmasına ek olarak, daha fazla işlemeye yönelik gereksinimler de yapıya dahil edilir, böylece yüzey dilbilgisinden doğrudan bir biçimsel türetme genellikle sonuç olarak yetersiz kalır.

Bağlamdan bağımsız yüzey dilbilgisi , daha dar anlamda çoğunlukla cebirsel bir veri türü olan soyut bir dilbilgisine zıttır . Sözdizimi ağaçları daha sonra teknik olarak çok yönlü terimler olarak temsil edilir . Analiz, dilbilgisel ve cebirsel-mantıksal terimler arasındaki geçiş içindedir, böylece burada uçsuzlar ve türler veya ağaçlardan ve terimlerden akıcı bir şekilde bahsedilebilir.

misal

İfade için somut (sol) ve soyut (sağ) sözdizimi ağacı ${\ displaystyle a \ times (b + 3)}$

Yandaki resim, aşağıdaki gramerler için somut ve soyut sözdizimi ağaçlarını gösterir.

E :: E "+" T - ifade
  :: T
T :: T "*" F terimi
  :: F
F :: V - faktör
  :: N
  :: "(" E ")"
V - değişken
N - sayı

E :: E "+" E
  :: E "*" E
  :: V
  :: N

E yazın = ekle (E, E);
        mul (E, E);
        var (V);
        num (N)

Bu örnekteki somut dilbilgisi, operatörlerin (kısmi) ifadelere uygulanma sırasını düzenlemelidir - yani, tireden önce nokta ve aynı önceliğe sahip kısmi ifadeler soldan sağa gruplanmalıdır. Parantez içindeki ifadelerle farklı bir özet oluşturma imkanı da sunulmaktadır. Belirli terminallerle birlikte (burada "(", ")", "+", "*") bunlar yalnızca sözdizimsel yüzeyin daha sonraki analizlerde ve sonraki işlemlerde artık bir rol oynamayan özellikleridir. Özellikle, farklı ifade türleri (burada E, T ve F) ve anahtar kelimeler arasındaki ayrım, soyut sözdizimi ağacından da görülebileceği gibi tamamen ortadan kaldırılabilir, bu da aynı zamanda içeriğin "içeriğine" çok daha yakındır. ifade. Ayrıca bu yüzey detaylarından dolayı, beton türev ağaçları sadece hızlı bir şekilde kafa karıştırıcı hale gelmekle kalmaz, aynı zamanda detaylarından dolayı bilgisayarda bir veri yapısı olarak gerekenden daha fazla depolama alanı kaplar. Bu, daha sonra türetme ağacını işleyecek programların çalışma süresine ve karmaşıklığına da yansır. Teknik nedenlerden dolayı, bir kaynak metnin dökümü bu nedenle genellikle belirli bir türetme ağacı ile temsil edilmez.

Soyut sözdizimi ağaçlarının temsili

Örnekte gösterilen (operatör) ağaç olarak grafiksel gösterime ek olarak, soyut sözdizimi ağaçları da teknik olarak terimler olarak not edilir , ör. B.: mul(var('a'), add(var('b'), num(3))).

Soyut dilbilgisi

Soyut sözdizimi ağaçları veri yapıları iken ve cebirsel türler bunlarda dilbilgisinin rolünü üstlenirken, literatürde, özellikle kalkül ile bağlantılı olarak, genellikle yalnızca kaba, belirsiz bir dilbilgisi verilir; bu, yukarıdaki örnekte gösterildiği gibi, terimlerle aynı yapı, ancak yine de anahtar kelimeler içerir. Bu biçim, genellikle gerçek kaynağa çok yakın olan soyut sözdizimi ağaçlarının hoş bir şekilde yazılmasını sağlar. Genellikle girişte parantezlerin belirsizliği gidermek için kullanılabileceği belirtilir. Yukarıdaki örnek için soyut bir sözdizimi ağacı daha sonra aslında olarak a * (b + 3)yazılır. Ancak bu literatür bağlamında odak her zaman terim üzerinedir.Daha önce de belirtildiği gibi, dilbilgisi ve cebir arasındaki sınırlar biçimle oynanarak bulanıklaşır.

Tipik bir örnek olarak ifadelerdir lambda hesabı , soyut gramer genellikle sadece bir yazıya. Aynı teknik, kapsamlı gramerler için de kullanılır. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

Edebiyat

• Ingo Wegener : Teorik Bilgisayar Bilimi . Algoritma odaklı bir giriş. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Bağlamdan bağımsız dil örnekleri ve sözdizimi ağaçları, s. 147-148 . 
• Uwe Schöning : Teorik Bilgisayar Bilimi - kısaca . 5. baskı. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Sözdizimi ağaçları, s. 15-17 . 
• Juraj Hromkovič : Teorik Bilgisayar Bilimi . Biçimsel diller, öngörülebilirlik, karmaşıklık teorisi, algoritmalar, iletişim ve kriptografi. 3. Baskı. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Bağlamdan bağımsız gramerler ve basmalı düğme otomatları, s. 378 . 
• Hans Zima: Derleyici ben . Analiz. Bibliographisches Institut, Mannheim / Viyana / Zürih 1982, ISBN 3-411-01644-2 , 4.3 Soyut ağaçlar ve özellikleri, s. 216-229 . 
• Stefan Müller : Dilbilgisi Kuramı. Dönüşümsel gramerden kısıt tabanlı yaklaşımlara. 2. Baskı. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , böl. 2 ( langsci-press.org ). 

Bireysel kanıt

1. ↑ Müller (2018), s.59f.