Apstraktna sintaksna stabla u programiranju: kompletan vodič

Informatec Digital » Resursi » Apstraktna sintaksna stabla u programiranju: kompletan vodič

Apstraktna sintaksna stabla u programiranju su jedan od onih koncepata koji u početku zvuče vrlo teoretski, ali kada ih jednom shvatite, shvatit ćete da su svuda: kompajleri, interpreteri , analiza koda, alati za refaktorisanje, čak i u jezicima za strukturirane upite podataka. Ona su, u suštini, način na koji mašina "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 dizajnirana struktura podataka koja eliminira sve suvišno iz konkretne sintakse (zagrade, zareze, redundantne ključne riječi itd.) i fokusira se na bitno: koje se operacije izvode, nad kojim vrijednostima i kojim redoslijedom.

Šta je tač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 poređenju sa konkretnim stablom parsiranja. Sadrži iste bitne informacije kao i stablo parsiranja, ali organizovano na kompaktniji i upravljiviji način.

Stablo parsiranja sadrži sve gramatičke produkcije i sve terminalne simbole, uključujući zagrade, zareze, tačka-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, aplikacija funkcije, binarni operator itd.), i dodatnih svojstava koja opisuju njegov sadržaj: vrijednost, ime, potomci, lista 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

Da bismo u potpunosti razumjeli doprinos AST-a, korisno je prvo uporediti konkretno stablo parsiranja sa apstraktnim. Zamislite jednostavnu gramatiku koja prepoznaje aritmetičke izraze poput "a + 4 * 5" . Konkretno stablo parsiranja precizno 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 za održavanje formalne strukture gramatike. Na primjer, mogu postojati čvorovi za "Izraz", "Član", "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 nivoa "Izraza" i "Člana", mogli bismo imati korijenski čvor koji predstavlja sabiranje, 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 direktnijem i kompaktnijem obliku. Ova kondenzacija je ključna za efikasan rad s kodom u alatima za analizu ili izvršavanje.

Drveće i alfabeti s funkcijom arnosti

Za formalizaciju ovih stabala sa matematičke tačke gledišta, obično se koristi ideja abecede sa funkcijom arnosti . Umjesto jednostavnog skupa simbola, definiše se abeceda u kojoj je svaki simbol povezan sa 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). Ovaj 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 dozvoliti simbole promjenjive arnosti za operatore kao liste argumenata.

Simboli arnosti 0 odgovaraju listovima stabla (na primjer, konstante ili identifikatori). Simboli arnosti 1 koriste se za konstrukcije koje uključuju jedan podređeni izraz. Simboli arnosti 2 predstavljaju klasične binarne operacije kao što su sabiranje, množenje, dodjeljivanje itd. A simboli varijabilne arnosti omogućavaju modeliranje konstrukcija koje prihvataju 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 od praznog stabla (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. Ovo daje jezik stabla (ili termin) povezan s abecedom.

Jezik stabla i pojam čvora

Skup svih stabala formiranih pomoću abecede i njene funkcije arnosti naziva se, u ovom kontekstu, jezik stabla ili jezik termina . To je ekvivalent, ali za strukture stabla, onoga što je Kleeneovo zatvaranje za stringove.

Baš kao što prilikom analize stringova koristimo termin tokeni da bismo označili pojavljivanja abecednih simbola unutar niza, kada radimo sa stablima obično koristimo termin čvorovi . Čvor je, u suštini, specifično pojavljivanje abecednog simbola sa arnošću koje se nalazi na određenoj poziciji u stablu.

Iz ove perspektive, ovaj jezik stabla je za čvorove ono što je skup stringova 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 veoma koristan pri dizajniranju parsera i AST generatora , jer omogućava razmišljanje o pravilima konstrukcije ovih stabala na način analogan gramatici stringova, ali radeći direktno 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 ovom kontekstu, koristi se nekoliko glavnih tipova čvorova, svaki s dobro definiranom arnošću , što ih čini vrlo jednostavnim za manipulaciju.

U tipičnom Egg AST-u, VALUE čvorovi se smatraju listovima: oni predstavljaju literale poput stringova ili brojeva. Nemaju djecu; oni samo pohranjuju 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 ARRAY čvor odgovoran za održavanje kolekcije podstabala, po jednog za svaki argument.

Nizovi su, dakle, prirodan način uvođenja varijabilne arnosti u AST: APPLY uvijek ima dvije komponente (operator i listu argumenata), ali ta interna lista 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 nivou implementacije, Egg-ovi AST čvorovi su obično 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 se koriste za literalne konstante . Sadrže svojstvo, često nazvano vrijednost , gdje se pohranjuje broj ili niz znakova koji predstavljaju. Nemaju dodatnu djecu jer je njihov sadržaj u potpunosti opisan tim literalom.

Riječni čvorovi su rezervirani za identifikatore : imena varijabli, imena funkcija, imena parametara i slično. Obično imaju svojstvo `name` koje pohranjuje identifikator kao string. Slično VALUE čvorovima, oni djeluju kao listovi u stablu, jer im je jedina svrha da daju to ime.

Č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čan čvor unutar AST-a, čija je svrha držanje liste argumenata aplikacije .

Čvor ARRAY se može shvatiti kao strukturirani kontejner za druge čvorove, koji predstavlja niz podstabala. Iz perspektive arnosti, on uvodi fleksibilnost jer omogućava 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

Da bismo vizualizirali sve navedeno, razmislimo o reprezentaciji 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 konceptualnom nivou, u korijenu bismo imali čvor APPLY . Njegovo svojstvo operatora bi pokazivalo na čvor tipa WORD pod nazivom X, a njegovo svojstvo args bi se odnosilo na čvor tipa ARRAY koji sadrži jedan element: čvor tipa VALUE s numeričkom vrijednošću 5. Na ovaj način, struktura jasno odražava na koga se primjenjuje i na šta se primjenjuje.

Ako bismo željeli da svi atributi budu eksplicitni, mogli bismo napisati detaljniju notaciju koja prikazuje tip, operator, argumente, ime i vrijednost. Ova detaljnija notacija je vrlo korisna za otklanjanje greš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šeg pohranjivanja, prijenosa ili inspekcije. U stvari, alati i moduli, poput paketa evm2term u npm ekosistemu, pružaju kompaktne reprezentacije ovih AST-ova radi lakše analize ili transformacije.

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

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

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

Ta druga APPLY bi imala kao operator WRIC pod nazivom "*" i kao argumente ARRAY sa dva VALUE čvora: jedan sa vrijednošću 4 i drugi sa vrijednošću 5. Posmatrano kao cjelina, struktura jasno pokazuje da se redoslijed evaluacije sastoji od množenja 4 sa 5, a zatim dodavanja rezultata na 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 sa prethodno spomenutim svojstvima.

Gramatika stabla i gramatika parsera

Način na koji se generiraju ovi AST-ovi nije proizvoljan: zasnovan je na onome što se naziva Gramatika stabla . U tipičnoj formulaciji, takva gramatika se definira kao četvorka sastavljena 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 je prilagođena direktnom generiranju stabala umjesto nizova simbola.

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

Ova gramatika stabla može se posmatrati 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

Kada 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 sekcija i podsekcija u dokumentima.

U ovoj notaciji, počevši od stabla t, podstablo se označava nizom brojeva odvojenih tačkama . Svaki broj označava poziciju 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 string se odnosi na cijelo stablo; ako se string sastoji od broja kojeg slijedi više brojeva odvojenih tačkama, interpretira se tako što se prvo uzme podstablo koje odgovara naznačenom indeksu, a zatim se ista logika rekurzivno primjenjuje na ostatak stringa.

Na primjer, ako imamo stablo t koje predstavlja izraz poput "+(a, *(4,5))", s korijenskim čvorom APPLY za sabiranje, podređenim čvorom WORD pod nazivom "+" i drugim podređenim čvorom APPLY za množenje, možemo identificirati specifične pozicije. Dakle, t/1 bi mogao 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 je veoma koristan za isticanje specifičnih lokacija prilikom prijavljivanja grešaka, navigacije kroz stablo 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 za teoriju stabala; u stvari, 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 pišemo izraze s operatorom tačka u programskom jeziku , kao što je object.property.subproperty, 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 internih čvorova.

Isti obrazac se pojavljuje u Unix-sličnim datotečnim sistemima, gdje se operator kose crte naprijed (/) koristi za odvajanje direktorija: /src/js/tutu.js opisuje putanju od korijena datotečnog sistema do određenog resursa, prolazeći kroz uzastopne nivoe 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 nivoa dubine.

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

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 ovim 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 odmah ispod korijena ili drugih roditeljskih čvorova i služe za hijerarhijsko organiziranje dijelova rečenice ili programa. S druge strane, listovi čvorovi nalaze se na najnižem nivou stabla i nemaju djecu, čime se zatvara struktura grananja.

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

U zavisnosti od cilja analize, možemo pronaći različite vrste analitičkih stabala . Neka naglašavaju zavisnosti između riječi ili komponenti (na primjer, ko zavisi od koga u rečenici), dok se druga fokusiraju na grupisanje u fraze ili konstituente, što rezultira dvjema glavnim porodicama.

Sintaksna stabla po zavisnosti i po izbornoj jedinici

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

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

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

Često viđeni predlošci stabla izbornih jedinica prikazuju duge rečenice s brojnim listovima, nekoliko nivoa grananja i dobro definiranim korijenskim čvorom. Posebno su korisni za raščlanjivanje složenih rečenica ili programa s više slojeva ugniježđenih struktura.

I u stablima zavisnosti i u stablima izbornih jedinica, primjeri i vizualni resursi dostupni su kao predlošci, što vam omogućava da jednostavno popunite čvorove željenim informacijama. Ovo štedi vrijeme i izbjegava potrebu za dizajniranjem dijagrama od nule svaki put kada želite ilustrirati strukturu.

Praktične primjene i alati vezani za AST

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

Tipičan kompajler uzima izvorni kod, tokenizira ga, parsira i generira apstraktno sintaksno stablo. Odatle vrši semantičke provjere (tipovi, opseg varijabli, neispravna upotreba konstrukata) i primjenjuje optimizaciju koda prolaskom i transformiranjem AST-a prije generiranja strojnog koda ili bajtkoda.

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

U JavaScript ekosistemu, na primjer, postoji više biblioteka koje izlažu AST u JSON formatu, što olakšava drugim alatima da se oslanjaju na njega za refaktorisanje, generisanje automatske dokumentacije ili kreiranje vizualizacija strukture složenih programa.

Čak i u nešto specijalizovanijim oblastima, kao što su instrumentacija za mjerenje pokrivenosti testovima ili transformacija izvornog koda u druge jezike, AST je osnova na kojoj se zasnivaju mnoga moderna rješenja, jer omogućava rad na vrlo udobnom nivou apstrakcije između sirovog teksta i mašinskog koda.

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