I sorgenti sono disponibili per il download.
in questo articolo vengono spiegate varie soluzioni che si adottano durante la realizzazione
di un parser matematico e gli errori in cui è possibile incappare; inoltre viene fornito un esempio pratico
che è implementato all’interno del parser di stringhe visto in precedenza
Il parser matematico si occupa di estrarre un’espressione matematica
da un input per calcolame il valore.
Esistono numerose implementazioni di parser e quella che troverete in allegato al dischetto è una delle tante.
La cosa più importante di questo parser ai fini della realizzazione del parser
per la gestione delle stringhe consiste nel fatto che esso elabora l’input
finché trova dei dati che può considerare validi e restituisce un puntatore al carattere successivo
a quello utilizzato per ultimo, quindi senza provocare un errore.
Questa caratteristica consente di utilizzano per elaborare i parametri delle funzioni:
ad esempio la funzione del Basic Mid$(str, pos, len) nella quale il parser matematico deve essere invocato due volte:
la prima per estrarre il parametro pos e poi perlen.
Per l’elaborazione di str e la valutazione di Mid$() si ricorrerà al parser pubblicato in precedenza.
Un’altra caratteristica di questo parser è che acquisisce i dati direttamente da una stringa
senza richiedere la sua preventiva suddivisione in token;
questo consente un discreto risparmio di RAM
e una immediatezza elaborativa non necessitando di una fase di scanning, ma,
per contro, causa un rallentamento di elaborazione soprattutto nei loop
in quanto il parser deve valutare ogni volta cosa rappresenti ogni singolo carattere
che deve via via elaborare.
Vediamo adesso come un parser matematico gestisce i vari elementi.
Precedenze
Le espressioni matematiche devono essere valutate procedendo da sinistra verso destra
rispettando le eventuali precedenze dei vari operatori
e delle parentesi che appaiono nell’espressione.
Appare abbastanza intuitivo che si possa fare largo impiego della ricorsione
per la gestione delle priontà fra operatori;
così il primo approccio alla costruzione del parser
prevede che esso venga rilanciato ricorsivamente
ogni qualvolta che l’operatore matematico successivo
a quello in elaborazione abbia la priorità.
Questo significa che l’espressione 1+2*3+4
causa le seguenti operazioni:
-
acquisisce il primo operando, l’operatore ed il secondo operando (1+2);
-
acquisisce l’operatore a destra del secondo operando (l’asterisco);
-
valuta che l’operatore di moltiplicazione abbia priorità
sull’operatore di somma per cui viene rilanciato il parser in ricorsione.
Il valore che il parser restituisce va a sostituire
il secondo parametro al livello superiore che era il valore 2 e diventa 10.
-
esegue il calcolo fra il primo operando ed il secondo.
Al termine il parser restituirà correttamente il valore 11, ma si tratta di un caso.
Infatti questa gestione non tiene in considerazione un punto fondamentale esposto all’inizio del capitolo:
l’elaborazione deve avvenire rispettando le precedenze fra gli operatori,
ma fondamentalmente da sinistra verso destra, mentre l’elaborazione è stata gestita
come se l’espressione fosse stata 1+(2*3+4).
Dov’è il problema?
Se l’espressione fosse stata 1-2*3+4 il parser avrebbe eseguito le seguenti valutazioni:
-
dopo aver preso i primi quat tro token i - 2 * si deve dar luo go alla ricorsione;
-
la ricorsione ha luogo calcolando tutto ciò che trova
in quanto non necessita di ulteriore ricorsione (non sono presenti parentesi oppure operatori con maggiore priorità
rispetto alla moltiplicazione, come l’elevazione a potenza).
Così facendo elabora 2*3+4 e restituisce 10 al chiamante che lo utilizzerà come secondo parametro.
il parser che ha invocato la ricorsione dispone del valore 1 e l’operatore di sottrazione;
il secondo parametro che era 2 viene correttamente sostituito
con quanto la ricorsione ha calcolato. In tal modo il parser deve eseguire 1-10.
L’errore è causato dalla mancata interruzione della ricorsione dopo 2*3.
Per ovviare a questo errore è sufficiente passare al parser,
quando entra in ricorsione, il livello di priorità fra operatori che è gestito dal chiamante.
In altre parole, la funzione che invoca la ricorsione (sia essa stessa una ricorsione o sia il livello primario)
deve porre un limite all’elaborazione da parte del nuovo livello:
il limite è determinato dalla parità delle precedenze fra l’operatore che il livello chiamante
doveva gestire e quelli che via via la ricorsione incontra.
Così facendo, quando il parser incontra +4 verifica che l’operatore di somma non ha priorità
rispetto a quello che non è stato possibile gestire dal chiamante (la sottrazione)
e termina la sua elaborazione informando contestualmente il chiamante del punto in cui si è interrotta l’ ela borazione
affinché possa proseguire oltre.
L’algoritmo così concepito lavora correttamente.
Ma analizziamo adesso come le parentesi influiscano sul comportamento del parser.
Le parentesi
Le parentesi servono ad alterare le priorità di calcolo
all’interno di un’espressione.
L’elaborazione di quanto racchiuso fra parentesi restituisce un valore numerico.
Queste banali considerazioni permettono di implementare la gestione delle parentesi semplicemente indicando al parser che,
quando incontra una parentesi aperta, deve lanciare una ricorsione
la quale deve terminare quando ne trova una chiusa.
Evidentemente, le parentesi possono essere nidificate, ma questo non solleva nessuna eccezione o problema
in quanto il parser esegue una ulteriore ricorsione per ogni parentesi aperta che trova.
Più in particolare, visto che le parentesi sostituiscono un numero
si ottiene dopo l’elaborazione di quanto in esse contenuto,
il metodo migliore per gestirle consiste nel delegare alla funzione che acquisisce il numero
il compito di lanciare la ricorsione del parser
allorquando trova la parentesi aperta.
In tal modo il nucleo del parser non le vede e non deve gestirle ottenendo una buona pulizia e leggibilità del sorgente.
Piu o meno
I caratteri più e meno rivestono due significati:
possono essere gli operatori matematici di somma e sottrazione oppure esprimere il segno del numero che segue.
Moltissimi parser non gestiscono i caratteri più e meno come segno
ma solo come operatori matematici,
eccezion fatta per il primo numero che si incontra ai vari livelli di ricorsione:
dovrebbe essere sempre valutata come sintatticamente corretta la se guente espressione:
-1+(-2*(+3))
in quanto ai tre livelli di esecuzione (o ricorsione)
il carattere piùo meno è presente come primo token.
Ma altri parser ammettono anche la presenza del segno anche all’ interno delle espressioni
accettando quindi come valida la seguente:
+1 / —2 * 4 — +5
sennonché talvolta effettuano alcune ottimizzazioni quali l’eliminare i segni superflui, così il precedente esempio diventa:
1 / —2 * 4 - 5
Se il secondo parser consente di rappresentare meglio le espressioni matematiche,
è altrettanto vero che questa libertà rischia di sfociare nell’aumento delle possibilità di errori nella digitazione:
ad esempio, se erroneamente viene inserita una coppia in meno,
il parser la interpreterà come una sottrazione di un numero negativo che matematicamente ne comporta la somma.
Entrambi i tipi presentano vantaggi e svantaggi: è libertà del programmatore adottare a piacimento l’una o l’altra tecnica di parsing.
Il parser che vedremo adotta la prima tecnica.
Un particolare che talvolta viene dimenticato consiste nella possibilità di avere un segno prima di una parentesi aperta:
-(+(-1))
è un’espressione valida a tutti gli effetti.
Non necessita di alcuna considerazione particolare per essere gestita in quanto,
come abbiamo detto, ogni parser accetta il segno come primo carattere a qualunque livello di ricorsione
e la parentesi attiva una ricorsione che restituisce ovviamente un numero.
Il loop del parser
Vediamo ora come può essere strutturato il loop che il parser esegue.
Iniziamo con l’analizzare una funzione che è quasi sempre fornita col parser
che ha funzioni di shell; serve per dare al programmatore uno strumento il più semplice e mnemonico possibile.
La shell infatti richiede come parametro generalmente solo la stringa contenente l’espressione matematica da calcolare.
Questo consente di accedere ed utilizzare il parser in maniera assai semplice e snella.
La shell si prende l’onere di creare le variabili locali e di richiamare il parser con i parametri necessari;
in particolare definisce il limite della ricorsione, il quale deve essere impostato come fine dei dati contenuti nella stringa.
Ciò si ottiene semplicemente passandogli un valore che sia inferiore
a quelli che rappresentano gli operatori matematici di somma e sottrazione;
di solito è utilizzato lo zero.
Questo limite viene incluso fra i parametri solo perché richiesto;
infatti non avrebbe senso includerlo alla prima chiamata:
il suo scopo è di evitare il problema spiegato nel capitolo Precedenze man mano che si susseguono le ricorsioni.
Una volta invocato il parser esso compie i seguenti passi:
-
acquisisce l’eventuale segno;
-
acquisisce il primo valore che chiameremo sx per indicare che è l’operando che si trova a sinistra dell’operatore matematico.
La funzione che se ne occupa verifica se al posto di un numero c’è una parentesi:
in tal caso lancia una ricorsione che restituisce un valore utilizzato come sx.
-
acquisisce l’operatore matematico che chiameremo sxOp
per indicare che si trova dopo l’operando di sinistra;
se i dati sono terminati,
sxOp conterrà il valore che ne segnala la fine (zero);
-
verifica se sxOp ha priorità rispetto a limite:
in caso negativo esce dal loop restituendo il valore contenuto in sx.
-
acquisisce il secondo valore che chiameremo dx in quanto si trova a destra dell’operatore.
La funzione di acquisizione è la stessa che viene utilizzata per sx
e conseguentemente valgono le stesse considerazioni;
-
acquisisce l’operatore matematico che si trova dopo il secondo numero.
Ad esso viene dato il nome di dxOp. Le considerazioni relative all’estrazione di sxOp valgono anche per questa variabile.
A questo punto non resta altro che valutare se dxOp è un operatore con precedenza
rispetto sxOp; in tal caso si deve lanciare la ricorsione e si torna all’inizio
dell’elenco sopra riportato, altrimenti si procede:
-
calcolando il risultato dell’operazione indicata da sxOp fra sx e dx memorizzandone il risultato il sx;
copiando il valore di dxOp in sxOp;
il ciclo prosegue tornando al punto in cui esegue la valutazione di sxOp
dove viene confrontato con il limite;
Come avvengono i calcoli
Il calcolo rappresenta un aspetto molto semplice:
basta creare una funzione che riceve come parametri sx, sxOp e dx e,
mediante uno switch basato sul valore di sxOp,
esegue la Case opportuna e restituisce il valore di quanto calcolato.
Il parser
Una volta che si è preso confidenza con i vari concetti qui esposti,
diviene facile implementare un parser matematico.
L’importante è avere ben chiari i vari concetti implicati nella sua realizzazione.
Dopo averlo realizzato, poco importa se i dati provengono da una stringa,
da un array o da qualche altra fonte in quanto è sufficiente intervenire sulle funzioni
che acquisiscono i numeri e gli operatori per con sentire varie trasformazioni.
La prima di esse dovrebbe consistere nel creare un preprocessore
che prende generalmente il nome di scanner, il quale si occupa di trasformare la fonte dei dati
in una rappresentazione interna la quale può venire elaborata agevolmente dal parser
le cui funzioni diventano così molto più veloci
consentendo di ottenere significativi miglioramenti.
Veniamo adesso al parser matematico presente all’interno del parser
delle funzioni di tipo stringa pubblicato precedentemente.
La shell ha nome funn_exec() e, a causa del suo ambito d’utilizzo, necessita di svariati parametri.
Essi sono:
-
puntatore alla stringa che contiene l’espressione matematica da calcolare:
-
puntatore ad un integer in cui verrà immesso l’eventuale codice di errore verificatosi durante l’elaborazione.
E' possibile utilizzare l’indirizzo NULL senza causare anomalie:
semplicemente non verrà restituito alcun codice di errore;
-
la lunghezza massima che le stringhe di appoggio possono assumere
nel caso debba essere invocato il parser di stringhe
(è da osservare che il parser matematico è già a sua volta stato lanciato da quest’ultimo);
esso viene utilizzato quanto sono presenti delle funzioni che operano sulle stringhe come la funzione Len();
-
puntatore a puntatore di char in cui verrà memorizzato l’indirizzo del primo carattere inutilizzato della stringa.
Esso è fondamentale in quanto l’espressione matematica è contenuta all’interno di una funzione di tipo stringa,
perciò, dopo che questo parser ha compiuto il suo compito, deve informare il chiamante da dove può proseguire.
Molto più sfruttabile anche al di fuori del
contesto in cui essa è implementata, è la
funzione funn_elabora(), la quale richiede
i seguenti parametri:
- puntatore a puntatore alla stringa che contiene l’espressione matematica
- valore limite della ricorsione (come abbiamo visto,
il limite per la prima chiamata deve avere priorità inferiore agli operatori di somma e sottrazione
affinché il parser elabori tutta la stringa);
-
puntatore alla variabile sx;
-
puntatore alla variabile sxOp;
-
puntatore all’integer in cui viene memorizzato l’eventuale codice di errore; esso non deve essere NULL.
La funzione funprende() si occupa di gestire l’acquisizione dei valori
prelevandoli direttamente dalla stringa oppure gestendo la ricorsione
nel caso incontri la parentesi aperta; se il carattere che incontra è invece una lettera,
viene lanciato il gestore delle funzioni numeriche che ha nome funn_funnum();
in ogni caso restituisce un valore numerico salvo si siano verificati degli errori.
Conclusioni
Nel caso abbiate problemi connessi all’utilizzo delle funzioni esposte in questo articolo
o nei precedenti potete contattarmi preferibilmente al mio indirizzo Internet oppure tramite la BBS Shineline.
Inoltre e come sempre, qualunque suggerimento o critica costruttiva sono sempre graditi.