Paolo Guccini

Impossibile non é per sempre

ELABORARE ESPRESSIONI MATEMATICHE
FORNITE ATTRAVERSO LE STRINGHE

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.

Il testo e' stato acquisito tramite OCR dalla rivista su cui e' stato pubblicato e velocemente ricontrollato.
Le segnalazioni di errori saranno molto gradite e si possono fare alla pagina Contatti.

Tratto da:
Paolo Guccini
Rivista DEV Computer Programming
Edizioni Infomedia
Aprile 1996