[Vari] Contest 16 + 1: Compilatori e interpreti. Parte I: interpreti.

[Vincenzo1968]

Questo contest è diviso in due parti: la prima riguarda l'implementazione di un interprete per un semplice linguaggio di programmazione; la seconda(che svolgeremo, successivamente, in un thread a parte) sarà un po' più impegnativa. Riguarderà l'implementazione di un compilatore per un linguaggio di programmazione a oggetti.

punto A

La grammatica per il nostro semplicissimo linguaggio di questa prima parte è la seguente:

program : decl_list code_block;
decl_list : {decl};
decl : type var_list ';'
		| T_KW_ARRAY T_ID '[' T_INT_LITERAL ']' {'[' T_INT_LITERAL ']'} T_KW_OF type ';'
		;
type : T_KW_INT | T_KW_REAL | T_KW_BOOL | T_KW_STRING;
var_list : T_ID ['=' expr] {',' T_ID['=' expr]};
code_block : T_BEGIN stmt_list T_END;
stmt_list : {stmt};
stmt : T_KW_PRINT expr ';'
		| T_KW_READ expr ';'
		| T_KW_WHILE '(' expr ')' stmt
		| T_KW_IF '(' expr ')' stmt [T_KW_ELSE stmt]
		| T_BEGIN stmt_list T_END
		| T_ID {'[' expr ']'} '=' expr ';'
		;
expr  : expr1 {('&' | '|') expr1};
expr1 : expr2 {relop expr2};
expr2 : expr3 {addop expr3};
expr3 : expr4 {mulop expr4};
expr4 : T_INT_LITERAL
		| T_REAL_LITERAL
		| T_STRING_LITERAL
		| T_KW_TRUE
		| T_KW_FALSE
		| '(' expr ')'
		| '-' expr
		| '!' expr
		| T_ID {'[' expr ']'}
		;

Un programma, secondo la grammatica di cui sopra, è composto da una serie di dichiarazioni di variabili, seguita da un blocco di codice.
Un blocco di codice è costituito dalla parola chiave begin seguita da una lista di statements seguita, a sua volta, dalla parola chiave end.

Ecco il classico "hello world":

string strHello;

begin
	strHello = "Hello World!\n";
	print strHello;
end

Nel codice precedente dichiariamo una variabile, strHello, di tipo string e, nel blocco di codice, la inizializziamo alla stringa "Hello World" e la stampiamo.
Si noti che la costante stringa, alla fine, contiene il carattere speciale '\n'. I caratteri speciali previsti per i letterali stringa sono i seguenti:

'\n' = new line.
'\t' = carattere di tabulazione.
'\\' = stampa il carattere '\'.

Vediamo un esempio con gli array:

array a[5] of real;

begin
	a[0] = 1.5;
	a[1] = 2.8;
	a[2] = 3.15;
	a[3] = 4.3;
	a[4] = 5.7;


	print a[0];
	print "\n";

	print a[1];
	print "\n";

	print a[2];
	print "\n";

	print a[3];
	print "\n";

	print a[4];
	print "\n";
end

Nel codice precedente viene dichiarato un array di cinque elementi di tipo real(numeri in virgola mobile).
Nel blocco di codice l'array viene inizializzato e stampato con l'istruzione print. Si noti che, dopo aver stampato un elemento dell'array, andiamo a capo con l'istruzione print "\n";.

Altro esempio:

array a[2][2][2] of string;

begin
	a[0][0][0] = "stringa 1";
	a[0][0][1] = "stringa 2";

	a[0][1][0] = "stringa 3";
	a[0][1][1] = "stringa 4";

	a[1][0][0] = "stringa 5";
	a[1][0][1] = "stringa 6";

	a[1][1][0] = "stringa 7";
	a[1][1][1] = "stringa 8";


	print a[0][0][0];
	print "\n";
	print a[0][0][1];
	print "\n";

	print a[0][1][0];
	print "\n";
	print a[0][1][1];
	print "\n";

	print a[1][0][0];
	print "\n";
	print a[1][0][1];
	print "\n";

	print a[1][1][0];
	print "\n";
	print a[1][1][1];
	print "\n";
end

Viene dichiarato un array tridimensionale 2x2x2 di tipo string, inizializzato e stampato.
L'inizializzazione degli array deve essere effettuata nel blocco di codice. Le variabili semplici, possono invece essere inizializzate anche in fase di dichiarazione:

int k = 1;
real x, y=1.8, z = 2.55E-5;

begin
	x = 2 * y;
	k = 21.5;
	print k + z * x;
end

Nella prima riga dichiariamo la variabile k di tipo int e la inizializziamo al valore 1;
Nella seconda riga dichiariamo tre variabili di tipo real: x, y e z. Le variabili y e z sono inizializzate, rispettivamente, ai valori 21.5 e 2.55E-5.

Nel blocco di codice eseguiamo alcune operazioni aritmetiche e, nell'ultima riga, stampiamo il valore dell'espressione k + z* x.

Gli statements previsti sono i seguenti:

stmt : T_KW_PRINT expr ';'
		| T_KW_READ expr ';'
		| T_KW_WHILE '(' expr ')' stmt
		| T_KW_IF '(' expr ')' stmt [T_KW_ELSE stmt]
		| T_BEGIN stmt_list T_END
		| T_ID {'[' expr ']'} '=' expr ';'
		;

1°) PRINT: consiste della parola chiave print seguita da un'espressione seguita da un punto e virgola.
2°) READ: consiste della parola chiave [b]read[\b] seguita da un espressione(che deve essere una variabile di tipo semplice o un riferimento ad un elemento di un array) seguita dal punto e virgola. Questa istruzione legge il valore inserito dall'utente da tastiera e lo assegna alla variabile specificata in expr.
3) WHILE: consiste della parola chiave while seguita da una parentesi tonda aperta seguita da un'espressione di tipo booleano seguita da una parentesi tonda chiusa seguita da uno statement. Quest'ultimo viene ripetutamente eseguito finché è vera l'espressione booleana all'interno delle parentesi.
4) IF: consiste della parola chiave [if] seguita da un'espressione booleana racchiusa entro parentesi tonde seguita da uno statement (stmt1). Può opzionalmente seguire la parola chiave else seguita da uno statement (stmt2). stmt1 viene eseguito se è vera l'espressione booleana tra parentesi. Altrimenti viene eseguito stmt2.
5) BLOCCHI DI CODICE: consistono della parola chiave begin seguita da uno o più statement seguiti dalla parola chiave end.
6) ASSEGNAMENTO: consiste di un'espressione che può essere il nome di una variabile semplice o un riferimento ad un elemento di array seguito dal carattere '=' seguito da un'espressione. L'espressione alla destra del carattere '=' viene valutata e il suo valore viene assegnato all'espressione alla sinistra.

Gli operatori del linguaggio sono i seguenti:

1) Operatori aritmetici: +, -, *, /.
2) Operatori logici &, |, !.
3) Operatori booleani <, <=, ==, >, >=, >.

Gli operatori aritmetici e booleano hanno lo stesso significato di quelli presenti nei linguaggi C, C++, Java e C#. Non si confondano gli operatori logici (&, |, !) con gli operatori bitwise(che non esistono nel nostro linguaggio) del C/C++.
Nel nostro caso:
& significa: and booleano.
| significa: or booleano.
! significa: not, negazione.

Ecco un esempio:

int x;

begin
	x = 5;

	while ( x <= 5 & x > 0 )
	begin
		print "x = ";
		print x;
		print "\n";
		x = x - 1;
	end
end

Nel codice sopra la lista di statement compresa tra begin e end viene eseguita finché x è minore o uguale a 5 e x è maggiore di 0. Questo è l'output:

x = 5
x = 4
x = 3
x = 2
x = 1

punto B:
Anticipiamo un po' quella che sarà la seconda parte del contest. Si scriva il front end di un compilatore per il linguaggio specificato nel punto A. Il compilatore dovrà produrre il cosiddetto codice a tre indirizzi.

In questa rappresentazione c'è al più un operatore nel lato destro di un'istruzione. Quindi, le espressioni vanno scomposte in più istruzioni.
Per esempio, l'espressione x+y*z si traduce nelle seguenti istruzioni in three address code:

t1 = y * z
t2 = x + t1

t1 e t2 sono variabili temporanee create dal compilatore.
Le istruzioni di assegnamento sono nella forma x = y op z dove op è un operatore binario e x, y e z sono indirizzi.
Gli assegnamenti possono essere anche nella forma x = op y dove op è un operatore unario.
Le istruzioni di copia sono espresse nella forma x = y; ad x è assegnato il valore di y.
I salti incondizionati si esprimono così: goto L; L rappresenta un'etichetta.
I salti condizionati sono nella forma if x goto L e ifFalse x goto L. Queste istruzioni saltano all'istruzione seguente l'etichetta L se x è vero o falso, rispettivamente.
I salti condizionati possono essere anche nella forma if x relop y goto L. Si applica un operatore relazionale(<, <=, ==, etc) alle variabili x e y. Se l'operatore restituisce true si salta all'indirizzo specificato dall'etichetta L.
Le istruzioni di copia indicizzate(riferimenti a locazioni di array) si indicano con

y = a[x]
e
a[x] = y

Nella prima istruzione viene assegnato il valore contenuto nella locazione x dell'array a alla variabile y; nella seconda, alla locazione x dell'array a viene assegnato il valore di y.

Esempio:

int c, x, i, j;
array a[2][3] of int;

begin
	a[0][0] = 1;
	a[0][1] = 2;
	a[0][2] = 3;

	a[1][0] = 4;
	a[1][1] = 5;
	a[1][2] = 6;

	c = 5;
	i = 1;
	j = 2;
	x = c + a[i][j];
	print x;
end

Il compilatore dovrà produrre il seguente three address code:

t1 = 0 * 12
t2 = 0 * 4
t3 = t1 + t2
t4 = a[t3]
t4 = 1
t5 = 0 * 12
t6 = 1 * 4
t7 = t5 + t6
t8 = a[t7]
t8 = 2
t9 = 0 * 12
t10 = 2 * 4
t11 = t9 + t10
t12 = a[t11]
t12 = 3
t13 = 1 * 12
t14 = 0 * 4
t15 = t13 + t14
t16 = a[t15]
t16 = 4
t17 = 1 * 12
t18 = 1 * 4
t19 = t17 + t18
t20 = a[t19]
t20 = 5
t21 = 1 * 12
t22 = 2 * 4
t23 = t21 + t22
t24 = a[t23]
t24 = 6
c = 5
i = 1
j = 2
t25 = i * 12
t26 = j * 4
t27 = t25 + t26
t28 = a[t27]
t29 = c + t28
x = t29
print x

Esempio 2:

int x, y;

begin
	x = 0;
	y = 2;

	while ( x < 5 )
	begin
		print x + y;
		x = x + 1;
	end
end

Three address code:

x = 0
y = 2
L001:
t1 = x < 5
if not t1 goto L002
t2 = x + y
print t2
t3 = x + 1
x = t3
goto L001
L002:

Punto C
Simile al punto B ma, al posto del codice a tre indirizzi, bisogna produrre, in output, un file class. Le specifiche le trovate qui:

http://docs.oracle.com/javase/specs/

Ovviamente il file .class deve essere prodotto direttamente(e manualmente); non si può trasformare il file in input in un sorgente Java e utilizzare il compilatore javac.

Buon divertimento

[Vincenzo1968]

Dimenticavo. Questa è la lista delle parole chiave del linguaggio:


array
begin
bool
else
end
false
if
int
of
print
read
real
string
true
while


EDIT: il linguaggio di questa prima parte del contest è volutamente semplice; è ridotto all'osso: non ci sono funzioni definite dall'utente, non ci sono classi e oggetti, etc. Questo ci consentirà di concentrarci e discutere sui principali metodi delle tecniche di parsing senza perderci in pesanti dettagli di implementazione. La seconda parte, come già accennato, sarà più complicatuccia: implementazione di un compilatore(compilatore e non interprete ) per un linguaggio a oggetti con caratteristiche come override dei metodi di classe, parametri dei metodi con argomenti di default, etc).

EDIT 2: L'interprete dovrà gestire i commenti in stile C/C++: una doppia barra // per i commenti fino a fine riga e /* */ per i commenti multiriga.

[DanieleC88]

Cominciano a farsi tosti i contest (per i miei standard)

[Vincenzo1968]

Ciao Daniele,

si, ho intenzione di proporre una serie di contest un po' più impegnativi rispetto ai precedenti. Dopo i due su compilatori e interpreti ne proporrò uno sull'implementazione di una piccola base di dati.

[Vincenzo1968]

Ecco la mia soluzione:

Sorgenti Linux:
http://www.filedropper.com/contest17sorgentilinuxtar

Sorgenti Windows:
http://www.filedropper.com/contest17sorgentiwindows

Nota: in realtà il codice C dei sorgenti Linux e Windows è uguale. Cambia il formato dei file. Su Linux le righe dei file di testo sono terminate con LF; su Windows CR/LF.

Programmi di test:
http://www.filedropper.com/contest17test

Eseguibile per Linux 32 bit i686:
http://www.filedropper.com/contest17...linux32i686tar

Eseguibile per Linux 64 bit x86_64:
http://www.filedropper.com/contest17...inux64x8664tar

Eseguibile per Windows 32 bit i686:
http://www.filedropper.com/contest17eseguibilewin32i686

Eseguibile per Windows 64 bit x86_64:
http://www.filedropper.com/contest17...bilewin64x8664


L'eseguibile va lanciato passandogli da riga di comando il file da interpretare.
Es.

contest17 prog01.txt

Per produrre in output il codice a tre indirizzi:

contest17 prog01.txt tac

Per produrre il file per la Java Virtual Machine 6:

contest17 prog01.txt jvm

Comando per compilare con GCC:

gcc -O2 main.c ast.c endianess.c jvm.c parser.c scanner.c symtab.c -o Contest17

[DanieleC88]

Chissà se avrò tempo da dedicare al contest. Spero di sì, perché mi sembra molto interessante, ma anche molto impegnativo.

Intanto buon lavoro agli altri partecipanti.
ciao

[Vincenzo1968]

Questi sono i miei output con i file di test:

prog01.txt:


prog02.txt:


prog03.txt:


prog04.txt:


prog05.txt:


prog06.txt:

[Vincenzo1968]

Originariamente inviato da DanieleC88

Chissà se avrò tempo da dedicare al contest. Spero di sì, perché mi sembra molto interessante, ma anche molto impegnativo.

Intanto buon lavoro agli altri partecipanti.
ciao

Possiamo prenderci tutto il tempo che ci serve. Anche perché, dato il periodo, molti saranno in ferie. Ma, più in là, riporterò a galla questo thread e zac! Per alcuni di loro(p.es. Gugo) non ci sarà scampo: la semplice non partecipazione farà automaticamente scattare sambenito e coroca.

[Vincenzo1968]

Spiego brevemente il metodo che ho utilizzato:

Per l'analisi lessicale(file "scanner.c") utilizzo un automa a stati finiti. La funzione GetNextToken viene richiamata ogni volta che il parser ha bisogno del token successivo.
Per l'analisi sintattica faccio uso di un parser predittivo a discesa ricorsiva(file "parser.c").
L'analisi semantica la svolgo direttamente durante la fase di parsing.
Se il parsing non riscontra errori, crea l'AST e lo passa alla funzione "interpret"(implementata nel file "main.c"). Questa funzione scorre l'albero in modalità pre-order ed esegue le azioni richieste.
Il file "symtab.c" implementa(con una hashtable) la tabella dei simboli utile per la gestione delle variabili del programma.

Per spiegazioni più dettagliate e/o chiarimenti sui sorgenti sono a disposizione( ma a partire da lunedì prossimo ).

[marko.fatto]

molto interessante però domani parto per la montagna =D
ci risentiamo al prossimo up del 3d

[PGI-Bis]

A quella grammatica mancano un bel po' di pezzi.

[Vincenzo1968]

Originariamente inviato da PGI-Bis

A quella grammatica mancano un bel po' di pezzi.

Che pezzi?


EDIT:
forse ti riferisci a questa parte della grammatica:

expr1 : expr2 {relop expr2};
expr2 : expr3 {addop expr3};
expr3 : expr4 {mulop expr4};

relop indica uno tra i seguenti operatori:
'<', '<=', '==', '>', '>=', '!='.

addop indica uno tra i seguenti operatori:
'+', '-'.

mulop indica uno tra i seguenti operatori:
'*', '/'.

[PGI-Bis]

Bè, parlando di grammatica context-free tutto quello che manca.

Ad esempio è corretto se dico:

TK_ID = letter {letter | digit}

letter = 'A'|'B'|'C'|'D'|'E'|'F'|'G'|'H'|'I'|'J'|'K'|'L'|'M'|'N'|'O'|
'P'|'Q'|'R'|'S'|'T'|'U'|'V'|'W'|'X'|'Y'|'Z'|'a'|'b'|'c'|'d'|'e'|'f'|
'g'|'h'|'i'|'j'|'k'|'l'|'m'|'n'|'o'|'p'|'q'|'r'|'s'|'t'|'u'|'v'|'w'|'x'|'y'|'_'

digit = '0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'

T_REAL_LITERAL = {digit} "." digit {digit}
T_INT_LITERAL = digit {digit}

?

relop, mulop e addop cosa sono? Se sono operatori allora in expr4

"-"

e

"!"

cosa sono?

Va bene dire:

T_STRING_LITERAL = '"' (letter | digit) {letter | digit} '"'

?

Eccetera.

[Vincenzo1968]

EDIT: doppio.

[Vincenzo1968]

Si, hai perfettamente ragione.

Bisogna specificare meglio i simboli della grammatica(ma credevo che il significato di alcuni di essi risultasse chiaro dagli esempi esposti).

Dunque, per identificatore(T_ID) Si intende una stringa che comincia con un carattere alfabetico che può essere seguito da zero o più caratteri alfanumerici.
Non l'ho specificato tramite una regola grammaticale come quella che hai evidenziato tu( TK_ID = letter {letter | digit} ) perché lascio il compito di riconoscere un identificatore allo scanner(ed è il metodo usato da molti compilatori; dai, per esempio, un'occhiata ai sorgenti di GCC).

Per T_INT_LITERAL s'intende una stringa di caratteri numerici:

145
5
478

Per T_REAL_LITERAL s'intende una stringa di zero o più caratteri numerici seguita da un punto seguita opzionalmente da 'e' o 'E' seguita da (sempre opzionalmente) un '-' o '+' seguito da uno o più caratteri numerici:

0.25
.125E-2
14.23457e5

Per T_STRING_LITERAL s'intende una stringa che inizia col carattere '"' seguita da zero o più caratteri e conclusa dal carattere '"'. Il letterale stringa dev'essere contenuto in una sola riga. In caso contrario lo scanner deve restituire un errore(per esempio se viene matchato un new line prima del '"' finale):

"questa è una stringa"
"questa stringa contiene il carattere speciale di new line\n"
"dopo i due punti stampo uno spazio seguito dal carattere di backslash: \\"
"dopo i due punti stampo un carattere di tabulazione seguito dal carattere di backslash:\t\\"

Gli altri simboli terminali costituiscono le parole chiave del linguaggio.
Per esempio, per T_KW_PRINT(nota il prefisso T_KW_ dove KW sta per keyword), s'intende la parola chiave print.

Per gli operatori ho spiegato nel mio precedente post il significato. La grammatica ne cattura sia la precedenza che l'associatività.

Qui:

expr4 : T_INT_LITERAL
		| T_REAL_LITERAL
		| T_STRING_LITERAL
		| T_KW_TRUE
		| T_KW_FALSE
		| '(' expr ')'
		| '-' expr
		| '!' expr
		| T_ID {'[' expr ']'}
		;

la regola
'-' expr
rappresenta il meno unario.

la regola
'!' expr
rappresenta l'operatore di negazione.

esempio:

int x;

begin
	print "Inserisci un numero: ";
	read x;
	print "\n";

	if ( !x )
		print "x e' uguale a zero.\n";
	else
		print "x e' diverso da zero.\n";
end

[CwNd]

Originariamente inviato da Vincenzo1968

ne proporrò uno sull'implementazione di una piccola base di dati.

Non vedo l'ora

[Vincenzo1968]

Originariamente inviato da CwNd

Non vedo l'ora

Se t'interessa l'implementazione fisica delle basi di dati, segui con attenzione questo contest, ché, per il nostro piccolo DBMS, avremo bisogno di implementare un interprete per il linguaggio SQL.

[DanieleC88]

Originariamente inviato da CwNd

Non vedo l'ora

È sopra al tuo nick, affianco alla data.

[Kralizek]

Originariamente inviato da DanieleC88

È sopra al tuo nick, affianco alla data.

leggendo questa battuta, mi è venuta voglia di riesumare un "certo" topic sui Sistemi Operativi...

[DanieleC88]

Originariamente inviato da Kralizek

leggendo questa battuta, mi è venuta voglia di riesumare un "certo" topic sui Sistemi Operativi...

NUUUUOOOOOOOOOOOOOO


Chiedo venia!