Syntaxový strom

Syntax , odvození nebo parse tree je termín z teoretické informatiky a lingvistiky . Popisuje hierarchickou reprezentaci rozdělení textu. Stromy syntaxe se používají jak jako pomůcka pro grafickou vizualizaci rozdělení , tak ve formě datové struktury k zobrazení tohoto rozdělení pro strojové zpracování, např. B. v překladači nebo překladači .

Různé termíny nejsou v literatuře používány jednotně. Formálně přesně definován je pouze strom odvození pojmu , který je založen na odvození pojmu . Další názvy různých druhů stromů lze poté v případě potřeby podrobněji technicky definovat, jak je popsáno níže.

Na rozdíl od počítačové vědy, ve které lze jazyky definovat také podle technických možností, nachází lingvistika při práci s přirozenými jazyky obtížnější předpoklady, zejména proto, že pořadí složek ve větě se může lišit.

úvod

Reprezentace derivačního stromu

Při (mechanické) analýze vět v přirozeném jazyce nebo formálních textů (např. Počítačových programů) následuje po lexikální analýze (rozdělení na tokeny nebo symboly ) hierarchické shrnutí symbolů do souvisejících částí vět ( složek ) nebo sekcí místo toho formálního textu. Naopak to lze chápat také jako disekci textu. Výsledkem je strom, jako je ten, který je zobrazen vpravo. Kromě grafické podoby se pro syntaxové stromy používají také závorky:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]]}}$

Technicky se strom vlevo také nazývá strom odvození betonu , protože ukazuje výslednou strukturu přesně pomocí konkrétního textu. V lingvistice jsou však také běžné modely, které poskytují několik vrstev reprezentace (např. Povrchová a hloubková struktura ).

Uzly stromu jsou často obohaceny o atributy (v lingvistice se jedná hlavně o morfologické kategorie ). Tím získáte přidělený syntaxový strom s přidruženou přiřazenou gramatikou . Zatímco v prvních dvou stromových reprezentacích se používá bezkontextová gramatika, v druhé se hraje kontextová závislost . Tyto rozdíly se odrážejí v Chomského hierarchii . V takových případech se při konstrukci překladače používá termín sémantická analýza .

Odvozovací stromy

Zvažte bezkontextovou gramatiku . Derivačním stromem je strom, jehož uzly jsou označeny symboly z (tj. Terminální a neterminální symboly a prázdné slovo ). Strom je uspořádán , tj. H. děti každého uzlu mají pevné pořadí a pro označování platí následující: ${\ displaystyle G = \ left (N, \ Sigma, P, S \ right)}$${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• Kořen je označen symbolem startu . Tato vlastnost se někdy nevyžaduje. Strom, který je uspokojuje, se nazývá úplný derivační strom .${\ displaystyle S}$
• Pokud jsou podřízené prvky vnitřního uzlu označeného pomocí označeny symboly (v tomto pořadí), musí gramatika obsahovat pravidlo .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ až z_ {1} \ ldots z_ {m}}$
• Mezi listy stromu jsou označeny symboly .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Pokud je list označen, je jediným nástupcem jeho předchůdce.${\ displaystyle \ varepsilon}$

Jako vnitřní uzly lze použít pouze jiné než koncové symboly a pouze koncové symboly nebo prázdné slovo pro listy.

Konstrukce odvozovacích stromů

Možné syntaxové stromy / diagramy lze často snadno vytvořit pro krátké texty podle výrobních pravidel. Pro delší texty je k dispozici mnoho mechanických metod .

Například syntaxový diagram zobrazený v úvodu zahrnuje mimo jiné. jsou založeny na následujících pravidlech:

${\ displaystyle {\ begin {array} {lll} S & \ rightarrow & NP \ VP \\ NP & \ rightarrow & {\ mathtt {John}} \\ NP & \ 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 {ball}} \ end {pole}}}$

Aby bylo možné vygenerovat derivační strom, lze pravidla aplikovat krok za krokem od kořene systematickým nahrazováním jednoho neterminálu na levé straně pravidla symboly na pravé straně, dokud nezůstanou pouze terminály:

${\ 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 \ míč}}}$

S každým z kroků nakreslíte část stromu syntaxe shora dolů. Pravidla však můžete použít i opačně, začít psanou větou a potom postupně budovat strom zdola nahoru.

Odvozovací stromy pro jednoznačné a nejednoznačné gramatiky

Pokud existuje více než jeden odvozovací strom pro slovo v jazyce gramatiky, hovoří se o nejednoznačné gramatice , jinak o jednoznačné. Například následující gramatika je nejednoznačná

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

protože „aa a“ lze rozdělit na dva různé způsoby: „[aa] a“ a „a [aa]“. Následující gramatiku však umožňuje pouze jedna možná klasifikace

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

V případě nejednoznačných gramatik může počet možných derivačních stromů pro jedno a stejné slovo prudce vzrůst s délkou slova. V tomto případě derivační stromy již nejsou vhodnou reprezentací pro souhrn možných derivací. V případě formálních jazyků je konkrétní (povrchová) gramatika obvykle formulována jednoznačně. Na druhou stranu abstraktní gramatiky jsou často nejednoznačné, přičemž jedinečnost abstraktního derivačního stromu pak v průběhu analýzy vychází z konkrétního.

Abstraktní syntaxové stromy

Pro reprezentaci syntaxových stromů jako datové struktury v počítači se nyní poměrně jednotně používá označení abstraktní syntaxový strom (AST). B. také abstraktních odvozovacích stromů , operátorských stromů apod. lze mluvit. Přesné spojení mezi abstraktním stromem syntaxe a stromem konkrétních derivací je uvedeno v literatuře, např. Indikováno T. Kromě zhrubnutí derivačního stromu jsou však do struktury zahrnuty také požadavky na další zpracování, takže přímá formální derivace z povrchové gramatiky je ve výsledku obvykle neuspokojivá.

Bezkontextová povrchová gramatika je pak na rozdíl od abstraktní gramatiky , která je v užším smyslu většinou algebraickým datovým typem . Stromy syntaxe jsou pak technicky reprezentovány jako univerzální výrazy . Analýza je v přechodu mezi gramatickými a algebraicko-logickými výrazy, takže zde lze plynule hovořit o neterminálech a typech nebo stromech a výrazech.

příklad

Konkrétní (vlevo) a abstraktní (vpravo) strom syntaxe výrazu ${\ displaystyle a \ times (b + 3)}$

Ilustrační obrázek ukazuje konkrétní a abstraktní stromy syntaxe pro následující gramatiky.

E :: E "+" T - výraz
  :: T
T :: T "*" F termín
  :: F.
F :: V - faktor
  :: N
  :: "(" E ")"
V - proměnná
N - číslo

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

typ E = přidat (E, E);
        mul (E, E);
        var (V);
        číslo (N)

Konkrétní gramatika v tomto příkladu musí regulovat pořadí, ve kterém jsou operátory aplikovány na (částečné) výrazy - tj. Tečka před pomlčkou a částečné výrazy stejné priority mají být seskupeny zleva doprava. Možnost vytvoření jiného souhrnu nabízí také výrazy v závorkách. Spolu s určitými terminály (zde "(", ")", "+", "*") se jedná pouze o vlastnosti syntaktického povrchu, které již nehrají roli při pozdější analýze a dalším zpracování. Zejména lze zcela upustit od rozlišení mezi různými typy výrazů (zde E, T a F) a klíčovými slovy, jak je patrné z abstraktního stromu syntaxe, který je také mnohem blíže „obsahu“ výraz. Navíc díky těmto povrchovým detailům se stromy odvozené z betonu nejen rychle stávají matoucími, ale díky svým detailům také zabírají více úložného prostoru, než je nutné, jako datová struktura v počítači. To se také odráží v běhu a složitosti programů, které mají později zpracovat odvozovací strom. Z technických důvodů proto rozdělení zdrojového textu obvykle nepředstavuje konkrétní odvozovací strom.

Reprezentace abstraktních syntaxových stromů

Kromě grafického znázornění jako (operátorského) stromu uvedeného v příkladu jsou abstraktní syntaxe také technicky označovány jako termíny , např. B.: mul(var('a'), add(var('b'), num(3))).

Abstraktní gramatika

Zatímco abstraktní syntaxové stromy jsou datové struktury a algebraické typy v nich přebírají roli gramatiky, v literatuře, zejména v souvislosti s kalkulem, je často uvedena pouze hrubá nejednoznačná gramatika, která, jak ukazuje výše uvedený příklad, má stejnou strukturu jako výrazy, ale přesto obsahují klíčová slova. Tato forma umožňuje příjemné psaní abstraktních stromů syntaxe, které je často velmi blízké skutečnému zdroji. V úvodu je obvykle zdůrazněno, že pro disambiguaci lze použít závorky. Strom abstraktní syntaxe pro výše uvedený příklad by byl ve skutečnosti a * (b + 3)zapsán jako. V kontextu této literatury se však vždy zaměřuje na daný termín, jak již bylo zmíněno, hranice mezi gramatikou a algebrou se stírá hraním s formou.

Typickým příkladem jsou výrazy v lambda kalkulu , jehož abstraktní gramatika je často zapsána pouze jako. Stejná technika se používá i pro rozsáhlé gramatiky. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

literatura

• Ingo Wegener : Teoretická informatika . Úvod orientovaný na algoritmus. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Příklady bezkontextových jazyků a syntaxových stromů, str. 147-148 . 
• Uwe Schöning : Teoretická informatika - v kostce . 5. vydání. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Syntax trees, str. 15-17 . 
• Juraj Hromkovič : Teoretická informatika . Formální jazyky, předvídatelnost, teorie složitosti, algoritmy, komunikace a kryptografie. 3. vydání. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Bezkontextové gramatiky a tlačítkové automaty, str. 378 . 
• Hans Zima: Compiler I . Analýza. Bibliographisches Institut, Mannheim / Vienna / Zurich 1982, ISBN 3-411-01644-2 , 4.3 Abstraktní stromy a jejich přiřazení, str. 216-229 . 
• Stefan Müller : Gramatická teorie. Od transformační gramatiky po přístupy založené na omezeních. 2. vydání. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , kap. 2 ( langsci-press.org ). 

Individuální důkazy

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