Matematica in PHP: Abstract Syntax Tree

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).

Generazione dell'AST

La fase di generazione dell'AST è molto semplice: il Parser si occupa di validare l'input dal punto di vista sintattico e di tener conto delle eventuali precedenze; presupponendo che tutte le condizioni necessarie siano rispettate, viene istanziato un nodo appropriato e restituito dal flusso di parsing.

I nodi che compongono l'AST nel nostro caso sono i seguenti:

• AddExpression: addizione tra due termini;
• CallExpression: chiamata a funzione con un numero variabile di argomenti;
• DivExpression: divisione tra due fattori;
• IdentExpression: riferimento a variabile;
• MulExpression: moltiplicazione tra due fattori;
• NumberExpression: numero;
• SubExpression: sottrazione tra due termini;
• UnaryPlusExpression: più unario su un'unica espressione;
• UnaryMinusExpression: negazione unaria di un'unica espressione;

Tutte queste classi implementano l'interfaccia IExpression. I nodi che rappresentano un'operazione aritmetica tra due operandi hanno due sottonodi (left e right), i nodi che rappresentano operazioni unarie o costanti (numero ed identificatore) hanno un unico sottonodo, ed infine il nodo che rappresenta una chiamata a funzione contiene un array di nodi rappresentante gli argomenti della chiamata.

Ogni nodo nel nostro caso è responsabile di eseguire se stesso e di ritornare un valore numerico (come vedremo in seguito); i nodi stessi sono anche in grado di restituire la loro rappresentazione in notazione postfissa. Generalmente, per dare un po' più di flessibilità, si opta per utilizzare oggetti di navigazione ricorsiva dell'albero che, dato un nodo AST, sono in grado di trasformarlo nell'output desiderato. L'albero quindi non contiene logica ma funge da modello di dati per il Walker. Nel nostro caso, data la semplicità delle operazioni di interpretazione da eseguire, ho deciso di accorpare in ogni classe anche la logica di esecuzione.

Come accennato prima la generazione di un AST è molto semplice. Prendiamo ad esempio il metodo parseExpression:

private function parseExpression()
{
  $left = $this->parseTerm();

  while( ( $this->token->type == TokenType::$ADD ) || ( ( $this->token->type == TokenType::$SUB ) ) )
  {
    $operator = $this->token->type;
    $this->token = $this->scanner->nextToken();
    $right = $this->parseTerm();

    if( $operator == TokenType::$ADD )
    {
      $left = new AddExpression( $left, $right );
    }else
    {
      $left = new SubExpression( $left, $right );
    }
  }

  return $left;
}

Questo metodo restituisce un sottoalbero rappresentato da nodi di addizione o sottrazione. Il metodo calcola prima il nodo di sinistra, e poi nel ciclo while costruisce il sotto albero: in base all'operatore viene riassegnato un nodo AST al nodo di sinistra avente come sottonodi il nodo di sinistra precedente ed il nodo di destra, calcolato precedentemente. Il risultato restituito è il nodo di sinistra risultante, che sarà per l'appunto un sottoalbero di espressioni di addizione o sottrazione. Ogni metodo che genera nodi AST binari segue questa struttura.

Per quanto riguarda i nodi unari invece, ho deciso di procedere con un approccio molto semplice: dato che la priorità di un'espressione unaria è più alta delle altre, i nodi unari vengono generati a livello di fattore:

private function parseFactor()
{
  $unary = array();
  
  while( ( $this->token->type == TokenType::$ADD ) || ( ( $this->token->type == TokenType::$SUB ) ) )
  {
    array_push( $unary, $this->token );
    $this->token = $this->scanner->nextToken();
  }
  
  switch( $this->token->type )
  {
    ... 
  }
    
  while( count( $unary ) > 0 )
  {
    if( array_pop( $unary )->type == TokenType::$ADD )
    {
      $tree = new UnaryPlusExpression( $tree );
    }else
    {
      $tree = new UnaryMinusExpression( $tree );
    }
  }
    
  return $tree;
}

Inizialmente salviamo una lista di nodi unari finché il token corrente analizzato è un più o un meno; poi si procede con l'analisi del token successivo (che nel nostro caso può essere un'altra espressione tra parentesi, un identificatore, una chiamata a funzione o un numero). Quando l'analisi del token corrente è terminata senza errori, viene costruito un sottoalbero di nodi unari navigando la lista salvata precedentemente: questo sottoalbero avrà come foglia il nodo AST restituito dall'analisi precedente.

switch( $this->token->type )
{
  ...
    
  case TokenType::$IDENT:
    $ident_name = $this->token->value;
    $ident = $this->symbols->findAndAdd( $ident_name );
    $tree = new IdentExpression( $ident );
    $this->token = $this->scanner->nextToken();
      
    if( $this->token->type == TokenType::$LEFT_PAR )
    {
      $arguments = array();
      $this->token = $this->scanner->nextToken();
        
      if( $this->token->type != TokenType::$RIGHT_PAR )
      {
        do
        {
          array_push( $arguments, $this->parseExpression() );
        } while( $this->token->type == TokenType::$COMMA );
          
        if( $this->token->type != TokenType::$RIGHT_PAR )
        {
          throw new ExpressionError( "Unexpected token ".$this->token.", expecting )" );
        }else
        {
          $this->token = $this->scanner->nextToken();
        }
      }
        
      $tree = new CallExpression( $ident, $arguments );
    }
      
    break;

  ...
      
}

La generazione del nodo che rappresenta una chiamata a funzione è ambigua: difatti, trovato un identificatore, dobbiamo procedere con l'analisi del token successivo per capire come operare; se il token successivo è una parentesi, allora siamo di fronte ad un chiamata a funzione e quindi salviamo l'array di argomenti effettuando il parsing di una serie di espressioni separate da virgola. In caso non sia una parentesi invece ci troviamo semplicemente di fronte ad un identificatore e quindi restituiamo il nodo opportuno.

Esecuzione dell'albero sintattico

L'esecuzione di un albero sintattico avviene in modo ricorsivo e dipende dal tipo di nodo che si sta eseguento:

• nodo unario: viene eseguito l'unico nodo figlio e, in caso il nodo sia una negazione, viene negato il numero resituito;
• binario: viene eseguito prima il nodo di sinistra e poi quello di destra. I due numeri risultanti vengono combinati in base all'operatore associato al nodo;
• costante: viene restituito il valore della costante; in caso il nodo sia un identificatore, viene interrogata la SymbolTable per trovare il valore del nodo;
• chiamata a funzione: vengono valutati gli argomenti da sinistra a destra; successivamente viene recuperata la funzione dalla SynbolTable e viene invocata con gli argomenti collezionati;

L'esecuzione viene fatta partire eseguendo il metodo execute della classe CompiledExpression: questo metodo accetta come parametro un array associativo che viene utilizzato come contesto per assegnare agli identificatori incontrati in fase di parsing dei valori validi. Il contesto viene iterato ed ad ogni identificatore rappresentato dalla chiave viene assegnato il valore corrispondente.

public function execute( $context )
{
  foreach( $context as $key => $value )
  {
    $ident = $this->symbols->find( $key );
    
    if( $ident )
    {
      $ident->value = $value;
    }
  }

  return $this->expression->evaluate();
}

Poi si procede con l'esecuzione.

Conclusione

Siamo giunti alla fine dell'analisi della semplice libreria per l'interpretazione di espressioni matematiche semplici. Con questa breve serie di articoli spero di aver stuzzicato in qualcuno l'interesse sull'argomento. I futuro vedremo come utilizzare la libreria praticamente scrivendo una semplice applicazione che visualizza grafici derivanti dalla valutazione di espressioni passate in input.