Syntaks tre

En syntaks , avledning eller analysetre er et begrep fra teoretisk informatikk og lingvistikk . Den beskriver en hierarkisk fremstilling av fordelingen av en tekst. Syntakstrær brukes både som et hjelpemiddel for grafisk visualisering av sammenbruddet, og i form av en datastruktur , for å vise denne sammenbruddet for maskinbehandling, f.eks. B. i en kompilator eller oversetter .

De forskjellige begrepene brukes ikke ensartet i litteraturen. Bare begrepet derivasjonstreet , som er basert på begrepet derivasjon, er formelt presist definert . Andre navn på forskjellige treslag kan da defineres teknisk mer detaljert, som beskrevet nedenfor, om nødvendig.

I motsetning til informatikk, der språk også kan defineres i henhold til de tekniske mulighetene, finner språkvitenskap vanskeligere forutsetninger når man arbeider med naturlige språk , hovedsakelig fordi rekkefølgen på komponentene i en setning kan variere.

introduksjon

Representasjon av et avledningstre

I (mekanisk) analyse av setninger i naturlige språk eller formelle tekster (f.eks. Dataprogrammer) blir den leksikale analysen (sammenbrudd i symboler eller symboler ) ofte etterfulgt av en hierarkisk oppsummering av symbolene i relaterte deler av setninger ( bestanddeler ) eller seksjoner av den formelle teksten i stedet. Motsatt kan dette også forstås som en disseksjon av teksten. Resultatet er et tre som det som er vist til høyre. I tillegg til den grafiske formen, brukes parentes-representasjoner også for syntaksetrær:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]].}$

Teknisk sett kalles treet til venstre også et betongavledetre , da det viser den resulterende strukturen nøyaktig ved bruk av betongteksten. I lingvistikk er det imidlertid også vanlige modeller som gir flere lag med representasjon (f.eks. Overflate- og dybdestruktur ).

Ofte er noder på treet beriket med attributter (i lingvistikk er dette hovedsakelig morfologiske kategorier ). Dette gir deg et tilskrevet syntaks-tre med tilhørende tildelt grammatikk . Mens en kontekstfri grammatikk brukes i de to første trerepresentasjonene , kommer kontekstavhengigheten inn i spill i sistnevnte . Disse forskjellene gjenspeiles i Chomsky-hierarkiet . I slike tilfeller brukes begrepet semantisk analyse i kompilatorkonstruksjon .

Avledningstrær

Vurder en kontekstfri grammatikk . Et avledningstre for dette er et tre hvis noder er merket med symboler fra (dvs. terminale og ikke-terminale symboler og det tomme ordet ). Treet bestilles , dvs. H. barna til hver node har en fast rekkefølge, og følgende gjelder merkingen: ${\ displaystyle G = \ left (N, \ Sigma, P, S \ right)}$${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• Den rot er merket med startsymbolet . Denne egenskapen er noen ganger ikke nødvendig. Et tre som tilfredsstiller dem kalles et komplett avledningstre.${\ displaystyle S}$
• Hvis barna til en indre node merket med er merket med symbolene (i den rekkefølgen), må grammatikken inneholde regelen .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ to z_ {1} \ ldots z_ {m}}$
• De bladene på treet er merket med symboler .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Hvis et blad er merket med , er det den eneste etterfølgeren til forgjengeren.${\ displaystyle \ varepsilon}$

Bare ikke-terminale symboler kan brukes som indre noder, og bare terminalsymbolene eller det tomme ordet for bladene.

Bygging av avledningstrær

Mulige syntakstrær / diagrammer kan ofte enkelt opprettes for korte tekster ved å følge produksjonsreglene. Mange mekaniske metoder er tilgjengelige for lengre tekster .

For eksempel inkluderer syntaksdiagrammet vist i innledningen blant annet. er basert på følgende regler:

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

For å generere et derivasjonstreet, kan reglene brukes trinnvis fra roten ved systematisk å erstatte en ikke-terminal på venstre side av regelen med symbolene på høyre side til bare terminaler er igjen:

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

Med hvert av trinnene tegner du et stykke av syntakstreet fra topp til bunn. Men du kan også bruke reglene omvendt og starte med den skrevne setningen og deretter bygge opp treet trinnvis fra bunn til topp.

Derivasjonstrær for entydige og tvetydige grammatikker

Hvis det er mer enn ett avledningstre for et ord på språket til en grammatikk, snakker man om en tvetydig grammatikk , ellers om en entydig. For eksempel er følgende grammatikk tvetydig

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

fordi "aa a" kan deles inn på to forskjellige måter: "[aa] a" og "a [aa]". Imidlertid tillater bare en mulig klassifisering følgende grammatikk

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

Når det gjelder tvetydige grammatikker, kan antall mulige avledningstrær for ett og samme ord øke kraftig med lengden på ordet. I dette tilfellet er avledningstrær ikke lenger en passende representasjon for den totale mulige avledning. Når det gjelder formelle språk, formuleres vanligvis den konkrete (overflate) grammatikken entydig. Abstrakte grammatikker er derimot ofte tvetydige, hvorved det unike med det abstrakte avledningstreet blir resultatet av det konkrete i løpet av analysen.

Abstrakte syntaks trær

For fremstilling av syntakstrær som datastruktur i en datamaskin, brukes betegnelsen abstrakt syntaks-tre (AST) nå ganske jevnt. B. også av abstrakte avledningstrær , operatortrær eller lignende. kan snakkes om. En nøyaktig sammenheng mellom abstrakt syntaks-tre og konkret avledetre er vist i litteraturen f.eks. T. angitt. I tillegg til en grovgjøring av avledningstreet, er krav til videre behandling også inkludert i strukturen, slik at en direkte formell avledning fra overflategrammatikken vanligvis ikke er tilfredsstillende som et resultat.

Den kontekstfrie overflategrammatikken er da i motsetning til en abstrakt grammatikk , som i smalere forstand stort sett er en algebraisk datatype . Syntaksetrærne blir deretter teknisk representert som allsidige termer . Analysen er i overgangen mellom grammatiske og algebraisk-logiske termer, slik at man her kan snakke flytende om ikke-terminaler og typer eller om trær og termer.

eksempel

Betong (venstre) og abstrakt (høyre) syntakstreet for uttrykket ${\ displaystyle a \ times (b + 3)}$

Illustrasjonen motsatt viser konkrete og abstrakte syntaksetrær for følgende grammatikker.

E :: E "+" T - uttrykk
  :: T
T :: T "*" F begrep
  :: F
F :: V - faktor
  :: N
  :: "(" E ")"
V - variabel
N - nummer

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

type E = add (E, E);
        mul (E, E);
        var (V);
        antall (N)

Den konkrete grammatikken i dette eksemplet må regulere rekkefølgen operatørene brukes på (delvise) uttrykk - det vil si prikk før bindestrek og deluttrykk med samme prioritet skal grupperes fra venstre til høyre. Muligheten for å lage et annet sammendrag tilbys også med uttrykk i parentes. Sammen med visse terminaler (her "(", ")", "+", "*") er dette bare egenskaper til den syntaktiske overflaten som ikke lenger spiller en rolle i senere analyse og videre behandling. Spesielt kan skillet mellom forskjellige typer uttrykk (her E, T og F) og stikkordene fullstendig unnlates, slik man kan se fra det abstrakte syntaksetreet, som også er mye nærmere "innholdet" i uttrykk. Videre, på grunn av disse overflatedetaljene, blir betongavledningstrær ikke bare raskt forvirrende, men de tar også mer lagringsplass enn nødvendig som en datastruktur i datamaskinen på grunn av deres detaljer. Dette gjenspeiles også i kjøretiden og kompleksiteten til programmene som senere skal behandle avledningstreet. Av tekniske årsaker er derfor nedbrytningen av en kildetekst vanligvis ikke representert av et spesifikt avledningstre.

Representasjon av abstrakte syntaks trær

I tillegg til den grafiske representasjonen som (operator) tre vist i eksemplet, er abstrakte syntakstrær også teknisk angitt som termer , f.eks. B.: mul(var('a'), add(var('b'), num(3))).

Abstrakt grammatikk

Mens abstrakte syntakstrær er datastrukturer, og algebraiske typer inntar rollen som grammatikk i dem, er det i litteraturen, spesielt i forbindelse med kalkulasjoner, ofte bare gitt en grov, tvetydig grammatikk, som, som vist i eksemplet ovenfor, har samme struktur som vilkårene, men inneholder fortsatt nøkkelord. Dette skjemaet muliggjør en hyggelig skriving av abstrakte syntaksetrær, som ofte er veldig nær den faktiske kilden. Vanligvis påpekes det innledningsvis at parenteser kan brukes til å fortvivle. Et abstrakt syntaks-tre for eksemplet ovenfor vil da faktisk a * (b + 3)skrives ned som. I sammenheng med denne litteraturen er fokuset imidlertid alltid på begrepet. Som nevnt blir grensene mellom grammatikk og algebra uskarpe ved å leke med form.

Et typisk eksempel er uttrykkene i lambdakalkulus , hvis abstrakte grammatikk ofte bare er skrevet ned som. Den samme teknikken brukes også for omfattende grammatikker. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

litteratur

• Ingo Wegener : Teoretisk informatikk . En algoritmeorientert introduksjon. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Eksempler på kontekstfrie språk og syntakstrær, s. 147-148 . 
• Uwe Schöning : Teoretisk informatikk - i et nøtteskall . 5. utgave. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Syntaks trær, s. 15-17 . 
• Juraj Hromkovič : Teoretisk informatikk . Formelle språk, forutsigbarhet, kompleksitetsteori, algoritmer, kommunikasjon og kryptografi. 3. utgave. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Kontekstfrie grammatikker og trykknappautomater, s. 378 . 
• Hans Zima: Compiler jeg . Analyse. Bibliographisches Institut, Mannheim / Wien / Zürich 1982, ISBN 3-411-01644-2 , 4.3 Abstrakte trær og deres tilskrivning, s. 216-229 . 
• Stefan Müller : Grammatisk teori. Fra transformasjonsgrammatikk til begrensningsbaserte tilnærminger. 2. utgave. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , kap. 2 ( langsci-press.org ). 

Individuelle bevis

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