Apstraktna sintaksna stabla u programiranju: cjeloviti vodič

Informatec Digital » Sredstva » Apstraktna sintaksna stabla u programiranju: cjeloviti vodič

Apstraktna sintaksna stabla u programiranju jedan su od onih koncepata koji u početku zvuče vrlo teoretski, ali kad ih shvatite, shvatit ćete da su posvuda: kompajleri, interpreteri , analiza koda, alati za refaktoriranje, čak i u jezicima za strukturirane upite podataka. Ona su, u biti, način na koji stroj "razumije" strukturu programa izvan običnog teksta.

Iako se ponekad miješaju s klasičnim parsirajućim stablima, apstraktna sintaksna stabla (AST) imaju svoja pravila. Apstraktno sintaksno stablo nije samo lijep crtež: to je kompaktna i dobro osmišljena struktura podataka koja eliminira sve suvišno iz konkretne sintakse (zagrade, zareze, redundantne ključne riječi itd.) i usredotočuje se na bitno: koje se operacije izvode, na kojim vrijednostima i kojim redoslijedom.

Što je točno apstraktno sintaksno stablo (AST)?

U teoriji programskih jezika, apstraktno sintaksno stablo (AST) je struktura nalik stablu koja predstavlja sintaksu programa, ali u pojednostavljenom obliku u usporedbi s konkretnim stablom parsiranja. Sadrži iste bitne informacije kao stablo parsiranja, ali organizirano na kompaktniji i upravljiviji način.

Stablo parsiranja sadrži sve gramatičke produkcije i sve terminalne simbole, uključujući zagrade, zareze, točke-zareze i druge čisto sintaktičke elemente. AST, s druge strane, uklanja ove detalje koji ne doprinose semantičkom značenju i zadržava samo logičku strukturu izraza i rečenica.

Što se tiče implementacije, AST se obično sastoji od objekata čvorova s ​​tipom koji označava o kojoj se vrsti sintaktičke konstrukcije radi (konstanta, identifikator, primjena funkcije, binarni operator itd.) i dodatnih svojstava koja opisuju njegov sadržaj: vrijednost, naziv, potomci, popis argumenata itd.

Ljepota AST-a je u tome što olakšava kasnije faze kompajlera ili interpretera, kao što su provjera tipova, optimizacije ili generiranje koda , jer nudi čist pogled na strukturu programa bez sintaktičke buke.

Razlika između konkretnog sintaktičkog stabla i apstraktnog sintaktičkog stabla

Kako bismo u potpunosti razumjeli što AST doprinosi, korisno je prvo usporediti konkretno stablo parsiranja s apstraktnim. Zamislite jednostavnu gramatiku koja prepoznaje aritmetičke izraze poput "a + 4 * 5" . Konkretno stablo parsiranja točno odražava primjenu svakog gramatičkog pravila: neterminalne simbole, terminale, zagrade, operatore itd.

Ovo određeno stablo je obično duboko i ima mnogo međučvorova koji služe samo održavanju formalne strukture gramatike. Na primjer, mogu postojati čvorovi za "Izraz", "Pojam", "Faktor", a zatim terminalni simboli poput "+" , "*" , identifikatori i brojevi. Svaka produkcija postaje grana stabla, povećavajući strukturnu složenost.

S druge strane, apstraktno sintaksno stablo za isti izraz ograničeno je na predstavljanje stvarnih operacija i operanada . Dakle, umjesto nekoliko razina "Izraza" i "Člana", mogli bismo imati korijenski čvor koji predstavlja zbrajanje, s dva potomka: s lijeve strane identifikator a, a s desne strane čvor množenja čija su potomci vrijednosti 4 i 5. Čisto gramatički čvorovi nestaju, a dijelovi strukture se preuređuju ili sažimaju.

To znači da AST i konkretno sintaksno stablo sadrže iste semantičke informacije , ali prvo ih predstavlja u mnogo izravnijem i kompaktnijem obliku. Ova kondenzacija je ključna za učinkovit rad s kodom u alatima za analizu ili izvršavanje.

Stabla i abecede s funkcijom arnosti

Za formaliziranje ovih stabala s matematičkog gledišta obično se koristi ideja abecede s funkcijom arnosti . Umjesto jednostavnog skupa simbola, definira se abeceda u kojoj je svaki simbol povezan s brojem koji označava koliko djece može imati u stablu.

Abeceda s funkcijom arnosti je, neformalno, par koji se sastoji od konačnog skupa simbola i funkcije koja svakom simbolu dodjeljuje prirodni broj (uključujući nulu). Taj broj označava arnost simbola: ako je 0, simbol se ponaša kao list; ako je 1, ponaša se kao unarni čvor; ako je 2, binarni je; i tako dalje. Također je uobičajeno dopustiti simbole varijabilne arnosti za operatore kao liste argumenata.

Simboli arnosti 0 odgovaraju listovima stabla (na primjer, konstante ili identifikatori). Simboli arnosti 1 koriste se za konstrukte koji uključuju jedan podređeni izraz. Simboli arnosti 2 predstavljaju klasične binarne operacije poput zbrajanja, množenja, dodjeljivanja itd. A simboli varijabilne arnosti omogućuju modeliranje konstrukata koji prihvaćaju neodređen broj podstabala, kao što je poziv funkcije s više parametara.

Iz ove abecede s arnošću, skup svih mogućih stabala može se definirati: počevši s praznim stablom (kada se razmatra), dodajući sve simbole arnosti 0 i varijable, te induktivno proširujući: ako je simbol k-aran, može se postaviti kao roditeljski čvor k već konstruiranih podstabala. To daje jezik stabla (ili termin) povezan s abecedom.

Jezik stabla i pojam čvora

Skup svih stabala formiranih abecedom i njezinom funkcijom arnosti u ovom se kontekstu naziva jezik stabla ili jezik termina . To je ekvivalent, ali za strukture stabala, onoga što je Kleeneovo zatvaranje za stringove.

Baš kao što prilikom analize nizova znakova koristimo termin tokeni za označavanje pojavljivanja abecednih simbola unutar niza, prilikom rada sa stablima obično koristimo termin čvorovi . Čvor je, u biti, specifična pojava abecednog simbola s arnošću koja se nalazi na određenoj poziciji u stablu.

Iz ove perspektive, ovaj jezik stabla je za čvorove ono što je skup nizova za pojave tokena. Svako stablo se interpretira kao struktura izgrađena korak po korak iz abecede, a čvorovi su pojedinačni dijelovi koji fizički materijaliziraju njegove simbole.

Ovakav način gledanja na to je vrlo koristan pri dizajniranju parsera i AST generatora , jer omogućuje rasuđivanje o pravilima konstrukcije ovih stabala na način analogan gramatici stringova, ali radeći izravno na hijerarhijskim strukturama.

Arnost čvorova u specifičnom AST-u: slučaj Egg-a

Prelazeći s teorije na praktični primjer, mnogi nastavni materijali koriste Egg jezik za ilustraciju konstrukcije i manipulacije AST-ovima. U tom kontekstu koristi se nekoliko glavnih vrsta čvorova, svaki s dobro definiranom arnošću , što ih čini vrlo jednostavnima za manipuliranje.

U tipičnom Egg AST-u, VALUE čvorovi se smatraju listovima: predstavljaju literale poput nizova ili brojeva. Nemaju djecu; pohranjuju samo vrijednost. Slično tome, WORD čvorovi , koji se koriste za identifikatore (imena varijabli, imena funkcija itd.), također se tretiraju kao listovi sa svojstvom koje pohranjuje ime.

Ključni čvor u Egg-u je tip APPLY , koji predstavlja primjenu funkcije ili operatora. Ovaj tip čvora ima dva konceptualna potomka: potomka OPERATOR koji pokazuje na izraz koji se primjenjuje; i potomka ARGS , koji je zapravo poseban čvor ARRAY odgovoran za održavanje kolekcije podstabala, jednog za svaki argument.

Nizovi su stoga prirodan način uvođenja varijabilne arnosti u AST: APPLY uvijek ima dvije komponente (operator i popis argumenata), ali taj interni popis može sadržavati nula, jedno ili više podstabala ovisno o specifičnom pozivu koji se predstavlja.

Detaljna anatomija AST čvorova u Egg-u

Na razini implementacije, Egg-ovi AST čvorovi obično su predstavljeni kao objekti sa svojstvima , što se savršeno uklapa u jezike poput JavaScripta. Svi čvorovi dijele zajedničko svojstvo: `type` , koje identificira tip čvora (VALUE, WORD, APPLY, ARRAY, itd.) i, prema tome, strukturu koju će imati ostatak objekta.

Čvorovi VALUE koriste se za literalne konstante . Sadrže svojstvo, često nazvano vrijednost , gdje je pohranjen broj ili niz znakova koji predstavljaju. Nemaju dodatnu djecu jer je njihov sadržaj u potpunosti opisan tim literalom.

Riječni čvorovi rezervirani su za identifikatore : nazive varijabli, nazive funkcija, nazive parametara i slično. Obično imaju svojstvo `name` koje pohranjuje identifikator kao niz znakova. Slično čvorovima VALUE, djeluju kao listovi u stablu, jer im je jedina svrha dati taj naziv.

Čvorovi Apply predstavljaju aplikacije ili pozive. Uključuju svojstvo operatora koje pokazuje na izraz (drugi čvor) koji se primjenjuje i svojstvo args koje se povezuje s čvorom ARRAY. Potonji je specifični čvor unutar AST-a, čija je svrha držati popis argumenata aplikacije .

Čvor ARRAY može se shvatiti kao strukturirani spremnik za druge čvorove, koji predstavlja niz podstabala. Iz perspektive arnosti, uvodi fleksibilnost jer omogućuje pozive bez argumenata, s jednim argumentom ili s više argumenata unutar iste APPLY naredbe, bez potrebe za promjenom definicije glavnog tipa čvora.

Primjer AST-a: jednostavna aplikacija s jednom vrijednošću

Kako bismo vizualizirali sve navedeno, razmislimo o prikazu jednostavne instrukcije, kao što je primjena funkcije X s jednim argumentom 5. AST koji generira parser odgovara terminu konstruiranom s čvorovima VALUE, WORD i APPLY , slijedeći Eggova pravila.

Na konceptualnoj razini, u korijenu bismo imali čvor APPLY . Njegovo svojstvo operatora pokazivalo bi na čvor WORD pod nazivom X, a svojstvo args bi se odnosilo na čvor ARRAY koji sadrži jedan element: čvor VALUE s numeričkom vrijednošću 5. Na taj način struktura jasno odražava na koga se primjenjuje i na što se primjenjuje.

Ako bismo htjeli eksplicitno navesti sve atribute, mogli bismo napisati detaljniju notaciju koja prikazuje tip, operator, argumente, naziv i vrijednost. Ova detaljnija notacija vrlo je korisna za otklanjanje pogrešaka u parseru ili za razumijevanje kako se tekstualni izraz prevodi u objekt stabla unutar interpretera.

U stvarnim implementacijama, ovo stablo se obično serijalizira kao JSON radi lakše pohrane, prijenosa ili pregleda. Zapravo, alati i moduli, poput paketa evm2term u npm ekosustavu, pružaju kompaktne prikaze ovih AST-ova za lakšu analizu ili transformaciju.

Primjer AST-a: ugniježđeno zbrajanje i množenje

Drugi tipičan slučaj je nešto složeniji izraz, kao što je "+(a, *(4, 5))" . Ovdje imamo operaciju zbrajanja čiji je prvi argument identifikator a, a drugi argument rezultat množenja 4 s 5. AST koji rezultira iz ovog izraza odražava tu ugniježđenu strukturu.

U korijenu stabla, ponovno bismo imali APPLY čvor koji predstavlja operaciju zbrajanja. Njegov operator bio bi WORD čvor pod nazivom "+", dok bi se njegovi argumenti nalazili u ARRAY čvoru s dva elementa: prvi, WORD pod nazivom "a"; drugi, još jedan APPLY čvor koji predstavlja množenje.

Taj drugi APPLY bi kao operator imao WORK pod nazivom "*", a kao argumente ARRAY s dva VALUE čvora: jedan s vrijednošću 4 i drugi s vrijednošću 5. Gledano kao cjelina, struktura jasno pokazuje da se redoslijed evaluacije sastoji od množenja 4 s 5, a zatim dodavanja rezultata vrijednosti a.

Ako proširimo notaciju tako da uključuje sve atribute, vidjeli bismo tipove svih čvorova, njihova imena ili specifične vrijednosti i odnose među njima. Ovaj eksplicitni opis odgovara stvarnoj implementaciji u Egg interpreteru, gdje je svaki čvor objekt s prethodno spomenutim svojstvima.

Gramatika stabla i gramatika parsera

Način na koji se generiraju ovi AST-ovi nije proizvoljan: temelji se na onome što se naziva gramatika stabla . U tipičnoj formulaciji, takva gramatika definirana je kao četverostruki skup sastavljen od abecede s arnošću, konačnog skupa sintaktičkih (neterminalnih) varijabli, konačnog skupa produkcijskih pravila i početnog simbola.

U svakom produkcijskom pravilu, varijabla se zamjenjuje stablom čiji je korijen simbol abecede s arnošću, a čija su djeca pak varijable ili već definirana stabla. Ova struktura podsjeća na klasične regularne ili kontekstno neovisne gramatike, ali prilagođena je izravnom generiranju stabala umjesto nizova simbola.

S tom formalnijom definicijom povezana je specifična gramatika koju Egg-ov parser koristi za izradu svojih stabala. Ova gramatika, koja se obično neformalno predstavlja u dokumentaciji, točno opisuje koje su kombinacije ključnih riječi, operatora, zagrada i tako dalje prihvaćene u jeziku i kako se prevode u čvorove tipa VALUE, WORD, APPLY i ARRAY.

Ova gramatika stabla može se promatrati kao poseban slučaj onoga što je u literaturi poznato kao regularna gramatika stabla . Ideja je imati dobro definirana pravila za pretvaranje niza ulaznih tokena u strukturirani AST koji se zatim može interpretirati ili kompajlirati.

Deweyjeva notacija: koordinate unutar stabla

Nakon što imamo AST, često se moramo pozivati ​​na specifična podstabla : na primjer, drugi argument funkcije, operator izraza itd. Vrlo elegantan način za to je takozvana Deweyjeva decimalna notacija, koja posuđuje shemu koja se koristi za numeriranje odjeljaka i pododjeljaka u dokumentima.

U ovoj notaciji, počevši od stabla t, podstablo se označava nizom brojeva odvojenih točkama . Svaki broj označava položaj djeteta (obično počevši od 1) i niz ide niz stablo. Dakle, izraz poput t/2.1.3 odnosi se na treće dijete prvog djeteta drugog djeteta od t.

Induktivna definicija ove notacije je jednostavna: prazan niz se odnosi na cijelo stablo; ako se niz sastoji od broja kojeg slijedi više brojeva odvojenih točkama, interpretira se tako da se prvo uzme podstablo djeteta koje odgovara naznačenom indeksu, a zatim se ista logika rekurzivno primjenjuje na ostatak niza.

Na primjer, ako imamo stablo t koje predstavlja izraz poput "+(a, *(4,5))", s korijenskim čvorom APPLY za zbrajanje, podređenim čvorom WORD pod nazivom "+" i drugim podređenim čvorom APPLY za množenje, možemo identificirati specifične pozicije. Dakle, t/1 može biti čvor WORD s operatorom "+", t/2.1 identifikator "a", a t/2.2.2.1 čvor VALUE s vrijednošću 4, ako djecu odgovarajuće numeriramo.

Ovaj način davanja "koordinata" unutar AST-a vrlo je koristan za isticanje određenih lokacija prilikom prijavljivanja pogrešaka, navigacije stablom ili primjene lokalnih transformacija na određene čvorove bez dvosmislenosti.

Ekvivalentne notacije u programiranju i alatima

Ideja koja stoji iza Deweyjeve notacije nije isključivo vezana uz teoriju stabala; zapravo, ona se više puta pojavljuje u mnogim praktičnim notacijama koje svakodnevno koristimo u programiranju i rukovanju strukturiranim podacima, čak i ako toga nismo uvijek svjesni.

Kada u programskom jeziku pišemo izraze s operatorom točka , kao što je objekt.svojstvo.podsvojstvo, radimo nešto vrlo slično: prolazimo kroz stablo ugniježđenih objekata, odabirući dijete u svakom koraku po imenu umjesto po broju pozicije. Počevši od korijenskog čvora, spuštamo se do više unutarnjih čvorova.

Isti obrazac pojavljuje se u Unix-sličnim datotečnim sustavima, gdje se operator kose crte naprijed (/) koristi za odvajanje direktorija: /src/js/tutu.js opisuje put od korijena datotečnog sustava do određenog resursa, prolazeći kroz uzastopne razine strukture stabla.

U svijetu strukturiranih dokumenata, jezici poput XPath-a koriste vrlo slične notacije za odabir čvorova unutar XML stabla. Upit poput "A//B/*" bira prvo dijete (bez obzira na ime) svakog elementa B koji je potomak elementa A na odgovarajućoj poziciji u odnosu na trenutni kontekst, koristeći jednostruke i dvostruke kose crte za označavanje razina dubine.

Još jedan poznati alat, jq jezik , koristi paralelni sustav za navigaciju JSON strukturama, omogućujući odabir podobjekata putem složenih putanja, filtera i izraza. Sve ove notacije su jednostavno različiti načini izražavanja putanja u stablu , vrlo slične Deweyjevoj decimalnoj notaciji, ali prilagođene njihovim odgovarajućim domenama.

Stabla parsiranja u lingvistici i programiranju

Izvan svijeta kompajlera, sintaksna stabla se također koriste u lingvistici za predstavljanje rečenične strukture. Tamo se nazivaju derivacijska stabla ili stabla parsiranja, koja pokazuju kako je rečenica rastavljena na fraze, riječi i gramatičke kategorije.

U tim stablima, baš kao i u programiranju, nalazimo tri osnovne vrste čvorova: korijenski čvor , koji predstavlja cijelu rečenicu ili globalnu strukturu; interne ili granajuće čvorove, koji funkcioniraju kao roditeljski čvorovi i grupiraju podskupove rečenice; i listne čvorove, koji obično odgovaraju specifičnim riječima koje se pojavljuju u ulaznom nizu.

Korijenski čvor je jedinstven: cijela struktura stabla visi s njega. Čvorovi grananja nalaze se neposredno ispod korijena ili drugih roditeljskih čvorova i služe za hijerarhijsku organizaciju dijelova rečenice ili programa. S druge strane, listovi čvorovi nalaze se na najnižoj razini stabla i nemaju djecu, čime se zatvara struktura grananja.

Ova stabla smatraju se moćnim pedagoškim alatima jer pomažu u rastavljanju složenih rečenica na upravljive elemente. Isto vrijedi i za programiranje: dobro konstruirani AST omogućuje vam da na prvi pogled vidite koje su operacije povezane, koji su izrazi ugniježđeni i kako teče evaluacija.

Ovisno o cilju analize, možemo pronaći različite vrste analitičkih stabala . Neka naglašavaju ovisnosti između riječi ili komponenti (na primjer, tko ovisi o kome u rečenici), dok se druga usredotočuju na grupiranje u fraze ili sastavnice, što rezultira dvjema glavnim obiteljima.

Sintaktička stabla po ovisnosti i po izbornoj jedinici

Jedan od najpoznatijih tipova je sintaksno stablo temeljeno na ovisnostima . U ovoj varijanti, sve riječi u rečenici ili svi relevantni elementi tretiraju se kao listovi, a veze između njih ukazuju na izravne odnose ovisnosti (na primjer, glavni glagol i njegov subjekt). Kao rezultat toga, stabla s manje čvorova se često proizvode nego u drugim shemama.

Ova jednostavnost čini ih posebno prikladnima za početnike i za određene zadatke obrade jezika, jer se struktura fokusira na to tko ovisi o kome bez uvođenja toliko posrednih čvorova. Primijenjeno na programiranje, ideja je držati se samo bitnih odnosa, izostavljajući gramatičke ukrase.

Na drugom kraju imamo sintaksna stabla temeljena na sastavnicama ili konstituentima, koja razlikuju korijenske čvorove, unutarnje čvorove grananja i listove te čine sve relevantne grupacije vidljivima. Ova stabla obično sadrže više čvorova i detaljnije odražavaju hijerarhijsku strukturu rečenice ili programa.

Uobičajeni predlošci stabla izbornih jedinica prikazuju duge rečenice s brojnim listovima, nekoliko razina grananja i dobro definiranim korijenskim čvorom. Posebno su korisni za rastavljanje složenih rečenica ili programa s više slojeva ugniježđenih struktura.

I u stablima ovisnosti i u stablima izbornih jedinica, primjeri i vizualni resursi dostupni su kao predlošci, što vam omogućuje jednostavno popunjavanje čvorova željenim informacijama. To štedi vrijeme i izbjegava potrebu za dizajniranjem dijagrama od nule svaki put kada želite ilustrirati strukturu.

Praktične primjene i alati povezani s AST-om

AST-ovi nisu samo teorijski koncept: aktivno ih koristi svatko tko radi s kodom u mnoštvu svakodnevnih alata . Kompajleri, interpreteri, minifikatori, formateri koda i statički analizatori gotovo se uvijek oslanjaju na AST za obavljanje svoje funkcije.

Tipični kompajler uzima izvorni kod, tokenizira ga, parsira i generira apstraktno sintaksno stablo. Nakon toga provodi semantičke provjere (tipovi, opseg varijabli, netočna upotreba konstrukata) i primjenjuje optimizaciju koda prolaskom i transformiranjem AST-a prije stvaranja strojnog koda ili bajtkoda.

Alati poput lintera ili formatera također rade na AST-u: analiziraju strukturu kako bi otkrili problematične obrasce, loše prakse ili nedosljednosti te predlažu promjene koje održavaju semantičku strukturu stabla, ali prilagođavaju prezentaciju koda.

U JavaScript ekosustavu, na primjer, postoji više biblioteka koje izlažu AST u JSON formatu, što drugim alatima olakšava oslanjanje na njega za refaktoriranje, generiranje automatske dokumentacije ili stvaranje vizualizacija strukture složenih programa.

Čak i u nešto specijaliziranijim područjima, poput instrumentacije za mjerenje pokrivenosti testovima ili transformacije izvornog koda u druge jezike, AST je temelj na kojem se temelje mnoga moderna rješenja, jer omogućuje rad na vrlo ugodnoj razini apstrakcije između sirovog teksta i strojnog koda.

Uzeta zajedno, apstraktna sintaksna stabla ključni su dio koji povezuje formalnu gramatiku jezika, njegovu internu reprezentaciju u kompajleru ili interpreteru i napredne alate koje koristimo za sigurno i učinkovito pisanje, analizu i transformaciju koda. Razumijevanje kako su konstruirana, kako se njima kretati (s konceptima poput Deweyjeve decimalne notacije) i koje su vrste čvorova uključene (VALUE, WORLD, APPLY, fiksne ili varijabilne strukture arnosti itd.) pomaže nam da puno jasnije vidimo što stroj zapravo radi kada obrađuje program.