Abstrakt syntaks træ - Abstract syntax tree

For træer, der bruges i lingvistik, se Parse -træ .
Et abstrakt syntakstræ for følgende kode til den euklidiske algoritme :
mens b ≠ 0 
  hvis a> b 
    a: = a - b 
  ellers
     b: = b - en 
retur a

I datalogi er et abstrakt syntakstræ ( AST ), eller bare syntakstræ , en trærepræsentation af den abstrakte syntaktiske struktur af tekst (ofte kildekode ) skrevet i et formelt sprog . Hver knude i træet angiver en konstruktion, der forekommer i teksten.

Syntaksen er "abstrakt" i den forstand, at den ikke repræsenterer hver eneste detalje, der optræder i den virkelige syntaks, men derimod kun de strukturelle eller indholdsrelaterede detaljer. For eksempel er gruppering af parenteser implicit i træstrukturen, så disse behøver ikke at blive repræsenteret som separate noder. På samme måde kan en syntaktisk konstruktion som en if-condition-then-sætning betegnes ved hjælp af en enkelt knude med tre grene.

Dette adskiller abstrakte syntakstræer fra konkrete syntakstræer, traditionelt udpegede parsetræer . Parsetræer bygges typisk af en parser under kildekodens oversættelse og kompilering . Når den er bygget, tilføjes yderligere information til AST ved hjælp af efterfølgende behandling, f.eks. Kontekstuel analyse .

Abstrakte syntakstræer bruges også i programanalyser og programtransformationssystemer .

Ansøgning i kompilatorer

Abstrakte syntakstræer er datastrukturer, der i vid udstrækning bruges i kompilatorer til at repræsentere strukturen af ​​programkode. En AST er normalt resultatet af syntaksanalysefasen af en kompilator. Det fungerer ofte som en mellemrepræsentation af programmet gennem flere faser, som kompilatoren kræver, og har stor indflydelse på kompilatorens endelige output.

Motivering

En AST har flere egenskaber, der hjælper de yderligere trin i kompileringsprocessen:

  • En AST kan redigeres og forbedres med oplysninger såsom egenskaber og annoteringer for hvert element, den indeholder. Sådan redigering og annotering er umulig med kildekoden til et program, da det ville indebære at ændre det.
  • Sammenlignet med kildekoden inkluderer en AST ikke ubetydelig tegnsætning og afgrænsninger (seler, semikolon, parenteser osv.).
  • En AST indeholder normalt ekstra information om programmet på grund af de på hinanden følgende trin i analysen fra kompilatoren. For eksempel kan det gemme placeringen af ​​hvert element i kildekoden, så kompilatoren kan udskrive nyttige fejlmeddelelser.

AST'er er nødvendige på grund af programmeringssprogets iboende karakter og deres dokumentation. Sprog er ofte tvetydige af natur. For at undgå denne tvetydighed er programmeringssprog ofte specificeret som en kontekstfri grammatik (CFG). Imidlertid er der ofte aspekter ved programmeringssprog, som en CFG ikke kan udtrykke, men er en del af sproget og er dokumenteret i dens specifikation. Dette er detaljer, der kræver en kontekst for at bestemme deres gyldighed og adfærd. For eksempel, hvis et sprog tillader, at nye typer deklareres, kan en CFG ikke forudsige navnene på sådanne typer eller måden, de skal bruges på. Selvom et sprog har et foruddefineret sæt typer, kræver håndhævelse af korrekt brug normalt en vis kontekst. Et andet eksempel er andetypning , hvor typen af ​​et element kan ændre sig afhængigt af kontekst. Operatøroverbelastning er endnu et tilfælde, hvor korrekt brug og slutfunktion bestemmes ud fra konteksten. Java giver et glimrende eksempel, hvor '+' operatoren er både numerisk tilføjelse og sammenkædning af strenge.

Selvom der er andre datastrukturer involveret i en kompilers indre arbejde, udfører AST en unik funktion. I løbet af den første fase, syntaksanalysestadiet , producerer en kompilator et parsetræ. Dette parsetræ kan bruges til at udføre næsten alle funktioner i en kompilator ved hjælp af syntaksstyret oversættelse. Selvom denne metode kan føre til en mere effektiv kompilator, strider den imod de software engineering -principper for at skrive og vedligeholde programmer. En anden fordel, som AST har i forhold til et parsetræ, er størrelsen, især AST's mindre højde og det mindre antal elementer.

Design

Designet af en AST er ofte tæt forbundet med designet af en kompilator og dens forventede funktioner.

Kernekrav omfatter følgende:

  • Variable typer skal bevares, samt placeringen af ​​hver deklaration i kildekoden.
  • Rækkefølgen af ​​eksekverbare udsagn skal være eksplicit repræsenteret og veldefineret.
  • Venstre og højre komponenter i binære operationer skal lagres og identificeres korrekt.
  • Identifikatorer og deres tildelte værdier skal gemmes til opgørelseserklæringer.

Disse krav kan bruges til at designe datastrukturen for AST.

Nogle operationer kræver altid to elementer, f.eks. De to udtryk for tilføjelse. Nogle sprogkonstruktioner kræver imidlertid et vilkårligt stort antal børn, såsom argumentlister, der sendes til programmer fra kommandoskallen . Som følge heraf skal en AST, der bruges til at repræsentere kode skrevet på et sådant sprog, også være fleksibel nok til hurtigt at tilføje en ukendt mængde børn.

For at understøtte compiler -verifikation bør det være muligt at adskille en AST til kildekodeform. Den producerede kildekode skal være tilstrækkeligt identisk med originalen i udseende og identisk i udførelse ved rekompilering.

Anvendelse

AST bruges intensivt under semantisk analyse , hvor kompilatoren tjekker for korrekt brug af elementerne i programmet og sproget. Kompilatoren genererer også symboltabeller baseret på AST under semantisk analyse. En komplet gennemgang af træet muliggør verifikation af programmets korrekthed.

Efter at have verificeret korrektheden fungerer AST som basis for kodegenerering. AST bruges ofte til at generere en mellemrepræsentation (IR), undertiden kaldet et mellemliggende sprog , til kodegenerering.

Se også

Referencer

  • Denne artikel er baseret på materiale hentet fra Free On-line Dictionary of Computing før den 1. november 2008 og indarbejdet under "relicensering" -betingelserne i GFDL , version 1.3 eller nyere.

Yderligere læsning

  • Jones, Joel. "Abstrakte syntaks træimplementeringsidiomer" (PDF) . Citer journal kræver |journal=( hjælp ) (oversigt over AST -implementering i forskellige sprogfamilier)
  • Neamtiu, Iulian; Foster, Jeffrey S .; Hicks, Michael (17. maj 2005). Forståelse af kildekodeudvikling ved hjælp af abstrakt syntakstræ Matching . MSR'05. Saint Louis, Missouri: ACM. CiteSeerX  10.1.1.88.5815 .
  • Baxter, Ira D .; Yahin, Andrew; Moura, Leonardo; Sant 'Anna, Marcelo; Bier, Lorraine (16. - 19. november 1998). Klonopdagelse ved hjælp af abstrakte syntaktræer (PDF) . Procedurer i ICSM'98 . Bethesda, Maryland: IEEE .
  • Fluri, Beat; Würsch, Michael; Pinzger, Martin; Gall, Harald C. "Ændringsdestillering: Trædifferentiering for finkornet kildekodeskift-ekstraktion" (PDF) . Citer journal kræver |journal=( hjælp )( direkte link til PDF )
  • Würsch, Michael. Forbedring af abstrakt syntaks Træbaseret kildekode Ændringsdetektion (Diplomafhandling).
  • Falleri, Jean-Rémy; Morandat, Floréal; Blanc, Xavier; Martinez, Matias; Monperrus, Martin. Finkornet og præcis kildekodeforskel (PDF) . Procedurer fra ASE 2014 . doi : 10.1145/2642937.2642982 .
  • Lucas, Jason. "Tanker om Visual C ++ Abstract Syntax Tree (AST)" .

eksterne links