/JPocl

Compiler developed using ANTLR 3, String Template and Jasmin.

Primary LanguageJava

#JPocl - J(Piece of cake language)

###Introduzione

JPocl è un compilatore sviluppato a scopo didattico come progetto finale del corso di IPL, tenuto per l'anno accademico 2013/2014 dai professori Davide Ancona e Giovanni Lagorio. Obiettivo del progetto è lo sviluppo di un compilatore, che possa generare codice eseguibile sulla Java Virtual Machine.

###Sviluppo Per lo sviluppo di JPocl sono stati utilizzati diversi strumenti:

Durante lo sviluppo del progetto è stata sfruttata ampiamente la tecnica del TDD; oltre al codice strettamente necessario al compilatore è presente un package test, utile sia per la verifica delle funzionalità che come ulteriore documentazione dell'intero sistema.

##Il linguaggio NB: tutte le espressioni di JPocl devono essere seguite dal carattere "NewLine".

###Tipi di dato In JPocl sono presenti tre tipi di dato predefiniti, int, bool e void. E' inoltre possibile definire i propri tipi strutturati.

struct data{int giorno; int mese; int anno;}
struct progetto{int giorniSpesi; bool agile; struct data inizio;}
p = struct progetto{10, true, struct data{1,7,2013}}

Sono presenti i principali operatori aritmetici e logici, ed anche operatori più complessi come il fattoriale e l'elevamento a potenza. JPocl non prevede l'esplicita dichiarazione delle variabili, ma inferisce il tipo al primo assegnamento, vincolandone gli usi seguenti.

a = 1+2
a = a+3
a = (a == 6) -> int and bool are incompatible @[3,2]

Data un'istanza di tipo strutturato, è possibile accedere ai campi utilizzando l'operatore ".".

b = struct data{12,07,2013}.giorno
c = struct progetto{10, true, struct data{1,7,2013}}
c.inizio.giorno = b

###Funzioni JPocl è fornito di una piccola libreria, composta dalle funzioni:

  • int min(int a, int b)
  • int max(int a, int b)
  • void runScript() (La funzione runScript è il punto di accesso di ogni script JPocl, ed è definita dalle istruzioni contenute in essi)

La libreria, definita separatamente dalla grammatica di JPocl, evita che l'utente ridefinisca le funzioni elencate. Nota: potenzialmente l'utente può sfruttare in maniera ricorsiva la funzione runScript all'interno del proprio codice. (A proprio rischio e pericolo! :)) Oltre alle funzioni predefinite, l'utente può dichiararne di nuove. Le funzioni posso appartenere sia allo scope top-level, sia a scope interni; non è però possibile definire funzioni all'interno del corpo di altre.

struct data initData(int giorno, int mese, int anno){
	d = struct data{giorno, mese, anno}
	return d
}
echo initData(12,07,2013).mese -> 7

struct data meseProssimo(struct data oggi){
	meseProssimo = struct data{oggi.giorno, oggi.mese, oggi.anno}
	meseProssimo.mese = (meseProssimo.mese + 1) % 12
	return meseProssimo
}

oggi = struct data{31,12,2013}
echo meseProssimo(oggi) -> data[31,1,2013]
echo meseProssimo(meseProssimo(oggi)) -> data[31,2,2013]

In JPocl è disponibile esclusivamente la ricorsione semplice, non è quindi prevista la ricorsione mutua.

int mcd(int a, int b){
	r = a % b
	if(r == 0) return b
	return mcd(b,r)
}

echo mcd(256,512) -> 256

Vengono riconosciuti come errori:

  • la mancanza di espressioni return all'interno di una funzione con tipo di ritorno diverso da void;
  • l'uso di più espressioni return non condizionate;

###Espressioni

bool isPrime(int n){
	i = 2
	while(i<n){
		if (n%i==0) return false
		i = i + 1
	}
	return true
}
echo isPrime(37) -> true

d = struct data{31,12,2013}
p = struct progetto{10,true, d}
echo p -> progetto[10,true,data[31,12,2013]]

Oltre agli operatori e ai costrutti già mostrati, JPocl espone altre funzionalità:

  • le espressioni condizionali if e while (il simbolo {, se utilizzato, deve appartenere alla stessa riga del costrutto);
  • il comando echo per la stampa su terminale, utilizzabile sia per i tipi di dato primitivi che per le istanze di tipi strutturati;
  • l'operatore == effettua il confronto fra due espressioni delle stesso tipo (per i tipi strutturati, il risultato è dato dal confronto dei rispettivi campi).

###Type-Checking I messaggi di errore prodotti durante la fase di verifica statica del codice sorgente si presentano nella forma Messaggio @[linea, colonna].

I casi di errore gestiti sono i seguenti:

  • dichiarazione di funzioni con parametri duplicati;
  • dichiarazione di tipi strutturati con campi duplicati;
  • uso invalido di espressione di tipi void;
  • definizione di espressioni contenenti tipi incompatibili;
  • incompatibilità fra l'espressione return e il tipo di ritorno dichiarato nella funzione;
  • funzione non applicabile agli argomenti dati;
  • nuova dichiarazione di una funzione già presente nel codice;
  • nuova dichiarazione di un tipo strutturato già presente nel codice;
  • codice irraggiungibile;
  • assenza di espressioni return;
  • uso di tipo non dichiarato, o non visibile;
  • uso di funzione non dichiarata, o non visibile;
  • identificatore non dichiarato, o non visibile;

Per semplificare la definizione del type-checker, è stato scelto di anticipare alcuni controlli alla fase di parsing. In particolare, l'uso di espressioni return è limitato al corpo delle funzioni (sfruttando gli operatori semantici di ANTLR) e l'operatore "." è applicabile solo ad istanze di tipi strutturati o ad identificatori.

###Scoping Di seguito sono riportati alcuni esempi di scoping in JPocl.

a = 0
void f(bool a){
	echo a && false
}
echo a + 1

La variabile intera a, anche se dichiarata nello scope top-level, non è visibile all'interno di f(Z); non esiste quindi uno scope globale per le variabili.

struct data{int giorno; int mese; int anno;}
void f(){
	echo struct data{1,2,2013}
}

Le dichiarazioni di tipo, come per le funzioni, se dichiarate nello scope top-level, sono visibili in qualsiasi blocco.

{
	struct X{int x;}
}
{
	struct X{int x;}
}

Nonostante appartengano a due blocchi separati, non è possibile effettuare una seconda dichiarazione del tipo X. Anche per le dichiarazioni di funzioni si applica lo stesso criterio.

###Compilazione e generazione Per definire il lexer ed il parser, è stato sfruttato il codice prodotto durante i laboratori del corso. Sono state necessarie solo alcune correzioni, per semplificare maggiormente il codice. Anche il controllo statico non ha subito variazioni importanti. I file relativi alla grammatica e al controllo statico, sono rispettivamente "JPoclAST.g" e "JPoclTypedAST.g".

Il processo di compilazione si compie nelle seguenti fasi:

  • il lexer JPoclASTLexer analizza l'input e produce la sequenza di token;
  • il parser JPoclASTParser ottiene la sequenza di token e produce un AST di tipo TypeTree;
  • il type-checker JPoclTypedAST inferisce i tipi dei nodi ed effettua i controlli statici;
  • il generatore JPoclGenerator genera codice Jasmin, sfruttando lo String Template Group JPoclGenerator.stg;
  • l'output così prodotto viene suddiviso in diversi file ".j" e assemblato sfruttando la libreria "jasmin.jar";
  • i file ".class" prodotti da Jasmin vengono eseguiti.

Di seguito sono esposti i pattern di generazione di JPocl:

  • le classi prodotte dal generatore apparterranno al package "jpocl";
  • le dichiarazioni di tipi strutturati generano una classe jpocl.ID, con visibilità "public" se top-level, "default" altrimenti;
  • per ogni campo di struct è generato un attributo nella classe di appartenza, con visibilità pari a quella della classe;
  • per ogni classe sono definiti un costruttore, con i relativi parametri, ed i metodi "equals(Object)" e "toString";
  • viene creata una classe "jpocl.Api" contenente i metodi "main", "runScript" e le altre funzioni incluse nel linguaggio;
  • le espressioni presenti nel codice sorgente, ad eccezione delle dichiarazioni di tipi o funzioni, sono adeguatamente tradotte all'interno del metodo "jpocl/Api.runScript".

Frammento di codice JPocl:

struct TheAnswer{int answer;}
echo struct TheAnswer{42} -> TheAnswer[42]

Codice Jasmin generato:

.class public jpocl/Api
.super java/lang/Object

.method public static main([Ljava/lang/String;)V
  .limit stack 0
  .limit locals 1
  
  invokestatic jpocl/Api.runScript()V  
 	return

.end method

.method public static runScript()V
  .limit stack 4
  .limit locals 0

	getstatic java/lang/System/out Ljava/io/PrintStream;
	new jpocl/TheAnswer
	dup
	ldc 42
	invokespecial jpocl/TheAnswer.<init>(I)V
	invokevirtual jpocl/TheAnswer.toString()Ljava/lang/String;
	invokevirtual java/io/PrintStream.println(Ljava/lang/Object;)V
	
	return
.end method

.method public static min(II)I
  .limit stack 2
  .limit locals 2
  
  iload 0
  iload 1
  invokestatic java/lang/Math.min(II)I
  ireturn
.end method

.method public static max(II)I
  .limit stack 2
  .limit locals 2
  
(...)
.end method

.method public static fact(I)I
  .limit stack 4
  .limit locals 2
    
  L0:
   iload 0
   iconst_1
   if_icmpgt L1
  L2:
   iconst_1
   ireturn
  L1:
   iload 0
   iload 0
   iconst_1
   isub
   invokestatic jpocl/Api.fact(I)I
   imul
   ireturn
  L3:
.end method

##TheAnswer##
.class  public jpocl/TheAnswer
	.super  java/lang/Object
	
	.field public answer I
	
	.method public <init>(I)V
	  .limit stack 2
	  .limit locals 2
	aload 0
	invokespecial java/lang/Object.<init>()V
	aload 0
	iload 1
	putfield jpocl/TheAnswer.answer I
	return
	.end method

	
	.method public toString()Ljava/lang/String;
	  .limit stack 3
	  .limit locals 1
	(...)
	.end method

	
	.method public equals(Ljava/lang/Object;)Z
	  .limit stack 2
	  .limit locals 3
	(...)
	.end method

Come si può osservare, Jasmin mette a disposizione un linguaggio leggermente più astratto rispetto al bytecode puro di Java, ad esempio non è prevista la gestione della tabella delle costanti, ma sono mantenute le medesime istruzioni mnemoniche della JVM. L'elemento "##TheAnswer##" non appartiene al sintassi di JasminXT, bensì separa le classi generate permettendo la redirezione dell'output su diversi file ".j".

Oltre alla generazione tramite String Template, è stato necessario individuare due algoritmi per la gestione dei "locals" e dello "stack" dei vari control-frame. Il calcolo delle due soglie è stato effettuato all'interno della tree-grammar "JPoclGenerator.g".

scope BlockLocals{
	LinkedList<String> locals;
	int localsLimit;
	boolean isFunctionBlock;
}
scope FunctionStack{
	int stackLimit;
}

"BlockLocals" supporta il calcolo del limite di variabili per ciascuna funzione e mantiene una lista, utile per mantenere l'associazione (variabile, #num). "FunctionStack" è definito unicamente da il campo stackLimit, utilizzato come contatore. La definizione di due scope, unita alla possibilità di effettuare accessi dinamici da qualsiasi produzione della tree-grammar, ha semplificato l'applicazione degli algoritmi.

Per il calcolo del valore massimo di stack, è stato individuato un algoritmo che bilanciasse precisione e semplicità di applicazione, ottenendo valori leggermente eccessivi in alcuni casi particolari.

###Esecuzione JPocl è eseguibile sia in Windows che in Linux; data la necessità di eseguire il comando "java" è però richiesto di specificare il proprio ambiente di esecuzione.

JPocl usage: jpocl.jar -i InputFile [-o OutputDirectory] [-os {W,L}]
Default output directory is ./output
Default operative system is Linux(L)

L'eseguibile è situato all'interno della cartella Resources.