Syntaxisboom

Een syntaxis , afleiding of ontleedboom is een term uit de theoretische informatica en taalkunde . Het beschrijft een hiërarchische weergave van de uitsplitsing van een tekst. Syntaxisbomen worden gebruikt als hulpmiddel voor grafische visualisatie van de storing en, in de vorm van een datastructuur , om deze uitsplitsing weer te geven voor machinale verwerking, b.v. B. in een compiler of vertaler .

De verschillende termen worden in de literatuur niet eenduidig gebruikt. Alleen de term afleidingsboom , die is gebaseerd op de term afleiding, is formeel nauwkeurig gedefinieerd . Andere namen voor verschillende soorten bomen kunnen dan technisch gedetailleerder worden gedefinieerd, zoals hieronder beschreven, indien nodig.

In tegenstelling tot informatica, waarin talen ook kunnen worden gedefinieerd volgens de technische mogelijkheden, vindt taalkunde moeilijkere voorwaarden bij het omgaan met natuurlijke talen , voornamelijk omdat de volgorde van de componenten in een zin kan variëren.

invoering

Vertegenwoordiging van een afleidingsboom

Bij de (mechanische) analyse van zinnen of formele teksten in natuurlijke taal (bv. Computerprogramma's) wordt de lexicale analyse (de uitsplitsing in tokens of symbolen ) vaak gevolgd door een hiërarchische samenvatting van de symbolen in samenhangende delen van zinnen ( constituenten ) of secties van de formele tekst. Omgekeerd kan dit ook worden opgevat als een ontleding van de tekst. Het resultaat is een boom zoals rechts afgebeeld. Naast de grafische vorm, worden representaties tussen haakjes ook gebruikt voor syntaxisbomen: ${\ displaystyle [_ {S} \ [_ {\ mathit {NP}} \ John] \ [_ {\ mathit {VP}} \ [_ {V} \ hit] \ [_ {\ mathit {NP}} \ [_ {\ mathit {Det}} \ the] \ [_ {N} \ ball]]]].}$

Technisch gezien wordt de boom aan de linkerkant ook wel een betonnen afleidingsboom genoemd , omdat deze de resulterende structuur precies weergeeft met behulp van de concrete tekst. In de taalkunde zijn echter ook modellen gebruikelijk die meerdere representatielagen bieden (bijv. Oppervlakte- en dieptestructuur ).

Vaak zijn de knooppunten van de boom verrijkt met attributen (in de taalkunde zijn dit voornamelijk morfologische categorieën ). Dit geeft u een toegeschreven syntaxisboom met de bijbehorende toegeschreven grammatica . Terwijl een contextvrije grammatica wordt gebruikt in de eerste twee boomweergaven , speelt de contextafhankelijkheid een rol in de laatste . Deze verschillen worden weerspiegeld in de Chomsky-hiërarchie . In dergelijke gevallen wordt de term semantische analyse gebruikt in de compilerconstructie .

Afleidingsbomen

Overweeg een contextvrije grammatica . Een afleidingsboom hiervoor is een boom waarvan de knooppunten zijn gelabeld met symbolen van (d.w.z. terminal- en niet-terminalsymbolen en het lege woord ). De boom is besteld , i. H. de kinderen van elk knooppunt hebben een vaste volgorde, en het volgende is van toepassing op de etikettering: ${\ Displaystyle G = \ left (N, \ Sigma, P, S \ right)}$ ${\ displaystyle \ Sigma \ cup N \ cup \ {\ varepsilon \}}$

De wortel is gelabeld met het startsymbool . Deze eigenschap is soms niet vereist. Een boom die aan hen voldoet, wordt een volledige afleidingsboom genoemd . ${\ displaystyle S}$
Als de kinderen van een binnenknoop met het label met zijn gelabeld met de symbolen (in die volgorde), moet de grammatica de regel bevatten. ${\ displaystyle A}$ ${\ displaystyle z_ {1}, \ ldots, z_ {m}}$ ${\ displaystyle A \ to z_ {1} \ ldots z_ {m}}$
De bladeren van de boom zijn gelabeld met symbolen . ${\ displaystyle \ Sigma \ cup \ {\ varepsilon \}}$
Als een blad is gemarkeerd met , is het de enige opvolger van zijn voorgangerknooppunt. ${\ displaystyle \ varepsilon}$

Alleen niet-terminalsymbolen kunnen worden gebruikt als interne knooppunten, en alleen de terminalsymbolen of het lege woord voor de bladeren.

Bouw van afleidingsbomen

Mogelijke syntaxisbomen / -diagrammen kunnen vaak eenvoudig worden gemaakt voor korte teksten door de productieregels te volgen. Voor langere teksten zijn veel mechanische methoden beschikbaar.

Het syntaxisdiagram dat in de inleiding wordt getoond, bevat bijvoorbeeld onder andere. zijn gebaseerd op de volgende regels:

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

Om een afleidingsboom te genereren, kunnen de regels stap voor stap vanaf de wortel worden toegepast door systematisch één niet-terminal aan de linkerkant van de regel te vervangen door de symbolen aan de rechterkant totdat alleen terminals over zijn:

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

Met elk van de stappen teken je een stuk van de syntaxisboom van boven naar beneden. Maar je kunt de regels ook andersom toepassen en beginnen met de geschreven zin en vervolgens de boom stap voor stap van onder naar boven opbouwen.

Afleidingsbomen voor ondubbelzinnige en dubbelzinnige grammatica's

Als er meer dan één afleidingsboom is voor een woord in de taal van een grammatica, spreekt men van een dubbelzinnige grammatica , anders van een ondubbelzinnige. De volgende grammatica is bijvoorbeeld dubbelzinnig

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

omdat "aa a" op twee verschillende manieren kan worden onderverdeeld: "[aa] a" en "a [aa]". Er is echter slechts één mogelijke classificatie die de volgende grammatica toelaat

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

In het geval van dubbelzinnige grammatica's kan het aantal mogelijke afleidingsbomen voor een en hetzelfde woord sterk toenemen met de lengte van het woord. In dit geval zijn afleidingsbomen niet langer een geschikte weergave voor het geheel van mogelijke afleidingen. In het geval van formele talen is de concrete (oppervlakte) grammatica meestal ondubbelzinnig geformuleerd. Abstracte grammatica's zijn daarentegen vaak dubbelzinnig, waarbij het unieke karakter van de abstracte afleidingsboom vervolgens het resultaat is van het concrete tijdens het verloop van de analyse.

Abstracte syntaxisbomen

Voor de weergave van syntaxisbomen als een datastructuur in een computer, wordt de aanduiding abstracte syntaxisboom (AST) nu vrij uniform gebruikt. B. ook van abstracte afleidingsbomen , operatorbomen en dergelijke. kan worden besproken. Een exact verband tussen de abstracte syntaxisboom en de concrete afleidingsboom wordt getoond in de literatuur, b.v. T. aangegeven. Naast een verruwing van de afleidingsboom zijn er echter ook eisen voor verdere verwerking in de structuur opgenomen, zodat een directe formele afleiding uit de oppervlaktegrammatica daardoor meestal onbevredigend is.

De contextvrije oppervlakgrammatica is dan in tegenstelling tot een abstracte grammatica , die in engere zin meestal een algebraïsch gegevenstype is . De syntaxisbomen worden dan technisch weergegeven als veelzijdige termen . De analyse bevindt zich in de overgang tussen grammaticale en algebraïsch-logische termen, zodat men hier vloeiend kan spreken van niet-terminals en typen of van bomen en termen.

voorbeeld

Concrete (links) en abstracte (rechts) syntaxisboom voor de uitdrukking

{\ displaystyle a \ times (b + 3)}

De afbeelding hiernaast toont concrete en abstracte syntaxisbomen voor de volgende grammatica's.

concrete grammatica

abstracte grammatica

algebraïsch type

E :: E "+" T - uitdrukking
  :: T.
T :: T "*" F term
  :: F.
F :: V - factor
  :: N
  :: "(" E ")"
V - variabel
N - nummer

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

type E = toevoegen (E, E);
        mul (E, E);
        var (V);
        aantal (N)

De concrete grammatica in dit voorbeeld moet de volgorde regelen waarin de operatoren worden toegepast op de (deel) uitdrukkingen - dat wil zeggen punt voor het streepje en de deeluitdrukkingen met dezelfde prioriteit moeten van links naar rechts worden gegroepeerd. De mogelijkheid om een andere samenvatting te maken wordt ook geboden met uitdrukkingen tussen haakjes. Samen met bepaalde terminals (hier "(", ")", "+", "*") zijn dit slechts eigenschappen van het syntactische oppervlak die bij latere analyse en verdere verwerking geen rol meer spelen. Met name het onderscheid tussen verschillende soorten uitdrukkingen (hier E, T en F) en de sleutelwoorden kan volledig achterwege worden gelaten, zoals blijkt uit de abstracte syntaxisboom, die ook veel dichter bij de 'inhoud' van de uitdrukking. Bovendien worden betonnen afleidingsbomen door deze oppervlaktedetails niet alleen snel verwarrend, maar nemen ze vanwege hun details ook meer opslagruimte in dan nodig is als datastructuur in de computer. Dit komt ook tot uiting in de looptijd en complexiteit van de programma's die later de afleidingsboom gaan verwerken. Om technische redenen wordt de uitsplitsing van een brontekst daarom meestal niet weergegeven door een specifieke afleidingsboom.

Vertegenwoordiging van abstracte syntaxisbomen

Naast de grafische weergave als (operator) boom die in het voorbeeld wordt getoond, worden abstracte syntaxisbomen ook technisch genoteerd als termen , bijv. B .: mul(var('a'), add(var('b'), num(3))).

Abstracte grammatica

Terwijl abstracte syntaxisbomen datastructuren zijn en algebraïsche typen daarin de rol van grammatica spelen, wordt in de literatuur, vooral in verband met calculi, vaak alleen een grove, dubbelzinnige grammatica gegeven, die, zoals in het bovenstaande voorbeeld wordt getoond, de dezelfde structuur als de termen, maar bevat nog steeds trefwoorden. Dit formulier maakt het mogelijk om op een prettige manier abstracte syntaxisbomen te schrijven, die vaak heel dicht bij de eigenlijke bron liggen. Meestal wordt er in de inleiding op gewezen dat haakjes kunnen worden gebruikt voor het ondubbelzinnig maken. Een abstracte syntaxisboom voor het bovenstaande voorbeeld zou dan feitelijk worden a * (b + 3)opgeschreven als. In de context van deze literatuur ligt de focus echter altijd op de term, zoals gezegd vervagen de grenzen tussen grammatica en algebra door te spelen met vorm.

Een typisch voorbeeld zijn de uitdrukkingen in de lambda-calculus , waarvan de abstracte grammatica vaak maar net wordt opgeschreven als. Dezelfde techniek wordt ook gebruikt voor uitgebreide grammatica's. ${\ displaystyle E: = \ lambda VE \, | \, EE \, | \, V}$

literatuur

Ingo Wegener : Theoretische informatica . Een algoritme-georiënteerde introductie. BG Teubner, Stuttgart, ISBN 3-519-02123-4 , 6.1 Voorbeelden van contextvrije talen en syntaxisbomen, p. 147-148 .
Uwe Schöning : Theoretische informatica - in een notendop . 5e editie. Spektrum Akademischer Verlag, Heidelberg, ISBN 978-3-8274-1824-1 , 1.1.4 Syntaxisbomen, p. 15-17 .
Juraj Hromkovič : Theoretische informatica . Formele talen, voorspelbaarheid, complexiteitstheorie, algoritmen, communicatie en cryptografie. 3e editie. BG Teubner Verlag, Heidelberg, ISBN 978-3-8351-0043-5 , 10.4 Contextvrije grammatica's en drukknopautomaten, p. 378 .
Hans Zima: Compiler I . Analyse. Bibliographisches Institut, Mannheim / Wenen / Zürich 1982, ISBN 3-411-01644-2 , 4.3 Abstracte bomen en hun attributie, p. 216-229 .
Stefan Müller : grammaticale theorie. Van transformationele grammatica tot op beperkingen gebaseerde benaderingen. 2e editie. Language Science Press, Berlin 2018, ISBN 978-3-96110-074-3 , hfst. 2 ( langsci-press.org ).

Languages