È un albero radicato in cui i nodi intermedi rappresentano degli operatore, mentre le foglie gli operandi.
Arietà = numero di operandi per un operatore
Il numero di figli corrisponde all'arietà dell'operatore associato. La struttura ricorsiva dell'albero rappresenta la struttura ricorsiva dell'espresssione. Non servono espressioni.
L'espressione rappresentata dall'AST può essere valutata mediante una visita dell'albero in ordine posticipato (= visito i figli, poi applico l'operatore contenuto nel nodo. Devo conoscere il valore dei sotto-alberi per poterlo applicare).
Non solo le espressioni logico-aritmetiche possono essere descritte mediante un albero, ma anche le più importanti strutture di controllo.
#Ricorda eco del dibattito sul goto -> il GOTO non consente la programmazione strutturata. È tipico dei linguaggi di basso livello come l'assembler.
Eg:
- condizionale a due vie
if(<cond>) {<true section>} {<false section>}descritto da un albero ternario con condizione nel primo sottoalbero, TS nel secondo, FS nel terzo. - sequenza (tipica dei linguaggi strutturati):
<statement>; {<resto>}come albero binario con ; nella radice, statement nel primo ramo e resto nel secondo. Arresto la catena con<resto> := \0. Un questo modo i punti e virgola si trovano sulla dorsale di destra. - ciclo: albero binario con test nel figlio di destra e corpo nel figlio di sinistra. #Attenzione in questo caso la condizione dipende da cosa è successo nel corpo.
Nello statement = si trova a sinistra l'identificatore, a destra il valore. La foglia di sinistra punta tipicamente alla symbol table, che mantiene, oltre al nome, anche il tipo se il linguaggio è tipizzato.
#Ricorda i linguaggi imperativi si chiamano così perché scandiscono dei "comandi" impartiti al processore
Nei linguaggi imperativi una visita in post-ordine non è sufficiente per interpretare il codice: devo balzare avanti e indietro nell'albero più volte. È però sufficiente per produrre codice a tempo di compilazione.