Matematica in PHP: Abstract Syntax Tree

25 settembre 2008

Torniamo con un ultimo articolo ad un ciclo di approfondimenti che avevamo dedicato all’analisi e all’esecuzione di espressioni matematiche in PHP. Per poter comprendere l’argomento è necessario aver metabolizzato ciò che abbiamo indicato nel primo (Espressioni matematiche in PHP: la teoria) e nel secondo articolo (Espressioni matematiche in PHP: la pratica) pubblicati alcune settimane or sono.

L’AST (Abstract Syntax Tree)

Durante la fase di parsing, ogni metodo evidenziato nell’articolo precedente si occupa di generare un node AST. Il nodo AST ha come scopo quello di rappresentare un dato costrutto grammaticale attraverso una semplice struttura ad albero; gli alberi in programmazione sono strutture dati semplici ma estremamente potenti dato che, con le opportune modifiche, sono in grado di rappresentare una svariata quantità di dati mantenendo comunque un organizzazione semplice da interrogare ed esaminare ricorsivamente.

Quando si ha a che vedere con la scrittura di un compilatore o interprete, la fase di generazione dell’AST precede quella di ottimizzazione del flusso e generazione di codice (che può essere intermedio oppure codice oggetto); ogni nodo dell’albero solitamente rappresenta una regola o sottorgola sintattica del linguaggio (nel nostro caso della semplice espressione) e, oltre ad un riferimento al tipo di nodo (solitamente ottenuto usando un indice numerico intero oppure sfruttando l’ereditarietà ed il polimorfismo in fase di analisi), ha anche riferimenti hai nodi da cui dipende.

Prendiamo una semplice espressione di esempio:

( 10 + 11 *4 ) * 3

Questa espressione verrà trasformata nel seguente albero sintattico dal parser (che, ricordiamo, tiene conto della precedenza degli operatori e delle eventuali parentesi di raggruppamento):

Moltiplicazione
    left    ->
        Somma
            left    ->
                Numero ( 10 )
            right    ->
                Moltiplicazione
                    left    ->
                        Numero( 11 )
                    right    ->
                        Numero ( 4 )
            
    right     ->
        Numero ( 3 )

Come possiamo notare dalla rappresentazione testuale dell’albero sintattico, ogni nodo che rappresenta un’operazione (in questo caso solamente Somma e Moltiplicazione) ha un nome che ne identifica il tipo e due sottonodi (left e right). Il nodo di tipo Number invece non ha sottonodi ma ha un valore associato che verrà utilizzato in fase di valutazione. Come potete notare, nel caso l’esecuzione dell’albero avvenga partendo dalla radice ed eseguendo prima il ramo a sinistra di un nodo e poi quello a destra, viene mantenuta anche la precedenza ed il raggruppamento degli operatori.

Solitamente è opportuno mantenere un albero sintattico compatto che eviti ridondanze o utilizzo di nodi inutili; nel nostro caso non abbiamo fatto ottimizzazioni di questo tipo e quindi in alcune situazione l’albero potrebbe risultare eccessivamente lungo ( come ad esempio nel caso di negazioni successive – che potrebbero essere annullate a due a due).

Se vuoi aggiornamenti su Matematica in PHP: Abstract Syntax Tree inserisci la tua e-mail nel box qui sotto:
 
X
Se vuoi aggiornamenti su Matematica in PHP: Abstract Syntax Tree

inserisci la tua e-mail nel box qui sotto:

Ho letto e acconsento l'informativa sulla privacy

Acconsento al trattamento di cui al punto 3 dell'informativa sulla privacy