Free Press

Abstracte syntaxisbomen zijn gegevensstructuren die veel worden gebruikt in compilers om de structuur van programmacode weer te geven. Een AST is gewoonlijk het resultaat van de syntaxis-analysefase van een compiler. Het dient vaak als een tussenliggende representatie van het programma door verschillende stadia die de compiler nodig heeft, en heeft een sterke invloed op de uiteindelijke output van de compiler.

MotivatieEdit

Een AST heeft verschillende eigenschappen die de verdere stappen van het compilatieproces helpen:

• Een AST kan worden bewerkt en verrijkt met informatie zoals eigenschappen en annotaties voor elk element dat het bevat. Een dergelijke bewerking en annotatie is onmogelijk met de broncode van een programma, omdat deze dan zou moeten worden gewijzigd.
• Vergeleken met de broncode bevat een AST geen overbodige interpunctie en scheidingstekens (accolades, puntkomma’s, haakjes, enz.).
• Een AST bevat gewoonlijk extra informatie over het programma, als gevolg van de opeenvolgende stadia van analyse door de compiler. Het kan bijvoorbeeld de positie van elk element in de broncode opslaan, waardoor de compiler nuttige foutmeldingen kan afdrukken.

ASTs zijn nodig vanwege de inherente aard van programmeertalen en hun documentatie. Talen zijn vaak ambigu van aard. Om deze ambiguïteit te vermijden, worden programmeertalen vaak gespecificeerd als een contextvrije grammatika (CFG). Er zijn echter vaak aspecten van programmeertalen die een CFG niet kan uitdrukken, maar die deel uitmaken van de taal en in de specificatie ervan worden gedocumenteerd. Dit zijn details die een context vereisen om hun geldigheid en gedrag te bepalen. Als een taal bijvoorbeeld toelaat dat nieuwe types worden gedeclareerd, kan een CFG de namen van dergelijke types niet voorspellen, noch de manier waarop ze moeten worden gebruikt. Zelfs als een taal een voorgedefinieerde set van types heeft, vereist het afdwingen van correct gebruik meestal enige context. Een ander voorbeeld is duck typing, waarbij het type van een element kan veranderen afhankelijk van de context. Operator overloading is nog zo’n geval waar het juiste gebruik en de uiteindelijke functie bepaald worden op basis van de context. Java geeft een uitstekend voorbeeld, waar de ‘+’ operator zowel numerieke optelling als aaneenschakeling van strings is.

Hoewel er ook andere gegevensstructuren betrokken zijn bij de innerlijke werking van een compiler, vervult de AST een unieke functie. Tijdens de eerste fase, de syntaxis-analyse, produceert een compiler een parse tree. Deze parse tree kan worden gebruikt om bijna alle functies van een compiler uit te voeren door middel van syntax-gestuurde vertaling. Hoewel deze methode kan leiden tot een efficiëntere compiler, druist zij in tegen de software engineering principes van het schrijven en onderhouden van programma’s. Een ander voordeel dat de AST heeft boven een parse tree is de omvang, met name de kleinere hoogte van de AST en het kleinere aantal elementen.

DesignEdit

Het ontwerp van een AST hangt vaak nauw samen met het ontwerp van een compiler en de verwachte eigenschappen ervan.

De kerneisen omvatten het volgende:

• Variabele typen moeten worden behouden, evenals de plaats van elke declaratie in de broncode.
• De volgorde van uitvoerbare verklaringen moet expliciet worden weergegeven en goed worden gedefinieerd.
• Linkse en rechtse componenten van binaire bewerkingen moeten worden opgeslagen en correct worden geïdentificeerd.
• Identifiers en hun toegewezen waarden moeten worden opgeslagen voor toewijzingsverklaringen.

Deze vereisten kunnen worden gebruikt om de gegevensstructuur voor de AST te ontwerpen.

Sommige bewerkingen zullen altijd twee elementen vereisen, zoals de twee termen voor optelling. Sommige taalconstructies vereisen echter een willekeurig groot aantal kinderen, zoals argumentlijsten die vanuit de commandoregel aan programma’s worden doorgegeven. Dientengevolge moet een AST die wordt gebruikt om code weer te geven die in zo’n taal is geschreven, ook flexibel genoeg zijn om snel een onbekend aantal kinderen te kunnen toevoegen.

Om compiler verificatie te ondersteunen moet het mogelijk zijn om een AST te ontleden naar broncode vorm. De geproduceerde broncode moet bij hercompilatie voldoende lijken op het origineel qua uiterlijk en qua uitvoering identiek zijn.

UsageEdit

De AST wordt intensief gebruikt tijdens de semantische analyse, waarbij de compiler controleert op correct gebruik van de elementen van het programma en de taal. De compiler genereert tijdens de semantische analyse ook symbooltabellen op basis van de AST. Een volledige traversal van de boom maakt verificatie van de juistheid van het programma mogelijk.

Na verificatie van de juistheid dient de AST als basis voor codegeneratie. De AST wordt vaak gebruikt om een intermediaire representatie (IR) te genereren, soms een intermediaire taal genoemd, voor de codegeneratie.