- Un arbore sintactic abstract (AST) reprezintă structura logică a unui program, eliminând detaliile sintactice irelevante.
- AST-urile sunt construite din alfabete cu funcții de aritate și gramatici arborescente care definesc ce noduri și structuri sunt valide.
- Notațiile Dewey și operatorii precum „.” sau „/” permit referirea precisă la subarbori și căi din cadrul acestor structuri.
- Compilatoarele, interpretoarele și instrumentele de analiză a codului se bazează pe AST pentru a optimiza, transforma și înțelege în mod fiabil programele.
Arborii sintactici abstracti în programare sunt unul dintre acele concepte care inițial par foarte teoretice, dar odată ce te familiarizezi cu ei, îți dai seama că sunt peste tot: compilatoare, interpretoare , analiză de cod, instrumente de refactorizare, chiar și în limbaje de interogare a datelor structurate. Ei sunt, în esență, modul în care o mașină „înțelege” structura unui program dincolo de textul simplu.
Deși uneori sunt confundați cu arborii de sintaxă clasici, arborii de sintaxă abstractă (AST) au propriile reguli. Un arbore de sintaxă abstractă nu este doar un desen frumos: este o structură de date compactă și bine concepută, care elimină tot ce este superfluu din sintaxa concretă (paranteze, virgule, cuvinte cheie redundante etc.) și se concentrează pe elementele esențiale: ce operații sunt efectuate, pe ce valori și în ce ordine.
Ce este mai exact un arbore sintactic abstract (AST)?
În teoria limbajelor de programare, un arbore sintactic abstract (AST) este o structură asemănătoare unui arbore care reprezintă sintaxa unui program, dar într-o formă simplificată în comparație cu un arbore de analiză concret. Acesta conține aceleași informații esențiale ca un arbore de analiză, dar organizate într-un mod mai compact și mai ușor de gestionat.
Un arbore de analiză sintactică conține toate producțiile gramaticii și toate simbolurile terminale, inclusiv paranteze, virgule, punct și virgulă și alte elemente pur sintactice. AST, pe de altă parte, elimină aceste detalii care nu contribuie la semnificație semantică și păstrează doar structura logică a expresiilor și propozițiilor.
În ceea ce privește implementarea, un AST este de obicei alcătuit din obiecte nod cu un tip care indică ce fel de construcție sintactică este (constantă, identificator, aplicație de funcție, operator binar etc.) și proprietăți suplimentare care descriu conținutul său: valoare, nume, copii, listă de argumente etc.
Frumusețea AST constă în faptul că facilitează fazele ulterioare ale compilatorului sau interpretorului, cum ar fi verificarea tipului, optimizările sau generarea de cod , deoarece oferă o vedere clară a structurii programului, fără zgomot sintactic.
Diferența dintre un arbore sintactic concret și un arbore sintactic abstract
Pentru a înțelege pe deplin ce contribuie un AST, este util să comparați mai întâi arborele de analiză concret cu cel abstract. Imaginați-vă o gramatică simplă care recunoaște expresii aritmetice precum „a + 4 * 5” . Arborele de analiză concret reflectă cu acuratețe aplicarea fiecărei reguli gramaticale: simboluri neterminale, terminale, paranteze, operatori etc.
Acest arbore particular este de obicei profund și are multe noduri intermediare care servesc doar la menținerea structurii formale a gramaticii. De exemplu, ar putea exista noduri pentru „Expresie”, „Termen”, „Factor” și apoi simboluri terminale precum „+” , „*” , identificatori și numere. Fiecare producție devine o ramură a arborelui, crescând complexitatea structurală.
Arborele sintactic abstract pentru aceeași expresie, pe de altă parte, se limitează la reprezentarea operațiilor și operanzilor propriu-ziși . Astfel, în loc de mai multe niveluri de „Expresie” și „Termen”, am putea avea un nod rădăcină care reprezintă adunarea, cu doi copii: în stânga un identificator a și în dreapta un nod de înmulțire ai cărui copii sunt valorile 4 și 5. Nodurile pur gramaticale dispar, iar părți ale structurii sunt reordonate sau condensate.
Aceasta înseamnă că AST și arborele sintactic concret conțin aceleași informații semantice , dar primul le prezintă într-o formă mult mai directă și compactă. Această condensare este esențială pentru lucrul eficient cu codul în instrumentele de analiză sau execuție.
Copaci și alfabete cu funcție de aritate
Pentru a formaliza acești arbori din punct de vedere matematic, se folosește de obicei ideea unui alfabet cu o funcție de aritate . În loc de un simplu set de simboluri, se definește un alfabet în care fiecărui simbol i se asociază un număr care indică câți copii poate avea în arbore.
Un alfabet cu o funcție de aritate este, informal, o pereche formată dintr-un set finit de simboluri și o funcție care atribuie fiecărui simbol un număr natural (inclusiv zero). Acest număr indică aritatea simbolului: dacă este 0, simbolul se comportă ca o frunză; dacă este 1, se comportă ca un nod unar; dacă este 2, este binar; și așa mai departe. De asemenea, este obișnuit să se permită simboluri de aritate variabilă pentru operatori ca liste de argumente.
Simbolurile de aritate 0 corespund frunzelor arborelui (de exemplu, constante sau identificatori). Simbolurile de aritate 1 sunt utilizate pentru construcții care implică o singură expresie copil. Simbolurile de aritate 2 reprezintă operații binare clasice, cum ar fi adunarea, înmulțirea, atribuirea etc. Iar simbolurile de aritate variabilă permit modelarea construcțiilor care acceptă un număr nedeterminat de subarbori, cum ar fi un apel de funcție cu parametri multipli.
Din acest alfabet cu aritate, se poate defini mulțimea tuturor arborilor posibili: începând cu arborele gol (atunci când este luat în considerare), adăugând toate simbolurile de aritate 0 și variabilă și extinzându-se inductiv: dacă un simbol este k-ar, acesta poate fi plasat ca nod părinte al k subarbori deja construiți. Aceasta produce limbajul (sau termenul) arborelui asociat alfabetului.
Limbajul arborelui și noțiunea de nod
Mulțimea tuturor arborilor formați cu un alfabet și funcția sa de aritate se numește, în acest context, limbaj arborescent sau limbaj termeni . Este echivalentul, dar pentru structurile arborescente, al închiderii Kleene pentru șiruri de caractere.
La fel cum atunci când analizăm șiruri de caractere folosim termenul „token-uri” pentru a ne referi la aparițiile simbolurilor alfabetice într-o secvență, atunci când lucrăm cu arbori folosim de obicei termenul „ noduri” . Un nod este, în esență, o apariție specifică a unui simbol alfabetic cu aritate situată într-o anumită poziție în arbore.
Din această perspectivă, acest limbaj arborescent este pentru noduri ceea ce un set de șiruri este pentru apariții simbolice. Fiecare arbore este interpretat ca o structură construită pas cu pas pornind de la alfabet, iar nodurile sunt piesele individuale care materializează fizic simbolurile sale.
Această modalitate de a privi lucrurile este foarte utilă la proiectarea parserelor și a generatoarelor AST , deoarece permite raționamentul despre regulile de construcție ale acestor arbori într-un mod analog gramaticalii șirurilor, dar lucrând direct asupra structurilor ierarhice.
Aritatea nodurilor într-un AST specific: cazul Egg
Trecând de la teorie la un exemplu practic, multe materiale didactice folosesc limbajul Egg pentru a ilustra construcția și manipularea AST-urilor. În acest context, sunt utilizate mai multe tipuri principale de noduri, fiecare cu o aritate bine definită , ceea ce le face foarte ușor de manipulat.
Într-un Egg AST tipic, nodurile VALUE sunt considerate frunze: reprezintă literali precum șiruri de caractere sau numere. Nu au copii; stochează doar o valoare. În mod similar, nodurile WORD , care sunt utilizate pentru identificatori (nume de variabile, nume de funcții etc.), sunt, de asemenea, tratate ca frunze cu o proprietate care stochează numele.
Nodul cheie în Egg este tipul APPLY , care reprezintă aplicarea unei funcții sau a unui operator. Acest tip de nod are doi copii conceptuali: un copil OPERATOR care indică expresia aplicată; și un copil ARGS , care este de fapt un nod ARRAY special responsabil pentru menținerea unei colecții de subarbori, câte unul pentru fiecare argument.
Prin urmare, tablourile reprezintă o modalitate naturală de a introduce aritatea variabilelor în AST: un APPLY are întotdeauna două componente (o listă de operatori și o listă de argumente), dar acea listă internă poate conține zero, unul sau mai mulți subarbori, în funcție de apelul specific reprezentat.
Anatomia detaliată a nodurilor AST din Egg
La nivel de implementare, nodurile AST ale lui Egg sunt de obicei reprezentate ca obiecte cu proprietăți , ceea ce se potrivește perfect cu limbaje precum JavaScript. Toate nodurile au o proprietate comună: `type` , care identifică tipul de nod (VALUE, WORD, APPLY, ARRAY etc.) și, prin urmare, structura pe care o va avea restul obiectului.
Nodurile VALUE sunt utilizate pentru constante literale . Acestea conțin o proprietate, adesea numită valoare , unde este stocat numărul sau șirul pe care îl reprezintă. Nu au copii suplimentari, deoarece conținutul lor este descris complet de acel literal.
Nodurile Word sunt rezervate pentru identificatori : nume de variabile, nume de funcții, nume de parametri și altele asemenea. De obicei, acestea au o proprietate `name` care stochează identificatorul ca șir de caractere. Similar nodurilor VALUE, acestea acționează ca frunze în arbore, deoarece unicul lor scop este de a furniza acel nume.
Nodurile Apply reprezintă aplicații sau apeluri. Acestea includ o proprietate operator , care indică expresia (un alt nod) aplicată, și o proprietate args , care face legătura cu un nod ARRAY. Acesta din urmă este un nod specific în cadrul AST, al cărui scop este de a conține lista de argumente a aplicației .
Nodul ARRAY poate fi înțeles ca un container structurat pentru alte noduri, reprezentând o secvență de subarbori. Din perspectiva arității, introduce flexibilitate deoarece permite apeluri fără argumente, cu un singur argument sau cu argumente multiple în cadrul aceleiași instrucțiuni APPLY, fără a fi nevoie să se modifice definiția tipului de nod principal.
Exemplu de AST: aplicație simplă cu o singură valoare
Pentru a vizualiza toate cele de mai sus, să ne gândim la reprezentarea unei instrucțiuni simple, cum ar fi o aplicație a unei funcții X cu un singur argument 5. AST-ul generat de parser corespunde unui termen construit cu nodurile VALUE, WORD și APPLY , urmând regulile lui Egg.
La nivel conceptual, am avea un nod APPLY la rădăcină. Proprietatea sa de tip operator ar indica un nod WORD numit X, iar proprietatea sa de tip args s-ar referi la un nod ARRAY care conține un singur element: un nod VALUE cu valoarea numerică 5. În acest fel, structura reflectă clar cui se aplică și la ce se aplică.
Dacă am dori să facem toate atributele explicite, am putea scrie o notație mai detaliată care să arate tipul, operatorul, argumentele, numele și valoarea. Această notație mai detaliată este foarte utilă pentru depanarea parserului sau pentru înțelegerea modului în care o expresie textuală este tradusă într-un obiect arborescent în cadrul interpretorului.
În implementările din lumea reală, acest arbore este de obicei serializat ca JSON pentru stocare, transmitere sau inspecție ușoară. De fapt, instrumentele și modulele, cum ar fi pachetul evm2term din ecosistemul npm, oferă reprezentări compacte ale acestor AST-uri pentru o analiză sau transformare mai ușoară.
Exemplu de AST: adunare și înmulțire imbricate
Un alt caz tipic este o expresie puțin mai complexă, cum ar fi „+(a, *(4, 5))” . Aici avem o operație de adunare al cărei prim argument este identificatorul a și al cărei al doilea argument este rezultatul înmulțirii lui 4 cu 5. AST-ul care rezultă din această expresie reflectă acea structură imbricată.
La rădăcina arborelui, am avea din nou un nod APPLY care reprezintă operația de adunare. Operatorul său ar fi un nod WORD numit „+”, în timp ce argumentele sale s-ar afla într-un nod ARRAY cu două elemente: primul, un WORD numit „a”; al doilea, un alt nod APPLY care reprezintă înmulțirea.
A doua instrucțiune APPLY ar avea ca operator un WORD numit „*” și ca argumente un ARRAY cu două noduri VALUE: unul cu valoarea 4 și celălalt cu valoarea 5. Privită în ansamblu, structura arată clar că ordinea de evaluare constă în înmulțirea lui 4 cu 5 și apoi adunarea rezultatului la a.
Dacă extindem notația pentru a include toate atributele, am vedea tipurile tuturor nodurilor, numele sau valorile lor specifice și relațiile dintre ele. Această descriere explicită corespunde implementării propriu-zise în interpretorul Egg, unde fiecare nod este un obiect cu proprietățile menționate anterior.
Gramatica arborelui și gramatica parserului
Modul în care sunt generate aceste AST-uri nu este arbitrar: se bazează pe ceea ce se numește o gramatică arborescentă . Într-o formulare tipică, o astfel de gramatică este definită ca un cvadruplu compus dintr-un alfabet cu aritate, un set finit de variabile sintactice (neterminale), un set finit de reguli de producție și un simbol de început.
În fiecare regulă de producție, o variabilă este înlocuită de un arbore a cărui rădăcină este un simbol al alfabetului cu aritate și ai cărui copii sunt la rândul lor variabile sau arbori deja definiți. Această structură amintește de gramaticile clasice regulate sau independente de context, dar este adaptată generării directe de arbori în loc de șiruri de simboluri.
Legată de această definiție mai formală este gramatica specifică pe care parserul lui Egg o folosește pentru a produce arborii săi. Această gramatică, care este de obicei prezentată informal în documentație, descrie exact ce combinații de cuvinte cheie, operatori, paranteze și așa mai departe sunt acceptate în limbaj și cum se traduc acestea în noduri de tip VALUE, WORD, APPLY și ARRAY.
Această gramatică arborescentă poate fi văzută ca un caz special a ceea ce este cunoscut în literatura de specialitate sub numele de gramatică arborescentă regulată . Ideea este de a avea reguli bine definite pentru convertirea unei secvențe de jetoane de intrare într-un AST structurat care poate fi apoi interpretat sau compilat.
Notația Dewey: coordonate într-un arbore
Odată ce avem AST, adesea trebuie să ne referim la subarbori specifici : de exemplu, al doilea argument al unei funcții, operatorul unei expresii etc. O modalitate foarte elegantă de a face acest lucru este așa-numita notație zecimală Dewey, care împrumută schema utilizată pentru numerotarea secțiunilor și subsecțiunilor din documente.
În această notație, pornind de la un arbore t, un subarbore este notat printr-un șir de numere separate prin puncte . Fiecare număr indică poziția unui copil (de obicei începând de la 1), iar secvența coboară în arbore. Astfel, o expresie precum t/2.1.3 se referă la al treilea copil al primului copil al celui de-al doilea copil al lui t.
Definiția inductivă a acestei notații este simplă: șirul gol se referă la întregul arbore; dacă un șir constă dintr-un număr urmat de mai multe numere separate prin puncte, acesta este interpretat prin luarea mai întâi a subarborelelui copil corespunzător indexului indicat și apoi aplicarea recursivă a aceleiași logici la restul șirului.
De exemplu, dacă avem un arbore t care reprezintă o expresie de genul „+(a, *(4,5))”, cu un nod rădăcină APPLY pentru adunare, un copil WORD numit „+” și un alt copil APPLY pentru înmulțire, putem identifica poziții specifice. Astfel, t/1 ar putea fi nodul WORD cu operatorul „+”, t/2.1 identificatorul „a” și t/2.2.2.1 nodul VALUE cu valoarea 4, dacă numerotăm copiii corespunzător.
Această modalitate de a oferi „coordonate” în cadrul unui AST este foarte utilă pentru indicarea locațiilor specifice atunci când se raportează erori, se navighează în arbore sau se aplică transformări locale unor noduri specifice, fără ambiguitate.
Notații echivalente în programare și instrumente
Ideea din spatele notației lui Dewey nu este exclusivă teoriei arborilor; de fapt, ea apare în mod repetat în multe notații practice pe care le folosim zilnic în programare și manipularea datelor structurate, chiar dacă nu suntem întotdeauna conștienți de aceasta.
Când scriem expresii cu operatorul punct într-un limbaj de programare , cum ar fi object.property.subproperty, facem ceva foarte similar: parcurgem un arbore de obiecte imbricate, selectând un copil la fiecare pas după nume în loc de numărul poziției. Pornind de la un nod rădăcină, coborâm la mai multe noduri interne.
Același model apare și în sistemele de fișiere de tip Unix, unde operatorul slash înainte (/) este utilizat pentru a separa directoarele: /src/js/tutu.js descrie o cale de la rădăcina sistemului de fișiere către o resursă specifică, traversând niveluri succesive ale unei structuri arborescente.
În lumea documentelor structurate, limbaje precum XPath utilizează notații foarte similare pentru a selecta noduri dintr-un arbore XML. O interogare precum „A//B/*” alege primul copil (indiferent de numele său) al fiecărui element B care este descendent al unui element A în poziția corespunzătoare față de contextul curent, folosind bare oblice simple și duble pentru a indica nivelurile de adâncime.
Un alt instrument binecunoscut, limbajul jq , folosește un sistem paralel pentru navigarea structurilor JSON, permițând selectarea subobiectelor prin căi compozite, filtre și expresii. Toate aceste notații sunt pur și simplu moduri diferite de exprimare a căilor într-un arbore , foarte în concordanță cu notația zecimală Dewey, dar adaptate domeniilor respective.
Arbori de analiză sintactică în lingvistică și programare
Dincolo de lumea compilatoarelor, arborii sintactici sunt utilizați și în lingvistică pentru a reprezenta structura propozițiilor. Acolo, aceștia sunt numiți arbori de derivare sau arbori de analiză sintactică, care arată cum o propoziție este descompusă în fraze, cuvinte și categorii gramaticale.
În acești arbori, la fel ca în programare, găsim trei tipuri de bază de noduri: un nod rădăcină , care reprezintă propoziția completă sau structura globală; noduri interne sau ramificate, care funcționează ca noduri părinte și subseturi de grup ale propoziției; și noduri frunză, care corespund de obicei cuvintelor specifice care apar în șirul de intrare.
Nodul rădăcină este unic: întreaga structură arborescentă atârnă de el. Nodurile ramificate sunt situate imediat sub nodul rădăcină sau alte noduri părinte și servesc la organizarea ierarhică a părților propoziției sau programului. Nodurile frunză, pe de altă parte, se găsesc la cel mai scăzut nivel al arborelui și nu au copii, închizând astfel structura ramificată.
Acești arbori sunt considerați instrumente pedagogice puternice, deoarece ajută la descompunerea propozițiilor complexe în elemente ușor de gestionat. Același lucru este valabil și pentru programare: un AST bine construit vă permite să vedeți dintr-o privire ce operații sunt legate între ele, ce expresii sunt imbricate și cum decurge evaluarea.
În funcție de obiectivul analizei, putem găsi diferite tipuri de arbori de analiză . Unii pun accentul pe dependențele dintre cuvinte sau componente (de exemplu, cine depinde de cine într-o propoziție), în timp ce alții se concentrează pe gruparea în sintagme sau constituenți, rezultând două familii principale.
Arbori sintactice după dependență și după circumscripție
Unul dintre cele mai cunoscute tipuri este arborele sintactic bazat pe dependențe . În această variantă, toate cuvintele din propoziție sau toate elementele relevante sunt tratate ca noduri frunză, iar legăturile dintre ele indică relații de dependență directă (de exemplu, un verb principal și subiectul său). Drept urmare, se produc adesea arbori cu mai puține noduri decât în alte scheme.
Această simplitate le face deosebit de convenabile pentru începători și pentru anumite sarcini de procesare a limbajului, deoarece structura se concentrează pe cine depinde de cine, fără a introduce atât de multe noduri intermediare. Aplicată programării, ideea este de a se rămâne doar la relațiile esențiale, omițând înfloriturile gramaticale.
La cealaltă extremă, avem arbori sintactici bazați pe constituenți sau constituenți, care fac distincția între nodurile rădăcină, nodurile de ramificare interne și nodurile frunză și fac vizibile toate grupările relevante. Acești arbori conțin de obicei mai multe noduri și reflectă structura ierarhică a propoziției sau programului mai detaliat.
Șabloanele arborelui de circumscripție întâlnite frecvent afișează propoziții lungi cu numeroase noduri frunză, mai multe niveluri de ramificare și un nod rădăcină bine definit. Sunt utile în special pentru disecția propozițiilor complexe sau a programelor cu mai multe straturi de structuri imbricate.
Atât în arborii de dependențe, cât și în cei de constituenți, exemplele și resursele vizuale sunt disponibile ca șabloane, permițându-vă să completați pur și simplu nodurile cu informațiile dorite. Acest lucru economisește timp și evită necesitatea de a proiecta diagrama de la zero de fiecare dată când doriți să ilustrați o structură.
Aplicații practice și instrumente legate de AST
AST-urile nu sunt doar un concept teoretic: ele sunt utilizate activ într-o multitudine de instrumente de zi cu zi de către oricine lucrează cu cod. Compilatoarele, interpretoarele, minificatoarele, formatatoarele de cod și analizoarele statice se bazează aproape întotdeauna pe un AST pentru a-și îndeplini funcția.
Un compilator tipic preia codul sursă, îl tokenizează, îl analizează și generează un arbore sintactic abstract. De acolo, efectuează verificări semantice (tipuri, domeniul de aplicare al variabilelor, utilizări incorecte ale construcțiilor) și aplică optimizarea codului prin parcurgerea și transformarea AST înainte de a produce cod mașină sau bytecode.
Instrumente precum linterele sau formatoarele funcționează și ele pe AST: acestea analizează structura pentru a detecta modele problematice, practici greșite sau inconsecvențe și propun modificări care mențin structura semantică a arborelui, dar ajustează prezentarea codului.
În ecosistemul JavaScript, de exemplu, există mai multe biblioteci care expun AST în format JSON, facilitând utilizarea acestuia de către alte instrumente pentru a efectua refactorizare, a genera documentație automată sau a crea vizualizări ale structurii programelor complexe.
Chiar și în domenii ceva mai specializate, cum ar fi instrumentația pentru măsurarea acoperirii testelor sau transformarea codului sursă în alte limbaje, AST este fundamentul pe care se bazează multe soluții moderne, deoarece permite lucrul la un nivel de abstractizare foarte confortabil între textul brut și codul mașină.
Luați împreună, arborii sintactici abstracti sunt elementul cheie care conectează gramatica formală a unui limbaj, reprezentarea sa internă în compilator sau interpretor și instrumentele avansate pe care le folosim pentru a scrie, analiza și transforma codul în siguranță și eficient. Înțelegerea modului în care sunt construiți, a modului de navigare prin ei (cu concepte precum notația zecimală Dewey) și a tipurilor de noduri implicate (VALUE, WORD, APPLY, structuri de aritate fixe sau variabile etc.) ne ajută să vedem mult mai clar ce face de fapt mașina atunci când procesează un program.
