Drzewo składni

Składnia , pochodzenie lub drzewo parse to termin z teoretycznej informatyki i lingwistyki . Opisuje hierarchiczną reprezentację podziału tekstu. Drzewa składniowe są wykorzystywane zarówno jako pomoc w graficznej wizualizacji awarii, jak i, w postaci struktury danych , do wyświetlania tego podziału w celu przetwarzania maszynowego, np. B. w kompilatorze lub tłumaczu .

W literaturze różne terminy nie są używane jednolicie. Jedynie drzewo derywacji terminu , które jest oparte na derywacji terminu , jest formalnie precyzyjnie zdefiniowane . Inne nazwy różnych typów drzew można następnie technicznie zdefiniować bardziej szczegółowo, jak opisano poniżej, jeśli to konieczne.

W przeciwieństwie do informatyki, w której języki można również definiować zgodnie z możliwościami technicznymi, językoznawstwo napotyka trudniejsze warunki wstępne, gdy ma do czynienia z językami naturalnymi , głównie dlatego, że kolejność składników w zdaniu może być różna.

wprowadzenie

Reprezentacja drzewa pochodnego

W (mechanicznej) analizie zdań w języku naturalnym lub tekstów formalnych (np. Programów komputerowych) po analizie leksykalnej (rozbiciu na tokeny lub symbole ) często następuje hierarchiczne podsumowanie symboli na powiązane części zdań ( składniki ) lub sekcje zamiast tekstu formalnego. I odwrotnie, można to również rozumieć jako analizę tekstu. Rezultatem jest drzewo takie jak pokazane po prawej stronie. Oprócz postaci graficznej w drzewach składni używane są również reprezentacje w nawiasach:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ piłka]]]].}$

Technicznie rzecz biorąc, drzewo po lewej stronie jest również nazywane drzewem konkretnej pochodnej , ponieważ pokazuje wynikową strukturę dokładnie przy użyciu konkretnego tekstu. Jednak w językoznawstwie modele są również powszechne, które zapewniają kilka warstw reprezentacji (np. Struktura powierzchni i głębokości ).

Często węzły drzewa są wzbogacane atrybutami (w językoznawstwie są to głównie kategorie morfologiczne ). W ten sposób otrzymasz drzewo składni z przypisanymi atrybutami wraz z przypisaną gramatyką . Podczas gdy gramatyka bezkontekstowa jest używana w pierwszych dwóch reprezentacjach drzewa , zależność od kontekstu wchodzi w grę w drugiej . Te różnice znajdują odzwierciedlenie w hierarchii Chomsky'ego . W takich przypadkach termin analiza semantyczna jest używany w konstrukcji kompilatora .

Drzewa pochodne

Rozważ gramatykę bezkontekstową . Wyprowadzenie drzewa na to drzewa , którego węzły są oznaczone symbolami z (to znaczy złącza i symbole dla terminala oraz pustą słowa ). Drzewo jest uporządkowane , tj. H. elementy podrzędne każdego węzła mają ustaloną kolejność, a do etykietowania stosuje się następujące zasady: ${\ Displaystyle G = \ lewo (N, \ Sigma, P, S \ prawej)}$${\ Displaystyle \ Sigma \ Puchar N \ Puchar \ {\ varepsilon \}}$

• Korzeń jest oznaczony symbolem startowym . Ta właściwość czasami nie jest wymagana. Drzewo, które je spełnia, nazywane jest drzewem pełnej pochodnej.${\ displaystyle S}$
• Jeśli elementy podrzędne węzła wewnętrznego oznaczone symbolem są oznaczone symbolami (w tej kolejności), gramatyka musi zawierać regułę .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m.}}$${\ displaystyle A \ do z_ {1} \ ldots z_ {m.}}$
• Na liście drzewa są oznaczone symbolami .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Jeśli liść jest oznaczony, jest jedynym następcą poprzedniego węzła.${\ displaystyle \ varepsilon}$

Tylko symbole nieterminalowe mogą być używane jako węzły wewnętrzne i tylko symbole terminali lub puste słowo dla liści.

Budowa drzew pochodnych

Możliwe drzewa / diagramy składniowe można często łatwo utworzyć dla krótkich tekstów, stosując się do reguł produkcji. W przypadku dłuższych tekstów dostępnych jest wiele metod mechanicznych .

Na przykład przedstawiony we wstępie diagram składniowy obejmuje między innymi. opierają się na następujących zasadach:

${\ Displaystyle {\ rozpocząć {tablicę} {lll} S & \ rightarrow i NP \ VP \\ NP & \ rightarrow & {\ mathtt {John}} \\ NP i \ rightarrow & Det \ N \\ VP & \ rightarrow & V \ NP \\\ end {array}} \ quad \ quad {\ begin {array} {lll} V & \ rightarrow & {\ mathtt {hit}} \\ Det & \ rightarrow & {\ mathtt {the} } \\ N & \ rightarrow & {\ mathtt {piłka}} \ end {tablica}}}$

Aby wygenerować drzewo derywacyjne, reguły można stosować krok po kroku od korzenia, systematycznie zastępując jeden nieterminal po lewej stronie reguły symbolami po prawej stronie, aż pozostaną tylko terminale:

${\ 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 \ piłka}}}$

Z każdym krokiem rysujesz fragment drzewa składni od góry do dołu. Ale możesz też zastosować zasady na odwrót i zacząć od zdania pisemnego, a następnie budować drzewo krok po kroku od dołu do góry.

Drzewa derywacyjne dla jednoznacznych i niejednoznacznych gramatyk

Jeśli w języku danej gramatyki istnieje więcej niż jedno drzewo derywacji, mówi się o gramatyce niejednoznacznej , w przeciwnym razie o gramatyce jednoznacznej. Na przykład poniższa gramatyka jest niejednoznaczna

${\ Displaystyle {\ rozpocząć {tablicę} {lll} S & \ rightarrow i S \ S \\ S & \ rightarrow & a \ koniec {tablica}}}$

ponieważ „aa a” można podzielić na dwa różne sposoby: „[aa] a” i „a [aa]”. Jednak tylko jedna możliwa klasyfikacja dopuszcza następującą gramatykę

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

W przypadku gramatyk niejednoznacznych liczba możliwych drzew pochodnych dla jednego i tego samego słowa może gwałtownie wzrosnąć wraz z długością słowa. W tym przypadku drzewa derywacji nie są już odpowiednią reprezentacją dla wszystkich możliwych wyprowadzeń. W przypadku języków formalnych gramatyka konkretna (powierzchniowa) jest zwykle sformułowana jednoznacznie. Z drugiej strony, gramatyki abstrakcyjne są często niejednoznaczne, przez co wyjątkowość drzewa wyprowadzeń abstrakcyjnych wynika z konkretu w toku analizy.

Abstrakcyjne drzewa składniowe

Do reprezentacji drzew składniowych jako struktury danych w komputerze używane jest teraz dość jednolicie abstrakcyjne drzewo składni desygnacji (AST). B. również abstrakcyjnych drzew otrzymywania pochodnych , drzew operatora i tym podobnych. można rozmawiać. Dokładny związek między abstrakcyjnym drzewem składni a konkretnym drzewem pochodnym jest pokazany w literaturze, np. Wskazał T. Jednak oprócz zgrubnego przekształcenia drzewa derywacji, w strukturze zawarte są również wymagania dotyczące dalszego przetwarzania, tak że bezpośrednie formalne wyprowadzenie z gramatyki powierzchniowej jest zwykle niezadowalające.

Bezkontekstowa gramatyka powierzchniowa jest więc przeciwstawiana gramatyce abstrakcyjnej , która w węższym sensie jest głównie algebraicznym typem danych . Drzewa składniowe są następnie technicznie reprezentowane jako terminy uniwersalne . Analiza polega na przejściu między terminami gramatycznymi i algebraiczno-logicznymi, tak że można tu płynnie mówić o nieterminalach i typach lub o drzewach i terminach.

przykład

Konkretne (po lewej) i abstrakcyjne (po prawej) drzewo składni wyrażenia ${\ Displaystyle a \ razy (b + 3)}$

Ilustracja obok przedstawia konkretne i abstrakcyjne drzewa składniowe dla następujących gramatyk.

E :: E "+" T - wyrażenie
  :: T
T :: T "*" Termin F.
  :: F.
F :: V - współczynnik
  :: N
  :: "(" E ")"
V - zmienna
N - liczba

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

typ E = add (E, E);
        mul (E, E);
        var (V);
        num (N)

Gramatyka konkretna w tym przykładzie musi regulować kolejność, w jakiej operatory są stosowane do (częściowych) wyrażeń - to znaczy kropka przed myślnikiem i częściowe wyrażenia o tym samym priorytecie mają być grupowane od lewej do prawej. Możliwość stworzenia innego podsumowania jest również oferowana z wyrażeniami w nawiasach. Razem z określonymi końcówkami (tutaj „(”, „)”, „+”, „*”) są to tylko właściwości powierzchni syntaktycznej, które nie odgrywają już roli w późniejszej analizie i dalszym przetwarzaniu. W szczególności można całkowicie zrezygnować z rozróżnienia między różnymi typami wyrażeń (tutaj E, T i F) i słowami kluczowymi, jak widać z abstrakcyjnego drzewa składni, które jest również znacznie bliższe „treści” wyrażenia wyrażenie. Co więcej, ze względu na te szczegóły powierzchni, drzewa do pozyskiwania betonu nie tylko szybko stają się zagmatwane, ale także zajmują więcej miejsca w pamięci niż jest to konieczne jako struktura danych w komputerze ze względu na ich szczegóły. Znajduje to również odzwierciedlenie w czasie wykonywania i złożoności programów, które mają później przetwarzać drzewo pochodnych. Z przyczyn technicznych podział tekstu źródłowego zwykle nie jest zatem reprezentowany przez określone drzewo derywacji.

Reprezentacja abstrakcyjnych drzew składniowych

Oprócz graficznej reprezentacji w postaci drzewa (operatora) pokazanego w przykładzie, abstrakcyjne drzewa składniowe są również technicznie oznaczane jako terminy , np. B.: mul(var('a'), add(var('b'), num(3))).

Gramatyka abstrakcyjna

Podczas gdy abstrakcyjne drzewa składniowe są strukturami danych, a typy algebraiczne przejmują w nich rolę gramatyki, w literaturze, zwłaszcza w odniesieniu do rachunków, często podaje się tylko grubą, niejednoznaczną gramatykę, która, jak pokazano w powyższym przykładzie, ma ma taką samą strukturę jak terminy, ale nadal zawiera słowa kluczowe. Ta forma umożliwia przyjemne pisanie abstrakcyjnych drzew składniowych, które często są bardzo zbliżone do rzeczywistego źródła. Zwykle we wstępie zwraca się uwagę, że do ujednoznacznienia można użyć nawiasów. Abstrakcyjne drzewo składni dla powyższego przykładu byłoby wówczas a * (b + 3)zapisane jako. Jednak w kontekście tej literatury uwaga zawsze skupia się na pojęciu, jak wspomniano, granice między gramatyką a algebrą zacierają się poprzez grę formą.

Typowym przykładem są wyrażenia w rachunku lambda , którego gramatyka abstrakcyjna jest często zapisywana jako. Ta sama technika jest również używana do obszernych gramatyk. ${\ Displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

literatura

• Ingo Wegener : Informatyka teoretyczna . Wprowadzenie zorientowane na algorytm. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Przykłady języków bezkontekstowych i drzew składniowych, s. 147-148 . 
• Uwe Schöning : Informatyka teoretyczna - w pigułce . Wydanie 5. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Drzewa składniowe, s. 15-17 . 
• Juraj Hromkovič : Informatyka teoretyczna . Języki formalne, przewidywalność, teoria złożoności, algorytmy, komunikacja i kryptografia. Wydanie trzecie. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Gramatyki bezkontekstowe i automaty z przyciskami, s. 378 . 
• Hans Zima: Kompilator ja . Analiza. Bibliographisches Institut, Mannheim / Wiedeń / Zurych 1982, ISBN 3-411-01644-2 , 4.3 Abstrakcyjne drzewa i ich przypisanie, s. 216-229 . 
• Stefan Müller : Teoria gramatyczna. Od gramatyki transformacyjnej do podejść opartych na ograniczeniach. Wydanie 2. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , rozdz. 2 ( langsci-press.org ). 

Indywidualne dowody

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