Interprete pseudo-assembler
Da Tesine Linguaggi e Traduttori.
Contents |
Introduzione
L’interprete pseudo-Assembler svolge il ruolo di una macchina virtuale che si occupa di compiere l’analisi lessicale e sintattica di un codice scritto appunto in pseudo-Assembler che si suppone essere stato generato da un compilatore e non scritto da un umano. Questo implica che non vi sia teoricamente la possibilità di errori all’interno del codice sorgente, se non attribuibili ad un errore di implementazione del compilatore a livello superiore. Per questo motivo viene effettuato un ridottissimo controllo sugli errori nel corso dell’interpretazione, e prevalentemente utilizzato per la fase di debug.
Lo scopo della VM, in quanto tale, non è sicuramente quella di massimizzare le prestazioni,visto che esegue delle istruzioni in pseudo-Assembler trasformandole in codice C che viene successivamente eseguito simulando il comportamento dell’istruzione interpretata.
Funzionamento generale
Le istruzioni del linguaggio pseudo-Assembler sono composte da comandi, variabili e valori immediati. La struttura dati che permette di tenere traccia delle variabili e dei valori che assumono durante l’esecuzione del programma è la symbol table.
Ogni istruzione interpretata dalla VM comporta l’aggiornamento della symbol table (a seguito della lettura dei parametri dell’istruzione) e segue un processo di esecuzione dipendente dallo stato corrente del programma.
Il flusso d’esecuzione nel momento in cui il parser incomincia la sua analisi è il seguente:
- qualsiasi comando incontrato diverso da un’etichetta o da un comando di JMP viene salvato nella BD solo se il flag prima_etichetta di BD è vero e viene eseguito solo se il flag ESECUZIONE di BD è vero.
- il trattamento di riduzione di un comando di tipo JMP è lo stesso di un comando normale, cioè il comando viene salvato nella BD solo se il flag prima_etichetta di BD è vero e viene eseguito solo se il flag ESECUZIONE di BD è vero. La differenza consiste nel codice della funzione: se l’etichetta di destinazione è presente nella symbol table, allora si fa partire l’esecuzione dall’istruzione corrispondente nella BD (con la chiamata alla funzione execution). Altrimenti il flag ESECUZIONE di BD viene posto a false e la variabile etichetta_attesa di BD viene posta al valore dell’etichetta incontrata.
- Quando si incontra un’etichetta, questa viene inserita nella symbol table. Se l’etichetta è uguale alla variabile etichetta_attesa di BD e il flag ESECUZIONE di BD è falso, allora si fa partire l’esecuzione da quel punto. Altrimenti ci si comporta come per un comando normale.
La funzione execution ha come compito l’esecuzione dei comandi che sono presenti nella BD. Termina solamente quando bisogna eseguire un comando che non è presente nella BD: in questo caso si procede con il parsing finché non si incontra il comando atteso.
Compilazione e avvio
flex scanner.flex
bison -d parser.y
gcc -o <execFile> *.c
cat <inputFile> | <execFile>
-
<execFile>è il nome da assegnare al file eseguibile risultante dalla compilazione dei file .c -
<inputFile>è il file contentente il codice in pseudo-Assembler
Per eseguire il programma è necessario utilizzare la shell di un sistema Unix che abbia Flex, Bison e Gcc installati oppure Cygwin in ambiente MS Windows, durante la cui installazione si sia deciso di aggiungere Flex, Bison e Gcc.
La stampa delle informazioni di debug è opzionale e viene gestita con i flag definiti all'interno del file parser.y
#define DEBUG1 //"Macro"operazioni come inizializzazioni di strutture dati #define DEBUG2 //Verifica dell'inserimento/presenza nella symbol table #define DEBUG_VETTORI #define DEBUG3 //Segnala le operazioni di riduzione #define DEBUG4 //Segnala la riduzione di comandi #define DEBUG5 //Segnala esecuzioni di comandi #define DEBUG_SALTI #define DEBUG_EXEC
Inoltre il flag per la stampa degli errori di parsing è definito all'interno del file funzioni.h
#define PRINT_ERROR
Analisi lessicale e sintattica
Analisi lessicale
L'analisi lessicale viene svolta dallo scanner, implementato da scanner.flex. Di seguito è riportato lo scheletro di scanner.flex, cioè le regole per riconoscere i token. Ciascuna regola è composta da un'espressione regolare e da un blocco di codice C tra parentesi graffe. Il codice viene eseguito ogni volta che viene incontrato quanto specificato dall'espressione regolare.
Per passare i token riconosciuti al parser del linguaggio, si utilizza l'istruzione C return seguita dal nome del token che si vuole passare.
Analisi sintattica
L'analisi sintattica viene effettuata dal parser su una sequenza di token proveniente dall'analizzatore lessicale. Parser.y è l'implementazione del parser utilizzando Bison.
Una grammatica espressa con Bison ha 4 principali sezioni:
%{
Prologo
%}
Dichiarazioni
%%
Regole della grammatica
%%
Epilogo
La prima parte delle dichiarazioni in parser.y definisce i simboli della grammatica e i valori semantici ad essi associati. Possiamo notare in parser.y che i simboli sono suddivisi in due gruppi: i simboli introdotti da %token sono simboli terminali e provengono dallo scanner. Quelli introdotti da %type sono simboli non terminali. La parte contenente le regole della grammatica è il cuore del programma. Ad ogni regola può corrispondere un blocco di codice C tra parentesi graffe. Il codice viene eseguito ogni volta che si effettua la riduzione corrispondente ad esso.
Azioni semantiche
Lo scopo del programma è l'interpretazione e l'esecuzione di codice pseudo-Assembler.
Per eseguire il codice in pseudo-Assembler è necessario definire delle strutture dati che permettano di rappresentare e memorizzare gli elementi del codice (come istruzioni, variabili...). Inoltre devono essere definite delle funzioni che implementino i comandi descritti del codice pseudo-Assembler.
Strutture dati
La memorizzazione degli elementi del codice pseudo-Assembler avviene per mezzo di due principali strutture dati:
- la symbol table, definita e descritta all’interno di Definitions
- la base dati, definita e descritta all’interno di Bd_istruzioni.
Symbol table
typedef void (*operand)(struct RECORD_SYM_TABLE *, struct RECORD_SYM_TABLE *);
typedef enum {TYPE_INT, TYPE_FLOAT, TYPE_CHAR, TYPE_PNT, TYPE_OPERAND, UNKNOWN, LABEL} SYM_TYPE;
typedef union V_ELEM{
int label;
int val_int;
float val_float;
char val_char;
struct STRUCT_PNT val_pnt;
operand val_operand;
}V_ELEM;
typedef struct RECORD_SYM_TABLE{
char *symbol_name;
SYM_TYPE sym_type;
V_ELEM var_value;
} RECORD_SYM_TABLE;
typedef struct STRUCT_PNT{
SYM_TYPE pointed_type;
void * pnt;
struct RECORD_SYM_TABLE *index1;
struct RECORD_SYM_TABLE *index2;
}STRUCT_PNT;
Il file Definitions.h descrive la struttura di un record all’interno della symbol table. Ognuno di questi contiene il nome del simbolo, il suo tipo e il suo valore. Per la descrizione del tipo si usa una enum (SYM_TYPE) che permette di associare al simbolo un tipo tra TYPE_INT, TYPE_FLOAT, TYPE_CHAR, TYPE_PNT, TYPE_OPERAND, UNKNOWN, LABEL. Per la descrizione del valore si usa una union (V_ELEM) che permette di assegnare al simbolo un valore a seconda del tipo associato: label, intero, floating point, carattere, puntatore o puntatore a funzione (operand).
Nel caso in cui questo rappresenti un puntatore viene utilizzato come tipo associato alla union la struttura STRUCT_PNT.
Base dati
typedef struct{
int prima_etichetta;
char *etichetta_attesa;
int size;
BD_comando** bd;
int pos;
int next_execution;
} BD;
Il file Bd_istruzioni.h descrive le strutture e le funzioni associate alla gestione della base dati che contiene le istruzioni già eseguite (o comunque visitate) dalla macchina virtuale. La struttura BD contiene informazioni sullo stato dell’esecuzione (é già stata incontrata un’etichetta, l’esecuzione è bloccata in attesa dell’etichetta, l’etichetta che ci si attende di incontrare ecc…) e il vettore di strutture BD_comando, che rappresenta l’effettiva struttura dati in cui vengono memorizzate le istruzioni visitate. Un appunto particolare va fatto sul campo prima_etichetta: è inutile memorizzare all’interno della base dati un’istruzione che, non essendo ancora stata trovata un’etichetta a cui poter saltare, non verrà mai più eseguita.
typedef struct b{
operand operation;
struct RECORD_SYM_TABLE *p1;
struct RECORD_SYM_TABLE *p2;
struct RECORD_SYM_TABLE *i1;
struct RECORD_SYM_TABLE *i2;
} BD_comando;
La struttura BD_comando contiene il puntatore a funzione relativo all’istruzione e i suoi parametri (p1,p2) oltre agli eventuali indici di offset (i1, i2). Questi sono puntatori a record della symbol table.
Struttura del main
int main(){
sym_table=init_symbol_table();
bd_init(&bd_program, 30);
yyparse();
stampa_bd(&bd_program);
}
All’interno del main vengono richiamate le quattro funzioni chiave del programma:
- init_symbol_table() permette la creazione e l’inizializzazione della symbol table;
- bd_init(...) permetta la creazione l’inizializzazione della base dati per le istruzioni;
- yyparse() avvia il lavoro di parsing del file in pseudo-Assembler, eseguendo le azioni di semantica associate ad ogni istruzione.
- stampa_bd(...) si occupa di stampare gli elementi contenuti all’interno della base dati.
Funzioni
Il compito dei file funzioni.h e funzioni.c è quello di definire e implementare il comportamento assunto dalle funzioni associate ad ognuna delle istruzioni in pseudo-Assembler presenti nel programma in esecuzione. Ognuna di queste funzioni riceve in ingresso due parametri di tipo RECORD_SYM_TABLE, dovendo rispondere alla definizione del puntatore a funzione operand, con cui queste funzioni vengono richiamate.
Le funzioni contengono al loro interno la riproduzione in linguaggio C del modo di agire proprio delle corri-spondenti istruzioni pseudo-Assembler, richiamando i simboli che gli vengono passati come parametri dalla symbol table.
