XMLCompiler
designed by Michele Schirinzi
Indice
Introduzione..........................................................................................................................................1
Caratteristiche del linguaggio...............................................................................................................1
Definizione di nuovi tipi..................................................................................................................2
Dichiarazione di variabili globali.....................................................................................................2
Dichiarazione di funzioni.................................................................................................................2
Grammatica..........................................................................................................................................3
Fasi del compilatore..............................................................................................................................7
Analisi lessicale...............................................................................................................................7
Analisi sintattica e semantica...........................................................................................................8
Generazione codice intermedio.......................................................................................................9
Utilizzo di XMLCompiler....................................................................................................................9
Struttura pacchetto................................................................................................................................9
Introduzione
XMLCompiler è un front­end compiler che genera codice intermedio “mips”. Questo è stato realizzato come progetto per il corso di linguaggi di programmazioni per l'anno 2005/06. Il linguaggio che prende in input il compilatore, come si può intuire dal nome del compilatore, è XML. Questa scelta è stata fatta per poter sfruttare la moltitudine di editor già esistenti per XML.
Il compilatore utilizza un metodo a due passate, durante la prima passata viene controllato lessicalmente il file sorgente, viene effettuata l'analisi sintattica e semantica e viene costruito l'albero astratto; durante la seconda passata, viene generato il codice intermedio. Il compilatore permette anche di creare alcuni documenti HTML(risultati molto utili durante la fase di debug) che illustrano il funzionamento del compilatore. In particolare, permette di creare un documento HTML che rappresenta l'albero astratto del programma sorgente passato in input(facile da interpretare e 'navigare' grazie all'utilizzo di javascript e CSS), e un documento che elenca i nuovi tipi definiti nel programma sorgente.
Caratteristiche del linguaggio
Schematicamente, un programma scritto nel nostro linguaggio è definito da tre parti principali:
1. Definizione di nuovi tipi
2. Dichiarazione di variabili globali
3. Dichiarazione di funzioni
Una spiegazione più approfondita su ogni parte viene fornita nelle sezioni successive. Il linguaggio realizzato è case­sensitive; descriviamo di seguito i costrutti base che vengono messi a disposizione:
1. Comando condizionale (<If cond=” exp”><Then>...</Then><Else>...</Else></If>)
2. Comando iterativo (<While cond=” exp ”>....</While>)
3. Assegnamento (a = exp;)
4. Comandi input/output (Read(var); Write(exp))
5. Espressioni
6. Chiamata di funzioni
Definizione di nuovi tipi
Il linguaggio dispone di 3 tipi di dato base:
1. Intero
2. Carattere
3. Booleano
A partire da questi tipi base si possono costruire tipi composti attraverso il costruttore Array e il costruttore <Type>...</Type>.
1. Array[x] of type : Permette di costruire un array di elementi di tipo 'type', dove tipo può essere anche un tipo definito precedentemente dall'utente.
2. <Type name=”ID”>...</Type> : Permette di definire il tipo ID, come composizioni di altri tipi definiti in precedenza.
Quindi non esistono limiti per la creazione di nuovi tipi, si possono creare tipi molto complessi. L'unico vincolo, è che un tipo si può costruire solo come composizione di tipi definiti precedentemente, quindi non è permessa la definizione di tipi ricorsivi.
Es.
<Type name=”pippo”>
a: Int;
b: Char;
</Type>
<Type name=”pluto”>
vettore : Array[20] of pippo; record : pippo; </Type>
<Type name=”topolino”>
vettore: Array[12] of pluto;
record : pippo;
</Type>
Dichiarazione di variabili globali
In questa sezione si dichiarano le variabili accessibili in tutto il programma, cioè in qualsiasi funzione. Si possono dichiarare variabili di tipi base o di tipi definiti dall'utente. Il “tag” che racchiude questa parte è <Declaration>..</Declaration>.
Dichiarazione di funzioni
Una funzione può richiamare una funzione definita precedentemente, o di cui ne è stato definito solo il prototipo. La funzione 'main' deve essere necessariamente definita ed è quella che rappresenta il punto di ingresso al programma. La sintassi per definire una funzione è <Function name=”ID” return=”type”>...</Function>, che significa che sto definendo la funzione 'ID', che ha come tipo di ritorno 'type'. Per definire il prototipo di una funzione si usa la sintassi <_Function name=”ID” return=”type”>...</_Function>, e quindi successivamente nel codice si dovrà definire la funzione corrispondente. La definizione di una funzione si divide in tre parti:
1. Definizione dei parametri; (<Parameter>....</Parameter>)
2. Dichiarazione di variabili locali; (<Declaration>...</Declaration>)
3. Corpo della funzione; (<Body>...</Body>)
Il passaggio di parametri di tipo semplice avviene per valore, quello dei parametri di tipo complesso avviene per variabile. Le funzioni possono ritornare solo valori di tipo semplice(Bool,Char,Int), o eventualmente niente( 'Void').
Grammatica
Le parti in grassetto indicano i simboli terminali; nella grammatica sono inseriti dei simboli non terminali che vengono utilizzati durante il parsing per compiere particolari azioni semantiche. Es. start_env, viene usato per dire alla symbol_table che siamo in un nuovo ambiente
check_campi, viene usato per controllare la correttezza della definizione dei campi di un record.
program ­> <Program name="ID"> def_type_list decla_list def_func_list </Program>
def_type_list ­> ε
| <Type name="def_id_type"> def_field_list </Type> def_type_list
def_id_type ­> ID
def_field_list ­> ε
| id_list : tipo; check_campi def_field_list
check_campi ­> ε
decla_list ­> ε
| <Declaration> decla_var </Declaration>
start_env ­> ε
end_env ­> ε
decla_var ­> ε
| id_list : tipo ; check_lista
decla_var
check_lista ­> ε
id_list ­> ID , id_list
| ID
tipo ­> simple_type
| ID
| Array[ NUM ] of array_element_type
array_element_type ­> simple_type
| ID
simple_type ­> Int
| Char
| Bool
def_func_list ­> ε
| <Function name=" def_id_func " return=" return_type "> start_env def_param_list decla_list <Body> complex_command </Body> end_env </Function> check_funzione def_func_list
| <_Function name=" def_id_proto " return=" return_type "> start_env def_param_list end_env </_Function>
def_func_list
check_funzione ­> ε
def_id_func ­> ID
def_id_proto ­> ID
return_type ­> simple_type
| Void
def_param_list ­> ε
| <Parameter> def_param </Parameter>
def_param ­> ε
| ID : tipo ;
def_param
complex_command ­> ε
| command complex_command
command ­> variabile = exp ;
| <If cond=" exp "> <Then> complex_command </Then>
</If>
| <If cond=" exp "> <Then> complex_command </Then>
<Else> complex_command </Else>
</If>
| <While cond=" exp "> complex_command </While>
| chiamata_funzione ;
| Read( variabile );
| Read( variabile , exp );
| Write( exp );
| Return( exp );
variabile ­> ID dot_list
| ID [ exp ] dot_list
dot_list ­> ε
| . ID dot_list
| . ID [ exp ] dot_list
chiamata_funzione ­> ID ( lista_parametri )
lista_parametri ­> ε
| exp
| exp , lista_parametri
exp ­> simple_exp
| simple_exp minor simple_exp
| simple_exp major simple_exp
| simple_exp egual simple_exp
| simple_exp disegual simple_exp
simple_exp ­> termine
| + termine
| ­ termine
| simple_exp + termine
| simple_exp ­ termine
| simple_exp or termine
termine ­> fattore
| termine * fattore
| termine / fattore
| termine and fattore
fattore ­> variabile
| chiamata_funzione
| Not fattore
| ( exp )
| NUM
| CHAR
| STR
| BOOL
ID ­> [a­zA­Z] ([a­zA­Z]|[0­9])*
NUM ­> [0­9]+
CAR ­> '.' STR ­> '.*'
BOOL ­> TRUE
| FALSE
Fasi del compilatore
Il compilatore rispecchia la struttura standard sequenziale dei compilatori, esso infatti è strutturato in 4 moduli principali, connessi tra loro secondo uno schema sequenziale (anche se sono state previste sovrapposizione per aumentare l’ efficienza del compilatore, in particolare l'analisi sintattica e semantica vengono effettuate contemporaneamente): l’analizzatore lessicale, l’analizzatore sintattico­semantico e il generatore di codice. Descriviamo in breve i compiti principali di tali moduli, e come essi collaborano tra loro.
Il programma dato in input al compilatore viene innanzitutto letto dall’analizzatore lessicale che ha il compito di dividere l’intero testo in token lessicali, secondo determinate regole esplicitate con espressioni regolari. L’elenco dei token viene quindi passato all’analizzatore sintattico che ha il compito di riconoscere tutte le parti che compongono il programma e di creare il corrispondente albero sintattico, in questa fase facciamo anche il controllo sulla correttezza semantica del programma, cioè il name­checking e il type­checking. L’albero sintattico creato dall’analizzatore sintattico viene passato all’ultimo modulo del compilatore che si occupa della generazione del codice intermedio, nel nostro caso l' assembler “mips”.
Analisi lessicale
Questa fase serve per controllare che il programma sia lessicalmente corretto. Per realizzare l'analizzatore lessicale abbiamo usato FLEX. In questa fase, oltre ad associare alle stringhe i token, eliminiamo la parte di testo relativa ai commenti. Il riconoscimento avviene attraverso espressioni regolari, vedere il file “/fbi/lexical.f”.
Analisi sintattica e semantica
In questa fase controlliamo che il programma sia sintatticamente corretto, utilizzando l'analizzatore sintattico generato con BISON. Nelle azioni semantiche del parser viene effettuata l'analisi semantica e la costruzione dell'albero astratto. Nel caso si verifichi un errore sintattico, viene interrotto il parsing e viene segnalata la riga in cui è stato riscontrato il problema, invece se viene rilevato un errore semantico si continua con il parsing segnalando solo l'errore.
I controlli semantici effettuati sono di due tipi:
1. Controllo sui nomi
2. Controllo sui tipi
Il controllo sui nomi viene effettuato utilizzando una “symbol table” implementata nello stesso modo in cui è stata presentata durante il corso, cioè utilizzando una funzione hash per consentire accessi efficienti, un array di strutture per contenere i simboli incontrati e una pila che gestisce l'annidamento degli ambienti(SymbolTable.c). Ogni volta che troviamo una dichiarazione, inseriamo l'ID relativo nella symbol­table, controllando che nello stesso ambiente non ci siano dichiarazioni duplicate. Nel nostro linguaggio abbiamo un ambiente statico senza annidamento di funzioni, cioè una definizione di funzione non può essere annidata in un'altra. Quindi nell'ambiente globale possiamo trovare dichiarazioni di prototipi, funzioni e variabili globali, mentre nell'ambiente locale alla funzione, troviamo solo la dichiarazione dei parametri e delle variabili locali alla funzione. L'unica particolarità è nella dichiarazione di prototipi di funzione, in quanto questi vengono inseriti nella “symbol table” con l'ID: “_” seguito dal nome della funzione; questo ci permette di controllare successivamente che la definizione della funzione relativa sia coerente al prototipo dichiarato.
Il controllo sui tipi viene effettuato associando ad ogni tipo un valore intero pari. Se vengono definiti nuovi tipi, anche a questi viene associato un numero pari a partire da 10(Es, 10,12,14). Ai tipi base sono associati i seguenti valori:
●
Carattere = 2
●
Intero = 4
●
Booleano = 6
Un array di valori di un certo tipo è codificato con il codice del tipo + 1; Quindi se il codice di un tipo è dispari, allora stiamo parlando di un array di elementi di tipo codice­1; Es. 5 = Array di Interi , 3 = Array di Caratteri , 17 = array di elementi di nuovo tipo 16;
Il tipo funzione viene codificato con il codice 0, e con una lista di codici di tipo, dove l'elemento in testa rappresenta il tipo di ritorno della funzione, e gli elementi successivi, il tipo dei parametri che la funzione prende in input. Questo ci permette di controllare ad ogni chiamata, che la funzione sia richiamata con i parametri giusti e che il suo valore di ritorno sia coerente con il contesto in cui viene richiamata. Le operazioni definite sui tipi sono le seguenti:
●
Intero : + , ­ , / , * , major , minor , equal , disegual
●
Carettere : egual , disegual , major , minor
●
Booleano : or , and , not
Se nelle espressioni viene effettuata un'operazione diversa da quella permessa per i tipi corrispondenti, viene rilevato un errore. Il tipo delle espressioni all'interno dei costrutti condizionali(<If><While>) deve essere booleano. Mentre per la Read(var), il tipo della variabile può essere solo un tipo base, con la variante per la Read(var,exp), dove il tipo di “var” deve essere un array di caratteri e il tipo di “exp” un intero. La Write accetta i tipi base e il tipo array di caratteri, infine la parte sinistra e destra di un assegnamento devono essere dello stesso tipo.
In questa fase, viene anche calcolato, se possibile, il valore di espressioni o sottoespressioni. e rivelato eventualmente l'errore di “divisione per zero”. Inoltre vengono rilevati due tipi di warning:
1. Se la funzione dichiarata ritorna in ogni caso un valore costante;
2. Se la funzione ritorna un valore che non viene assegnato a nessuna variabile;
Generazione codice intermedio
In questa fase viene visitato l'albero astratto e generato il relativo codice. Le variabili globali vengono codificate attraverso delle etichette formate dal loro nome preceduto dalla stringa “__”, questo per non creare collisione con eventuali nome di funzione. Le variabili locali e i parametri delle funzioni vengono codificate attraverso l' offset sullo stack a partire dal valore del registro $sp.I dati statici come per esempio le stringhe di una Write(), vengono allocati staticamente in memoria. Per generare il codice dei costrutti condizionali viene usato il metodo delle etichette.
Utilizzo di XMLCompiler
./xmlcompile [opzioni] nomefile
Le opzioni possibili sono:
●
“­vtree” : genera un documento HTML contenente l'albero astratto del sorgente.
●
“­vtype” : genera un documento HTML contenente l'elenco dei nuovi tipi definiti
●
“­vcode” : Commenta il codice intermedio
I documenti HTML cercano i fogli di stile CSS nella cartella “./sty/”, quindi per visualizzarli correttamente bisogna aprirli un livello sopra questa cartella.
Es.
AbstractTree.html
NewTypeTable.html
sty/style.css
Struttura pacchetto
Il pacchetto XMLCompiler comprende:
● ./doc : Contiene la documentazione su XMLCompiler;
● ./example : Contiene numerosi esempi di programmi scritti per XMLCompiler;
● ./fbi : Contiene il file sorgente di FLEX(lexical.f) e il file sorgente di BISON(syntax.y);
● ./src : Contiene i sorgenti di XMLCompiler;
● ./sty : Contiene il foglio di stile utile per la visualizzazione dei documenti HTML informativi;
●
●
./obj : Directory in cui vengono collocati temporaneamente i file oggetto durante la compilazione.
xmlcompile : Eseguibile del compilatore
Per compilare il pacchetto sono necessari:
● flex
● bison
● gcc >= 3.3.5