Abstrakte syntaksetræer er datastrukturer, der i vid udstrækning anvendes i compilere til at repræsentere strukturen af programkode. Et AST er normalt resultatet af syntaksanalysefasen i en compiler. Det tjener ofte som en mellemliggende repræsentation af programmet gennem flere faser, som compileren kræver, og har en stærk indflydelse på compilerens endelige output.
MotivationRediger
Et AST har flere egenskaber, der hjælper de yderligere trin i kompileringsprocessen:
- Et AST kan redigeres og forbedres med oplysninger såsom egenskaber og annotationer for hvert element, det indeholder. En sådan redigering og annotation er umulig med et programs kildekode, da det ville indebære en ændring af den.
- I forhold til kildekoden indeholder en AST ikke uvæsentlig tegnsætning og afgrænsere (parenteser, semikolon, parenteser osv.).
- En AST indeholder normalt ekstra oplysninger om programmet på grund af kompilerens på hinanden følgende analysefaser. Den kan f.eks. gemme placeringen af hvert element i kildekoden, hvilket gør det muligt for compileren at udskrive nyttige fejlmeddelelser.
AST’er er nødvendige på grund af programmeringssprogenes iboende natur og deres dokumentation. Sprog er ofte tvetydige af natur. For at undgå denne tvetydighed er programmeringssprog ofte specificeret som en kontekstfri grammatik (CFG). Der er imidlertid ofte aspekter af programmeringssprog, som en CFG ikke kan udtrykke, men som er en del af sproget og er dokumenteret i dets specifikation. Det er detaljer, som kræver en kontekst for at bestemme deres gyldighed og adfærd. Hvis et sprog f.eks. tillader, at der kan deklareres nye typer, kan en CFG ikke forudsige navnene på sådanne typer eller den måde, hvorpå de skal anvendes. Selv hvis et sprog har et foruddefineret sæt typer, kræver det normalt en vis kontekst at håndhæve korrekt brug. Et andet eksempel er duck typing, hvor typen af et element kan ændre sig afhængigt af konteksten. Operatoroverloading er endnu et tilfælde, hvor korrekt brug og slutfunktion bestemmes ud fra konteksten. Java giver et glimrende eksempel, hvor operatoren “+” både er numerisk addition og sammenkædning af strenge.
Og selv om der er andre datastrukturer involveret i en compilers indre arbejde, udfører AST’en en unik funktion. I den første fase, syntaksanalysefasen, producerer en compiler et parse tree. Dette parse tree kan bruges til at udføre næsten alle en compilers funktioner ved hjælp af syntaksrettet oversættelse. Selv om denne metode kan føre til en mere effektiv compiler, er den i strid med de softwaretekniske principper for skrivning og vedligeholdelse af programmer. En anden fordel, som AST’en har i forhold til et parse tree, er størrelsen, især AST’ens mindre højde og det mindre antal elementer.
DesignEdit
Designet af en AST er ofte tæt forbundet med designet af en compiler og dens forventede funktioner.
Kernekravene omfatter følgende:
- Variabeltyper skal bevares, og det samme gælder placeringen af hver enkelt deklaration i kildekoden.
- Rækkefølgen af eksekverbare erklæringer skal være eksplicit repræsenteret og veldefineret.
- Venstre og højre komponent i binære operationer skal gemmes og identificeres korrekt.
- Identifikatorer og deres tildelte værdier skal gemmes for tildelingserklæringer.
Disse krav kan bruges til at designe datastrukturen for AST’en.
Nogle operationer vil altid kræve to elementer, f.eks. de to udtryk for addition. Nogle sprogkonstruktioner kræver imidlertid et vilkårligt stort antal børn, f.eks. argumentlister, der overføres til programmer fra kommandoskallen. Som følge heraf skal en AST, der bruges til at repræsentere kode skrevet i et sådant sprog, også være fleksibel nok til at muliggøre hurtig tilføjelse af et ukendt antal børn.
For at understøtte compilerverificering bør det være muligt at unparse en AST til kildekodeform. Den producerede kildekode skal være tilstrækkelig lig originalen i udseende og identisk i udførelse ved genkompilering.
UsageEdit
AST’en anvendes intensivt under den semantiske analyse, hvor compileren kontrollerer, om programmets og sprogets elementer anvendes korrekt. Compileren genererer også symboltabeller baseret på AST’en under den semantiske analyse. En fuldstændig traversering af træet gør det muligt at verificere programmets korrekthed.
Når korrektheden er verificeret, tjener AST’en som grundlag for kodegenerering. AST’en bruges ofte til at generere en mellemliggende repræsentation (IR), undertiden kaldet et mellemliggende sprog, til kodegenerering.