Paolo Guccini

Impossibile non é per sempre

Interpreti di linguaggio: costruire l'istruzione "if"

I sorgenti sono disponibili per il download.

In quest’articolo viene sinteticamente spiegato quanto attiene al concetto di parser, focalizzando maggiormente l’attenzione sulla implementazione pratica della costruzione della funzione di gestione delle if di tipo c-style



Negli articoli apparsi nei mesiprece denti in questa rubrica sono stati trattati argomenti relativi alla gestione dell’input da parte dell’utente finalizzata all’ acquisizione di funzioni matematiche o di tipo stringa.
In quest’ultimo tipo di parser era implementata la funzione IIF(), la quale restituisce il secondo o il terzo parametro in relazione al valore vero/falso della condizione che riceve come primo parametro.
In questo articolo verranno affrontate al cune tecniche per costruire una funzione in C++ (facilmente esportabile verso il mondo C) che possa valutare un’espressione che riceve come parametro in formato stringa.
Essa trova impiego in moltissimi casi di interazione fra il programma e l’utente, soprattutto quando l’utente è chiamato a stabilire un criterio di selezione come, ad esempio, nel caso dell’ estrazione di record da un file oppure, più genericamente, per definire una condizione a run time.
Inoltre, le funzioni presentate possono essere utilizzate come moduli nello sviluppo degli interpreti di linguaggio: una delle parti più pesanti nella loro realizzazione sono proprio i parser e la gestione delle condizioni.


Modi e tecniche implementative

In relazione alla tecnica di implementazione adottata, la valutazione di un’espressione può essere preceduta da un’operazione di scanning che consente di estrarre dalla stringa le varie parti che compongono la condizione come i numeri, le parentesi, gli operatori, eccetera.
Questa operazione consente di creare un array contenente le varie informazioni dette token.
Questo consente una analisi sulla sintassi dell’espressione, ma soprattutto non dover eseguire ogni volta il riconoscimento del token ed avviare le eventuali azioni relative come la conversione da stringa a numero: la conseguenza è una velocità di esecuzione sensibilmente inferiore a discapito di un maggiore consumo di RAM necessaria ad allocare l’array.
Altra tecnica consiste nel generare un albero delle varie operazioni da eseguire costruendolo osservando la rappresentazione polacca inversa. Questo sistema si rivela particolarmente utile e funzionale nelle condizioni: a differenza delle espressioni matematiche che devono necessariamente essere interamente elaborate per ottenere il risultato, il risultato di una condizione anche molto complessa può essere ottenuto valutandone solo una parte.
Ad esempio, la seguente condizione:

1=2 and (((4-3)*2)/5)+l = 0

risulta falsa già dopo aver valutato che 1=2 e quindi non è più necessario proseguire calcolando la restante parte in quando l’operatore AND restituisce vero solo se i valori precedenti e seguenti sono veri.
Discorso analogo vale per l’operatore OR con la prima condizione vera.
L’impiego della tecnica basata su array o albero differenzia il comportamento dell’analizzatore di condizioni: nel primo caso sono generalmente ammesse espressioni C/C++ style quali:

1<2<3 AND 1+2 AND 7

mentre il secondo si avvicina di più alla maggior correttezza formale richiesta da linguaggi quali il Basic. Ma approfondiremo questo argo mento più avanti parlando degli operatori. Per ora è sufficiente conosce re che la funzione conditionMgr() che rappresenta l’applicazione pratica di quanto descriveremo, non opera la funzione di scanning e quindi prende i dati direttamente dalla stringa che riceve come parametro e la elabora completamente.


Tipi di valori gestiti

Anche se la release qui presentata può elaborare solo numeri integer, la funzione di analisi della condizione è stata concepita per gestire vari tipi di dati. Questa potenziale elasticità è resa possibile dall’introduzione di un tipo di dato di nome USERLANG_VAL, il quale è così costituito:

struct USERLANG_VAL {
    char type ; // tipo del dato contenuto in "val"
    union { int vint ;
    char *vcharp ;
} val ; // valore


questa struttura, definita all’interno del file ulcondit.hpp, può essere arricchita di tutti i tipi di dato che si desidera gestire semplicemente introducendoli all’interno di "val". Così si possono memorizzare le date, i numeri immaginari e quant’altro necessiti.
Per la variabile type si dovrà prevedere un valore che identifichi i vari tipi affinché il programma possa sapere che cosa USERLANG_VAL.val contenga.
La parte più complessa inerente l’introduzione di nuovi tipi di dati è quella che coinvolge le funzioni di acquisizione e calcolo. Ad esempio, la funzione che estrae i valori numerici dalla stringa contenente la condizione si chiama takeNumValue() e converte solo in formato integer. Per consentirle di gestire altri tipi come il long o float è possibile analizzare la lunghezza in caratteri del numero estratto dalla stringa, il quale viene temporaneamente memorizzato in un char array di nome strNum e stabilire di conseguenza il tipo più idoneo avendo cura di utilizzare l’appropriata funzione di conversione e di memorizzarne il tipo in USERLANG_VAL.type.
Per quanto attiene la parte dei calcoli la situazione si presenta più complessa in quanto si devono prevedere delle funzioni di conversione fra tipi come nel caso di somma di un integer con un float. Inoltre la funzione numExprCompute_Compute() che si occupa di eseguire i calcoli riceve come parametri due integer. Ma in realtà non costituisce un grosso inconveniente in quanto essa può essere modificata per ricevere come parametro due USERLANG_VAL: al suo interno si gestiranno le eventuali conversioni di tipo. Anche il ricorso ai template può sostituire un metodo per ampliare questa funzione.


Gli operatori

Gli operatori matematici sono la somma, la sottrazione, la moltiplicazione, la divisione, il modulo, l’elevazione a potenza. Gli operatori di relazione sono il minore, il maggiore, l’uguale, il diverso, il minore/uguale ed il maggiore/uguale. Gli operatori logici sono l’AND, l’OR ed il NOT.
Poiché le loro caratteristiche intrinseche dovrebbero essere già chiare a tutti non ci si soffermerà a parlarne, mentre si affronterà l’aspetto di come sono fra loro correlate.
La forma più semplice di una condizione in C è rappresentata da un valore: se esso è zero la condizione è falsa, altrimenti essa risulta vera.
Forme più complesse vedono presenti gli operatori di relazione e logici. Risulta impossibile realizzare una funzione in grado di analizzare una condizione in stile Basic senza realizzare un albero, mentre ciò è possibile se la condizione può essere di tipo C style.
Il motivo di questa differenza è semplice: se la condizione inizia con delle parentesi non si può sapere se esse si riferiscono a un’espressione matematica e quindi si debba lanciare la relativa funzione di calcolo, oppure esse servono a raggruppare espressioni relazionali o logiche come nell’esempio:


(((1+5)—4<9 AND 1=1) OR (2<2)) AND 3=3

Sfruttando la visione più aperta tipica del linguaggio C, tutti gli operatori non vengono fra loro divisi, ma solo catalogati in tre famiglie aventi fra loro differenti priorità. Così gli operatori matematici hanno priorità rispetto agli operatori relazionali che a loro volta hanno maggior priorità rispetto a quelli logici.
Con questo principio la condizione risulta un’espressione contenente vari tipi di operatori che può essere elaborata con un semplicissimo analizzatore a discesa ricorsiva. Gli operatori logici e relazionali restituiscono il risultato vero o falso utilizzando un integer che può avere valori zero e 1: questo permette di realizzare anche espressioni quali:

(1=2 OR 34) +3÷ (i. AND 1)

A chi programma in linguaggio C/C++ questa espressione è generalmente familiare e può tranquillamente venire utilizzata; essa viene valutata come vera. Ma ben si sa che l’eccessiva libertà del C può causare qualche problema. Ad esempio, l’espressione 1 < 2 < 3 è simile alla forma utilizzata dalla matematica per rappresentare i range: così 1 < x < 10 si può leggere come x assume valori compresi fra i limiti 1 e 10 esclusi. Ma se questo esempio restituisce il valore vero, l’espressione 9 > 5 > 3 restituisce falso.
Come abbiamo visto prima, un semplice ed efficace sistema per creare un analizzatore di condizioni consiste nel considerare tutti gli operatori come facenti parte di un solo insieme all’interno del quale esistono delle priorità e che gli operatori condizionali e logici restituiscono un integer con valore zero oppure 1. La prima parte dell’espressione, 9 > 5, viene valutata come vera; la successiva valutazione fra il risultato ottenuto (vero, quindi 1) ed il numero 3 otterrà il valore falso perché l’analizzatore valuterà se uno è maggiore di tre. Tornando al programma, il file contiene al suo inizio la dichiarazione di tutti gli operatori che gestisce ed i sottoinsiemi di appartenenza. La priorità è definita mediante l’attribuzione di un valore numerico progressivo. Per gestire la pariteticità delle priorità fra operatori quali la somma e la sottrazione, gli ultimi due bit non vengono presi in considerazione: la funzione conditionMgrExec2() esegue uno shift a destra per poter eseguire correttamente la valutazione delle priorità; l’operatore di somma che ha codice 65 e quello di sottrazione che ha codice 66 sono considerati equivalenti (in quanto lo shift dei 2 bit di destra li trasforma entrambi nel numero 16) e vengono quindi eseguiti nella successione in cui appaiono nell’espressione in rispetto delle regole matematiche.


Parser matematico ed altro

In altre parole, la condizione rappresentata e gestita in formato C style è a tutti gli effetti un’espressione che viene calcolata e gestita da un parser matematico in grado di gestire un set di opera tori superiore a quello standard. Da questa semplice osservazione si può intuire che con il parser che troverete nel dischetto si possono anche eseguire i normali calcoli matematici senza bisogno di ricorrere ad altre funzioni. Esiste però una differenza fra un’espressione matematica più o meno compressa come tipo di operatori ed una condizione: generalmente la stringa contenente la condizione deve essere elaborata interamente e deve restituire i valori zero oppure 1. Invece, l’espressione matematica può essere racchiusa in qualcos’altro come nel caso di parametro di una funzione e conseguentemente l’elaborazione della stringa non necessariamente deve coincidere con la fine della stringa. Da questa osservazione sono state introdotte due diverse funzioni: computeExpression() che esegue il calcolo di un’espressione e conditionMgr() che restituisce vero o falso dopo aver elaborato una condizione. I parametri richiesti dalla prima funzione sono i seguenti: una variabile USERLANG_VAL ove memorizzare il risultato del calcolo ed un char * alla stringa da elaborare. Essa restituisce un puntatore al primo carattere inutilizzato della stringa.
La seconda richiede solo il char * alla stringa contenente la condizione. A parte la differenziazione dei parametri e il tipo che restituiscono, esse sono fra loro quasi identiche.
Per evitare errori di tipo, la funzione che ckTypeCoerence() verifica che le due variabili che sono oggetto di elaborazione in un determinato momento siano fra loro compatibili. Questa funzione esegue semplicemente un controllo sulle variabili type contenute in USERLANG_ VAL delle due variabili coinvolte; introducendo nuovi tipi di dati si potrebbe pensare a far eseguire le conversioni opportune direttamente a questa funzione: così facendo si otterrebbe il duplice vantaggio di avere un controllo sulla coerenza e un contemporaneo aggiustamento dei tipi ove fosse necessario con un sostanzioso guadagno nella leggibilità del programma.


Le stringhe

Come abbiamo visto, anche se non è stata implementata la gestione delle stringhe, è comunque stata prevista. Utilizzando opportunamente le funzioni e tecniche descritte apparse nei numeri precedenti inerenti il parser per funzioni di tipo stringa si può realizzare il tutto disponendo già di buona parte dei sor genti necessari.


Studio del funzionamento

Chi fosse interessato ad approfondire il funzionamento dell’analizzatore di condizioni può vederlo attivando il simbolo DBG_DSP_EXEC che si trova in condmgr.cpp: esso visualizza il comportamento della ricorsione con i vari operatori che vengono man mano elaborati attraverso la compilazione di chiamate a funzioni quali la conditionMgrDisplay(); esse sono disponibili solo se questo simbolo viene attivato, altrimenti esse non vengono compilate. Il file main.cpp contiene alcuni esempi di come queste funzioni operino. Esso può venire impiegato come prova iniziale anche per vedere che per queste funzioni non c’è differenza fra un’espressione matematica ed una condizione.


Conclusioni

In questi mesi abbiamo parlato molto di parser: questo articolo chiude l’argomento presentando idee aggiuntive e soluzioni per certi aspetti più raffinate delle precedenti.
Attualmente sono al lavoro per cercare di realizzare un interprete di linguaggio che possa essere introdotto e gestito all’interno di un software al fine di renderlo programmabile dall’utente, come avviene con il Dbase.
Quanto è sta to esposto in questo articolo è stato tratto da tale lavoro. Se l’argomento può essere di vostro interesse fatemelo sapere. Nel frattempo non mi rimane che salutarvi e ricordarvi che ogni suggerimento e critica costrutti va 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
Maggio 1996