I sorgenti sono disponibili per il download.
Poter fornire all’utente del software programmabile mediante un’interprete interno
come accade per il dbase è spesso visto come un aspetto di grande pregio
Molti sviluppatori di software hanno accarezzato l’idea di realizzare un linguaggio di programmazione, ma spesso hanno desistito per vari problemi quali la complessità ed i costi oppure la mancanza di una reale utilità oggettiva. Ma vi sono d casi in cui sussistono delle tangibili necessità per le quali ci si deve affrontare l’oscuro mondo degli interpreti e dei compilatori. Ad esempio quando si realizzano delle schede elettroniche che possono essere programmabili a runtime tramite software oppure quando si vuole fornire al l’utente uno strumento altamente sofisticato per parametrizzare o gestire il comportamento di un programma come accade con il Dbase o l’Access.
Lo scopo di questo articolo è illustrare e fornire alcune tecniche per realizzare un interprete di linguaggio non ché una serie di classi realizzate in C++ che gestiscono un piccolo linguaggio Basic-like prendendo spunto dal Basic 2.0 dell’IBM. Suddette classi, opportunamente implementate all’interno di altri programmi, consentiranno di fornire all’utente una vera e propria interfaccia programmabile.
Cos’è un interprete di linguaggio
Il microprocessore è in grado di elaborare esclusiva mente istruzioni binarie
in linguaggio macchina, conseguentemente i programmi eseguibili
devono essere in questo formato.
Per scrivere un programma si può ricorrere a linguaggi differenti che,
in relazione alla somiglianza che hanno rispetto al codice binario della CPU,
prendono il nome di linguaggi a basso o alto livello.
L’assembler rappresenta il linguaggio più a basso livello disponibile.
I linguaggi ad alto livello dispongono di un’ottima astrazione dall’hardware
ovvero non sono influenzati dalle differenze che intercorrono fra i vari microprocessori:
lo stesso programma scritto in Basic può essere compilato ed elaborato su un Intel (utilizzato dai personal computer)
e su un Motorola (impiegato dai Macintosh) senza problemi.
La compilazione è quella fase che trasforma un programma scritto in un qualunque linguaggio
nel formato binario riconoscibile dal microprocessore.
L’interprete è esso stesso un programma ma, a differenza del compilatore,
non genera un altro programma in formato binario:
si limita ad eseguire le varie istruzioni che incontra.
Per fare un esempio concreto, pensiamo all’istruzione PRINT
che genera la stampa a video di una linea vuota.
Quando l’interprete riconosce di essere in sua presenza, esegue la funzione fprinf()
oppure utilizza lo stream cout: essi sono parti compilate dell’interprete medesimo
che vengono utilizzate all’occorrenza.
Il compilatore è in grado di generare pro grammi eseguibili ed autonomi
dotati di una velocità di esecuzione elevata; la loro dimensione è generalmente sensibile.
L’interprete non è in grado di generare un programma autonomo,
il quale invece necessita sempre del l’interprete per poter essere elaborato
e la velocità di elaborazione del programma è limitata
mentre la sua dimensione è di solito modesta.
L’interprete vantava nel passato una estrema facilità di debugging
che i compilatori non avevano assolutamente,
ma quest’ultimi hanno raggiunto da vari anni un livello di sofisticazione tale che i loro strumenti
risultano decisa mente più efficaci anche in quest’area così importante per chi sviluppa software.
L’operazione di trace interattiva,
ovvero la possibilità di eseguire passo passo l’elaborazione e verificare con temporaneamente il valore delle variabili,
è divenuta una possibilità standard offerta da tutti i compilatori
per cui è venuta a mancare uno dei motivi fondamentali che han no contribuito al successo del Basic.
Ma gli interpreti non sono assolutamente morti:
in de terminate situazioni essi dimostrano tutta la loro utilità che un compilatore non può offrire.
Per esempio il Dbase dispone di un interprete il cui linguaggio
è compilabile mediante programmi quali il Clipper,
ma, se il programma interpretato è lungo qualche centinaio di byte,
la sua versione compilata sorpasserà i cento kilobyte.
Il motivo di questa notevole differenza consiste nel fatto che
l’interprete dispone al proprio interno di moduli che devono essere ricompresi nella versione eseguibile.
Altro esempio di utilità dell’interprete lo si può trovare nelle interrogazioni
ai database: se ogni volta che si desiderasse eseguire una qualunque serie di elaborazioni
anche estemporanee su un archivio fosse necessario compilare un programma,
si avrebbe un dispendio di tempo eccessivo ed una scomodità a cui l’interprete pone rimedio.
Continuando con gli esempi si può pensare ai programmi che forniscono
all’utente un linguaggio macro o script come i programmi di comunicazione.
A questo punto il concetto di interprete di linguaggio dovrebbe essere chiaro.
L’inutilità di un nuovo linguaggio
I linguaggi di programmazione sono davvero numerosi e vengono catalogati in famiglie
in base a vari parametri di valutazione. Alcuni di essi raggiungono alti livelli di specializzazione
per cui sono giudicati come più idonei allo sviluppo in de terminati settori:
il Cobol è conosciuto come il linguaggio per le applicazioni commerciali
mentre il Fortran è più indicato in ambiti matematici.
Ma, seppur ancora valide in linea di principio, queste suddivisioni perdono di consistenza dì anno in anno:
Per esempio, il Basic originario ha ben poco in comune con quei linguaggi
con cui spartisce solo il nome e vagamente la sintassi come accade nel caso del Visual Basic.
Il Basic, ovvero Beginner s’ All-purpose Symbolic Instruction Code, era nato come un semplice linguaggio interpretato adatto ai novizi che permettesse di essere utilizzato per qua si qualunque scopo. Oggi la sua fisionomia si è radicalmente trasformata sino ad elevano al rango di un ottimo strumento di sviluppo che unisce doti di notevole semplicità formale e quindi facilità di apprendimento ad una alta efficienza del codice che produce. Anche l’aspetto iniziale di puro interprete è oggi stato sorpassato: quasi tutti i Basic producono codice eseguibile in formato binario con evidenti guadagni in termini di efficienza.
Il motivo di questa radicale trasformazione senza cambio del nome ha dei semplici motivi commerciali:
ogni sviluppatore ben conosce gli aspetti quasi tutti negativi connessi all’apprendimento di un nuovo linguaggio.
La sua padronanza la si acquisisce solo con il tempo,
facendo esperienza con l’antico sistema del provare e riprovare.
Conseguente mente le software house, ben consce di questo problema,
si appoggiano a linguaggi che si ritengono già noti ai programmatori
e che quindi consentano a quest’ultimi di limitare considerevolmente i tempi di apprendimento.
Da queste ed altre considerazioni ha preso il via la produzione di nuovi linguaggi estremamente simili a linguaggi già noti,
ma arricchiti di numerosissime funzionalità.
Delphi e il Visual Basic possono rappresentarne un esempio.
A parte queste considerazioni di principio, è comunque da ricordare che esistono situazioni
in cui i linguaggi "standard" non sono soddisfacenti.
Da qui il nascere di linguaggi orientati alla risoluzione di specifiche problematiche in aree ben definite e delimitate:
il PCL (Page Con trol Language), l’HPGL (Hewlett Packard Graphic Language)
ed il Postscript sono linguaggi o, se preferite, metalinguaggi nati esclusivamente
per descrivere e riempire un documento cartaceo.
Non esulano da questo discorso i linguaggi macro come quelli implementati
in alcuni word processor e fogli elettronici come il WinWord o l’Excel;
anche l’SQL (Structured Query Language) ne rappresenta un esempio:
esso dispone di statement specifici per la gestione dei database e, a parte qualche critica mossagli da più parti,
costituisce un eccellente strumento che è stato implementato in numerosi programmi.
Traendo le conclusioni, esistono linguaggi specifici o quasi per ogni area applicativa.
Ma se qualcuno, per una qualunque ragione, ritiene che un nuovo linguaggio possa essere più efficiente
rispetto a quelli già esistenti, può tranquillamente provare a costruire un interprete o compilatore
per il proprio linguaggio.
Affrontiamo ora le principali considerazioni sul linguaggio che vanno formulate
prima di incominciare la stesura del programma interprete.
Considerazioni sul linguaggio
Lo sviluppo di un programma richiede sempre una fase di analisi
per stabilire come esso dovrà essere costruito e quali caratteristiche dovrà presentare.
Anche un interprete non si discosta da questa regola.
Si può iniziare con lo stabilire se il linguaggio permetterà di definire tipi di dato aggregati
come accade con la struct del C/C++.
Questo aspetto importante per la progettazione del sistema di gestione delle variabili
in quanto le struct devono poter essere nidificate
e quindi anche l’accesso alle variabili deve prevedere un meccanismo idoneo allo scopo.
Devono essere oggetto di analisi anche i sistemi di controllo incondizionato del flusso
come le istruzioni analoghe al goto.
Sebbene alcuni puristi della programmazione strutturata asseriscano
che l’impiego di questa istruzione non è indispensabile, la sua presenza permette una maggiore libertà al programmatore
che non ne abusi e, talvolta, consente significativi miglioramenti della leggibilità del sorgente.
La disponibilità dell’istruzione goto introduce ad alcune considerazioni fondamentali
quali lo scope e la ricorsione. Nel Basic ogni variabile è globale ovvero ha una visibilità o scope estesa a tutto il programma,
il quale è libero di acquisirne o modificarne il valore da ogni parte del programma.
Nel caso si desideri introdurre meccanismi di protezione o limitazione della visibilità (information hiding)
come accade per le variabili nelle varie funzioni scritte in C/C++,
è indispensabile che il linguaggio consenta la suddivisione del programma in moduli autonomi:
in Basic essi vengono chiamati subroutine oppure function.
Sebbene questi concetti non siano stati implementati nella versione del l’interprete Basic
che stiamo analizzando, è comunque utile ed interessante vederne alcuni particolari operativi.
La gestione dei moduli come parti costituenti il programma può essere efficacemente realizzata
partendo dall’idea che anche il programma principale è a sua volta un modulo.
Di conseguenza, con alcune relativamente semplici modifiche, l’interprete può gestire i moduli separati
tramite la ricorsione su se stesso. La gestione delle variabili non presenta grossi problemi
in quanto essa segue la stessa prassi di allocazione in tut ti i moduli,
ovvero si provvede a creare un array delle variabili ogni volta che ha inizio l’elaborazione di un modulo;
le variabili pubbliche possono essere definite all’interno di un array separato
che risulti accessibile da ogni modulo.
L’introduzione dei moduli comporta un limite all’utilizzo del goto: non è possibile saltare a label definite in altri moduli,
bensì, in tali casi, si deve poter utilizzare un’istruzione che, una volta terminata l’elaborazione del modulo,
riporti il controllo all’istruzione successiva a quella chiamante (Call).
La gestione dei salti interni al modulo è semplice e verrà illustrata in seguito,
mentre l’esecuzione di un altro modulo rappresenta un aspetto più impegnativo.
Senza voler spiegare tutti i dettagli, si può dire che il lancio della ricorsione dell’interprete
con parametro il modulo da elaborare risolve egregiamente molti problemi.
La progettazione
A questo punto si può procedere con il determinare tutti gli statement
che il programma deve riconoscere e la relativa sintassi.
Nella figura 1 è riportato questo elenco.
Nel caso la vostra intenzione sia quella di ricalcare un linguaggio già esistente
questa operazione risulterà alquanto semplice perché si conoscono a priori gli statement
e quindi i vari compiti che svolgono.
Se si desidera invece creare un linguaggio ex novo,
si deve considerare che quest’ultimo dovrebbe permettere all’utente di eseguire
le seguenti operazioni base:
- dimensionamento delle variabili;
- assegnamento di valori alle variabili;
- test di confronto;
- calcolo di espressioni matematiche;
- calcolo di espressioni logiche o boolene;
- apertura, lettura, scrittura e chiu sura di un canale di I/O.
Ovviamente stiamo facendo riferimento ad un normale linguaggio procedurale
in quanto esistono altri linguaggi in cui il concetto di variabile è radicalmente diverso o assente.
I canali di Input/Output corrispondono alla tastiera, al video, alla stampante ed ai files.
L’interprete dovrebbe consentire basilarmente l’accesso al video ed alla tastiera e, possibilmente, alla stampante.
Se non viene fornito anche uno strumento per l’accesso ai files, ciò non renderà inutile l’interprete
ma potrebbe essere considerato come dotato di caratteristiche insufficienti
per essere un vero e proprio completo strumento di lavoro.
Il limite massimo di canali che l’interprete potrà gestire simultaneamente
verrà determinato a priori creando un array di dimensione prefissata contenente una serie di puntatori ai vari canali,
oppure senza li mite ricorrendo ad una gestione tra mite una lista dinamica.
In ogni caso è indispensabile fare attenzione ai confini imposti dal sistema operativo:
ad esempio, si potrebbe creare l’array dei canali contenente mille puntatori,
ma il DOS non con sente di aprire simultaneamente un così grande numero di files,
perciò il dimensionamento deve essere eseguito con criterio.
Le variabili
Le variabili rappresentano un componente importante dell’interprete.
Esse sono composte da due parti: il nome ed il valore.
Il nome dovrebbe essere generalmente composto da una sequenza di caratteri, tipicamente fino a trenta,
ed inizia con una lettera seguita da altre lettere o numeri.
Il valore può essere di diversi tipi in relazione a quanti si decide di implementarne.
Un buon sistema può essere sintetizzato mediante la creazione di una struttura contenente
una union ricomprendente tutti i tipi che l’interprete gestisce,
come l’integer, il float e la stringa.
La seconda parte della struttura sarà costituita da una variabile
indicante il tipo di dato che la prece dente union racchiude.
La figura 2 ne riporta un esempio: in essa viene dichiarata il valore enumerativo VALTYPE
che viene sfruttato nella struct VARIABLE per conoscere quale informazione
fra quelle contenute in VARVALUE è quella valida, mentre varName contiene il nome assegnato alla variabile in formato stringa Asciiz.
L’aggiunta di un altro tipo di v bili è relativamente semplice:
dopo aver aggiornato VALTYPE si procede a mettere nella union di VARVALUE il nuovo tipo.
La parte più problematica consiste nella gestione del le operazioni matematiche fra le variabili:
per motivi di semplicità di programmazione il Basic eseguiva una conversione di tipo
di tutti i valori coinvolti verso un formato di massima precisione e poi provvede va ad eseguire i calcoli.
Un’altra con versione verso l’eventuale variabile che avrebbe contenuto il risultato concludeva l’operazione.
Questo è senz’altro un sistema poco efficiente ma ha il pregio di essere di semplice implementazione:
a quei tempi non erano disponibili i linguaggi con template per cui la scelta dei programmatori è ben comprensibile.
Come lavora un interprete
Esistono vari tipi di interpreti e altrettanti sistemi per l’elaborazione del sorgente da eseguire.
Uno dei sistemi più utilizzati consiste nel leggere tutto il file contenente il programma sorgente
e trasformarlo in oggetti più semplici da gestire, i qua li verranno poi sottoposti a successive elaborazioni
per ottenere un’altra serie di oggetti che possano essere utilizzate per l’esecuzione del programma.
Queste due operazioni si chiamano scanning e parsing.
Il compito della prima consiste semplicemente nell’individuare i vari token,
ovvero dei vari elementi che lo compongono, come le keyword, le costanti, gli operatori, eccetera.
Ognuno di essi viene memorizzato in una linked list simile a quella che appare nella figura 4.
In essa appaiono i seguenti elementi:
- una variabile di nome tokenld che identifica il tipo di token che l’elemento della linked list con tiene;
- una union di tipo CONSTVALUE che memorizza il token e/o il suo valore;
- un puntatore al successivo elemento della linked list;
- un interger che memorizza il numero di linea del programma che conteneva il token; esso serve per poter segnalare all’utente il nu mero di riga in cui si trovi un to ken errato.
Questa linked list potrebbe già essere utilizzata per l’esecuzione del programma che contiene,
ma sarebbe altamente inefficiente in quanto ogni statement di controllo del flusso
causerebbe un inaccettabile overhead in quanto ogni salto non sarebbe immediato ma necessiterebbe di specifiche ricerche:
la IF, per esempio, richiede di saltare al primo statement successivo la ELSE oppure successivo la ENDIF
se la condizione è falsa. Perciò si imporrebbe la scansione successi va di tutti i token fino a quando non si trova lo statement ricercato.
Ovviamente si rende indispensabile la gestione delle IF nidificate.
Discorso altrettanto pesante ricorre per il WHILE, in quanto ad ogni WEND si dovrebbe ripercorrere la linked list dall’inizio
alla ricerca del WHILE che precede il WEND in esame.
Altro difetto di questa linked list consiste nel fatto che non consente nessun tipo di analisi formale e sintattica del programma
come una IF senza ENDIF. Successivamente è la volta di un’altra operazione detta parsing,
la quale si occupa di eseguire una valutazione sulla correttezza del programma e di generare un’altra linked list che,
dopo un ulteriore elaborazione, possa essere impiegata per l’elaborazione del programma dell’utente.
Gli interpreti più sofisticati possiedono delle tabelle dette first and follow che consentono al parser
di eseguire delle valutazioni sulla correttezza del programma. A tal proposito esistono numerosi software, anche Public Domain,
per la definizione della grammatica del linguaggio.
Per esempio, la definizione della grammatica per un’espressione matematica appare in figura 5 ([1], pagina 134 e seguenti).
Essa potrebbe essere interpretata cosi:
- una espressione (expr) è costituita da un termine (term) a cui potrebbe (le parentesi graffe significano che la presenza di quanto esse racchiudono è opzionale) essere sommato o sottratto un altro termine;
- un termine è un elemento chiamato factor che potrebbe essere moltiplicato o diviso per un altro factor; si può notare che con questo metodo è già stata espressa la priorità fra gli operatori matematici;
- il factor è costituito da un valore numerico (ID) oppure da un’al tra espressione matematica.
A riguardo potrebbe essere interessante confrontare il libro [2] a pagina 295 e seguenti.
Ma se gli interpreti più sofisticati utilizzano queste tecniche che sono quelle impiegate
per la definizione della grammatica per compilatori di linguaggi particolarmente complessi,
esistono altre versioni di interpreti che rimandano questo tipo di analisi a runtime.
Questo tipo di approccio, identico a quello del vecchio Basic, consente di snellire considerevolmente
la stesura e la realizzazione dell’interprete, ma, per controparte,
fornisce all’utente uno scarso o ad dirittura insignificante livello di controllo sulla correttezza del suo programma.
Ritornando alla linked list che il parser genera, la si può concepire come una lista dei soli statement senza i relativi token.
Questo permette di accedere con la massima velocità
allo statement successivo, mentre i token saranno memorizzati in tante piccole liste,
ognuna agganciata al l’elemento della prima lista che con tiene lo statement a cui essi si riferiscono.
La figura 6 contiene uno schema di quanto esposto prendendo come esempio il seguente programma:
Print A + 2
Let C = 7 + A
Input E, F
In essa appare a sinistra, disposta in verticale, la linked list degli statement,
mentre alla destra di ogni elemento appaiono i singoli token.
Evidentemente i token di ogni singolo statement non sono accessibili dagli altri statement,
né tantomeno avrebbe senso il contrario.
Vediamo ora esattamente come l’interprete organizza la lista degli statement.
WHILE e IF
Il flusso di elaborazione del programma dell’utente è sequenziale.
Ogni statement conosce il suo successore in quanto contiene un puntatore ad esso all’interno della linked list.
Così l’elaborazione parte dal primo statement, esegue le operazioni ad esso associate e,
al termine, prende l’indirizzo dello statement seguente e ripete il ciclo
finché non terminano gli statement.
Ma esistono delle istruzioni che ne modificano il flusso come la WHILE e la IF.
Alla WHILE è associato lo statement WEND ed essi operano nel seguente modo:
la WHILE contiene una condizione che, se è vera, fa sì che l’interprete esegua lo statement successivo a WHILE,
altrimenti verrà eseguito quello posto dopo il WEND; ne consegue che ogni elemento della lista degli statement
deve contenere due puntatori che si potrebbero chiamare JumpTrue e JumpFalse;
essi contengono gli in dirizzi degli statement da eseguire dopo che sia stata valutata la condizione.
WEND non deve far altro che definire come statement successivo la WHILE associata; questo valore viene memorizzato in JumpTrue.
Per quegli statement che non alterano il normale flusso come PRINT ed INPUT,
lo statement successivo verrebbe individuato da JumpTrue.
Il discorso si complica leggermente per lo statement IF / ELSE / ENDIF,
in cui bisogna prevedere una doppia
serie di salti: se la condizione della IF è vera allora bisogna eseguire tutti gli Statement
sino a raggiungere ELSE per poi saltare ad ENDIF.
Se invece è falsa bisogna saltare al primo statement successivo la ELSE e continuare l’elaborazione dei vari statement.
La figura 7 contiene uno schema che illustra il valore definito per JumpTrue e JumpFalse
per ogni statement di un breve programma che esegue un ipotetico controllo su due variabili
e che ne stampa il nome di quella maggiore.
La creazione di un qualunque altro statement che modifichi il flusso come il DO / WHILE
è relativamente semplice: dopo averlo inserito nel la tabella degli statement riconosciuti,
si deve intervenire sulla funzione che costruisce i salti fra gli statement
affinché l’interprete sappia come combinare i salti in relazione ai vari statement.
Il punto della situazione
Sono stati toccati sinteticamente i diversi aspetti coinvolti nella definizione
di un linguaggio quali le strutture, la ricorsione, lo scope delle variabili.
Per quanto attiene la parte dell’implementazione delle classi,
sono sta te accennate le tabelle che l’interprete genera durante la scansione del programma sorgente.
Il mese prossimo affronteremo nella pratica la scansione del sorgente e i vari passi necessari
per predisporre quanto necessario alla fase di esecuzione del programma. Per ora non mi rimane che congedarmi.
Bibliografia
C. Faser, D. Hanson: A retarge table C Compiler: design and implementation; The Benjamin/ Cummings Publishing Company; 1995
R. Wilheim, D. Maurer: Compi ler Design, Addison Wesley, 1995