A molti di voi probabilmente verrà da chiedersi quale sia la necessità di scrivere codice PHP che, data un'espressione matematica, sia in grado di valutarne il risultato in un determinato contesto. Abbiamo già la funzione eval che può fare al caso nostro per esempio, ed è molto probabilmente più potente di gran parte del codice che potremmo scrivere per raggiungere l'obiettivo posto.
Ma, per quanto utile possa essere la funzione sopra citata, quello di cui mi appresto a scrivere in questa breve serie di articoli riguarda un po' di teoria che sta dietro alla scrittura di strumenti capaci di analizzare e valutare espressioni. L'obiettivo è quello di ottenere una libreria su cui si abbia un controllo assoluto che il codice eseguito non sia dannoso per il sistema. Purtroppo eval, a meno che non si provveda alla pulizia dell'input con minuziosità, rischia di essere abusata dai malintenzionati nel caso in cui ci sia una piccola falla e si possa immettere del codice potenzialmente dannoso.
In questo articolo vedremo come gettare le basi per gli strumenti che servono per trasformare un'espressione in una struttura dati facilmente analizzabile e come valutare il risultato di un'espressione partendo da questa struttura dati e da un contesto fornito (come ad esempio variabili o funzioni native).
Breve introduzione sull'esecuzione di espressioni
Iniziamo con un po' di teoria prima di passare alla pratica. Valutare espressioni è un'operazione tendenzialmente molto semplice, che però - se affrontata come ci apprestiamo a fare in questo articolo - tocca diversi interessanti punti che vengono poi ripresi quando si parla di scrittura di compilatori, linguaggi di programmazione, interpreti e correlati. La valutazione di un'espressione avviene attraverso tre passaggi principali: l'analisi lessicale, il parsing ed infine l'esecuzione.
Analisi lessicale
L'analisi lessicale è un processo che permette di trasformare una stringa in input potenzialmente generica in una serie di simboli con un significato specifico. L'analisi lessicale avviene tramite uno scanner (o Lexer o Tokenizer) che si occupa di riconoscere all'intero della stringa gruppi di caratteri che - indipendentemente dalla loro posizione - possono avere un significato nell'espressione.
Prendiamo per esempio la libreria che andremo a scrivere: accetta espressioni composte da numeri interi o float, operazioni aritmetiche base, chiamate a funzioni, variabili e raggruppamento tra parentesi. Lo scanner nel nostro caso deve trasformare l'espressione in input in una lista di gruppi di carattere che saranno identificati espressamente come numero, operatore, parentesi o identificatore. Su questi gruppi di caratteri, chiamati Token, si andrà poi a basare la successiva fase di parsing.
Per chiarire meglio, nel caso dessimo al nostro Scanner questa espressione in input:
+ - sin ( a + 10 ( * ) sqrt( 16.4
otterremo una lista di Token rappresentabile graficamente in questo modo (il primo valore nella parentesi rappresenta il tipo di token):
(operator, + ) (operator, - ) (identifier, sin ) (left-parenthesis) (identifier, + ) (operator, + ) (number, 10 ) (operator, + ) (left-parenthesis) (operator, * ) (right-parenthesis) (identifier, sqrt ) (number, 16.4 )
Lo scanner scarta gli spazi, che non hanno significato in un'espressione, e restituisce una lista di Token che riesce a riconoscere. Notate come lo scanner ignori completamente se la stringa in input ha una struttura valida o meno. Questo è compito della fase successiva.
Parsing
La fase di "parsing" è quella in cui una serie indefinita di Token viene analizzata per capire se l'espressione che ci si appresta ad eseguire ha una struttura valida. Effettuare il Parsing è un'operazione che varia parecchio di difficoltà in base alla complessità dell'input accettato. Nel caso di espressioni aritmetiche basilari effettuare il Parsing è semplice, mentre nel caso di linguaggi di programmazione per esempio l'operazione è nettamente più complessa. La serie di regole che definiscono se l'input è valido o meno è chiamata grammatica. Per onor di cronaca va detto che esistono diverse tipologie di grammatiche per definire un linguaggio, e che non tutte queste grammatiche possono essere semplicemente trasformate in una serie di righe di codice per validare l'input.
Nei casi più semplici - come il nostro - il parsing viene effettuato scrivendo manualmente il codice con una serie di funzioni ricorsive che eseguono determinato codice quando sono sicuri di aver trovato una serie di caratteri validi riconducibili ad una regola accettabile. Nei casi più complessi invece si utilizzano dei Parser Generator che, data una grammatica in input definita con un determinato linguaggio, sono in grado di auto-generare il codice necessario per analizzare l'output dello Scanner.
La fase di Parsing valida l'input e se tutto va a buon fine lo trasforma in una struttura dati facilmente analizzabile da un linguaggio. Solitamente questa struttura è chiamata AST (Abstract Syntax Tree) e non è altro che un albero in cui ogni foglia è rappresentata da un Token, ed ogni ramo da una regola accettata dalla grammatica. Alcune volte - come avremmo potuto fare noi ad esempio - non viene effettuata la traduzione ad AST e si procede direttamente con il valutare l'input man mano che il Parser accetta parti di input.
Solitamente i Token che sono definiti come identificatori vengono salvati all'interno di una tabella (chiamata SymbolTable) che potrà successivamente essere utilizzata per associare un valore a questi identificatori nel caso in cui fosse necessario.
Sempre per chiarire meglio, prendiamo un'espressione (valida per la nostra grammatica) in input:
sin( a * ( -5 + 15.6) )
E vediamo una rappresentazione grafica dell'AST che verrebbe restituito dal Parser (il primo valore nelle parentesi è il nome del nodo, i seguenti le proprietà necessarie per specificare il nodo):
(call sin
(multiplication
(identifier a)
(sum
(neg (number 5))
(number 15.6))))
Notate come ogni informazioni inutile relativa all'espression è stata scartata, e si abbia una struttura ad albero facilmente interrogabile navigandone i nodi.
Esistono differenti tecniche di Parsing, alcune delle quali più semplici da scrivere ma più lente da eseguire, ed altre molto più complesse da scrivere ma più rapide da eseguire. Nella nostra libreria utilizzeremo una tecnica chiamata Recursive Descent Parsing: questa tecnica (che ovviamente fa parte del primo gruppo) prevede l'analisi dei Token in ingresso utilizzando una serie di chiamate a funzione ricorsive; ogni funzione ha come compito quello di accettare una regola, e restituisce un AST valido per quella regola oppure un errore. Dato che le regole possono a loro volta essere rappresentate da altre regole annidate (ad esempio una moltiplicazione può essere composta da due termini che a loro volta sono espressioni) otteniamo la ricorsione.
I Recursive Descent Parser fanno parte dei parser di tipo Top-Down, mentre spesso i parser più veloci sono di tipo Bottom-Up. Lascio a voi il compito di dare un'occhiata su Wikipedia per comprendere meglio le differenze.
Ottenuta questa struttura possiamo fornirla in input a diverse procedure per gli usi più disparati; nel nostro caso il calcolo dell'espressione.
Esecuzione
La fase di esecuzione è probabilmente la più semplice: abbiamo un AST che sappiamo rappresentare un'espressione sicuramente valida (dato che è stata validata nella fase di Parsing) e quello che ci resta fare è fornire un contesto di esecuzione e navigare ricorsivamente i nodi per estrarne il valore. In base al tipo di nodo il valore restituito sarà diverso. Fornire un contesto di esecuzione significa definire il valore delle variabili e delle funzioni in modo che tutti gli identificatori registrati nella SymbolTable abbiano un valore valido.
Prendiamo per esempio l'AST generato nell'esempio precedente e cerchiamo di eseguirlo nel contesto in cui la variabile a vale 10 e l'identificatore sin sia mappato alla omonima funzione per il calcolo del seno di un angolo. L'esecuzione ricorsiva valuta prima i figli dei nodi, e quando ha finito la valutazione di questi torna ai padri fino a raggiungere la cima. I nodi in grassetto sono quelli valutati nello step successivo
(call sin (multiplication (identifier a) (sum (neg (number 5)) (number 15.6)))) (call sin (multiplication (identifier a) (sum (neg (number 5)) 15.6))) (call sin (multiplication (identifier a) (sum (neg 5) 15.6))) (call sin (multiplication (identifier a) (sum -5 15.6))) (call sin (multiplication (identifier a) 10.6)) (call sin (multiplication 5 10.6)) (call sin 53) = 0.39592515018183422
Il risultato è facilmente raggiunto e probabilmente matematicamente corretto nel contesto fornito. Dato un AST avremmo anche potuto per esempio semplificare tutte le espressioni costanti e riscrivere la stessa espressione in modo più compatto.
Nel prossimo articolo vedremo come implementare la libreria ed analizzeremo il codice per comprendere come passare dalla teoria alla pratica.
