Syntaxträd

En syntax , härledning eller parse-träd är en term från teoretisk datavetenskap och lingvistik . Den beskriver en hierarkisk representation av uppdelningen av en text. Syntaxträd används både som ett hjälpmedel för grafisk visualisering av uppdelningen och, i form av en datastruktur , för att visa denna uppdelning för maskinbearbetning, t.ex. B. i en kompilator eller översättare .

De olika termerna används inte enhetligt i litteraturen. Endast termen härledningsträd , som är baserad på termen härledning, definieras formellt exakt . Andra namn för olika typer av träd kan sedan definieras mer detaljerat, såsom beskrivs nedan, vid behov.

Till skillnad från datavetenskap, där språk också kan definieras utifrån de tekniska möjligheterna, har lingvistiken svårare förutsättningar när det gäller naturliga språk , främst för att komponenternas ordning i en mening kan variera.

introduktion

Representation av ett derivatsträd

I (mekanisk) analys av naturliga språkmeningar eller formella texter (t.ex. datorprogram) följs den lexiska analysen (uppdelningen i symboler eller symboler ) ofta av en hierarkisk sammanfattning av symbolerna i relaterade delar av meningar ( beståndsdelar ) eller sektioner av den formella texten istället. Omvänt kan detta också förstås som en dissektion av texten. Resultatet är ett träd som det som visas till höger. Förutom den grafiska formen används hakparenteser för syntaxträd:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]].}$

Tekniskt kallas trädet till vänster också ett betongavledningsträd , eftersom det visar den resulterande strukturen exakt med hjälp av betongtexten. Inom språkvetenskap är dock vanliga modeller också vanliga som ger flera lager av representation (t.ex. yta och djupstruktur ).

Ofta berikas trädets noder med attribut (inom lingvistik är detta huvudsakligen morfologiska kategorier ). Detta ger dig ett tillskrivet syntaxträd med tillhörande tillskriven grammatik . Medan en sammanhangsfri grammatik används i de två första trädrepresentationerna , spelas sammanhangsberoendet in i den senare . Dessa skillnader återspeglas i Chomsky-hierarkin . I sådana fall används termen semantisk analys i kompilatorkonstruktionen .

Derivationsträd

Tänk på en sammanhangsfri grammatik . Ett härledningsträd för detta är ett träd vars noder är märkta med symboler från (dvs. terminala och icke-terminala symboler och det tomma ordet ). Trädet beställs , dvs. H. barnen till varje nod har en fast ordning och följande gäller märkningen: ${\ displaystyle G = \ left (N, \ Sigma, P, S \ right)}$${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• Den rot är märkt med startsymbolen . Den här egenskapen krävs ibland inte. Ett träd som uppfyller dem kallas ett fullständigt härledningsträd.${\ displaystyle S}$
• Om barnen till en inre nod märkt med är märkta med symbolerna (i den ordningen) måste grammatiken innehålla regeln .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ till z_ {1} \ ldots z_ {m}}$
• De blad av trädet är märkta med symboler .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Om ett blad är markerat med är det den enda efterföljaren till dess föregångare.${\ displaystyle \ varepsilon}$

Endast icke-terminala symboler kan användas som inre noder, och endast terminalsymboler eller det tomma ordet för bladen.

Konstruktion av härledningsträd

Möjliga syntaxträd / diagram kan ofta enkelt skapas för korta texter genom att följa produktionsreglerna. Många mekaniska metoder finns för längre texter .

Till exempel inkluderar syntaxdiagrammet som visas i inledningen bland annat. baseras på följande regler:

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

För att generera ett derivatsträd kan reglerna tillämpas steg för steg från roten genom att systematiskt ersätta en icke-terminal på vänster sida av regeln med symbolerna på höger sida tills endast terminaler är kvar:

${\ 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 \ boll}}}$

Med vart och ett av stegen ritar du en bit av syntaxträdet från topp till botten. Men du kan också tillämpa reglerna tvärtom och börja med den skrivna meningen och sedan bygga upp trädet steg för steg från botten till toppen.

Derivationsträd för entydiga och tvetydiga grammatiker

Om det finns mer än ett derivatsträd för ett ord på språket för en grammatik, talar man om en tvetydig grammatik , annars om en entydig. Till exempel är följande grammatik tvetydig

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

eftersom "aa a" kan delas in på två olika sätt: "[aa] a" och "a [aa]". Men endast en möjlig klassificering tillåter följande grammatik

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

När det gäller tvetydiga grammatiker kan antalet möjliga härledningsträd för ett och samma ord öka kraftigt med ordets längd. I detta fall är härledningsträd inte längre en lämplig representation för de totala möjliga härledningarna. När det gäller formella språk formuleras vanligtvis den konkreta (ytan) grammatiken entydigt. Abstrakta grammatik är å andra sidan ofta tvetydiga, varigenom det unika med det abstrakta härledningsträdet härrör från det konkreta under analysens gång.

Abstrakta syntaxträd

För framställningen av syntaxträd som en datastruktur i en dator används beteckningen abstrakt syntaxträd (AST) nu ganska enhetligt. B. även av abstrakta härledningsträd , operatörsträd eller liknande. kan pratas om. En exakt koppling mellan abstrakt syntaxträd och konkret härledningsträd visas i litteraturen, t.ex. T. indikerade. Förutom en grovhet av härledningsträdet inkluderas emellertid också krav för vidare bearbetning i strukturen, så att en direkt formell härledning från ytgrammatiken vanligtvis är otillfredsställande som ett resultat.

Den sammanhangsfria ytgrammatiken står då emot en abstrakt grammatik , som i snävare mening mestadels är en algebraisk datatyp . Syntaxens träd representeras sedan tekniskt som mångsidiga termer . Analysen är i övergången mellan grammatiska och algebraisk-logiska termer, så att man här kan tala flytande om icke-terminaler och typer eller om träd och termer.

exempel

Konkret (vänster) och abstrakt (höger) syntaxträd för uttrycket ${\ displaystyle a \ times (b + 3)}$

Bilden motsatt visar konkreta och abstrakta syntaxträd för följande grammatik.

E :: E "+" T - uttryck
  :: T
T :: T "*" F term
  :: F
F :: V - faktor
  :: N
  :: "(" E ")"
V - variabel
N - nummer

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

typ E = lägg till (E, E);
        mul (E, E);
        var (V);
        antal (N)

Den konkreta grammatiken i detta exempel måste reglera ordningen i vilken operatörerna tillämpas på (partiella) uttryck - det vill säga punkt före streck och de partiella uttrycken med samma prioritet ska grupperas från vänster till höger. Möjligheten att skapa en annan sammanfattning erbjuds också med uttryck inom parentes. Tillsammans med vissa terminaler (här "(", ")", "+", "*") är detta bara egenskaper hos den syntaktiska ytan som inte längre spelar en roll i senare analys och vidare bearbetning. I synnerhet kan skillnaden mellan olika typer av uttryck (här E, T och F) och nyckelorden helt undvikas, vilket framgår av det abstrakta syntaxträdet, som också ligger mycket närmare "innehållet" i uttryck. Dessutom, på grund av dessa ytdetaljer, blir betongderivationsträd inte bara snabbt förvirrande utan tar också mer lagringsutrymme än nödvändigt som en datastruktur i datorn på grund av deras detaljer. Detta återspeglas också i körtiden och komplexiteten hos de program som senare ska bearbeta derivatträdet. Av tekniska skäl representeras därför uppdelningen av en källtext vanligtvis inte av ett specifikt derivatsträd.

Representation av abstrakta syntaxträd

Förutom den grafiska representationen som (operator) träd som visas i exemplet, är abstrakta syntaxträd också tekniskt noterade som termer , t.ex. B.: mul(var('a'), add(var('b'), num(3))).

Abstrakt grammatik

Medan abstrakta syntaxträd är datastrukturer och algebraiska typer intar grammatikens roll i dem, ges i litteraturen, särskilt i samband med calculi, ofta bara en grov, tvetydig grammatik, som, som visas i exemplet ovan, har samma struktur som termerna men innehåller fortfarande nyckelord. Denna form möjliggör en trevlig skrivning av abstrakta syntaxträd, som ofta ligger mycket nära den faktiska källan. Vanligtvis påpekades det i inledningen att parenteser kan användas för otydlighet. Ett abstrakt syntaxträd för ovanstående exempel skulle då faktiskt a * (b + 3)skrivas ner som. Inom ramen för denna litteratur fokuseras emellertid alltid på termen. Som nämnts är gränserna mellan grammatik och algebra suddiga genom att leka med form.

Ett typiskt exempel är uttrycken i lambdakalkylen , vars abstrakta grammatik ofta bara bara skrivs ner som. Samma teknik används också för omfattande grammatik. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

litteratur

• Ingo Wegener : Teoretisk datavetenskap . En algoritmorienterad introduktion. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Exempel på sammanhangsfria språk och syntaxträd, s. 147-148 . 
• Uwe Schöning : Teoretisk datavetenskap - i ett nötskal . 5: e upplagan. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Syntaxträd, s. 15-17 . 
• Juraj Hromkovič : Teoretisk datavetenskap . Formella språk, förutsägbarhet, komplexitetsteori, algoritmer, kommunikation och kryptografi. 3: e upplagan. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Kontextfria grammatik och tryckknappsautomat, s. 378 . 
• Hans Zima: Compiler I . Analys. Bibliographisches Institut, Mannheim / Wien / Zürich 1982, ISBN 3-411-01644-2 , 4.3 Abstrakta träd och deras tillskrivning, s. 216-229 . 
• Stefan Müller : Grammatisk teori. Från transformationsgrammatik till begränsningsbaserade tillvägagångssätt. 2: a upplagan. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , kap. 2 ( langsci-press.org ). 

Individuella bevis

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