Paolo Guccini

Impossibile non é per sempre

INTERPRETI DI LINGUAGGIO:
Come eseguono i programmi

I sorgenti sono disponibili per il download.

Un programma può essere eseguito solo dopo che le funzioni di scanning e parsing hanno analizzato con successo e conseguentemente prodotto le strutture dati che verranno utilizzate a run time.
Riprendiamo e concludiamo l’analisi e la realizzazione pratica di un interprete basic.


In quasi tutti i linguaggi di programmazione, l’allocazione e la dichiarazione delle variabili costituisce un passaggio da compiersi necessariamente prima degli altri. Sebbene questa priorità nella sequenza delle istruzioni non strettamente indispensabile sotto l’aspetto squisitamente tecnico, viene comunque richiesta per dare una maggiore leggibilità al programma. Infatti non causerebbe nessuna difficoltà di gestione un programma come seguente:

DIM A AS INTEGER
A = 1
DIM B AS INTEGER
B = 2
PRINT A + B

Infatti l’interprete non dovrebbe far altro che inserire ‘A’ nella tabella delle variabili, assegnarle il valore ‘1’, inserire ‘B’ come altro elemento nella stessa tabella delle variabili, assegnare a quest’ultima il valore ‘2’ e stampare la somma di ‘A’ e ‘B’.
Ma questo sorgente non è generalmente accettato in quanto la grammatica dei linguaggi richiede che le variabili vengano dimensionate nella primissima parte del programma.
Questo consente all’interprete di eseguire un miglior esame del sorgente e di scoprire eventuali errori, nonché di realizzare un certo livello di ottimizzazione.
Comunque, sotto l’aspetto puramente pratico, un interprete non necessita quindi di questa restizione per il programmatore, mentre per i compilatori potrebbe essere diverso in quanto le variabili rappresentano un argomento un poco più articolato perché devono essere previsti vari tipi di variabili: globali, statiche e temporanee, le quali prevedono differenti allocazioni.
L’elasticità di definire le variabili in ogni parte del programma, che potrebbe essere definibile anche come una certa forma di anarchia del Basic, era una caratteristica di alcuni suoi dialetti che prevedevano che esse potessero essere dichiarate implicitamente, semplicemente facendo apparire all’interno di un’istruzione un nome valido per una variabile: automaticamente veniva inserita nella tabella delle variabili con il valore zero oppure di stringa nulla a seconda del tipo che l’interprete era in grado di dedurre dall’eventuale presenza del carattere ‘$‘ (dollaro) posto in fondo al nome.
Questa possibilità portava a conseguenze talvolta disastrose generando bug che non risultavano immediatamente comprensibili: se, per esempio, veniva utilizzata la variabile TOTALEIMPONIBILE per memorizzare il valore da assoggettare all’iva in una fattura e con ALIQUOTA se ne definiva l’aliquota, potevano nascere problemi simili a quelli generati dalla seguente istruzione:

IVA = ALIQUOTA * TOTALEIMPONIPILE

la quale presenta un banalissimo errore di digitazione: nell’ultima variabile, la ‘B’ è stata sostituita da una ‘P’; esso è comunque sufficiente ad originare un errore di calcolo che porta la variabile IVA ad avere un valore costantemente a zero.
Si tratta certamente di un bug che non è di difficile comprensione e risoluzione, ma che talvolta può sfuggire ad un primo controllo portando il programmatore che non disponga di validi strumenti di debugging a dover effettuare svariati test: questa era una situazione abbastanza tipica nei primi anni dello sviluppo software sul personal computer dove il comando Trace oppure Step costituivano l’unico metodo allora disponibile.
Questa stessa si tuazione di potenziale rischio d’errore ricorre ancor oggi in linguaggi relativamente nuovi quali il Visual Basic For Excel, i quali però fomiscono istruzioni come la "Option Explicit" che forza il linguaggio a segnalare un errore ogni volta che incontra una variabile non precedentemente dichiarata in via esplicita tramite DIM.


Acquisire il valore di una variabile

L’interprete necessita di poter acquisire e modificare il valore delle variabili. La tecnica impiegata da questo interprete per ritrovare le variabili all’interno della relativa tabella è molto semplice in quanto esso le ricer ca scorrendo tutti gli elementi della linked list (costituita da delle struct VARIABLE) finché non raggiunge quella desiderata.
In altre parole siamo di fronte ad una semplicissima tecnica di ricerca sequenziale e quindi non particolarmente evoluta; il programmatore può migliorare le prestazioni delle ricerche semplicemente dichiarando le variabili più utilizzate prima delle altre affinché la ricerca inizi da esse e non sia quindi necessario scorrere tutta la linked list.
Ovviamente esistono tecniche decisamente più sofisticate che consentono di apportare un significativo aumento delle performance: le tabelle indicizzate con algoritmi di ricerca come l’hash oppure l’impiego di alberi binari in cui le variabili appaiano in ordine alfabetico costituiscono degli esempi alternativi.
Un dettaglio molto interessante consiste nel fatto che apportare questi cambiamenti risulta abbastanza semplice in quanto la tabella delle variabili viene gestita mediante una serie di funzioni dedicate, per cui ogni modifica interna ad esse non richiede interventi di riadeguamento o manutenzione anche in altre parti dell’interprete.

La precisione nelle variabili numeriche

Quando il programma interpretato necessita di eseguire un calcolo, si rende in dispensabile effettuare un’analisi sul tipo di precisione dei singoli dati che sono via via coinvolti e di quello della variabile che dovrà eventualmente contenere il risultato.
Per esempio, se deve essere calcolata la seguente espressione matematica

RISULT_INT = A_INT + 123456789,4321

in cui le variabili RISULT_INT e A_INT siano dichiarate come integer, l’interprete deve considerare che il calcolo avviene fra un integer ed un float (rappresentato dalla costante numerica) ed il risultato deve essere memorizzato in un altro integer con una conseguente possibilità di perdita di dati o di precisione.
Siccome gli operatori matematici utilizzati dall’interprete svolgono il loro lavoro utilizzando gli operatori nativi del linguaggio con cui esso stesso è stato realizzato, non costituirebbe nessun problema l’effettuare la somma di due tipi di dati differenti in quanto è già prevista all’origine la possibilità di sommare un integer con un float.
Il problema è invece rappresentato dal fatto che l’interprete, per memorizzare le variabili, alloca una struttura di nome VARIABLE al cui interno si trova una union di nome VARVALUE e che il tipo del valore in essa contenuto è ottenibile solo mediante il test sulla variabile membro VARIABLE::type.
Conseguentemente, in questa situazione, non è disponibile nessuno strumento nativo per eseguire i calcoli perché il linguaggio non sa come sommare due strutture e si deve necessariamente ricorrere allo scrivere il relativo codice all’interno dell’interprete.
Da qui prende il via la costruzione di una funzione che analizza i due tipi di dati coinvolti e provvede ad eseguire un upgrade della variabile che ha la precisione minore.
Si ottiene così un’operazione fra due variabili dello stesso tipo e si può conseguentemente richiamare l’operatore matematico nativo.
Un altro modo per risolvere questo problema può essere rappresentato dal casting, ovvero segnalare esplicitamente i tipi delle variabili, ma necessiterebbe di una serie di istruzioni switch troppo compressa per rappresentare e gestire tutte le possibili combinazioni dei tipi, ovvero bisognerebbe costruire uno switch contenente tanti case quanti sono i tipi delle variabili che consentano di selezionare il tipo della prima variabile e, per ogni case, un analogo switch che permetta di selezionare il tipo della seconda variabile.
I primi Basic risolvevano il problema dei calcoli fra valori aventi precisioni differenti con una tecnica banale ma funzionale: convertivano tutte le variabili in virgola mobile. Questo sistema portava ad una diminuzione delle prestazioni ma rappresentava per lo sviluppatore dell’interprete una veloce soluzione del problema.


L'esecuzione del programma

Affrontiamo ora i vari passi che consentono all’interprete di porre il programma in esecuzione dopo che le funzioni di scanning e parsing hanno svolto il loro lavoro.
L’esecuzione del programma incomincia reperendo dalla struttura PROGRAM::exeStatements la variabile first, la quale punta al primo statement contenuto nella linked list costituita da elementi EXESTATEMENT_STAT che è stata precedentemente generata [Giu96] [Lug96].
Questa operazione viene svolta dalla funzione UserLang::run() che esegue un loop fino a quando non si incontra lo statement di fine programma oppure viene riscontrato un errore di esecuzione.
Interessante notare che a questo livello viene gestito il comando Trace il quale permette la visualizzazione del numero di linea che viene di volta in volta eseguita racchiusa fra parentesi quadre; esso viene attivato e disattivato semplicemente modificando il valore della variabile Trace contenuta all’interno della classe UserLang.
Il loop della funzione ::run() esegue i vari statement mediante la chiamata ad un’apposita funzione di nome ::runSingleStatement(), la quale provvede ad identificare il tipo di statement analizzando la variabile EXESTATEMENT_STAT::statementId.
Si rende quindi necessario eseguire la specifica funzione che gestisce lo statement.
Esistono due tecniche per ottenere questo scopo: la prima ricorre al l’ istruzione switch che presenta tanti case quanti sono gli statement riconosciuti; la seconda si basa su una precedente costruzione di un array contenente l’indirizzo delle varie funzioni e l’esecuzione avverrebbe lanciando la funzione puntata dal l’elemento indicato dalla variabile ::statementId.
Se il secondo sistema garantisce un guadagno di tempo nell’avvio di ogni statement, il primo permette una maggioere facilità di comprensione da parte di chi studia l’interprete e consente di attivare una serie di controlli specifici per ogni statement come, per esempio, la verifica della corretta dichiarazione delle variabili che andrebbe effettuata esclusivamente all’inizio del programma e non dopo.
Se il parser ha svolto un approfondito lavoro di analisi del programma e l’interprete passa dalla fase di studio a quella dell’implementazione pratica, allora è preferibile impiegare la seconda tecnica basata sul l’array di puntatori a funzioni.
La gestione dei salti da statement a statement è gestita dalla funzione ::runSingieStatement(): il suo compito è quello di eseguire un singolo statement e, una volta terminata l’elaborazione, restituire alla funzione chiamante ::run() un puntatore allo statement che dovrà essere elaborato; quando ::run() riprende il controllo deve verificare se il valore che ha ricevuto da ::runSingleStatement() costituisce uno statement da elaborare oppure se il ciclo deve terminare in quanto è stata raggiunta la fine del programma.
Passiamo ora in rassegna i vari statement al fine di vederne gli aspetti più significativi in relazione al lavoro che l’interprete deve eseguire per ognuno di essi.


Lo statement DIM

L’allocazione di una variabile richiede semplicemente una chiamata alle funzioni deputate alla loro gestione richiedendo la creazione di un nuovo elemento che presenti le caratteristiche specificate nell’istruzione DIM: il nome ed il tipo. Questo sistema di delegare il lavoro ad una funzione specifica, solleva l’interprete di un lavoro consistente e permette, a chi desiderasse apportare ampliamenti a questo programma, di implementare con relativa facilità gli array e le strutture.


Lo statement LET o di assegnazione

Lo statement Let viene utilizzato per assegnare un valore ad una variabile.
La keyword Let può essere omessa in quanto la sintassi la prevede come opzionale; fondamentale è invece l’operatore = (uguale).
Un esempio di assegnazione con e senza la keyword Let può essere il seguente:

LET A = B + 1 A = B + 1

in entrambi i casi viene assegnato il valore 1 alla variabile "A".
Questo statement rappresenta uno degli aspetti più complessi legati allo sviluppo di un interprete. Infatti esso interagisce con le variabili in quanto deve poterne acquisire e modificare il valore nonché deve poter effettuare il calcolo di espressioni matematiche.
Per migliorare le prestazioni dell’interprete, è possibile modificare il parser affinché esegua dei controlli sul tipo di precisione delle variabili coinvolte e segnali eventuali rischi di perdita di precisione.


Gli statement IF e WHILE

Probabilmente l’analisi di una condizione, sia quella comparente in una IF oppure in un ciclo quale il WHILE, costituisce l’aspetto più ostico da affrontare e sviluppare.
La condizione deve poter con tenere varie sotto-condizioni legate fra loro da operatori relazionali AND / OR / NOT, le quali sono rappresentate da un confronto svolto dagli operatori condizionali (minore, maggiore, uguale, eccetera) su due distinti elementi, i quali sono costituiti dalle variabili, da costanti e dalle espressioni matematiche.
Coinvolgendo moltissimi aspetti di un interprete, la gestione delle condizioni viene lasciata per ultima: prima si crea il gestore delle variabili, poi quello delle espressioni matematiche, e poi quello per la gestione delle espressioni booleane; a questo punto si dispone di tutti i moduli necessari ad implementare la IF.


Lo statement PRINT

Lo statement PRINT ha un ruolo molto semplice: deve visualizzare un dato. Esso può essere rappresentato da una variabile, da una costante oppure da un’espressione matematica.
Appare abbastanza evidente l’analogia con le condizioni della IF: infatti i moduli utilizzati da questo statement sono identici e differiscono solo per il tipo di dato finale che gestiscono; la IF si limita ad eseguire una valutazione booleana sul risultato dell’espressione logica, mentre lo statement PRINT provvede a fornire una visualizzazione del risultato dell’elaborazione.

Lo statement INPUT

L’interazione programma/utente avviene mediante gli statement PRINT ed INPUT. Quest’ultimo consente all’utente di digitare un valore che verrà utilizzato per modificare la variabile specificata. Per poter implementare questo statement è sufficiente prevedere un sistema che acquisisca da tastiera una sequenza di caratteri e che la gestisca in relazione al tipo di valore atteso che viene determinato dal tipo della variabile specificata nel l’INPUT: se è numerica si ricorre alle apposite funzioni come la atoi() per eseguire le opportune conversioni, mentre se è una stringa è sufficiente passare la sequenza digitata alla funzione che si occupa di aggiornare il valore delle variabili.

Gli altri statement

Abbiamo sinteticamente visto i vari statement che l’interprete "Very Small Basic" mette a disposizione dell’utente e, palesemente, mancano nell’elenco alcuni statement classici del Basic.
Per esempio manca la coppia di statement OPEN e CLOSE. Essi non sono stati implementa ti in quanto richiederebbero anche l’introduzione di statement specifici per la gestione dei file quali: FIELD, GET, PUT, PRINT#, INPUT#, LSET, RSET.
Se a prima vista questa mancanza può ridurre questo interprete ad un semplice esempio accademico, in realtà si può osservare che implementare questi statement non è affatto difficile: l’OPEN deve semplicemente richiamare una funzione fstream :open() e per la CLOSE il discorso è analogo.
Ma chi dovesse realizzare un interprete per la gestione di sistemi di controllo utilizzerà altri tipi di statement specifici per acquisire stati e generare movimenti programmabili attraverso l’accesso alle porte di I/O. Conseguentemente, realizzare un piccolo interprete che potesse soddisfare le esigenze di tutti avrebbe rappresentato un progetto la cui portata andava ben oltre quelli che erano i traguardi prefissati, per ciò è stata fornita una base la quale, in relazione all’utilizzo che ritenete più ido neo al vostro scopo, potete modificare introducendo tutti gli statement di cui necessitate con la relativa specifica sintassi.
Ma ancora più importanti degli statement non implementati sono le possibilità di richiamare funzioni o subroutine.
Ogni linguaggio necessita della possibilità di identificare delle porzioni di programma con un nome simbolico e di poterlo richiamare. L’argomento è già stato introdotto il [Lug96] ma si rende utile un maggiore approfondimento.
I problemi connessi alla costruzione della gestione delle routine sono: la creazione di variabili la cui visibilità o scope sia ridotta alla routine stessa, la necessità di riprendere l’elaborazione dallo statement successivo a quello che ha richiamato la routine quando quest’ultima ha terminato l’elaborazione, l’abilitazione della ricorsività.
Il primo problema relativo alle variabili si può risolvere in vari modi.
Uno può essere la realizzazione di una linked list delle variabili separata per ogni routine considerando lo stesso programma come una routine; essa verrà creata all’inizio della routine e deallocata all’uscita.
Altro sistema può essere l’identificare le variabili con una stringa composta dal nome della routine e quello della variabile.
Per quanto attiene alle chiamate delle subroutine, in linea di principio si può dire che, modificando opportunamente la funzione : : runSingleStatement() affinché possa lanciare una ricorsione, si risolve brillantemente il problema.
In dettaglio, se lo statement in esecuzione è un GOSUB, allora si deve salvare l’indirizzo dello statement successivo (che si ottiene dalla variabile EXESTATEMENT_STAT ::jumpTrue relativo allo statement corrente e lanciare una funzione simile a ::run() che inizi l’elaborazione dallo statement che riceve come parametro ed esegua il ciclo fino a quando non viene incontrato lo statement RETURN.
Quando il controllo ritorna a ::runSingleStatement(), essa deve semplicemente restituire alla funzione chiamante l’indirizzo precedentemente salvato.

Conclusioni

Abbiamo affrontato dettagliatamente varie tecniche che si possono impiegare per realizzare un interprete di linguaggio Basic ad uso generico.
Esso può venire impiegato direttamente per gestire degli script oppure per rendere programmabile il vostro software esattamente come accade con il Dbase oppure con l’Excel o il WinWord; andrà ovviamente arricchito di tutti quegli statement che si rendono necessari nei vari ambienti applicativi.
L’obbiettivo principale e forse più interessante era quello di tracciare chiaramente una strada nel mondo degli interpreti di linguaggio e della loro realizzazione: sui compilatori è possibile trovare numerosi libri che spiegano dettagliatamente la parte teorica ed affrontano nella pratica come li si possano realizzare per svariati linguaggi, ma per gli interpreti il materiale è decisamente più scarso.
Mi auguro che l’argomento abbia suscitato in voi l’interesse e la curiosità che merita, infatti l’utente è alla costante ricerca di software altamente parametrico e, possibilmente, programmabile; ora disponete di una classe in C++ da utilizzare all’occorrenza nonché del le conoscenze teoriche necessarie per le modifiche del caso o addirittura la completa riscrittura.
Non mi rimane che congedarmi ricordandovi che ogni critica costruttiva o suggerimento è sempre apprezzato.

Bibliografia

[Giu96] Paolo Guccini, Computer programming DEV, "Realizzare un linguaggio di programmazione", Giugno 1996, Edizioni Infomedia. [Lug96] Paolo Guccini, Computer programming DEV, "Interpreti di linguaggio: lo scanner ed il parser", Luglio/Agosto 1996, Edizioni Infomedia.

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
1995