Alberi di sintassi astratta nella programmazione: una guida completa

Informatec Digital » Risorse » Alberi di sintassi astratta nella programmazione: una guida completa

Gli alberi di sintassi astratta nella programmazione sono uno di quei concetti che inizialmente sembrano molto teorici, ma una volta compresi, ci si rende conto che sono ovunque: nei compilatori, negli interpreti , nell'analisi del codice, negli strumenti di refactoring, persino nei linguaggi di interrogazione di dati strutturati. In sostanza, rappresentano il modo in cui una macchina "comprende" la struttura di un programma al di là del semplice testo.

Sebbene a volte vengano confusi con i classici alberi di analisi sintattica, gli alberi di sintassi astratta (AST) hanno regole proprie. Un albero di sintassi astratta non è solo un bel disegno: è una struttura dati compatta e ben progettata che elimina tutto ciò che è superfluo dalla sintassi concreta (parentesi, virgole, parole chiave ridondanti, ecc.) e si concentra sull'essenziale: quali operazioni vengono eseguite, su quali valori e in quale ordine.

Che cos'è esattamente un albero sintattico astratto (AST)?

Nella teoria dei linguaggi di programmazione, un albero sintattico astratto (AST) è una struttura ad albero che rappresenta la sintassi di un programma, ma in una forma semplificata rispetto a un albero di analisi sintattica concreto. Contiene le stesse informazioni essenziali di un albero di analisi sintattica, ma organizzate in modo più compatto e gestibile.

Un albero di analisi sintattica contiene tutte le produzioni della grammatica e tutti i simboli terminali, incluse parentesi, virgole, punti e virgola e altri elementi puramente sintattici. L'AST, d'altra parte, rimuove questi dettagli che non contribuiscono al significato semantico e conserva solo la struttura logica delle espressioni e delle frasi.

In termini di implementazione, un AST è solitamente composto da oggetti nodo con un tipo che indica di che tipo di costrutto si tratta (costante, identificatore, applicazione di funzione, operatore binario, ecc.) e proprietà aggiuntive che ne descrivono il contenuto: valore, nome, figli, elenco di argomenti e così via.

Il pregio dell'AST è che facilita le fasi successive del compilatore o dell'interprete, come il controllo dei tipi, le ottimizzazioni o la generazione del codice , perché offre una visione chiara della struttura del programma, priva di rumore sintattico.

Differenza tra un albero sintattico concreto e un albero sintattico astratto

Per comprendere appieno il contributo di un AST, è utile confrontare innanzitutto l' albero di analisi sintattica concreto con quello astratto. Immaginiamo una grammatica semplice che riconosce espressioni aritmetiche come "a + 4 * 5" . L'albero di analisi sintattica concreto riflette accuratamente l'applicazione di ogni regola grammaticale: simboli non terminali, terminali, parentesi, operatori, ecc.

Questo particolare albero è solitamente profondo e presenta molti nodi intermedi che servono unicamente a mantenere la struttura formale della grammatica. Ad esempio, potrebbero esserci nodi per "Espressione", "Termine", "Fattore" e poi simboli terminali come "+" , "*" , identificatori e numeri. Ogni produzione diventa un ramo dell'albero, aumentando la complessità strutturale.

L'albero sintattico astratto per la stessa espressione, d'altra parte, si limita a rappresentare le operazioni e gli operandi effettivi . Pertanto, invece di diversi livelli di "Espressione" e "Termine", potremmo avere un nodo radice che rappresenta l'addizione, con due figli: a sinistra un identificatore a e a destra un nodo di moltiplicazione i cui figli sono i valori 4 e 5. I nodi puramente grammaticali scompaiono e parti della struttura vengono riordinate o condensate.

Ciò significa che l'AST e l'albero sintattico concreto contengono le stesse informazioni semantiche , ma il primo le presenta in una forma molto più diretta e compatta. Questa condensazione è fondamentale per lavorare in modo efficiente con il codice negli strumenti di analisi o di esecuzione.

Alberi e alfabeti con funzione di arità

Per formalizzare questi alberi da un punto di vista matematico, si utilizza solitamente l'idea di un alfabeto con una funzione di arità . Invece di un semplice insieme di simboli, si definisce un alfabeto in cui a ciascun simbolo è associato un numero che indica quanti figli può avere nell'albero.

Un alfabeto con una funzione di arità è, informalmente, una coppia composta da un insieme finito di simboli e una funzione che assegna a ciascun simbolo un numero naturale (incluso lo zero). Questo numero indica l'arità del simbolo: se è 0, il simbolo si comporta come una foglia; se è 1, si comporta come un nodo unario; se è 2, è binario; e così via. È anche comune consentire simboli di arità variabile per gli operatori come liste di argomenti.

I simboli di arità 0 corrispondono alle foglie dell'albero (ad esempio, costanti o identificatori). I simboli di arità 1 sono utilizzati per costrutti che coinvolgono una singola espressione figlia. I simboli di arità 2 rappresentano le classiche operazioni binarie come addizione, moltiplicazione, assegnazione, ecc. Infine, i simboli di arità variabile consentono di modellare costrutti che accettano un numero indeterminato di sottoalberi, come ad esempio una chiamata di funzione con più parametri.

A partire da questo alfabeto con arità, è possibile definire l'insieme di tutti gli alberi possibili: partendo dall'albero vuoto (quando considerato), aggiungendo tutti i simboli di arità 0 e variabile, ed estendendo induttivamente: se un simbolo è k-ario, può essere posto come nodo genitore di k sottoalberi già costruiti. Questo produce il linguaggio ad albero (o termine) associato all'alfabeto.

Il linguaggio degli alberi e la nozione di nodo

L'insieme di tutti gli alberi formati con un alfabeto e la sua funzione di arità è chiamato, in questo contesto, linguaggio ad albero o linguaggio dei termini . È l'equivalente, ma per le strutture ad albero, di ciò che la chiusura di Kleene è per le stringhe.

Così come nell'analisi delle stringhe usiamo il termine token per riferirci alle occorrenze dei simboli alfabetici all'interno di una sequenza, quando lavoriamo con gli alberi usiamo solitamente il termine nodi . Un nodo è, essenzialmente, una specifica occorrenza di un simbolo alfabetico con arità situata in una particolare posizione nell'albero.

Da questa prospettiva, questo linguaggio ad albero sta ai nodi come un insieme di stringhe sta alle occorrenze di token. Ogni albero viene interpretato come una struttura costruita passo dopo passo a partire dall'alfabeto, e i nodi sono i singoli elementi che materializzano fisicamente i suoi simboli.

Questo modo di vedere le cose è molto utile nella progettazione di parser e generatori di AST , perché permette di ragionare sulle regole di costruzione di questi alberi in modo analogo alla grammatica delle stringhe, ma lavorando direttamente su strutture gerarchiche.

Arità dei nodi in uno specifico AST: il caso di Egg

Passando dalla teoria a un esempio pratico, molti materiali didattici utilizzano il linguaggio Egg per illustrare la costruzione e la manipolazione degli AST (Abstract Syntax Tree). In questo contesto, vengono utilizzati diversi tipi principali di nodi, ognuno con un'arità ben definita , il che li rende molto facili da manipolare.

In un tipico Egg AST, i nodi VALUE sono considerati foglie: rappresentano valori letterali come stringhe o numeri. Non hanno figli; memorizzano solo un valore. Allo stesso modo, i nodi WORD , utilizzati per gli identificatori (nomi di variabili, nomi di funzioni, ecc.), sono anch'essi trattati come foglie con una proprietà che memorizza il nome.

Il nodo chiave in Egg è il tipo APPLY , che rappresenta l'applicazione di una funzione o di un operatore. Questo tipo di nodo ha due figli concettuali: un figlio OPERATOR che punta all'espressione da applicare; e un figlio ARGS , che in realtà è uno speciale nodo ARRAY responsabile della gestione di una collezione di sottoalberi, uno per ogni argomento.

Gli array, quindi, rappresentano un modo naturale per introdurre l'arità variabile nell'AST: un'operazione APPLY ha sempre due componenti (operatore e lista di argomenti), ma tale lista interna può contenere zero, uno o molti sottoalberi a seconda della specifica chiamata rappresentata.

Anatomia dettagliata dei nodi AST nell'uovo

A livello di implementazione, i nodi AST di Egg sono tipicamente rappresentati come oggetti con proprietà , il che si adatta perfettamente a linguaggi come JavaScript. Tutti i nodi condividono una proprietà comune: `type` , che identifica il tipo di nodo (VALUE, WORD, APPLY, ARRAY, ecc.) e, di conseguenza, la struttura che avrà il resto dell'oggetto.

I nodi VALUE vengono utilizzati per le costanti letterali . Contengono una proprietà, spesso chiamata value , in cui viene memorizzato il numero o la stringa che rappresentano. Non hanno figli aggiuntivi perché il loro contenuto è completamente descritto da quel letterale.

I nodi parola sono riservati agli identificatori : nomi di variabili, nomi di funzioni, nomi di parametri e simili. In genere hanno una proprietà `name` che memorizza l'identificatore come stringa. Analogamente ai nodi VALORE, agiscono come foglie nell'albero, poiché il loro unico scopo è quello di fornire quel nome.

I nodi Apply rappresentano applicazioni o chiamate. Includono una proprietà operator , che punta all'espressione (un altro nodo) che viene applicata, e una proprietà args , che si collega a un nodo ARRAY. Quest'ultimo è un nodo specifico all'interno dell'AST, il cui scopo è quello di contenere l' elenco degli argomenti dell'applicazione .

Il nodo ARRAY può essere inteso come un contenitore strutturato per altri nodi, che rappresenta una sequenza di sottoalberi. Dal punto di vista dell'arità, introduce flessibilità perché consente chiamate senza argomenti, con un argomento o con più argomenti all'interno della stessa istruzione APPLY, senza dover modificare la definizione del tipo di nodo principale.

Esempio di AST: semplice applicazione con un valore

Per visualizzare tutto quanto sopra, consideriamo la rappresentazione di una semplice istruzione, come l'applicazione di una funzione X con un singolo argomento 5. L'AST generato dal parser corrisponde a un termine costruito con nodi VALUE, WORD e APPLY , seguendo le regole di Egg.

A livello concettuale, avremmo un nodo APPLY alla radice. La sua proprietà operator punterebbe a un nodo WORD chiamato X, e la sua proprietà args farebbe riferimento a un nodo ARRAY contenente un singolo elemento: un nodo VALUE con il valore numerico 5. In questo modo, la struttura riflette chiaramente a chi viene applicata e a cosa viene applicata.

Se volessimo rendere espliciti tutti gli attributi, potremmo scrivere una notazione più dettagliata che mostri il tipo, l'operatore, gli argomenti, il nome e il valore. Questa notazione più verbosa è molto utile per il debug del parser o per capire come un'espressione testuale viene tradotta in un oggetto ad albero all'interno dell'interprete.

Nelle implementazioni reali, questo albero viene tipicamente serializzato in formato JSON per facilitarne l'archiviazione, la trasmissione o l'ispezione. Infatti, strumenti e moduli, come il pacchetto evm2term nell'ecosistema npm, forniscono rappresentazioni compatte di questi AST per semplificarne l'analisi o la trasformazione.

Esempio di AST: addizione e moltiplicazione annidate

Un altro caso tipico è un'espressione leggermente più complessa, come "+(a, *(4, 5))" . Qui abbiamo un'operazione di addizione il cui primo argomento è l'identificatore a e il cui secondo argomento è il risultato della moltiplicazione di 4 per 5. L'AST risultante da questa espressione riflette tale struttura annidata.

Alla radice dell'albero, avremmo di nuovo un nodo APPLY che rappresenta l'operazione di addizione. Il suo operatore sarebbe un nodo WORD chiamato "+", mentre i suoi argomenti sarebbero in un nodo ARRAY con due elementi: il primo, una WORD chiamata "a"; il secondo, un altro nodo APPLY che rappresenta la moltiplicazione.

Quel secondo APPLY avrebbe come operatore una PAROLA chiamata "*" e come argomenti un ARRAY con due nodi VALUE: uno con valore 4 e l'altro con valore 5. Vista nel suo insieme, la struttura mostra chiaramente che l'ordine di valutazione consiste nel moltiplicare 4 per 5 e quindi aggiungere il risultato ad a.

Se estendessimo la notazione per includere tutti gli attributi, vedremmo i tipi di tutti i nodi, i loro nomi o valori specifici e le relazioni tra di essi. Questa descrizione esplicita corrisponde all'implementazione effettiva nell'interprete Egg, dove ogni nodo è un oggetto con le proprietà sopra menzionate.

Grammatica ad albero e grammatica del parser

Il modo in cui questi AST vengono generati non è arbitrario: si basa su quella che viene chiamata grammatica ad albero . In una formulazione tipica, tale grammatica è definita come una quadrupla composta da un alfabeto con arità, un insieme finito di variabili sintattiche (non terminali), un insieme finito di regole di produzione e un simbolo iniziale.

In ogni regola di produzione, una variabile viene sostituita da un albero la cui radice è un simbolo dell'alfabeto con arità, e i cui figli sono a loro volta variabili o alberi già definiti. Questa struttura ricorda le grammatiche regolari o libere dal contesto classiche, ma è adattata alla generazione diretta di alberi anziché di stringhe di simboli.

Collegata a questa definizione più formale è la grammatica specifica che il parser di Egg utilizza per generare i suoi alberi. Questa grammatica, che di solito viene presentata in modo informale nella documentazione, descrive esattamente quali combinazioni di parole chiave, operatori, parentesi e così via sono accettate nel linguaggio e come si traducono in nodi di tipo VALUE, WORD, APPLY e ARRAY.

Questa grammatica ad albero può essere vista come un caso speciale di ciò che in letteratura è noto come grammatica ad albero regolare . L'idea è di avere regole ben definite per convertire una sequenza di token di input in un AST strutturato che possa poi essere interpretato o compilato.

Notazione Dewey: coordinate all'interno di un albero

Una volta ottenuto l'AST, spesso è necessario fare riferimento a specifici sottoalberi : ad esempio, il secondo argomento di una funzione, l'operatore di un'espressione, ecc. Un modo molto elegante per farlo è la cosiddetta notazione decimale Dewey, che riprende lo schema utilizzato per numerare sezioni e sottosezioni nei documenti.

In questa notazione, a partire da un albero t, un sottoalbero è indicato da una sequenza di numeri separati da punti . Ogni numero indica la posizione di un figlio (di solito a partire da 1) e la sequenza procede lungo l'albero. Pertanto, un'espressione come t/2.1.3 si riferisce al terzo figlio del primo figlio del secondo figlio di t.

La definizione induttiva di questa notazione è semplice: la stringa vuota si riferisce all'intero albero; se una stringa è composta da un numero seguito da altri numeri separati da punti, viene interpretata prendendo prima il sottoalbero figlio corrispondente all'indice indicato e poi applicando la stessa logica ricorsivamente al resto della stringa.

Ad esempio, se abbiamo un albero t che rappresenta un'espressione come "+(a, *(4,5))", con un nodo radice APPLY per l'addizione, un figlio WORD chiamato "+", e un altro figlio APPLY per la moltiplicazione, possiamo identificare posizioni specifiche. Quindi, t/1 potrebbe essere il nodo WORD con l'operatore "+", t/2.1 l'identificatore "a", e t/2.2.2.1 il nodo VALUE con il valore 4, se numeriamo i figli in modo appropriato.

Questo modo di fornire "coordinate" all'interno di un AST è molto utile per indicare posizioni specifiche quando si segnalano errori, per navigare nell'albero o per applicare trasformazioni locali a nodi specifici senza ambiguità.

Notazioni equivalenti nella programmazione e negli strumenti

L'idea alla base della notazione di Dewey non è esclusiva della teoria degli alberi; infatti, ricorre spesso in molte notazioni pratiche che utilizziamo quotidianamente nella programmazione e nella gestione di dati strutturati, anche se non sempre ne siamo consapevoli.

Quando scriviamo espressioni con l' operatore punto in un linguaggio di programmazione , come ad esempio object.property.subproperty, stiamo facendo qualcosa di molto simile: attraversiamo un albero di oggetti annidati, selezionando un elemento figlio a ogni passaggio in base al nome anziché al numero di posizione. Partendo da un nodo radice, scendiamo verso nodi più interni.

Lo stesso schema si ripete nei file system di tipo Unix, dove l' operatore barra (/) viene utilizzato per separare le directory: /src/js/tutu.js descrive un percorso dalla radice del file system a una risorsa specifica, attraversando livelli successivi di una struttura ad albero.

Nel mondo dei documenti strutturati, linguaggi come XPath utilizzano notazioni molto simili per selezionare i nodi all'interno di un albero XML. Una query come "A//B/*" seleziona il primo figlio (indipendentemente dal suo nome) di ogni elemento B che sia un discendente di un elemento A nella posizione appropriata rispetto al contesto corrente, utilizzando barre singole e doppie per indicare i livelli di profondità.

Un altro strumento ben noto, il linguaggio jq , utilizza un sistema parallelo per navigare nelle strutture JSON, consentendo la selezione di sotto-oggetti tramite percorsi compositi, filtri ed espressioni. Tutte queste notazioni sono semplicemente modi diversi di esprimere percorsi in un albero , molto simili alla notazione decimale Dewey ma adattate ai rispettivi domini.

Analisi sintattica degli alberi in linguistica e programmazione

Oltre che nel mondo dei compilatori, gli alberi sintattici vengono utilizzati anche in linguistica per rappresentare la struttura delle frasi. In questo ambito, sono chiamati alberi di derivazione o alberi di analisi sintattica e mostrano come una frase viene scomposta in sintagmi, parole e categorie grammaticali.

In questi alberi, proprio come nella programmazione, troviamo tre tipi fondamentali di nodi: un nodo radice , che rappresenta l'intera frase o la struttura globale; nodi interni o ramificati, che fungono da nodi genitori e raggruppano sottoinsiemi della frase; e nodi foglia, che di solito corrispondono alle parole specifiche presenti nella stringa di input.

Il nodo radice è unico: l'intera struttura ad albero si sviluppa a partire da esso. I nodi di diramazione si trovano immediatamente al di sotto della radice o di altri nodi genitori e servono a organizzare gerarchicamente le parti della frase o del programma. I nodi foglia, invece, si trovano al livello più basso dell'albero e non hanno figli, chiudendo così la struttura ramificata.

Questi alberi sono considerati potenti strumenti pedagogici perché aiutano a scomporre frasi complesse in elementi gestibili. Lo stesso vale per la programmazione: un AST ben costruito permette di vedere a colpo d'occhio quali operazioni sono concatenate, quali espressioni sono annidate e come procede la valutazione.

A seconda dell'obiettivo dell'analisi, possiamo trovare diversi tipi di alberi di analisi . Alcuni enfatizzano le dipendenze tra parole o componenti (ad esempio, chi dipende da chi in una frase), mentre altri si concentrano sul raggruppamento in sintagmi o costituenti, dando luogo a due famiglie principali.

Alberi sintattici per dipendenza e per costituente

Uno dei tipi più noti è l' albero sintattico basato sulle dipendenze . In questa variante, tutte le parole della frase o tutti gli elementi rilevanti sono trattati come nodi foglia, e i collegamenti tra di essi indicano relazioni di dipendenza diretta (ad esempio, un verbo principale e il suo soggetto). Di conseguenza, si ottengono spesso alberi con un numero inferiore di nodi rispetto ad altri schemi.

Questa semplicità li rende particolarmente adatti ai principianti e per determinate attività di elaborazione del linguaggio, poiché la struttura si concentra sulle relazioni di dipendenza senza introdurre troppi nodi intermedi. Applicata alla programmazione, l'idea è di attenersi solo alle relazioni essenziali, omettendo gli abbellimenti grammaticali.

All'altro estremo, abbiamo gli alberi sintattici basati su costituenti o elementi, che distinguono tra nodi radice, nodi di ramificazione interni e nodi foglia, rendendo visibili tutti i raggruppamenti rilevanti. Questi alberi di solito contengono più nodi e riflettono la struttura gerarchica della frase o del programma in modo più dettagliato.

I modelli di albero delle circoscrizioni elettorali comunemente utilizzati mostrano frasi lunghe con numerosi nodi foglia, diversi livelli di ramificazione e un nodo radice ben definito. Sono particolarmente utili per analizzare frasi complesse o programmi con più livelli di strutture annidate.

Sia negli alberi di dipendenza che in quelli di costituente, sono disponibili esempi e risorse visive sotto forma di modelli, che consentono di compilare semplicemente i nodi con le informazioni desiderate. Ciò consente di risparmiare tempo ed evita di dover progettare il diagramma da zero ogni volta che si desidera illustrare una struttura.

Applicazioni pratiche e strumenti relativi all'AST

Gli AST non sono solo un concetto teorico: vengono utilizzati attivamente in una moltitudine di strumenti di uso quotidiano da chiunque lavori con il codice. Compilatori, interpreti, minificatori, formattatori di codice e analizzatori statici si basano quasi sempre su un AST per svolgere la loro funzione.

Un compilatore tipico prende il codice sorgente, lo suddivide in token, lo analizza sintatticamente e genera un albero sintattico astratto. Da lì, esegue controlli semantici (tipi, ambito delle variabili, usi errati delle strutture) e applica l'ottimizzazione del codice attraversando e trasformando l'AST prima di produrre il codice macchina, o bytecode.

Strumenti come i linter o i formattatori funzionano anche sull'AST: analizzano la struttura per individuare schemi problematici, cattive pratiche o incongruenze e propongono modifiche che mantengono la struttura semantica dell'albero ma ne migliorano la presentazione del codice.

Nell'ecosistema JavaScript, ad esempio, esistono diverse librerie che espongono l'AST in formato JSON, facilitando così l'utilizzo da parte di altri strumenti per eseguire il refactoring, generare documentazione automatica o creare visualizzazioni della struttura di programmi complessi.

Anche in ambiti più specializzati, come la strumentazione per la misurazione della copertura dei test o la trasformazione del codice sorgente in altri linguaggi, l'AST (Abstract Syntax Tree) costituisce il fondamento su cui si basano molte soluzioni moderne, poiché consente di lavorare a un livello di astrazione molto agevole tra testo grezzo e codice macchina.

Nel loro insieme, gli alberi sintattici astratti sono l'elemento chiave che collega la grammatica formale di un linguaggio, la sua rappresentazione interna nel compilatore o nell'interprete e gli strumenti avanzati che utilizziamo per scrivere, analizzare e trasformare il codice in modo sicuro ed efficiente. Comprendere come sono costruiti, come navigarli (con concetti come la notazione decimale Dewey) e quali tipi di nodi sono coinvolti (VALORE, PAROLA, APPLICA, strutture ad arità fissa o variabile, ecc.) ci aiuta a vedere molto più chiaramente cosa sta effettivamente facendo la macchina quando elabora un programma.