Syntaxisboom

Een syntaxisboom is een boomstructuur die als tussenstap gebruikt wordt bij het omzetten van een stuk code naar een datastructuur. Er zijn twee soorten: de concrete syntaxisboom en de abstracte syntaxisboom.

Situering

Een gebruiker van een programmeertaal zal een stuk code schrijven dat voor alle andere gebruikers van de programmeertaal leesbaar is. De computer kan de code niet in deze vorm uitvoeren. De code moet omgezet worden naar een vorm die leesbaar is voor de computer. Bij het omvormen van de code naar een datastructuur, die beter geschikt is voor verwerking door de computer, wordt gebruikgemaakt van een lexical analyzer en een parser. Na verwerking door de lexical analyzer en de parser zal de code omgevormd zijn tot een boomstructuur. Deze boomstructuur heet een syntaxisboom en wordt dan verder omgezet naar een datastructuur.

De lexical analyzer zal de tekst doorzoeken naar eenheden die betekenis hebben zoals getallen, variabelen en elementen die behoren tot de programmeertaal (bijvoorbeeld het element class). De parser controleert of deze eenheden wel voldoen aan de regels van de contextvrije grammatica (deze grammatica of syntaxis heet contextvrij omdat ze onafhankelijk is van specifieke elementen uit een programmeertaal). Als dat zo is, dan wordt een syntaxisboom opgebouwd volgens een lijst met contextvrije verwijzingen.

Opbouw van de syntaxisboom

Dit werkt zo: telkens als een element geïdentificeerd wordt, zal de parser een knoop aanmaken met de waarde of naam van dit element en eventueel een ouderknoop die het type van dit element bevat. Dan zal de parser dit element in de lijst opzoeken en de verwijzing volgen. Het resultaat van de verwijzing wordt een nieuwe ouderknoop. Uiteindelijk is de verwijzing gelijk aan de wortel van de boom, namelijk expressie. Deze procedure wordt herhaald totdat alle elementen van de code zijn verwerkt.

Twee soorten syntaxisbomen

Er zijn twee soorten syntaxisbomen, de concrete syntaxisboom en abstracte syntaxisboom. De abstracte syntaxisboom is een verbetering van de concrete syntaxisboom om twee redenen.

In de abstracte syntaxisboom wordt informatie die impliciet al vervat zit in de concrete syntaxisboom weggelaten. Een voorbeeld hiervan is het weglaten van haakjes rond een bewerking. Maar ook overbodige elementen zoals commentaar of elementen uit de lay-out zoals spaties of het teken ‘;’ op het einde van elke regel worden weggelaten.
Bij een abstracte syntaxisboom kan de lijst met contextvrije verwijzingen aangepast worden zodat de syntaxisboom kleiner wordt. Niet alle verwijzingen zullen aanleiding geven tot het aanmaken van een nieuwe knoop. Dit gebeurt door het invoeren van constructoren.

Voorbeeld

Laten we een voorbeeld bekijken van het opstellen van een abstracte syntaxisboom voor de expressie: (a b) × 1

We maken gebruik van deze lijst van contextvrije verwijzingen:

Id	→	Var {cons("Var")}
Var	→	Exp
IntConst	→	Exp {cons("Int")}
Exp "x" Exp	→	Exp {cons("x")}
Exp " " Exp	→	Exp {cons(" ")}
Exp "-" Exp	→	Exp {cons("-")}
Exp "=" Exp	→	Exp {cons("Eq")}
Exp ">" Exp	→	Exp {cons("Gt")}
"(" Exp ")"	→	Exp

De variabelen a en b zijn van het type identifier (Id) en via de verwijzing Id → Var wordt de constructor Var ({cons(“Var”)}) opgeroepen die een knoop maakt met de naam “Var”. Het getal 1 is van het type IntConst en via de verwijzing IntConst → Exp wordt de constructor Int ({const(“Int”)}) opgeroepen die een knoop maakt met de naam “Int”. Voor de bewerkingen en × worden ook knopen aangemaakt met telkens als naam het type bewerking.

Uit de laatste verwijzing blijkt dat haakjes geen aanleiding geven tot een extra knoop omdat er geen constructor is, een kenmerk van de abstracte syntaxisboom.

Hieronder is de abstracte syntaxisboom gegeven voor de expressie: (a b) × 1

Zie ook

Abstracte syntaxis