Abstrakte syntakstrær i programmering: en komplett guide

Informatec Digital » Ressurser » Abstrakte syntakstrær i programmering: En komplett guide

Abstrakte syntakstrær i programmering er et av de konseptene som i utgangspunktet høres svært teoretiske ut, men når du først får taket på dem, innser du at de er overalt: kompilatorer, tolker , kodeanalyse, refaktoreringsverktøy, selv i strukturerte dataspørrespråk. De er i hovedsak måten en maskin "forstår" strukturen til et program utover ren tekst.

Selv om de noen ganger forveksles med klassiske parsetrær, har abstrakte syntakstrær (AST-er) sine egne regler. Et abstrakt syntakstre er ikke bare en pen tegning: det er en kompakt og godt designet datastruktur som eliminerer alt overflødig fra konkret syntaks (parenteser, komma, overflødige nøkkelord osv.) og fokuserer på det essensielle: hvilke operasjoner som utføres, på hvilke verdier og i hvilken rekkefølge.

Hva er egentlig et abstrakt syntakstre (AST)?

I programmeringsspråkteori er et abstrakt syntakstre (AST) en trelignende struktur som representerer syntaksen til et program, men i en forenklet form sammenlignet med et konkret parsetre. Det inneholder den samme essensielle informasjonen som et parsetre, men organisert på en mer kompakt og håndterbar måte.

Et parsetre inneholder alle grammatikkens produksjoner og alle terminalsymboler, inkludert parenteser, komma, semikolon og andre rent syntaktiske elementer. AST, derimot, fjerner disse detaljene som ikke bidrar med semantisk mening og beholder bare den logiske strukturen til uttrykk og setninger.

Når det gjelder implementering, består en AST vanligvis av nodeobjekter med en type som indikerer hva slags syntaktisk konstruksjon det er (konstant, identifikator, funksjonsapplikasjon, binær operator osv.), og tilleggsegenskaper som beskriver innholdet: verdi, navn, barn, argumentliste og så videre.

Det fine med AST er at det forenkler senere faser av kompilatoren eller tolken, for eksempel typesjekk, optimaliseringer eller kodegenerering , fordi det gir en ren oversikt over programstrukturen uten syntaktisk støy.

Forskjellen mellom et konkret syntakstre og et abstrakt syntakstre

For å forstå hva en AST bidrar med, er det nyttig å først sammenligne det konkrete parsetreet med det abstrakte. Tenk deg en enkel grammatikk som gjenkjenner aritmetiske uttrykk som "a + 4 * 5" . Det konkrete parsetreet gjenspeiler nøyaktig anvendelsen av hver grammatikkregel: ikke-terminale symboler, terminaler, parenteser, operatorer osv.

Dette bestemte treet er vanligvis dypt og har mange mellomliggende noder som kun tjener til å opprettholde den formelle strukturen i grammatikken. For eksempel kan det være noder for «Uttrykk», «Term», «Faktor», og deretter terminalsymboler som «+» , «*» , identifikatorer og tall. Hver produksjon blir en gren av treet, noe som øker den strukturelle kompleksiteten.

Det abstrakte syntakstreet for det samme uttrykket er derimot begrenset til å representere de faktiske operasjonene og operandene . I stedet for flere nivåer av "Uttrykk" og "Term", kan vi derfor ha en rotnode som representerer addisjon, med to barn: til venstre en identifikator a og til høyre en multiplikasjonsnode hvis barn er verdiene 4 og 5. Rent grammatiske noder forsvinner, og deler av strukturen blir omorganisert eller kondensert.

Dette betyr at AST og det konkrete syntakstreet inneholder den samme semantiske informasjonen , men førstnevnte presenterer den i en mye mer direkte og kompakt form. Denne kondenseringen er nøkkelen til å jobbe effektivt med kode i analyse- eller utførelsesverktøy.

Trær og alfabeter med arity-funksjon

For å formalisere disse trærne fra et matematisk synspunkt brukes vanligvis ideen om et alfabet med en aritetsfunksjon . I stedet for bare et sett med symboler, defineres et alfabet der hvert symbol er assosiert med et tall som angir hvor mange barn det kan ha i treet.

Et alfabet med en aritetsfunksjon er, uformelt, et par som består av et endelig sett med symboler og en funksjon som tilordner hvert symbol et naturlig tall (inkludert null). Dette tallet indikerer symbolets aritet: hvis det er 0, oppfører symbolet seg som et blad; hvis det er 1, oppfører det seg som en unær node; hvis det er 2, er det binært; og så videre. Det er også vanlig å tillate symboler med variabel aritet for operatorer som argumentlister.

Symboler for arity 0 korresponderer med blader på treet (for eksempel konstanter eller identifikatorer). Symboler for arity 1 brukes for konstruksjoner som involverer et enkelt barnuttrykk. Symboler for arity 2 representerer klassiske binære operasjoner som addisjon, multiplikasjon, tildeling osv. Og symboler for variabel arity tillater modelleringskonstruksjoner som aksepterer et ubestemt antall undertrær, for eksempel et funksjonskall med flere parametere.

Fra dette alfabetet med arity kan settet med alle mulige trær defineres: startende med det tomme treet (når det tas i betraktning), legg til alle symbolene for arity 0 og variabel, og utvide induktivt: hvis et symbol er k-ary, kan det plasseres som foreldrenoden til k allerede konstruerte undertrær. Dette gir trespråket (eller termen) assosiert med alfabetet.

Trespråk og forestillingen om en node

Mengden av alle trær dannet med et alfabet og dets aritetsfunksjon kalles i denne sammenhengen et trespråk eller termspråk . Det er ekvivalenten, men for trestrukturer, av det Kleene-lukkingen er for strenger.

Akkurat som vi bruker begrepet tokens for å referere til forekomstene av alfabetsymboler i en sekvens når vi analyserer strenger, bruker vi vanligvis begrepet noder når vi arbeider med trær . En node er i hovedsak en spesifikk forekomst av et alfabetsymbol med en ritet plassert på en bestemt posisjon i treet.

Fra dette perspektivet er dette trespråket for noder det samme som et sett med strenger er for tokenforekomster. Hvert tre tolkes som en struktur bygget trinn for trinn fra alfabetet, og nodene er de individuelle delene som fysisk materialiserer symbolene.

Denne måten å se det på er veldig nyttig når man designer parsere og AST-generatorer , fordi den tillater resonnering om konstruksjonsreglene for disse trærne på en måte som er analog med strenggrammatikk, men som arbeider direkte på hierarkiske strukturer.

Aritet av noder i en spesifikk AST: tilfellet med Egg

Mange undervisningsmateriell bruker Egg- språket for å illustrere konstruksjon og manipulering av AST-er, og går fra teori til praktiske eksempler. I denne sammenhengen brukes flere hovedtyper noder, hver med en veldefinert aritet , noe som gjør dem svært enkle å manipulere.

I en typisk Egg AST regnes VALUE- noder som blader: de representerer litteraler som strenger eller tall. De har ingen underordnede verdier; de lagrer bare en verdi. På samme måte behandles WORD-noder , som brukes til identifikatorer (variabelnavn, funksjonsnavn osv.), også som blader med en egenskap som lagrer navnet.

Nøkkelnoden i Egg er APPLY- typen , som representerer anvendelsen av en funksjon eller operator. Denne nodetypen har to konseptuelle barn: et OPERATOR- barn som peker på uttrykket som brukes; og et ARGS- barn , som faktisk er en spesiell ARRAY-node som er ansvarlig for å vedlikeholde en samling av undertrær, ett for hvert argument.

Arrayer er derfor en naturlig måte å introdusere variabel arity i AST: en APPLY har alltid to komponenter (operator og argumentliste), men den interne listen kan inneholde null, ett eller mange undertrær avhengig av det spesifikke kallet som representeres.

Detaljert anatomi av AST-knutene i Egg

På implementeringsnivået er Eggs AST-noder vanligvis representert som objekter med egenskaper , noe som passer perfekt med språk som JavaScript. Alle noder deler en felles egenskap: `type` , som identifiserer nodetypen (VALUE, WORD, APPLY, ARRAY, osv.) og dermed strukturen som resten av objektet vil ha.

VALUE-noder brukes til literalkonstanter . De inneholder en egenskap, ofte kalt value , der tallet eller strengen de representerer er lagret. De har ingen ekstra barn fordi innholdet deres er fullstendig beskrevet av den literalen.

Ordnoder er reservert for identifikatorer : variabelnavn, funksjonsnavn, parameternavn og lignende. De har vanligvis en `name`- egenskap som lagrer identifikatoren som en streng. I likhet med VALUE-noder fungerer de som blader i treet, ettersom deres eneste formål er å oppgi det navnet.

Apply-noder representerer applikasjoner eller kall. De inkluderer en operatoregenskap , som peker til uttrykket (en annen node) som brukes, og en args- egenskap , som lenker til en ARRAY-node. Sistnevnte er en spesifikk node i AST-en, hvis formål er å inneholde applikasjonens argumentliste .

ARRAY-noden kan forstås som en strukturert beholder for andre noder, som representerer en sekvens av undertrær. Fra et arity-perspektiv introduserer den fleksibilitet fordi den tillater kall uten argumenter, med ett argument eller med flere argumenter innenfor samme APPLY-setning, uten å måtte endre definisjonen av hovednodetypen.

Eksempel på AST: enkel applikasjon med én verdi

For å visualisere alt det ovennevnte, la oss tenke på representasjonen av en enkel instruksjon, for eksempel en anvendelse av en funksjon X med et enkelt argument 5. AST-en generert av parseren tilsvarer et begrep konstruert med VALUE-, WORD- og APPLY-nodene , i henhold til Eggs regler.

På et konseptuelt nivå ville vi ha en APPLY- node ved roten. Operatoregenskapen ville peke til en WORD-node med navnet X, og args-egenskapen ville referere til en ARRAY-node som inneholder et enkelt element: en VALUE-node med den numeriske verdien 5. På denne måten gjenspeiler strukturen tydelig hvem som brukes på og hva som brukes på.

Hvis vi ønsket å gjøre alle attributtene eksplisitte, kunne vi skrive en mer detaljert notasjon som viser type, operator, argumenter, navn og verdi. Denne mer detaljerte notasjonen er svært nyttig for feilsøking av parseren eller for å forstå hvordan et tekstuttrykk oversettes til et treobjekt i tolken.

I implementeringer i den virkelige verden serialiseres dette treet vanligvis som JSON for enkel lagring, overføring eller inspeksjon. Faktisk gir verktøy og moduler, som evm2term- pakken i npm-økosystemet, kompakte representasjoner av disse AST-ene for enklere analyse eller transformasjon.

Eksempel på AST: nestet addisjon og multiplikasjon

Et annet typisk tilfelle er et litt mer komplekst uttrykk, for eksempel "+(a, *(4, 5))" . Her har vi en addisjonsoperasjon der det første argumentet er identifikatoren a og der det andre argumentet er resultatet av å multiplisere 4 med 5. AST-en som er resultatet av dette uttrykket gjenspeiler den nestede strukturen.

Ved roten av treet ville vi igjen ha en APPLY-node som representerer addisjonsoperasjonen. Operatoren ville være en WORD-node med navnet "+", mens argumentene ville være i en ARRAY-node med to elementer: det første, et WORD med navnet "a"; det andre, en annen APPLY-node som representerer multiplikasjon.

Den andre APPLY-en ville ha et WORD med navnet "*" som operator og et ARRAY med to VALUE-noder som argumenter: én med verdien 4 og den andre med verdien 5. Sett under ett viser strukturen tydelig at evalueringsrekkefølgen består av å multiplisere 4 med 5 og deretter legge resultatet til a.

Hvis vi utvider notasjonen til å inkludere alle attributter, vil vi se typene til alle noder, navnene eller spesifikke verdier, og forholdene mellom dem. Denne eksplisitte beskrivelsen samsvarer med den faktiske implementeringen i Egg-tolkeren, der hver node er et objekt med de nevnte egenskapene.

Tregrammatikk og parsergrammatikk

Måten disse AST-ene genereres på er ikke vilkårlig: den er basert på det som kalles en tregrammatikk . I en typisk formulering er en slik grammatikk definert som en firedobling bestående av et alfabet med aritet, et endelig sett med syntaktiske (ikke-terminale) variabler, et endelig sett med produksjonsregler og et startsymbol.

I hver produksjonsregel erstattes en variabel av et tre hvis rot er et symbol for alfabetet med aritet, og hvis barn igjen er variabler eller allerede definerte trær. Denne strukturen minner om klassiske regulære eller kontekstfrie grammatikker, men tilpasset direkte generering av trær i stedet for strenger av symboler.

Relatert til den mer formelle definisjonen er den spesifikke grammatikken som Eggs parser bruker for å produsere trærne sine. Denne grammatikken, som vanligvis presenteres uformelt i dokumentasjonen, beskriver nøyaktig hvilke kombinasjoner av nøkkelord, operatorer, parenteser og så videre som aksepteres i språket og hvordan de oversettes til noder av typen VALUE, WORD, APPLY og ARRAY.

Denne tregrammatikk kan sees på som et spesialtilfelle av det som i litteraturen er kjent som en vanlig tregrammatikk . Ideen er å ha veldefinerte regler for å konvertere en sekvens av input-tokens til en strukturert AST som deretter kan tolkes eller kompileres.

Dewey-notasjon: koordinater i et tre

Når vi har AST-funksjonen, må vi ofte referere til spesifikke undertrær : for eksempel det andre argumentet til en funksjon, operatoren til et uttrykk, osv. En veldig elegant måte å gjøre dette på er den såkalte Dewey-desimalnotasjonen, som låner skjemaet som brukes til å nummerere seksjoner og underavsnitt i dokumenter.

I denne notasjonen, startende fra et tre t, betegnes et undertre med en streng med tall atskilt med punktum . Hvert tall indikerer posisjonen til et barn (vanligvis startende ved 1), og sekvensen går nedover treet. Dermed refererer et uttrykk som t/2.1.3 til det tredje barnet til det første barnet til det andre barnet til t.

Den induktive definisjonen av denne notasjonen er enkel: den tomme strengen refererer til hele treet; hvis en streng består av et tall etterfulgt av flere tall atskilt med punktum, tolkes den ved først å ta undertreet som tilsvarer den angitte indeksen og deretter anvende den samme logikken rekursivt på resten av strengen.

Hvis vi for eksempel har et tre t som representerer et uttrykk som "+(a, *(4,5))", med en rotnode APPLY for addisjon, et barn WORD kalt "+", og et annet barn APPLY for multiplikasjon, kan vi identifisere spesifikke posisjoner. Dermed kan t/1 være WORD-noden med operatoren "+", t/2.1 identifikatoren "a", og t/2.2.2.1 VALUE-noden med verdien 4, hvis vi nummererer barna riktig.

Denne måten å gi "koordinater" i en AST på er veldig nyttig for å peke ut spesifikke steder når man rapporterer feil, navigerer i treet eller bruker lokale transformasjoner på spesifikke noder uten tvetydighet.

Ekvivalente notasjoner i programmering og verktøy

Ideen bak Deweys notasjon er ikke eksklusiv for treteori; faktisk dukker den opp gjentatte ganger i mange praktiske notasjoner som vi bruker daglig i programmering og strukturert datahåndtering, selv om vi ikke alltid er klar over det.

Når vi skriver uttrykk med punktumoperatoren i et programmeringsspråk , for eksempel object.property.subproperty, gjør vi noe veldig likt: vi går gjennom et tre av nestede objekter, og velger et barn i hvert trinn etter navn i stedet for etter posisjonsnummer. Vi starter fra en rotnode og går ned til flere interne noder.

Det samme mønsteret vises i Unix-lignende filsystemer, der skråstrekoperatoren (/) brukes til å skille mapper: /src/js/tutu.js beskriver en bane fra roten av filsystemet til en bestemt ressurs, og krysser suksessive nivåer i en trestruktur.

I strukturerte dokumenter bruker språk som XPath svært like notasjoner for å velge noder i et XML-tre. En spørring som «A//B/*» velger det første barnet (uansett navn) av hvert element B som er en etterkommer av et element A i riktig posisjon i forhold til gjeldende kontekst, ved å bruke enkle og doble skråstreker for å indikere dybdenivåer.

Et annet velkjent verktøy, jq- språket , bruker et parallelt system for å navigere i JSON-strukturer, noe som tillater valg av underobjekter gjennom sammensatte stier, filtre og uttrykk. Alle disse notasjonene er rett og slett forskjellige måter å uttrykke stier i et tre på , veldig i tråd med Dewey-desimalnotasjon, men tilpasset sine respektive domener.

Analysere trær i lingvistikk og programmering

Utover kompilatorenes verden brukes syntakstrær også i lingvistikk for å representere setningsstruktur. Der kalles de avledningstrær eller parsetrær, som viser hvordan en setning er delt inn i fraser, ord og grammatiske kategorier.

I disse trærne, akkurat som i programmering, finner vi tre grunnleggende typer noder: en rotnode , som representerer hele setningen eller den globale strukturen; interne eller forgreningsnoder, som fungerer som foreldrenoder og gruppedelsett av setningen; og bladnoder, som vanligvis korresponderer med de spesifikke ordene som vises i inputstrengen.

Rotnoden er unik: hele trestrukturen henger fra den. Forgreningsnoder er plassert rett under roten eller andre foreldrenoder, og tjener til å organisere delene av setningen eller programmet hierarkisk . Bladnoder, derimot, finnes på det laveste nivået av treet og har ingen undernoder, og dermed lukkes forgreningsstrukturen.

Disse trærne regnes som kraftige pedagogiske verktøy fordi de hjelper med å dele opp komplekse setninger til håndterbare elementer. Det samme gjelder programmering: en godt konstruert AST lar deg se med et øyeblikk hvilke operasjoner som er kjedet sammen, hvilke uttrykk som er nestet og hvordan evalueringen flyter.

Avhengig av analysens mål, kan vi finne ulike typer analysetrær . Noen vektlegger avhengigheter mellom ord eller komponenter (for eksempel hvem som er avhengig av hvem i en setning), mens andre fokuserer på gruppering i fraser eller bestanddeler, noe som resulterer i to hovedfamilier.

Syntakstrær etter avhengighet og etter valgkrets

En av de mest kjente typene er det avhengighetsbaserte syntakstreet . I denne varianten behandles alle ord i setningen eller alle relevante elementer som bladnoder, og koblingene mellom dem indikerer direkte avhengighetsforhold (for eksempel et hovedverb og dets subjekt). Som et resultat produseres det ofte trær med færre noder enn i andre skjemaer.

Denne enkelheten gjør dem spesielt praktiske for nybegynnere og for visse språkbehandlingsoppgaver, fordi strukturen fokuserer på hvem som er avhengig av hvem uten å introdusere så mange mellomliggende noder. Anvendt i programmering er ideen å holde seg kun til de essensielle relasjonene, og utelate grammatiske utsmykninger.

I den andre enden har vi syntakstrær basert på konstituenter eller bestanddeler, som skiller mellom rotnoder, interne forgreningsnoder og bladnoder, og gjør alle relevante grupperinger synlige. Disse trærne inneholder vanligvis flere noder og gjenspeiler den hierarkiske strukturen til setningen eller programmet i større detalj.

Vanlige maler for valgkretstre viser lange setninger med mange bladnoder, flere nivåer av forgrening og en veldefinert rotnode. De er spesielt nyttige for å dissekere komplekse setninger eller programmer med flere lag med nestede strukturer.

I både avhengighets- og konstituenstrær er eksempler og visuelle ressurser tilgjengelige som maler, slik at du enkelt kan fylle ut nodene med ønsket informasjon. Dette sparer tid og unngår å måtte designe diagrammet fra bunnen av hver gang du vil illustrere en struktur.

Praktiske anvendelser og verktøy knyttet til AST

AST-er er ikke bare et teoretisk konsept: de brukes aktivt i en rekke hverdagsverktøy av alle som jobber med kode. Kompilatorer, tolker, minifikatorer, kodeformaterere og statiske analysatorer er nesten alltid avhengige av en AST for å utføre funksjonen sin.

En typisk kompilator tar kildekoden, tokeniserer den, analyserer den og genererer et abstrakt syntakstre. Derfra utfører den semantiske kontroller (typer, variabelt omfang, feil bruk av konstruksjoner) og anvender kodeoptimalisering ved å krysse og transformere AST før den produserer maskinkode, eller bytekode.

Verktøy som lintere eller formatterere fungerer også på AST: de analyserer strukturen for å oppdage problematiske mønstre, dårlig praksis eller inkonsekvenser og foreslår endringer som opprettholder den semantiske strukturen til treet, men justerer presentasjonen av koden.

I JavaScript-økosystemet finnes det for eksempel flere biblioteker som eksponerer AST i JSON-format, noe som gjør det enklere for andre verktøy å stole på det for å utføre refaktorering, generere automatisk dokumentasjon eller lage visualiseringer av strukturen til komplekse programmer.

Selv på noe mer spesialiserte områder, som instrumentering for måling av testdekning eller transformasjon av kildekode til andre språk, er AST grunnlaget som mange moderne løsninger er basert på, ettersom det tillater arbeid på et veldig komfortabelt abstraksjonsnivå mellom råtekst og maskinkode.

Samlet sett er abstrakte syntakstrær den viktigste delen som forbinder et språks formelle grammatikk, dets interne representasjon i kompilatoren eller tolken, og de avanserte verktøyene vi bruker for å skrive, analysere og transformere kode trygt og effektivt. Å forstå hvordan de er konstruert, hvordan man navigerer i dem (med konsepter som Dewey-desimalnotasjon), og hvilke typer noder som er involvert (VALUE, WORD, APPLY, faste eller variable arity-strukturer, osv.) hjelper oss å se mye tydeligere hva maskinen faktisk gjør når den behandler et program.