Dopo aver introdotto brevemente la teoria che sta dietro all'analisi e all'esecuzione di espressioni in modo dinamico, possiamo passare alla parte pratica. Ho implementato un semplicissimo valutatore di espressioni, in grado di gestire le seguenti operazioni:
- addizione
- sottrazione
- moltiplicazione
- divisione
- raggruppamento di espressioni tramite parentesi
- chiamata di funzioni
- supporto per le variabili
- numeri negativi
Il sistema implementato è volutamente semplice in modo da suddividere nel modo più chiaro possibile i concetti discussi nell'articolo precedente (Scanner, Parser, AST). I sorgenti possono essere scaricati da qui.
Nel file zip allegato a questo articolo è contenuto in file di esempio. Questo esegue una semplice espressione stampandone il risultato e la notazione postfissa. Il codice dell'esempio è il seguente:
<?php
require_once "it/html/expr/Scanner.php";
require_once "it/html/expr/Parser.php";
require_once "it/html/expr/error/ ExpressionError.php";
$expression = "sin( x / ( 4 / 2 * 2 - 2 + 2 * x / x ) ) * 100";
$scanner = new Scanner( $expression );
$parser = new Parser( $scanner );
$compiled = $parser->parse();
$context = array(
"x" => 100,
"sin" => "sin",
"cos" => "cos"
);
echo 'Postfix:', $compiled;
echo 'Result:', $compiled->execute( $context );
?>
Come possiamo notare, tralasciando le inclusioni, il sistema risulta di semplice utilizzo; il parser accetta come parametro uno scanner, che si occupa di suddividere l'espressione in token riconoscibili dal sistema, ed il metodo parse restituisce un oggetto (CompiledExpression) che espone un metodo execute che valuta l'espressione. Il metodo execute accetta come parametro un array che definisce il contesto di esecuzione. Come potete notare difatti l'espressione che vogliamo valutare contiene la variabile x ed una chiamata alla funzione sin. I valori di questi due identificatori non sono conosciuti dal sistema, e quindi devono essere specificati manualmente. Cambiando il valore di x per esempio otterremo risultati differenti. sin e cos sono invece funzioni, mappate alle corrispettive funzioni PHP. Internamente il sistema utilizza call_user_func_array per chiamare la funzione corrispondente.
La struttura del file zip include tutto il codice necessario all'interno della directory it/html/expr e sottocartelle:
- Ident: classe utilizzata per registrare un identificatore e mappare la variabile ad un valore specificato dal contesto del metodo execute discusso sopra;
- Parser: Il parser di espressioni che legge i Token generati dallo scanner alla ricerca di sequenze valide trasformabili in nodi x l'albero sintattico (AST);
- Scanner: lo scanner che si occupa di assegnare ad ogni carattere o sequenza di caratteri un Token, che rappresenta l'unità minima di input comprensibile dal Parser;
- SymbolTable: una tabella utilizzata per salvare i simboli incontrati durante il parsing, per far si che poi siano agilmente recuperabili durante la valutazione dell'espressione;
- Token: il Token è l'unità minima di input compresa dal parser; i Token possono essere composti da uno o più caratteri, e sono generati dallo Scanner;
- TokenType: classe di utilità usata per definire le costanti che differenziano i vari tipi di Token;
- CompiledExpression: classe utilizzata per rappresentare un'espressione compilata in AST. L'albero dei nodi AST è salvato all'interno, ed è valutato quando si chiama il metodo execute;
- error/ExpressionError: eccezione lanciata quando il parser incontra un errore;
- ast/*: ogni classe contenuta in questa directory rappresenta un nodo dell'AST. Ogni nodo implementa l'interfaccia
IExpression, in modo che ogni nodo abbia la sua rappresentazione sotto forma di stringa e sia in grado di eseguirsi;
Analizziamo ora le classi principali, cercando di chiarire i concetti implementativi nel modo migliore possibile. Per brevità non includerò tutto il codice ma solo le parti interessanti, mettendo tre puntini nel caso di codice omesso.
Scanner, Token e TokenType
La classe Scanner, come già ripetuto più volte, serve a suddividere l'input in una serie di elementi riconosciuti dal parser. Il parser e lo scanner stabiliscono un contratto rappresentato dai token comprensibili dal primo e generabili dal secondo, in modo che tutte le esigenze vengano rispettate. La lista dei token comprensibili è definita nella classe TokenType:
class TokenType
{
public static $ADD = 1;
public static $SUB = 2;
public static $MUL = 3;
public static $DIV = 4;
public static $NUM = 5;
public static $IDENT = 6;
public static $LEFT_PAR = 7;
public static $RIGHT_PAR = 8;
public static $COMMA = 9;
public static $NULL = 0;
public static $EOF = -1;
public static function typeToString( $type )
{
switch( type )
{
case 0: return "NULL";
case 1: return "ADD";
case 2: return "SUB";
case 3: return "MUL";
case 4: return "DIV";
case 5: return "NUM";
case 6: return "IDENT";
case 7: return "LEFT_PAR";
case 8: return "RIGHT_PAR";
case 9: return "COMMA";
default: return "EOF";
}
return null;
}
}
Ogni tipo di token ha associato un intero: abbiamo i vari operatori supportati, le parentesi, la virgola (utilizzata per parametri multipli alle funzioni), numero, identificatore, e due token speciali: EOF e NULL. EOF indica la fine dell'input, e NULL viene restituito dallo scanner nel caso in cui il carattere corrente analizzato non fosse valido.
La classe token associa il tipo di token ed il valore del token insieme: il tipo di token è l'intero, il valore è la stringa corrispondente estratta dall'input.
class Token
{
public $type;
public $value;
public function Token( $type, $value = null )
{
$this->type = $type;
$this->value = $value;
}
public function __toString()
{
if( is_null( $this->value ) )
{
return TokenType::typeToString( $this->type );
}else
{
return "<".TokenType::typeToString( $this->type ).", ".$this->value.">";
}
}
}
Nel caso di token a carattere singolo, il valore è il solo carattere letto (come + nel caso di token di tipo ADD) mentre per NUM o IDENT, il valore è rispettivamente il numero letto o l'identificatore accettato. Nella prossima pagina vedremo la classe Scanner.
Il cuore della classe Scanner sta nel metodo nextToken, che legge dalla posizione corrente dell'input finché non incontra un token valido, e lo restituisce.
public function nextToken()
{
....
$this->skipWhites();
if( $this->isEOF() )
{
return new Token( TokenType::$EOF );
}
$c = $this->source{ $this->pos++ };
switch( $c )
{
case '+': return new Token( TokenType::$ADD, '+' );
case '-': return new Token( TokenType::$SUB, '-' );
...
default:
$buf = "";
$code = ord( $c );
if( $this->isNumber( $code ) )
{
while( $this->isNumber( $code ) )
{
$buf .= $c;
if( $this->isEOF() )
{
++$this->pos;
break;
}
$c = $this->source{ $this->pos++ };
$code = ord( $c );
}
if( $c == '.' )
{
$buf .= $c;
$c = $this->source{ $this->pos++ };
$code = ord( $c );
while( $this->isNumber( $code ) )
{
...
}
$num = floatval( $buf );
}else
{
$num = floatval( $buf.".0" );
}
--$ this->pos;
return new Token( TokenType::$NUM, $num );
}
if( $this->isAlpha( $code ) || ( $c == '_' ) )
{
while( $this->isAlpha( $code ) || ( $c == '_' ) || $this->isNumber( $code ) )
{
$buf .= $c;
if( $this->isEOF() )
{
++$this->pos;
break;
}
$c = $this->source{ $this->pos++ };
$code = ord( $c );
}
--$ this->pos;
return new Token( TokenType::$IDENT, $buf );
}
break;
}
return new Token( TokenType::$NULL, $c );
}
Il flusso è molto semplice; per prima cosa ignoriamo tutti gli spazi bianchi: lo spazio non ha alcun significato in fase di valutazione, per cui è scartato; successivamente viene letto il carattere corrente e si procede con la ricerca del tipo di token corretto. Nel caso in cui corrisponda ad uno dei token a carattere singolo accettati, restituiamo il token corrispondente. Altrimenti dobbiamo decidere se il token in input è un numero o un identificatore. Per regola generale abbiamo deciso che un identificatore non può iniziare con un numero. Quindi se il primo carattere è un numero, significa che il token successivo sarà un numero, in caso invece sia una lettera o il simbolo underscore, significa che il token successivo è un identificatore. In caso nessuna delle precedenti analisi venga accettata, viene restituito il token NULL (ed il parser terminerà la sua esecuzione).
Come possiamo notare, la lettura di un numero o di un identificatore dalla stringa di input è ridotta semplicemente ad un loop che salva in un buffer i caratteri accettati finché non incontra un carattere non valido, e successivamente il token corretto viene restituito.
Lo scanner non fa alcun controllo sul fatto che la sequenza dei token abbia una valenza sintattica. Sia un'espressione valida che una errata verranno trasformati correttamente in uno stream di token e dati in pasto al parser.
Nella prossima parte
Nella prossima parte di questo articolo in due puntate finiremo di analizzare il codice entrando in dettaglio delle classi di parsing e dell'albero sintattico. Successivamente vedremo un esempio pratico di utilizzo, in modo da rendere chiara l'utilità che potrebbe avere questo tipo di codice nel mondo reale.
Come discusso nella prima parte di questo articolo e nel precedente dedicato alla teoria, il parser è il componente di un interprete o compilatore in grado di prendere uno stream di token e, in base a determinate regole di grammatica, definire se l'input passato ha una struttura corretta ed in quel caso eseguire operazioni specifiche sull'input; solitamente si tratta di operazioni di trasformazione in un formato più facilmente gestibile dal programma, come un albero sintattico.
Nel nostro caso specifico il parser accetta una grammatica molto semplice, composta da un'espressione a riga singola che accetta le operazioni di moltiplicazione, addizione, sottrazione, divisione, negazione, le variabili e le chiamate a funzione. L'output generato è un semplicissimo albero sintattico che tiene conto della precedenza degli operatori e dell'eventuale raggruppamento con parentesi; ogni nodo dell'albero sintattico sarà in grado di generare una stringa rappresentante il nodo in notazione postfissa oppure di valutare il risultato numerico delle operazioni rappresentate dal quel nodo (e da eventuali nodi figlio).
Il parser implementato è di tipo top down ricorsivo discendente: fondamentalmente sfrutta la ricorsione per analizzare l'input, implementando una serie di funzioni ognuna delle quali accetta una porzione di input sempre più piccola. Queste funzioni vengono richiamate ricorsivamente quando necessario in modo da far avanzare il parser. Essendo la nostra grammatica una grammatica valida (e molto semplice), il parser è a sua volta compatto e facilmente mantenibile.
Solitamente, in caso di grammatiche più complesse, si opta per l'utilizzo dei cosiddetti Parser Generators, programmi in grado di accettare le definizione di una grammatica in un linguaggio descrittivo molto semplice, e di generare in output un parser implementato in un linguaggio specifico. Per onor di cronaca, nonostante non siano programmi in grado di generare output in PHP, dobbiamo ricordare Yacc/Bison ed Antlr. Ogni parser generator solitamente implementa i suoi algoritmi in modo da generare parser ottimizzati o utilizzanti una tecnica piuttosto che un altra (se ricordate parlavamo di top down parser o bottom up parser, ma ci sono parecchie varianti come parecchie sono le tipologie di grammatiche esistenti - ma questa è un'altra storia ...).
Tornando al nostro parser, la ricorsione assicura che l'output accettato possa essere a sua volta ricorsivo: ad esempio nel nostro caso un'espressione può essere rappresentata da un numero, da un'addizione tra numeri o da un addizione tra espressioni; nell'ultimo caso la ricorsione è palese poiché l'espressione stessa può essere a sua volta un numero, un'addizione di numeri o un'addizione di espressioni.
Le operazioni accettate nell'espressione sono a loro volta composte da fattori o termini (nel caso di moltiplicazione/divisione o addizione/sottrazione), e l'implementazione del parser rispecchia per l'appunto questa struttura: le funzioni implementate sono per l'appunto le seguenti:
parse: funzione pubblica che effettua il parsing e la trasformazione in AST; accetta un'espressione valida;parseExpression: accetta un'espressione valida di addizione o sottrazione tra due termini;parseTerm: accetta un'espressione valida di moltiplicazione o divisione tra due fattori;parseFactor: accetta una costante numerica, una negazione, un identificatore, una chiamata a funzione o un'espressione valida racchiusa tra parentesi;
L'implementazione quindi risulta abbastanza semplice: ad esempio parseExpression controllerà che l'input in ingresso sia composta da un termine, seguito da un operatore di addizione o sottrazione, seguito a sua volta da un altro termine; per controllare che l'input sia un termine valido, non farà altro che chiamare parseTerm, che si occuperà di fare i suoi check e generare il nodo AST necessario. Dato che la nostra grammatica è molto semplice, parseExpression e parseTerm accettano rispettivamente una sequenza di uno o più operazioni di addizione/sottrazione o moltiplicazione/divisione.
Vediamo ora l'implementazione dei quattro metodi, omettendo con i soliti tre punti il codice non necessario:
public function parse()
{
$this->token = $this->scanner->nextToken();
$expr = $this->parseExpression();
if( $this->token->type == TokenType::$EOF )
{
return new CompiledExpression( $expr, $this->symbols );
}else
{
throw new ExpressionError( "Unexpected token: ".$this->token );
}
}
Il metodo parse è estremamente semplice: salva il token corrente in una variabile di istanza in modo che sia sempre accessibile se necessario e, dato che la nostra grammatica accetta un'espressione valida, chiama parseExpression per validarla. Come vedremo in seguito, parseExpression, parseTerm e parseFactor restituiscono dei nodi AST; in questo caso il nodo AST è utilizzato insieme alla tabella dei simboli per costruire un'istanza di CompiledExpression, che nel nostro caso rappresenta l'espressione compilata.
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;
}
Il metodo parseExpression accetta una sequenza di operazioni di addizione o sottrazione; come vediamo questa frase è tradotta molto semplicemente in codice, accettando prima un termine e poi accettando una sequenza di operatori di addizione e sottrazione seguiti a loro volta da un altro termine. Il valore restituito è un nodo AST.
Il metodo parseTerm è molto simile al precedente, ma accetta dei fattori ed un sequenza di moltiplicazioni o divisioni:
private function parseTerm()
{
$left = $this->parseFactor();
while( ( $this->token->type == TokenType::$MUL ) || ( ( $this->token->type == TokenType::$DIV ) ) )
{
...
$right = $this->parseFactor();
...
}
return $left;
}
Infine abbiamo parseFactor, che differentemente dagli altri può accettare sia input che termina la ricorsione che input che la continua (come nel caso di una chiamata a funzione o un'espressione racchiusa tra parentesi):
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 )
{
case TokenType::$NUM:
$tree = new NumberExpression( $this->token->value );
$this->token = $this->scanner->nextToken();
break;
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;
case TokenType::$LEFT_PAR:
$this->token = $this->scanner->nextToken();
$tree = $this->parseExpression();
...
break;
default:
throw new ExpressionError( "Unexpected token ".$this->token );
break;
}
while( count( $unary ) > 0 )
{
if( array_pop( $unary )->type == TokenType::$ADD )
{
$tree = new UnaryPlusExpression( $tree );
}else
{
$tree = new UnaryMinusExpression( $tree );
}
}
return $tree;
}
Il metodo parseFactor è principalmente composto da due porzioni: una parse è un grosso switch che controlla il token attualmente in analisi ed esegue differenti operazioni in base al suo valore; un'altra parte invece è una fase che si occupa di registrare il numero di negazioni unarie per poi poter generale correttamente i nodi dell'AST corrispondenti. Nel caso in cui il token sia un identificativo, viene effettuata un'operazione di lookhaead: sei il token successivo è una parentesi aperta, allora l'identificatore è il nome di una funzione; altrimenti siamo di fronte ad un semplice riferimento ad una variabile.
La tabella dei simboli
La tabella dei simboli (SymbolTable) merita un'analisi separata: ogni qual volta un identificatore è trovato all'interno dell'espressione, la tabella dei simboli viene interrogata per cercare il simbolo a cui quell'identificatore fa riferimento; in caso non esista viene aggiunto alla tabella dei simboli. Nel nostro caso la tabella dei simboli è di tipo particolare, perché l'associazione di un valore ai simboli viene effettuata successivamente durante la valutazione attraverso un oggetto di contesto che specificherà, per ogni simbolo, il valore opportuno.
