I sorgenti sono disponibili per il download.
La realizzazione di un interprete basic inizia attraverso la creazione di quelle funzioni che acquisiscono il programma sorgente e lo convertono in un formato idoneo all’esecuzione
Un programma attraversa varie fasi prima di poter essere eseguito:
la prima elaborazione a cui il sorgente viene sottoposto prende il nome di scanning.
Essa identifica ed estrae ogni singolo componente quali gli statement,
i numeri e le variabili per memorizzarli in una struttura interna all’interprete o al compilatore.
Questo consentirà alle varie funzioni che si succederanno di poter operare su oggetti noti a priori
con un conseguente significativo guadagno nelle prestazioni.
La fase successiva viene chiamata parsing e si occupa di verificare la coerenza al linguaggio dei vari token estratti dal sorgente
mediante lo scanner, nonché di realizzare una struttura che possa essere passata alle funzioni di elaborazione.
Scopo di questo articolo è presentare ed illustrare dettagliatamente il funzionamento di queste due routine
attraverso l’esempio pratico di alcune specifiche classi.
Lo scanner
Lo scanner è una funzione che accede direttamente al file contenente il programma sorgente.
Esso legge sequenzialmente ogni linea identificando ed estraendo ogni singolo componente
che viene chiamato token: gli operatori matematici, le variabili, le parentesi,
le costanti numeriche, gli statement.
Tutte le funzioni di cui lo scanner ha bisogno
sono state riunite all’interno di una sola classe a cui è stato dato il nome di UserLangScanner.
Questo consente un buon livello di astrazione dell’interprete,
il quale vede solo una classe alla quale richiede di espletare lo scanning;
questo sistema consentirebbe al programmatore di sostituire questa class con un’altra
nell’ipotesi che desideri cambiare addirittura linguaggio, ma, in forza della genericità del lavoro che lo scanner esegue,
non sarebbe neppure necessario intervenire realizzandone un altro ex novo:
basterebbe cambiare gli statement che esso riconosce.
Il costruttore di questa classe genera una tabella che contiene tutti gli statement del linguaggio
attraverso chiamate successive della funzione statementTableSetValue()
ed inizializza la variabile signature con un valore costante che fornisce
un piccolo ma utile aiuto in fase di debugging: il suo valore rimane invariato
fino a quando non viene invocato il distruttore. Ad ogni nuova linea di sorgente letta,
lo scanner aggiorna un contatore di nome sourceLineNum,
il quale contiene il numero di linea che è in elaborazione:
il suo valore viene memorizzato in ogni token che viene estratto dalla singola riga
affinché, se durante le fasi successive si individua un errore,
sia possibile comunicare all’utente su quale linea sia stato riscontrato il problema.
La funzione che si occupa di elaborare ogni singola linea e scomporla nei vari token si chiama scan_line().
Essa esegue un ciclo su tutta la sequenza di caratteri che compone la linea
passando il controllo a funzioni specifiche in base al tipo di carattere che via via viene trovato.
Quando il flow del programma ritorna a questa funzione,
essa provvede a memorizzare il token estratto mediante la funzione insertToken()
che impiega una linked list di strutture SCANTOKEN. Il primo carattere di un token può essere di cinque tipi:
- lettera dell’alfabeto
- numero
- operatori: matematici e di uguaglianza, modulo, elevazione a potenza
- identificatore di stringa (doppie virgolette)
- parentesi tonde e quadre
Vediamo quindi quali sono i comportamenti dello scanner in relazione al carattere che trova. Nel caso si sia trovato un carattere alfabetico viene richiamata la funzione extractAlpha() che attiva un loop di estrazione di tutti i caratteri consecutivi che siano lettere o numeri.
Segue l’identificazione immediata di quanto estratto che potrà essere:
- un operatore logico (AND, OR, NOT)
- uno statement
- una variabile
La funzione restituisce al chiamante ciò che ha estratto attraverso la variabile var
che ha ricevuto come parametro,
mentre attraverso il return comunica il tipo di token trovato.
Se il token inizia con un numero significa che si è in presenza di una costante numerica.
La funzione deputata alla sua estrazione si chiama extractConstNum():
essa inizia prendendo tutte le cifre contigue che trova memorizzandole sul char[] di nome tknChars
conteggiando contemporaneamente il numero di cifre componenti la parte intera e quella decimale.
Se è presente una parte decimale allora il valore viene convertito in unfloat, altrimenti,
in relazione alla lunghezza della parte intera,
la conversione prevederà due possibili tipi: integer oppure long.
Gli operatori matematici vengono estratti mediante la funzione extractOperator()
che è estremamente semplice: mediante un’istruzione switch
viene identificato il token il cui tipo viene restituito a scan_line() attraverso il consueto return.
La funzione extractConstStr() viene richiamata
allorquando il carattere in elaborazione identifica una stringa, il quale
è generalmente costituito dalle doppie virgolette.
Anch’essa è molto semplice ed intuitiva:
un loop provvede ad estrar re tutti i caratteri presenti sino a quando non viene trovato il carattere di chiusura della stringa;
quest’ultima viene quin di trasferita all’interno della struttura var
che la funzione ha ricevuto come para metro.
Unico dettaglio da osservare è che la stringa viene memorizzata temporaneamente
su una variabile membro di nome constTmp che ha una dimensione prefissata;
al fine di evitare gli overflow il loop di estrazione controlla
che la lunghezza raggiunta ad ogni nuo vo carattere inserito sia inferiore a quella prestabilita
mediante il simbolo CONSTSTR_MAXLEN.
L’ultima fun zione è extractBracket() che, ricorrendo ad un banale switch,
identifica il tipo di parentesi: tonda o quadra, aperta oppure chiusa.
Se la fase di scanning è stata completata senza problemi o errori,
allora la classe UserLangScanner ha generato una linked list contenente tutto il programma sorgente
scomposto nei suoi vari token: prossimamente vedremo che esiste una funzione membro di UserLangToken di nome tokenDump()
che provvede a visualizzare il valore dei vari token
consentendo così di avere una visione concreta di tutto il lavoro sin qui svolto
Il parser
Quando il programma sorgente è stato convertito da una sequenza di caratteri in una serie di token
mediante il lavoro dello scanner,
la gestione dei vari elementi diviene estremamente più semplice
in quanto non si rende necessario provvedere alla loro identificazione
perché contengono al loro interno la variabile tknId
il cui valore rappresenta il tipo di token.
Ora un’altra funzione prende la linked list dei token generata dallo scanner
per elaborarla e crearne un’altra affinché possa essere gestibile
dal modulo che si occupa dell’esecuzione del programma.
Le operazioni che il parser normalmente compie sono state descritte nell’articolo del mese precedente,
quindi non verrà affrontata nuovamente la parte teorica bensì analizzeremo come implementarlo la pratica.
Il parser è con tenuto in una classe di nome UserLangParser che mette a disposizione la funzione membro di nome parse().
Essa è costituita da un ciclo che richiama la funzione makeSingleLine() che alloca una struttura dati
la quale contiene tutte le informazioni relative ad ogni statement: EXESTATEMENT_STAT;
lo schema esemplificativo è già apparso in [DEV/6 96], figura 6.
Se ha avuto successo l’allocazione che viene eseguita tramite una specifica funzione
alla quale è delegato anche il compito di inizializzare tutte le variabili della struct,
viene richiamata la funzione makeSingleLine_Arguments();
essa scorre in successione tutti i token iniziando da quello che riceve come parametro,
allocando per ognuno di essi una struttura EXESTATEMENT_TOKEN
nella quale vengono memorizzati i dati del token e contemporaneamente creando ed aggiornando la linked list
che viene poi agganciata a EXESTATEMENT_STAT.
L’ultimo compito della funzione parse() consiste, al termine dell’elaborazione di ogni nuovo statement,
nel legare alla linked list la nuova istruzione.
Siccome non viene eseguita l’analisi sintattica che viene demandata alla fase di run time,
la classe UserLan gParser finisce il suo lavoro:
la costruzione dei salti da statement a statement viene fatta dalla funzione jumpBuilder()
che è una funzione membro del la classe ULCompiler.
i salti e l’istruzione GOTO
Le istruzioni quali la IF impongono la gestione dei salti fra istruzioni:
infatti se la condizione della IF risulta essere falsa,
allora il flow del programma deve riprendere dopo la corrispondente ENDIF.
Uno schema grafico rappresentante i vari salti che devono essere eseguiti è stato pubblicato come figura 7
in [DEV6/96].
Vediamo ora come si implementa la funzione che realizza il concatenamento degli statement.
In linea di principio gli statement vengono eseguiti in modo sequenziale, dal primo all’ultimo,
quindi una linked list semplice consente di legarli opportunamente. Gli statement che modificano il flow sono:
- i salti incondizionati
- i salti condizionati
- i cicli
I salti incondizionati sono quelli identificati dall’istruzione GOTO.
Per implementare la loro gestione nell’interprete è sufficiente costruire una tabella
all’interno della quale vengono inseriti tutti gli indirizzi dei token contenenti le label.
Essa può essere realizzata sia come array che come linked list e sarà costruita e distrutta
durante l’esecuzione della funzione che si occupa della creazione dei salti,
ovvero la funzione jumpBuilder(). Infatti, ai fini dell’esecuzione del programma,
questa tabella è inutile in quanto la linked list degli statement avrà già memorizzato
gli in dirizzi dei vari salti nelle variabili jump True e jumpFalse della struct EXESTATEMENT_STAT.
Per semplicità organizzativa, l’interprete dovrebbe eseguire una prima ricognizione degli statement
per ricercare tutte le label e memorizzarle nella tabella,
poi eseguire l’elaborazione per la connessione dei puntatori per i salti ai vari token.
Questo sistema evita di dover gestire le situazioni in cui nel programma compaia il GOTO prima della rispettiva label.
Altro metodo per la realizzazione di questo tipo di salti
è quello impiegato nei primi Basic i quali utilizzavano l’indirizzamento mediante il numero di linea:
a run time, quando si incontrava un GOTO veniva ricercata l’istruzione identificata dal numero di linea specificato
e si riprendeva l’esecuzione da essa.
Nel caso invece non esistesse nessuno statement a cui saltare,
l’esecuzione veniva interrotta segnalando un errore all’utente.
I salti condizionati ed i cicli vengono gestiti in maniera completamente differente.
Essi non hanno nessuna necessità di costruire delle tabelle di riferimento
ove memorizzare i vari indirizzi in quanto il problema si risolve brillantemente
ricorrendo ad una semplice analisi ricorsiva.
Partiamo analizzando i cicli.
Un ciclo ha un punto di inizio ed uno di fine ed uno di essi contiene una condizione che determina il salto.
Se la condizione appare all’inizio come nel caso del loop WHILE WEND,
allora il token che contiene l’istruzione WHILE avrà il puntatore jumpTrue
che indirizzerà all’istruzione successiva mentre jumpFalse indirizzerà all’istruzione che segue la WEND.
Quest’ultima con terrà l’indirizzo della WHILE in jumpTrue in quanto il flow deve riprendere dall’istruzione WHILE.
Se invece il ciclo ha la condizione espressa nel token finale come nel caso della DO WHILE.
allora lo statement DO non influenzerà minimamente il flow e si comporterà alla stregua di una label,
mentre tutto sarà a carico della WHILE: essa avrà il puntatore jumpTrue
che punterà all’istruzione DO oppure a quella immediatamente successiva,
mentre jumpFalse punterà a quella seguente il WHILE.
Di relativa facilità risulta l’implementazione di istruzioni
quali il LOOP che genera un’interruzione del flow per far lo riprendere dalla prima istruzione delciclo,
ed il BREAK che invece causa un’uscita da esso.
Infatti lo statement LOOP non deve far altro che avere la variabile jumpTrue puntante al token con cui inizia il loop,
mentre BREAK avrà la medesima variabile che punterà allo statement successivo a quello con cui termina il loop.
Vediamo ora una semplice ma concreta spiegazione di come si realizza una funzione che genera gli indirizzi
per le variabili jumpTrue e jumpFalse.
Il loop principale ha nome jumpBuilder2():
esso scorre tutta la linked list contenente gli statement (EXESTATEMENT_STAT)
ricercando quelli che possono modificare il flow del programma, eseguendo le relative operazioni
mediante uno switch/ case. Esse sono concettualmente semplici:
viene rilanciata la ricorsione di jumpBuilder2() affinché possano essere gestiti i cicli nidificati;
ogni ricorsione di questa funzione ha termine quando essa incontra
uno statement uguale al tipo che ha ricevuto come parametro dalla funzione chiamante.
Per esempio, se la funzione incontra lo statement WHILE
lancia in ricorsione se stessa specificando che lo statement che deve determinare l’interruzione del loop è il WEND.
Se durante la scansione degli statement incontra una IF,
allora viene avviata un’ altra ricorsione che avrà termine con lo statement ELSE oppure ENDIF.
Approfondiamo ulteriormente l’argomento.
Abbiamo detto che jumpBuilder2() lancia una ricorsione ogni volta che vengono trovati degli statement
che alterino il flow del programma e che essi sono gestiti mediante il costrutto switch/ case,
ma osservando il programma in C++ di questa funzione si nota che WEND, ELSE ed ENDIF
appaiono solo per segnalare un errore. Il motivo è semplice:
siccome la sintassi del linguaggio Basic non ammette dei loop che si intersechino fra loro,
ovvero non nidificati, ne consegue che un ciclo può iniziare solo con il WHILE oppure con la IF,
perciò la presenza degli altri implica necessariamente una situazione di errore.
Un approfondimento particola re si rende necessario per la IF/ ENDIF.
Quando viene eseguita una ricorsione perché la funzione incontra lo statement IF,
è indispensabile informare quest’ultima che le istruzioni che determineranno l’uscita dal ciclo possono essere due: la ELSE e la ENDIF.
Se si incontra quest’ultima non si deve far altro che trattarla come una WEND o un’altra istruzione di fine loop,
mentre se è la ELSE bisogna svolgere un ulteriore lavoro, ovvero lanciare una nuova ricorsione che terminerà con la ENDIF.
Per evitare di dover conoscere quali parametri abbisogni questa funzione,
è stata implementata una funzione di nome jumpBuilder(): essa richiede esclusivamente l’indirizzo del primo statement e null’altro.
Questa nuova funzione, oltre ad essere di immediata comprensione,
consente di creare dei controlli sullo svolgimento della precedente funzione e di effettuare automaticamente segnalazioni all’utente.
A completamento dell’argomento dei salti è bene specificare
che queste due funzioni sono membro della classe UserLangfumpBuilder
e che essa si trova me morizzata nel file Uljumpb.cpp.
Uno sguardo indiscreto alle linked list
Al termine del suo compito, lo scanner ha generato una linked list di tutti i token che ha trovato. In essa possiamo trovare alcuni token aggiuntivi che segnalano la fine degli statement (TOKEN_ENDSTATEMENT).
Per poter ispezionare questa struttura dati, la classe UserLangToken mette a disposizione la funzione tokenDump() che provvede a visualizzare ogni singolo token organizzato nei vari statement; inoltre, essa costituisce uno strumento più comodo dei normali ispettori di oggetti messi a disposizione dei vari compilatori C++.
La funzione scan() della classe UserLang Scanner contiene un esempio di come richiamarla: è sufficiente eliminare i caratteri di commento che si trovano all’inizio della linea.
Partendo dalla linked list generata dallo scanner, il parser ne crea un’ altra contenente tutti gli statement dalla quale partono altre linked list all’intemo delle quali trovano posto i vari parametri dei singoli statement.
Per poter eseguire una visualizzazione di questa struttura dati alquanto compressa viene fornita la funzione printProgram() appartenente alla classe UserLangParser; esattamente come nel caso precedente, un esempio d’uso è contenuto nella funzione scan() di quest’ultima classe nella quale appare sotto forma di commento.
Queste due funzioni sono utili sia in fase di debugging nel caso apportiate modi fiche all’interprete, sia per meglio comprenderne il funzionamento. Esse andrebbero eliminate dalla versione definitiva del programma affinché non occupassero spazio inutile.
Perché tante classi?
Probabilmente appare eccessivo lo sviluppo di tante piccole classi dedicate a compiti specifici e limitati.
Una prima risposta risiede nella logica della programmazione ad oggetti
che predilige una folta ma ragionata schiera di classi che,
in forza della specificità e limitatezza delle operazioni che generalmente svolgono,
possano essere riutilizzate all’interno di altri programmi.
Un altro motivo consisteva nel fatto che l’interprete doveva poter essere messo in esecuzione
su macchine che disponessero anche di memoria limitata
simulando inoltre la funzionalità di multitasking,
perciò il risparmio anche di solo qualche KByte risultava importante.
Oramai quest’ultima caratteristica non riveste più alcuna importanza pratica,
per cui quella parte di programma demandata a svolgere tale compito è stata stralciata
per maggiore leggibilità, ma, nel caso fosse di vostro interesse implementare tale funzionalità, potete contattarmi.
Conclusioni
Abbiamo affrontato le varie classi che compongono e gestiscono la fase di scanning e quella di parsing.
La prima di esse è relativamente semplice da creare in quanto deve leggere un file
e creare una struttura dati contenente i vari token che estrae ed identifica.
La seconda fase può essere più o meno complessa in relazione alle caratteristiche che l’interprete deve avere:
ad esempio l’analisi sintattica delle istruzioni è spessissimo eseguita da questa funzione.
Purtroppo questa operazione è marcatamente più complicata di quanto non possa apparire a prima vista;
inoltre questo piccolo interprete vuole essere semplicemente una concreta e funzionale base di partenza
per con sentirvi di svilupparlo secondo le vostre necessità
senza quindi la pretesa di esse re un prodotto da utilizzarsi a scatola chiusa,
questo anche con grande gioia di molti studenti universitari alle prese con l’esame di programmazione.
Ora che abbiamo descritto tutte le fasi preliminari all’esecuzione del programma,
non rimane che analizzare ciò che accade a run time.
Come sempre, qualora abbiate commenti, suggerimenti o critiche costruttive non esitate a contattarmi
via email o BBS i cui riferimenti sono riportati in calce all’articolo o al sommario.
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.