Syntaks træ

En syntaks , afledning eller parsetræ er et udtryk fra teoretisk datalogi og lingvistik . Det beskriver en hierarkisk gengivelse af opdeling af en tekst. Syntaks træer bruges både som et hjælpemiddel til grafisk visualisering af sammenbruddet og i form af en datastruktur til at vise denne opdeling til maskinbehandling, f.eks. B. i en kompilator eller oversætter .

De forskellige udtryk bruges ikke ensartet i litteraturen. Kun udtrykket afledningstræ , der er baseret på udtrykket afledning, er formelt præcist defineret . Andre navne på forskellige typer træer kan derefter defineres teknisk mere detaljeret som beskrevet nedenfor, hvis det er nødvendigt.

I modsætning til datalogi, hvor sprog også kan defineres i henhold til de tekniske muligheder, finder lingvistik sværere forudsætninger, når man beskæftiger sig med naturlige sprog , primært fordi rækkefølgen af ​​komponenterne i en sætning kan variere.

introduktion

Repræsentation af et afledningstræ

I (mekanisk) analyse af naturlige sproglige sætninger eller formelle tekster (f.eks. Computerprogrammer) følges den leksikale analyse (opdeling i tokens eller symboler ) ofte af en hierarkisk oversigt over symbolerne i relaterede dele af sætninger ( bestanddele ) eller sektioner af den formelle tekst i stedet. Omvendt kan dette også forstås som en dissektion af teksten. Resultatet er et træ som det, der vises til højre. Ud over den grafiske form bruges parenteser også til syntaks træer:${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]].}$

Teknisk set er træet til venstre også kaldet en konkret afledning træ , da det viser den resulterende struktur præcis ved hjælp af konkrete tekst. Inden for lingvistik er der dog også almindelige modeller, der giver flere repræsentationslag (f.eks. Overflade- og dybdestruktur ).

Ofte er træets noder beriget med attributter (inden for lingvistik er dette hovedsageligt morfologiske kategorier ). Dette giver dig et tilskrevet syntaks-træ med den tilknyttede tildelte grammatik . Mens en kontekstfri grammatik bruges i de to første trærepræsentationer , kommer kontekstafhængigheden i spil i sidstnævnte . Disse forskelle afspejles i Chomsky-hierarkiet . I sådanne tilfælde bruges udtrykket semantisk analyse i kompilatorkonstruktionen .

Afledningstræer

Overvej en kontekstfri grammatik . Et afledningstræ til dette er et træ, hvis knudepunkter er mærket med symboler fra (dvs. terminale og ikke-terminale symboler og det tomme ord ). Træet bestilles , dvs. H. børnene til hver knude har en fast rækkefølge, og følgende gælder for mærkning: ${\ displaystyle G = \ left (N, \ Sigma, P, S \ right)}$${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

• Den rod er mærket med start symbolet . Denne egenskab er undertiden ikke påkrævet. Et træ der tilfredsstiller dem kaldes et komplet afledningstræ.${\ displaystyle S}$
• Hvis børnene til en indre node, der er mærket med, er mærket med symbolerne (i den rækkefølge), skal grammatikken indeholde reglen .${\ displaystyle A}$${\ displaystyle z_ {1}, \ ldots, z_ {m}}$${\ displaystyle A \ til z_ {1} \ ldots z_ {m}}$
• De blade af træet er mærket med symboler .${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
• Hvis et blad er markeret med , er det den eneste efterfølger til dets forgængerknude.${\ displaystyle \ varepsilon}$

Kun ikke-terminale symboler kan bruges som indre knudepunkter, og kun terminalsymboler eller det tomme ord for bladene.

Konstruktion af afledningstræer

Mulige syntaks træer / diagrammer kan ofte let oprettes til korte tekster ved at følge produktionsreglerne. Mange mekaniske metoder er tilgængelige for længere tekster .

For eksempel inkluderer syntaksdiagrammet vist i introduktionen blandt andet. er baseret på følgende 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}}}$

For at generere et afledningstræ kan reglerne anvendes trin for trin fra roden ved systematisk at erstatte en ikke-terminal på venstre side af reglen med symbolerne på højre side, indtil kun terminaler er tilbage:

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

Med hvert af trinnene tegner du et stykke af syntaks træet fra top til bund. Men du kan også anvende reglerne omvendt og starte med den skrevne sætning og derefter opbygge træet trin for trin fra bund til top.

Afledningstræer til entydige og tvetydige grammatikker

Hvis der er mere end et afledningstræ for et ord på sproget i en grammatik, taler man om en tvetydig grammatik , ellers om en utvetydig. For eksempel er følgende grammatik tvetydig

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

fordi "aa a" kan opdeles på to forskellige måder: "[aa] a" og "a [aa]". Imidlertid tillader kun en mulig klassificering følgende grammatik

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

I tilfælde af tvetydige grammatikker kan antallet af mulige afledningstræer for et og det samme ord stige kraftigt med længden af ​​ordet. I dette tilfælde er afledningstræer ikke længere en passende repræsentation for de samlede mulige afledninger. I tilfælde af formelle sprog formuleres den konkrete (overflade) grammatik normalt entydigt. Abstrakte grammatikker er derimod ofte tvetydige, hvorved det unikke ved det abstrakte afledningstræ resulterer fra det konkrete gennem analysens forløb.

Abstrakte syntaks træer

Til gengivelse af syntaks træer som en datastruktur i en computer anvendes betegnelsen abstrakt syntaks træ (AST) nu ret ensartet. B. også af abstrakte afledningstræer , operatortræer eller lignende. kan tales om. En nøjagtig sammenhæng mellem abstrakt syntaks træ og konkret afledningstræ er vist i litteraturen, f.eks. T. angivet. Ud over en grovhed af afledningstræet er krav til yderligere behandling også inkluderet i strukturen, således at en direkte formel afledning fra overfladegrammatikken normalt ikke er tilfredsstillende som et resultat.

Den kontekstfri overfladegrammatik er derefter imod en abstrakt grammatik , som i snævrere forstand for det meste er en algebraisk datatype . Syntaks træerne er derefter teknisk repræsenteret som alsidige termer . Analysen foregår i overgangen mellem grammatiske og algebraisk-logiske termer, så man her kan tale flydende om ikke-terminaler og typer eller om træer og termer.

eksempel

Konkret (venstre) og abstrakt (højre) syntaks træ til udtrykket ${\ displaystyle a \ times (b + 3)}$

Illustrationen overfor viser konkrete og abstrakte syntaks træer for de følgende grammatikker.

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

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

type E = tilføj (E, E);
        mul (E, E);
        var (V);
        antal (N)

Den konkrete grammatik i dette eksempel skal regulere rækkefølgen, i hvilken operatørerne anvendes på de (delvise) udtryk - det vil sige prik før bindestreg, og de delvise udtryk med samme prioritet skal grupperes fra venstre mod højre. Muligheden for at oprette et andet resumé tilbydes også med udtryk i parentes. Sammen med visse terminaler (her "(", ")", "+", "*") er dette kun egenskaber ved den syntaktiske overflade, som ikke længere spiller en rolle i senere analyse og videre behandling. Navnlig kan forskellen mellem forskellige typer udtryk (her E, T og F) og nøgleordene helt undlades, som det fremgår af det abstrakte syntaks-træ, som også er meget tættere på "indholdet" af udtryk. Desuden på grund af disse overfladedetaljer bliver betonafledningstræer ikke kun hurtigt forvirrende, men optager også mere lagerplads end nødvendigt som en datastruktur i computeren på grund af deres detaljer. Dette afspejles også i runtime og kompleksiteten af ​​de programmer, der senere skal behandle afledningstræet. Af tekniske årsager er opdeling af en kildetekst derfor normalt ikke repræsenteret af et specifikt afledningstræ.

Repræsentation af abstrakte syntaks træer

Ud over den grafiske repræsentation som (operator) træ vist i eksemplet, er abstrakte syntaks træer også teknisk bemærket som termer , f.eks. B.: mul(var('a'), add(var('b'), num(3))).

Abstrakt grammatik

Mens abstrakte syntaks træer er datastrukturer, og algebraiske typer påtager sig grammatikens rolle i dem, gives der i litteraturen, især i forbindelse med calculi, ofte kun en grov, tvetydig grammatik, som, som vist i eksemplet ovenfor, har samme struktur som vilkårene, men indeholder stadig nøgleord. Denne form muliggør en behagelig skrivning af abstrakte syntaks træer, som ofte er meget tæt på den faktiske kilde. Normalt påpeges det indledningsvis, at parenteser kan bruges til at fortvivle. Et abstrakt syntaks-træ til ovenstående eksempel ville så faktisk blive a * (b + 3)skrevet ned som. I litteraturens sammenhæng er fokus imidlertid altid på begrebet. Som nævnt er grænserne mellem grammatik og algebra sløret ved at lege med form.

Et typisk eksempel er udtryk i lambda-calculus , hvis abstrakte grammatik ofte kun lige er skrevet ned som. Den samme teknik bruges også til omfattende grammatikker. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

litteratur

• Ingo Wegener : Teoretisk datalogi . En algoritmeorienteret introduktion. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Eksempler på kontekstfrie sprog og syntaks træer, s. 147-148 . 
• Uwe Schöning : Teoretisk datalogi - i en nøddeskal . 5. udgave. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Syntaks træer, s. 15-17 . 
• Juraj Hromkovič : Teoretisk datalogi . Formelle sprog, forudsigelighed, kompleksitetsteori, algoritmer, kommunikation og kryptografi. 3. udgave. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Kontekstfri grammatik og trykknapautomat, s. 378 . 
• Hans Zima: Compiler jeg . Analyse. Bibliographisches Institut, Mannheim / Wien / Zürich 1982, ISBN 3-411-01644-2 , 4.3 Abstrakte træer og deres tilskrivning, s. 216-229 . 
• Stefan Müller : Grammatisk teori. Fra transformationsgrammatik til begrænsningsbaserede tilgange. 2. udgave. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , kap. 2 ( langsci-press.org ). 

Individuelle beviser

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