Abstrakte syntakstræer i programmering: en komplet guide

Informatic Digital » Recursos » Abstrakte syntakstræer i programmering: en komplet guide

Abstrakte syntakstræer i programmering er et af de koncepter, der i starten lyder meget teoretiske, men når man først får styr på dem, indser man, at de er overalt: compilere, fortolkere , kodeanalyse, refaktoreringsværktøjer, selv i strukturerede dataforespørgselssprog. De er i bund og grund den måde, en maskine "forstår" strukturen af ​​et program ud over almindelig tekst.

Selvom de nogle gange forveksles med klassiske parsetræer, har abstrakte syntakstræer (AST'er) deres egne regler. Et abstrakt syntakstræ er ikke bare en flot tegning: det er en kompakt og veldesignet datastruktur, der eliminerer alt overflødigt fra konkret syntaks (parenteser, kommaer, redundante nøgleord osv.) og fokuserer på det væsentlige: hvilke operationer der udføres, på hvilke værdier og i hvilken rækkefølge.

Hvad er et abstrakt syntakstræ (AST) præcist?

I programmeringssprogsteori er et abstrakt syntakstræ (AST) en trælignende struktur, der repræsenterer syntaksen i et program, men i en forenklet form sammenlignet med et konkret parsetræ. Det indeholder den samme væsentlige information som et parsetræ, men organiseret på en mere kompakt og håndterbar måde.

Et parsetræ indeholder alle grammatikkens produktioner og alle terminalsymboler, inklusive parenteser, kommaer, semikolon og andre rent syntaktiske elementer. AST fjerner derimod disse detaljer, der ikke bidrager med semantisk betydning, og bevarer kun den logiske struktur af udtryk og sætninger.

Med hensyn til implementering består en AST normalt af nodeobjekter med en type , der angiver, hvilken slags syntaktisk konstruktion det er (konstant, identifikator, funktionsapplikation, binær operator osv.), og yderligere egenskaber, der beskriver dens indhold: værdi, navn, underordnede elementer, argumentliste osv.

Det smukke ved AST er, at det letter senere faser af compileren eller fortolkeren, såsom typekontrol, optimeringer eller kodegenerering , fordi det giver et rent overblik over programstrukturen uden syntaktisk støj.

Forskellen mellem et konkret syntakstræ og et abstrakt syntakstræ

For fuldt ud at forstå, hvad en AST bidrager med, er det nyttigt først at sammenligne det konkrete parsetræ med det abstrakte. Forestil dig en simpel grammatik, der genkender aritmetiske udtryk som "a + 4 * 5" . Det konkrete parsetræ afspejler nøjagtigt anvendelsen af ​​hver grammatikregel: ikke-terminale symboler, terminaler, parenteser, operatorer osv.

Dette særlige træ er normalt dybt og har mange mellemliggende noder, der kun tjener til at opretholde grammatikkens formelle struktur. For eksempel kan der være noder for "Udtryk", "Term", "Faktor" og derefter terminalsymboler som "+" , "*" , identifikatorer og tal. Hver produktion bliver en gren af ​​træet, hvilket øger den strukturelle kompleksitet.

Det abstrakte syntakstræ for det samme udtryk er derimod begrænset til at repræsentere de faktiske operationer og operander . I stedet for flere niveauer af "Udtryk" og "Term" kunne vi således have en rodknude, der repræsenterer addition, med to børn: til venstre en identifikator a og til højre en multiplikationsknude, hvis børn er værdierne 4 og 5. Rent grammatiske noder forsvinder, og dele af strukturen omordnes eller kondenseres.

Det betyder, at AST og det konkrete syntakstræ indeholder den samme semantiske information , men førstnævnte præsenterer den i en langt mere direkte og kompakt form. Denne kondensering er nøglen til at arbejde effektivt med kode i analyse- eller udførelsesværktøjer.

Træer og alfabeter med arity-funktion

For at formalisere disse træer fra et matematisk synspunkt bruges normalt ideen om et alfabet med en arity-funktion . I stedet for blot et sæt symboler defineres et alfabet, hvor hvert symbol er knyttet til et tal, der angiver, hvor mange børn det kan have i træet.

Et alfabet med en aritetsfunktion er uformelt et par bestående af et endeligt sæt symboler og en funktion, der tildeler hvert symbol et naturligt tal (inklusive nul). Dette tal angiver symbolets aritet: hvis det er 0, opfører symbolet sig som et blad; hvis det er 1, opfører det sig som en unær node; hvis det er 2, er det binært; og så videre. Det er også almindeligt at tillade symboler med variabel aritet for operatorer som argumentlister.

Symboler for arity 0 svarer til blade på træet (f.eks. konstanter eller identifikatorer). Symboler for arity 1 bruges til konstruktioner, der involverer et enkelt underudtryk. Symboler for arity 2 repræsenterer klassiske binære operationer såsom addition, multiplikation, tildeling osv. Og symboler for variabel arity tillader modelleringskonstruktioner, der accepterer et ubestemt antal undertræer, såsom et funktionskald med flere parametre.

Ud fra dette alfabet med arity kan mængden af ​​alle mulige træer defineres: startende med det tomme træ (når det tages i betragtning), tilføjelse af alle symboler for arity 0 og variabel, og induktiv udvidelse: hvis et symbol er k-ary, kan det placeres som den overordnede knude til k allerede konstruerede undertræer. Dette giver træsproget (eller termen) forbundet med alfabetet.

Træsprog og begrebet node

Mængden af ​​alle træer dannet med et alfabet og dets aritetsfunktion kaldes i denne sammenhæng et træsprog eller termsprog . Det er det tilsvarende, men for træstrukturer, til hvad Kleene-lukningen er for strenge.

Ligesom vi, når vi analyserer strenge, bruger udtrykket tokens til at henvise til forekomsten af ​​alfabetsymboler i en sekvens, bruger vi normalt udtrykket noder , når vi arbejder med træer . En node er i bund og grund en specifik forekomst af et alfabetsymbol med en enhed placeret på en bestemt position i træet.

Fra dette perspektiv er dette træsprog for noder, hvad et sæt strenge er for tokenforekomster. Hvert træ fortolkes som en struktur bygget trin for trin ud fra alfabetet, og noderne er de individuelle dele, der fysisk materialiserer dets symboler.

Denne måde at se på det er meget nyttig, når man designer parsere og AST-generatorer , fordi den giver mulighed for at ræsonnere om konstruktionsreglerne for disse træer på en måde, der er analog med strenggrammatik, men som arbejder direkte på hierarkiske strukturer.

Aritet af noder i en specifik AST: tilfældet med Egg

I mange undervisningsmaterialer går man fra teori til praktiske eksempler og bruger Egg- sproget til at illustrere konstruktionen og manipulationen af ​​AST'er. I denne sammenhæng anvendes flere hovedtyper af noder, hver med en veldefineret aritet , hvilket gør dem meget nemme at manipulere.

I en typisk Egg AST betragtes VALUE- noder som blade: de repræsenterer literaler såsom strenge eller tal. De har ingen underordnede værdier; de gemmer kun en værdi. På samme måde behandles WORD-noder , der bruges til identifikatorer (variabelnavne, funktionsnavne osv.), også som blade med en egenskab, der gemmer navnet.

Nøglenoden i Egg er APPLY- typen , som repræsenterer anvendelsen af ​​en funktion eller operator. Denne nodetype har to konceptuelle børn: et OPERATOR- barn , der peger på det udtryk, der anvendes; og et ARGS- barn , som faktisk er en speciel ARRAY-node, der er ansvarlig for at vedligeholde en samling af undertræer, et for hvert argument.

Arrays er derfor en naturlig måde at introducere variabel arity i AST: en APPLY har altid to komponenter (operator og argumentliste), men den interne liste kan indeholde nul, et eller mange undertræer afhængigt af det specifikke kald, der repræsenteres.

Detaljeret anatomi af AST-knuder i Egg

På implementeringsniveau repræsenteres Eggs AST-noder typisk som objekter med egenskaber , hvilket passer perfekt til sprog som JavaScript. Alle noder deler en fælles egenskab: `type` , som identificerer nodetypen (VALUE, WORD, APPLY, ARRAY osv.) og dermed den struktur, som resten af ​​objektet vil have.

VALUE-noder bruges til konstanter i en literal . De indeholder en egenskab, ofte kaldet value , hvor det tal eller den streng, de repræsenterer, er gemt. De har ingen yderligere underordnede værdier, fordi deres indhold er fuldstændigt beskrevet af den pågældende literal.

Ordnoder er reserveret til identifikatorer : variabelnavne, funktionsnavne, parameternavne og lignende. De har typisk en `name`- egenskab , der gemmer identifikatoren som en streng. Ligesom VALUE-noder fungerer de som blade i træet, da deres eneste formål er at angive dette navn.

Anvend-noder repræsenterer applikationer eller kald. De omfatter en operatoregenskab , som peger på det udtryk (en anden node), der anvendes, og en args- egenskab , som linker til en ARRAY-node. Sidstnævnte er en specifik node i AST'en, hvis formål er at indeholde applikationens argumentliste .

ARRAY-noden kan forstås som en struktureret beholder for andre noder, der repræsenterer en sekvens af undertræer. Fra et ARRAY-perspektiv introducerer den fleksibilitet, fordi den tillader kald uden argumenter, med ét argument eller med flere argumenter inden for den samme APPLY-sætning, uden at skulle ændre definitionen af ​​hovednodetypen.

Eksempel på AST: simpel applikation med én værdi

For at visualisere alt ovenstående, lad os tænke på repræsentationen af ​​en simpel instruktion, såsom en anvendelse af en funktion X med et enkelt argument 5. Den AST, der genereres af parseren, svarer til et term konstrueret med VALUE-, WORD- og APPLY-noder , i overensstemmelse med Eggs regler.

På et konceptuelt niveau ville vi have en APPLY- node i roden. Dens operatoregenskab ville pege på en WORD-node ved navn X, og dens args-egenskab ville referere til en ARRAY-node, der indeholder et enkelt element: en VALUE-node med den numeriske værdi 5. På denne måde afspejler strukturen tydeligt, hvem der anvendes på, og hvad der anvendes på.

Hvis vi ville gøre alle attributterne eksplicitte, kunne vi skrive en mere detaljeret notation, der viser type, operator, argumenter, navn og værdi. Denne mere detaljerede notation er meget nyttig til fejlfinding af parseren eller til at forstå, hvordan et tekstligt udtryk oversættes til et træobjekt i fortolkeren.

I implementeringer i den virkelige verden serialiseres dette træ typisk som JSON for nem lagring, transmission eller inspektion. Faktisk giver værktøjer og moduler, såsom evm2term- pakken i npm-økosystemet, kompakte repræsentationer af disse AST'er for nemmere analyse eller transformation.

Eksempel på AST: indlejret addition og multiplikation

Et andet typisk tilfælde er et lidt mere komplekst udtryk, såsom "+(a, *(4, 5))" . Her har vi en additionsoperation, hvis første argument er identifikatoren a, og hvis andet argument er resultatet af at gange 4 med 5. Den AST, der er resultatet af dette udtryk, afspejler den indbyggede struktur.

Ved træets rod ville vi igen have en APPLY-node, der repræsenterer additionsoperationen. Dens operator ville være en WORD-node med navnet "+", mens dens argumenter ville være i en ARRAY-node med to elementer: det første, et WORD med navnet "a"; det andet, en anden APPLY-node, der repræsenterer multiplikation.

Den anden APPLY ville have et WORD med navnet "*" som operator og et ARRAY med to VALUE-noder som argumenter: en med værdien 4 og den anden med værdien 5. Set som en helhed viser strukturen tydeligt, at evalueringsrækkefølgen består af at gange 4 med 5 og derefter lægge resultatet til a.

Hvis vi udvider notationen til at omfatte alle attributter, ville vi se typerne af alle noder, deres navne eller specifikke værdier og relationerne mellem dem. Denne eksplicitte beskrivelse svarer til den faktiske implementering i Egg-fortolkeren, hvor hver node er et objekt med de førnævnte egenskaber.

Trægrammatik og parsergrammatik

Måden, hvorpå disse AST'er genereres, er ikke vilkårlig: den er baseret på det, der kaldes en trægrammatik . I en typisk formulering defineres en sådan grammatik som en firedobling bestående af et alfabet med aritet, et endeligt sæt syntaktiske (ikke-terminale) variabler, et endeligt sæt produktionsregler og et startsymbol.

I hver produktionsregel erstattes en variabel af et træ, hvis rod er et symbol for alfabetet med arity, og hvis børn til gengæld er variabler eller allerede definerede træer. Denne struktur minder om klassiske regulære eller kontekstfri grammatikker, men er tilpasset til direkte generering af træer i stedet for strenge af symboler.

Relateret til den mere formelle definition er den specifikke grammatik, som Eggs parser bruger til at producere sine træer. Denne grammatik, som normalt præsenteres uformelt i dokumentationen, beskriver præcis, hvilke kombinationer af nøgleord, operatorer, parenteser osv. der accepteres i sproget, og hvordan de oversættes til noder af typen VALUE, WORD, APPLY og ARRAY.

Denne trægrammatik kan ses som et særtilfælde af, hvad der i litteraturen er kendt som en regulær trægrammatik . Ideen er at have veldefinerede regler for at konvertere en sekvens af inputtokens til en struktureret AST, der derefter kan fortolkes eller kompileres.

Dewey-notation: koordinater i et træ

Når vi har AST, skal vi ofte referere til specifikke undertræer : for eksempel det andet argument i en funktion, operatoren i et udtryk osv. En meget elegant måde at gøre dette på er den såkaldte Dewey Decimal-notation, som låner den ordning, der bruges til at nummerere sektioner og underafsnit i dokumenter.

I denne notation, startende fra et træ t, betegnes et undertræ med en streng af tal adskilt af punktummer . Hvert tal angiver positionen af ​​et undertræ (normalt startende ved 1), og sekvensen går ned i træet. Således refererer et udtryk som t/2.1.3 til det tredje undertræ af det første undertræ af det andet undertræ af t.

Den induktive definition af denne notation er enkel: den tomme streng refererer til hele selve træet; hvis en streng består af et tal efterfulgt af flere tal adskilt af punktummer, fortolkes den ved først at tage det underordnede undertræ svarende til det angivne indeks og derefter anvende den samme logik rekursivt på resten af ​​strengen.

Hvis vi for eksempel har et træ t, der repræsenterer et udtryk som "+(a, *(4,5))", med en rodknude APPLY til addition, et barn WORD med navnet "+" og et andet barn APPLY til multiplikation, kan vi identificere specifikke positioner. Således kan t/1 være WORD-noden med operatoren "+", t/2.1 identifikatoren "a", og t/2.2.2.1 VALUE-noden med værdien 4, hvis vi nummererer børnene korrekt.

Denne måde at angive "koordinater" i en AST er meget nyttig til at udpege specifikke placeringer, når man rapporterer fejl, navigerer i træet eller anvender lokale transformationer på specifikke noder uden tvetydighed.

Ækvivalente notationer i programmering og værktøjer

Ideen bag Deweys notation er ikke eksklusiv for træteori; faktisk optræder den gentagne gange i mange praktiske notationer , som vi bruger dagligt i programmering og struktureret datahåndtering, selvom vi ikke altid er bevidste om den.

Når vi skriver udtryk med punktumoperatoren i et programmeringssprog , såsom object.property.subproperty, gør vi noget meget lignende: vi gennemløber et træ af indbyggede objekter og vælger et barn i hvert trin efter navn i stedet for efter positionsnummer. Fra en rodnode går vi ned til flere interne noder.

Det samme mønster ses i Unix-lignende filsystemer, hvor skråstregoperatoren (/) bruges til at adskille mapper: /src/js/tutu.js beskriver en sti fra roden af ​​filsystemet til en specifik ressource, der krydser successive niveauer i en træstruktur.

I strukturerede dokumenters verden bruger sprog som XPath meget lignende notationer til at vælge noder i et XML-træ. En forespørgsel som "A//B/*" vælger det første barn (uanset navnet) af hvert element B, der er en efterkommer af et element A i den relevante position i forhold til den aktuelle kontekst, ved hjælp af enkelte og dobbelte skråstreger for at angive dybdeniveauer.

Et andet velkendt værktøj, sproget jq , bruger et parallelt system til at navigere i JSON-strukturer, hvilket muliggør valg af underobjekter gennem sammensatte stier, filtre og udtryk. Alle disse notationer er simpelthen forskellige måder at udtrykke stier i et træ på , meget i tråd med Dewey Decimal-notation, men tilpasset deres respektive domæner.

Parse træer i lingvistik og programmering

Ud over compilernes verden bruges syntakstræer også i lingvistik til at repræsentere sætningsstruktur. Der kaldes de afledningstræer eller parsetræer, som viser, hvordan en sætning er opdelt i sætninger, ord og grammatiske kategorier.

I disse træer, ligesom i programmering, finder vi tre grundlæggende typer af noder: en rodknude , som repræsenterer den komplette sætning eller den globale struktur; interne eller forgrenende noder, som fungerer som forældrenoder og gruppeundergrupper af sætningen; og bladnoder, som normalt svarer til de specifikke ord, der vises i inputstrengen.

Rodnoden er unik: hele træstrukturen hænger fra den. Forgreningsnoder er placeret umiddelbart under roden eller andre overordnede noder og tjener til hierarkisk at organisere delene af sætningen eller programmet. Bladknoder findes derimod på det laveste niveau af træet og har ingen underordnede noder, hvilket lukker forgreningsstrukturen.

Disse træer betragtes som effektive pædagogiske værktøjer, fordi de hjælper med at opdele komplekse sætninger i håndterbare elementer. Det samme gælder programmering: en velkonstrueret AST giver dig mulighed for at se med et hurtigt blik, hvilke operationer der er kædet sammen, hvilke udtryk der er indlejrede, og hvordan evalueringen forløber.

Afhængigt af analysens formål kan vi finde forskellige typer analysetræer . Nogle understreger afhængigheder mellem ord eller komponenter (for eksempel hvem afhænger af hvem i en sætning), mens andre fokuserer på gruppering i sætninger eller bestanddele, hvilket resulterer i to hovedfamilier.

Syntakstræer efter afhængighed og efter valgkreds

En af de mest kendte typer er det afhængighedsbaserede syntakstræ . I denne variant behandles alle ord i sætningen eller alle relevante elementer som bladnoder, og forbindelserne mellem dem angiver direkte afhængighedsrelationer (for eksempel et hovedverbum og dets subjekt). Som et resultat produceres der ofte træer med færre noder end i andre ordninger.

Denne enkelhed gør dem særligt praktiske for begyndere og til visse sprogbehandlingsopgaver, fordi strukturen fokuserer på, hvem der er afhængig af hvem, uden at introducere så mange mellemliggende noder. Anvendt i programmering er ideen kun at holde sig til de væsentlige relationer og udelade grammatiske udsmykninger.

I den anden ende har vi syntakstræer baseret på konstituenter eller bestanddele, som skelner mellem rodnoder, interne forgreningsnoder og bladnoder og gør alle relevante grupperinger synlige. Disse træer indeholder normalt flere noder og afspejler sætningens eller programmets hierarkiske struktur mere detaljeret.

Almindeligt set skabeloner til valgkredstræer viser lange sætninger med adskillige bladnoder, flere niveauer af forgrening og en veldefineret rodnode. De er især nyttige til at dissekere komplekse sætninger eller programmer med flere lag af indbyggede strukturer.

I både afhængigheds- og konstituenstræer er eksempler og visuelle ressourcer tilgængelige som skabeloner, så du blot kan udfylde noderne med de ønskede oplysninger. Dette sparer tid og undgår at skulle designe diagrammet fra bunden hver gang du vil illustrere en struktur.

Praktiske anvendelser og værktøjer relateret til AST

AST'er er ikke blot et teoretisk koncept: de bruges aktivt i en lang række hverdagsværktøjer af alle, der arbejder med kode. Compilere, fortolkere, minifikatorer, kodeformatterere og statiske analysatorer er næsten altid afhængige af en AST til at udføre deres funktion.

En typisk compiler tager kildekoden, tokeniserer den, parser den og genererer et abstrakt syntakstræ. Derfra udfører den semantiske kontroller (typer, variabelt omfang, forkert brug af konstruktioner) og anvender kodeoptimering ved at gennemgå og transformere AST'en, før den producerer maskinkode eller bytekode.

Værktøjer som linters eller formateringsværktøjer fungerer også på AST: de analyserer strukturen for at opdage problematiske mønstre, dårlig praksis eller uoverensstemmelser og foreslår ændringer, der bevarer træets semantiske struktur , men justerer præsentationen af ​​koden.

I JavaScript-økosystemet er der for eksempel flere biblioteker, der eksponerer AST i JSON-format, hvilket gør det nemmere for andre værktøjer at bruge det til at udføre refactoring, generere automatisk dokumentation eller skabe visualiseringer af strukturen i komplekse programmer.

Selv inden for noget mere specialiserede områder, såsom instrumentering til måling af testdækning eller transformation af kildekode til andre sprog, er AST fundamentet for mange moderne løsninger, da det muliggør arbejde på et meget behageligt abstraktionsniveau mellem rå tekst og maskinkode.

Samlet set er abstrakte syntakstræer den centrale del, der forbinder et sprogs formelle grammatik, dets interne repræsentation i compileren eller fortolkeren, og de avancerede værktøjer, vi bruger til at skrive, analysere og transformere kode sikkert og effektivt. Forståelse af, hvordan de er konstrueret, hvordan man navigerer i dem (med koncepter som Dewey Decimal notation), og hvilke typer noder der er involveret (VALUE, WORD, APPLY, faste eller variable arity-strukturer osv.), hjælper os med at se meget tydeligere, hvad maskinen rent faktisk laver, når den behandler et program.