Attributengrammatica

Een attributengrammatica is een formele methode voor het specificeren van structurele eigenschappen van een programmeertaal door de productieregels van een contextvrije grammatica aan te vullen met regels die betrekking hebben op de (contextgevoelige) structuur van de taal.

Attributengrammatica's kunnen gebruikt worden om structurele eigenschappen van een taal te specificeren die moeilijk, of helemaal niet, in een contextvrije grammatica vastgelegd kunnen worden. Voorbeelden hiervan zijn onder andere de eisen die een taal stelt wat betreft het gebruik van verschillende datatypen in expressies en de eis dat een variabele gedeclareerd moet worden voor deze gebruikt wordt.

Syntax-directed translation en decorated syntax trees

Attributengrammatica's zijn een formalisatie van het principe van syntax-directed translation. Bij syntax-directed translation worden aan de terminale en niet-terminale symbolen van een contextvrije grammatica een of meerdere attributen (eigenschappen) toegekend. Daarnaast worden de productieregels van de grammatica uitgebreid met regels om deze attributen te berekenen. Het resultaat wordt een syntax-directed definition genoemd en het gebruik ervan syntax-directed translation.

Het parsen van een invoertekst met behulp van een grammatica levert een syntaxisboom op. De knopen in deze boom corresponderen met productieregels uit de grammatica. Bij syntax-directed translation gebruiken we deze knopen als records waarin een of meerdere attributen kunnen worden opgeslagen. Door de syntaxisboom in de juiste volgorde te doorlopen en daarbij voor iedere knoop de attribuutregels van de met die knoop corresponderende productieregel uit te voeren, worden alle attributen in de knopen ingevuld. Zo'n syntaxisboom waarin in de knopen extra informatie is opgeslagen wordt wel een decorated syntax tree of annotated syntax tree genoemd.

Wanneer de regels in een syntax-directed definition geen neveneffecten hebben, is er sprake van een attributengrammatica.

Hoewel bij het implementeren van programmeertalen niet altijd gebruik wordt gemaakt van een formele, expliciet geformuleerde attributengrammatica, wordt het achterliggende principe van syntax-directed translation in vrijwel iedere compiler gebruikt.

Voorbeeld

Als voorbeeld nemen we een attributengrammatica voor eenvoudige rekenkundige expressies, zoals "(3+6)*2". De volgende grammatica beschrijft de toegestane expressie's: 

Expr ::= Expr '+' Term
      |  Expr '-' Term
      |  Term
      
Term ::= Term '*' Factor
      |  Term '/' Factor
      |  Factor
      
Factor ::= '(' Expr ')'
        |  integer

We stellen een attributengrammatica op die de waarde van geldige expressies berekent. Hiertoe verbinden we met alle niet-terminale symbolen een waarde-attribuut, dat de numerieke waarde van het deel van de expressie dat door dat niet-terminale symbool gerepresenteerd wordt bevat. Bij alle productieregels specificeren we hoe de waarde dat bij het niet-terminale symbool aan de linkerkant hoort afgeleid kan worden uit de waarden van de symbolen aan de rechterkant. Voor het gemak nummeren we de onderdelen van productieregels waar nodig, schrijven we ze compleet uit en voeren we een startsymbool met een bijbehorende productieregel toe.

Productieregel Attribuutregel
Start ::= Expr Start.waarde = Expr.waarde
Expr1 ::= Expr2 '+' Term Expr1.waarde = Expr2.waarde + Term.waarde
Expr1 ::= Expr2 '-' Term Expr1.waarde = Expr2.waarde - Term.waarde
Expr ::= Term Expr.waarde = Term.waarde
Term1 ::= Term2 '*' Factor Term1.waarde = Term2.waarde * Factor.waarde
Term1 ::= Term2 '/' Factor Term1.waarde = Term2.waarde / Factor.waarde
Term ::= Factor Term.waarde = Factor.waarde
Factor ::= '(' Expr ')' Factor.waarde = Expr.waarde
Factor ::= integer Factor.waarde = string_naar_int(integer.text)

De uitkomst van een expressie kan nu berekend worden door een syntaxisboom van beneden naar boven (van de bladeren naar de wortel) te doorlopen en iedere keer dat we bij een knoop komen de betreffende regel te gebruiken om het attribuut te berekenen en in de knoop op te slaan. Als we alle knopen gehad hebben, met als laatste de wortel (de wortel correspondeert altijd met de Start-productie in onze voorbeeldgrammatica), dan bevat de wortel de uitkomst van de berekening.

Hoewel het nogal omslachtig is om de waarde van expressies op deze manier te specificeren, kan dit toch een aantal voordelen hebben. We hebben nu een uitgangspunt voor het ontwerpen van een programma dat de uitkomst van dit soort expressies kan berekenen. Als we al een parser hebben die geldige expressies kan herkennen, kunnen we deze ook de berekening laten uitvoeren. Dat doen we door op iedere plaats waar de parser een productieregel 'herkent' de code die de bijbehorende attribuutregel uitvoert in te voegen. Als we nog geen parser hebben, kunnen we gebruikmaken van een parsergenerator. De meeste parsergenerators maken het mogelijk om acties te specificeren: fragmenten programmacode die aan een bepaalde productieregel gekoppeld worden en die uitgevoerd worden als de betreffende productieregel gebruikt wordt. We hoeven de attribuutregels in de attributengrammatica hierboven dan alleen nog om te zetten geldige code, waarna we deze als acties kunnen invoegen in de grammatica. De parsergenerator produceert vervolgens een programma dat expressies niet alleen herkent maar ook kan verwerken.

Afgeleide, samengestelde en intrinsieke attributen

We kunnen de attributen die in een attributengrammatica gebruikt worden onderverdelen in drie soorten:

Samengesteld (meestal met de Engelse term synthesized aangeduid)
Bij samengestelde attributen wordt de waarde van het attribuut van het niet-terminale symbool aan de linkerkant van een produktieregel bepaald door attributen van de terminale en niet-terminale symbolen aan de rechterkant van de productie. Dit betekent dat in een syntaxisboom de waarde van dat attribuut in een knoop bepaald wordt door de waarden van dat attribuut in de kinderen van die knoop. Deze attributen bewegen zich als het ware omhoog, in de richting van de wortel van de syntaxisboom. De bladeren van de syntaxisboom hebben geen samengestelde attributen. In ons voorbeeld, de attributengrammatica voor expressies hierboven, zijn alle attributen samengesteld (behalve het waarde-attribuut van het terminale symbool integer).
Afgeleid (meestal met de Engelse term inherited aangeduid)
Bij een afgeleid attribuut hangt de waarde van het attribuut in een knoop van de syntaxisboom af van de waarde van de attributen in knopen die geen kindknoop van de knoop zijn, maar bijvoorbeeld bovenliggende of naastliggende knopen. De informatie in afgeleide attributen verplaatst zich dus als het ware naar beneden of opzij in de syntaxisboom.
Intrinsiek
Intrinsieke attributen worden niet afgeleid van andere attributen. De waarde van deze attributen komt 'van buiten'. In ons voorbeeld hierboven geldt dat voor de laatste productie (Factor → integer). Het attribuut 'waarde' van het niet-terminale symbool Factor wordt niet uit een ander attribuut afgeleid, maar komt van buiten, via de hypothetische constructie string_naar_int(integer.text), die we gekozen hebben om aan te geven dat we de tekst die de scanner als integer herkent heeft omzetten naar het juiste getal.

Samengestelde attributen komen in de praktijk het meest voor. Een attributengrammatica die, zoals ons voorbeeld hierboven, enkel uit samengestelde en intrinsieke attributen bestaat wordt een S-attributed grammar genoemd. Bij zo'n S-attributed grammatica kunnen alle attributen in een syntaxisboom berekend worden door de knopen van beneden naar boven (bottom-up) te verwerken. Bij grammatica's die niet S-attributed zijn, en die dus ook afgeleide attributen hebben, is de volgorde waarin de knopen verwerkt kunnen worden meestal minder duidelijk. In sommige gevallen kan er zelfs geen enkele bruikbare volgorde zijn, bijvoorbeeld als het attribuut van een of meer knopen direct of indirect afhangt van zichzelf, waardoor er een cirkel ontstaat.

Zie ook