Free Press

Abstrakta syntaxträd är datastrukturer som ofta används i kompilatorer för att representera programkodens struktur. Ett AST är vanligtvis resultatet av syntaxanalysfasen i en kompilator. Det fungerar ofta som en mellanliggande representation av programmet genom flera steg som kompilatorn kräver, och har en stark inverkan på kompilatorns slutresultat.

MotiveringRedigera

Ett AST har flera egenskaper som underlättar de fortsatta stegen i kompileringsprocessen:

• Ett AST kan redigeras och förbättras med information som egenskaper och annotationer för varje element som det innehåller. En sådan redigering och annotering är omöjlig med ett programs källkod, eftersom det skulle innebära att man ändrar den.
• Vid jämförelse med källkoden innehåller ett AST inte obehövlig interpunktion och avgränsare (hakparenteser, semikolon, parenteser etc.).
• Ett AST innehåller vanligen extra information om programmet, på grund av de på varandra följande analysstegen som kompilatorn gör. Det kan till exempel lagra positionen för varje element i källkoden, vilket gör det möjligt för kompilatorn att skriva ut användbara felmeddelanden.

AST:er behövs på grund av den inneboende karaktären hos programmeringsspråk och deras dokumentation. Språk är ofta tvetydiga till sin natur. För att undvika denna tvetydighet specificeras programmeringsspråk ofta som en kontextfri grammatik (CFG). Det finns dock ofta aspekter av programmeringsspråk som en CFG inte kan uttrycka, men som är en del av språket och dokumenteras i dess specifikation. Detta är detaljer som kräver ett sammanhang för att bestämma deras giltighet och beteende. Om ett språk till exempel tillåter att nya typer deklareras kan en CFG inte förutsäga namnen på sådana typer eller hur de ska användas. Även om ett språk har en fördefinierad uppsättning typer krävs det vanligtvis en viss kontext för att säkerställa korrekt användning. Ett annat exempel är duck typing, där typen av ett element kan ändras beroende på sammanhanget. Överladdning av operatörer är ännu ett fall där korrekt användning och slutlig funktion bestäms utifrån sammanhanget. Java ger ett utmärkt exempel, där operatören ”+” är både numerisk addition och sammanlänkning av strängar.

Och om det finns andra datastrukturer som är involverade i en kompilators inre arbete, utför AST en unik funktion. Under det första steget, syntaxanalyssteget, producerar en kompilator ett parseträd. Detta parseträd kan användas för att utföra nästan alla funktioner hos en kompilator med hjälp av syntaxriktad översättning. Även om denna metod kan leda till en effektivare kompilator går den emot de programvarutekniska principerna för att skriva och underhålla program. En annan fördel som AST har jämfört med ett parseträd är storleken, särskilt den mindre höjden på AST och det mindre antalet element.

DesignEdit

Designen av ett AST är ofta nära kopplad till designen av en kompilator och dess förväntade funktioner.

Kärnkraven omfattar följande:

• Variabeltyper måste bevaras, liksom platsen för varje deklaration i källkoden.
• Förordningen av körbara påståenden måste uttryckligen representeras och vara väldefinierad.
• Vänster- och högerkomponenter av binära operationer måste lagras och identifieras korrekt.
• Identifierare och deras tilldelade värden måste lagras för tilldelningsangivelser.

Dessa krav kan användas för att utforma datastrukturen för AST:et.

Vissa operationer kommer alltid att kräva två element, t.ex. de två termerna för addition. Vissa språkkonstruktioner kräver dock ett godtyckligt stort antal barn, t.ex. argumentlistor som skickas till program från kommandosystemet. Därför måste ett AST som används för att representera kod skriven i ett sådant språk också vara tillräckligt flexibelt för att snabbt kunna lägga till en okänd mängd barn.

För att stödja verifiering av kompilatorer bör det vara möjligt att upplösa ett AST till källkodsform. Den källkod som produceras bör vara tillräckligt lik originalet till utseendet och identisk i utförandet vid omkompilering.

UsageEdit

AST används intensivt under semantisk analys, där kompilatorn kontrollerar att programmets och språkets beståndsdelar används på ett korrekt sätt. Kompilatorn genererar också symboltabeller baserade på AST under den semantiska analysen. En fullständig traversering av trädet gör det möjligt att verifiera programmets korrekthet.

När korrektheten har verifierats tjänar AST:et som bas för kodgenerering. AST används ofta för att generera en mellanliggande representation (IR), ibland kallad ett mellanliggande språk, för kodgenerering.