[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 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 [b]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 (http://it.wikipedia.org/wiki/Three_address_code).

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]

:eek:

Cominciano a farsi tosti i contest :D (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/contest17eseguibilelinux32i686tar

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

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

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


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. :D
ciao ;)

[Vincenzo1968]

Questi sono i miei output con i file di test:

prog01.txt:
http://img405.imageshack.us/img405/3290/contest17img01.jpg

prog02.txt:
http://img35.imageshack.us/img35/6398/contest17img02.jpg

prog03.txt:
http://img812.imageshack.us/img812/5120/contest17img03.jpg

prog04.txt:
http://img405.imageshack.us/img405/4838/contest17img04.jpg

prog05.txt:
http://img825.imageshack.us/img825/27/contest17img05.jpg

prog06.txt:
http://img716.imageshack.us/img716/7213/contest17img06.jpg

[Vincenzo1968]

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. :D
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. :D

;)

[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]

A quella grammatica mancano un bel po' di pezzi.

:confused:
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


http://img547.imageshack.us/img547/2627/contest17img07.jpg

[CwNd]

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


Non vedo l'ora :D

[Vincenzo1968]

Non vedo l'ora :D

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]

Non vedo l'ora :D
È sopra al tuo nick, affianco alla data.














:D

[Kralizek]

È sopra al tuo nick, affianco alla data.

:D

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

[DanieleC88]

leggendo questa battuta, mi è venuta voglia di riesumare un "certo" topic sui Sistemi Operativi... :sofico:
:eek: NUUUUOOOOOOOOOOOOOO :eek:
:cry: :cry: :cry: :cry: :cry:

Chiedo venia! :(

[gugoXX]

Prima (e penso mia quasi ultima) versione.
Ho cambiato lavoro e casa da poco, so che ci sono errori ma non penso riusciro' a trovare il tempo di correggerli.
Tanto piu' che immagino la mia soluzione non piacera'.
Essendo che non avevo proprio tempo ho tirato giu' qualcosa, tanto da poter dire che ho partecipato evitando quindi sanbenito (???) e gatto a nove code.

Ho in pratica scritto un convertitore di linguaggio VC ==> C#, essendo che e' molto simile. (VC sta per VincenzoC)
Devo ancora piazzare la parte di input, e dovrei cambiare le RegEx per gestire commenti vs stringhe.
In piu' immagino che abbia tralasciato parecchi aspetti delle stringhe, ma il concetto (che tanto non piacera') e' questo.

Ho poi compilato il nuovo programmino C# al volo, ho scritto l'eseguibile su disco e l'ho poi eseguito sulla sua finestra...

Essendo che ho proprio poco tempo da dedicare il mio target e' la dimensione del codice. Poco e' meglio.
Tanto piu' e poco, tanto meglio.


class Program
{
static void Main(string[] args)
{
string prog = File.ReadAllText(@"c:\temp\programmino.txt");

//Begin end
prog = Regex.Replace(prog, "begin", "{");
prog = Regex.Replace(prog, "end", "}");

//real = float
prog = Regex.Replace(prog, "real", "float");

//array
prog = Regex.Replace(prog, @"array\s+(?<defin>[^\s]*)\s+of\s+(?<type>\w*)", MatchArray);

//print
prog = Regex.Replace(prog, @"print(?<toprint>[^;]*);", MatchPrint);

//Embed

prog = string.Format("{0}{1}{2}", @"
using System;
using System.Collections.Generic;
//using System.Linq;
using System.Text;
using System.IO;

namespace Programmuzzo
{
class Program
{
static void Main(string[] args)
{",
prog, @"
}
}
}");

//Compile
string outname = @"C:\temp\prog.exe";
CodeDomProvider provider = CodeDomProvider.CreateProvider("C#");
CompilerParameters compilerParameters = new CompilerParameters();
compilerParameters.GenerateExecutable = true;
compilerParameters.GenerateInMemory = false;
compilerParameters.IncludeDebugInformation = false;
compilerParameters.OutputAssembly = outname;
compilerParameters.TreatWarningsAsErrors = false;
compilerParameters.ReferencedAssemblies.Add("System.dll");
//compilerParameters.ReferencedAssemblies.Add("System.dll");

CompilerResults compilerResults = provider.CompileAssemblyFromSource(compilerParameters, prog);
if (compilerResults.Errors.HasErrors)
{
compilerResults.Output.OfType<string>().ToList().ForEach(Console.WriteLine);
return;
}

Process.Start(new ProcessStartInfo(outname));

}

public static string MatchArray(Match m)
{
string defin = m.Groups["defin"].Value;
string type = m.Groups["type"].Value;

//Estraggo il nome
int idx=defin.IndexOf("[");
if (idx==-1) throw new Exception("Illegal array definition");
string nome = defin.Substring(0,idx);

//Estraggo la definizione
string def=defin.Substring(idx);

//Conto le dimensioni
int dim = defin.ToCharArray().Count(t => t == '[');

string[] tmpdd = Enumerable.Range(0,dim).Select(t=>"[]").ToArray();
string extender = string.Join("",tmpdd);

string ret = string.Format("{0}{1} {2}=new {0}{3}", type, extender, nome, def);
return ret;
}

public static string MatchPrint(Match m)
{
string toprint = m.Groups["toprint"].Value;
string ret=string.Format("Console.Write({0});",toprint);
return ret;
}
}

[Vincenzo1968]

Prima (e penso mia quasi ultima) versione.
Ho cambiato lavoro e casa da poco, so che ci sono errori ma non penso riusciro' a trovare il tempo di correggerli.
Tanto piu' che immagino la mia soluzione non piacera'.
Essendo che non avevo proprio tempo ho tirato giu' qualcosa, tanto da poter dire che ho partecipato evitando quindi sanbenito (???) e gatto a nove code.

Ho in pratica scritto un convertitore di linguaggio VC ==> C#, essendo che e' molto simile. (VC sta per VincenzoC)
Devo ancora piazzare la parte di input, e dovrei cambiare le RegEx per gestire commenti vs stringhe.
In piu' immagino che abbia tralasciato parecchi aspetti delle stringhe, ma il concetto (che tanto non piacera') e' questo.

Ho poi compilato il nuovo programmino C# al volo, ho scritto l'eseguibile su disco e l'ho poi eseguito sulla sua finestra...

Essendo che ho proprio poco tempo da dedicare il mio target e' la dimensione del codice. Poco e' meglio.
Tanto piu' e poco, tanto meglio.
...


Eh no, così non va. E non che non mi piaccia la tua soluzione(ché la trovo elegante e arguta*), ma l'interprete deve essere implementato. Non possiamo convertire, con una serie di replace, il sorgente nel nostro linguaggio preferito e darlo in pasto a un interprete/VM esistente.
Anche perché questa prima parte del contest ci serve per illustrare le tecniche che saranno impiegate nella seconda parte.

Per quanto riguarda il tempo, l'ho scritto prima, possiamo prenderci tutto quello che ci serve. Non dobbiamo fare la gara a chi finisce prima o a chi ce l'ha più corto(più corto, dico, il codice ;)).

;)

* arguto = che ha o dimostra prontezza e vivacità d'ingegno miste a uno spirito sottile, garbato e spesso anche piacevolmente mordace. (definizione tratta da Il Nuovo Zingarelli).

[Vincenzo1968]

Segnalo un link a un corso universitario online(uno tra i tanti disponibili in rete):

http://www.cs.unicam.it/tesei/didattica/LPC20032004.html

Il metodo di parsing predittivo a discesa ricorsiva, che ho utilizzato nella mia soluzione, è ben spiegato in questo pdf:

http://www.cs.unicam.it/tesei/didattica/LPC20032004/materiale/GramTopDown.pdf

Per l'automa a stati finiti che implementa lo scanner si veda quest'altro:

http://www.cs.unicam.it/tesei/didattica/LPC20032004/materiale/TeseiLPC20032004Capitolo2.pdf

Come libri consiglio il classico di Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman che trovate in fondo alla pagina del primo link(occhio che esiste una seconda edizione, del 2006).

EDIT: Dimenticavo: il mio parser l'ho implementato a mano, ma è possibile utilizzare uno dei tanti strumenti freeware per la generazione automatica di parser(come Flex/Bison o Antlr).

[Vincenzo1968]

Per la costruzione dell'AST utilizzo una struttura a stack: i terminali vanno nei nodi foglia; operatori e costrutti sono inseriti nei nodi interni.

Vediamo un esempio per il costrutto if-then-else. Bisogna costruire un nodo con tre figli: il primo figlio contiene l'espressione booleana; il secondo contiene lo statement(o la lista di statement) da eseguire se l'espressione è vera; il terzo contiene lo statement(o la lista di statement) da eseguire se l'espressione è falsa;


...
if ( x - y )
b = true;
else
b = false;
...


Nel frammento di codice precedente, x e y sono due variabili di tipo int; b è una variabile di tipo bool. Per la costruzione dell'AST si procede come segue:

La funzione stmt riconosce il costrutto if-then-else dato che il token di lookahead è la parola chiave if. A questo punto si richiama la funzione match che controlla se il token successivo è una parentesi aperta ed eventualmente eguaglia il lookahead al token successivo(altrimenti si riporta un messaggio di errore).
Viene richiamata la funzione expr. questa richiama, nell'ordine, le funzioni expr1, expr2, expr3 e expr4. Quest'ultima riconosce un ID, la variabile x; crea dunque un nodo terminale(un nodo foglia, senza figli) e lo pone in cima allo stack:

http://img259.imageshack.us/img259/2104/contest17stack01.jpg

Il nodo successivo è il carattere '-' (l'operatore di sottrazione). Viene chiamata nuovamente la funzione [/i]expr[/i]. Questa fa in modo che venga posto, in cima allo stack, l'operando destro(la variabile y):

http://img534.imageshack.us/img534/5273/contest17stack02.jpg

Alla fine, la funzione expr preleva i due operandi dallo stack, crea un nodo etichettato con l'operatore '-', e vi aggiunge i due figli prelevati dallo stack. Il nodo così creato viene posto in cima allo stack:

http://img441.imageshack.us/img441/3546/contest17stack03.jpg

A questo punto il controllo ritorna alla funzione stmt. Viene controllato che il token successivo sia una parentesi tonda di chiusura. In caso positivo si prosegue richiamando ricorsivamente stmt. Quest'ultima chiamata riconosce uno statement di assegnamento. La creazione del nodo nello stack è simile a quanto già visto per la condizione booleana:

http://img14.imageshack.us/img14/568/contest17stack04.jpg

http://img707.imageshack.us/img707/1617/contest17stack05.jpg

Ancora una volta il controllo ritorna alla funzione stmt. Verifichiamo che il token successivo sia costituito dalla parola chiave else. Se questo non avviene, si prelevano due nodi dallo stack, si costruisce il nodo padre etichettato IF e si creano i figli con i nodi prelevati dallo stack(il terzo figlio si pone a NULL). Se, invece, è presente la keyword else(come nel nostro esempio), si prosegue con una chiamata ricorsiva alla funzione stmt. Questa costruisce il nodo relativo all'espressione di assegnamento b = false:

http://img213.imageshack.us/img213/9759/contest17stack06.jpg

Infine, la funzione stmt preleva tre nodi dallo stack e crea il nodo IF:

http://img87.imageshack.us/img87/8251/contest17stack07.jpg

[marco.r]

A quella grammatica mancano un bel po' di pezzi.

Mi sembra che manchi "solo" il lexer, pero' a quello si rimedia con un po' di intuito. Piu' che altro, cosi' a naso mi sembra che la grammatica sia ambigua o sbaglio ? Ad esempio a-b-c forse mi sembra interpretabile sia come (a-b)-c che come a-(b-c).
Usando un generatore dove si possa specificare direttamente l'associativita' la cosa si risolve, pero' andrebbe sistemata anche grammatica (sempre che sia effettivamente sbagliata...)

[PGI-Bis]

Mi sembra che manchi "solo" il lexer

Come diceva Kant, "e sputace sopra!" :D.

Una volta specificata la parte lessicale un combinatore sembra masticarla senza problemi. D'altronde se non ricordo male gli "operatori convezionali" delle grammatiche libere dal contesto sono tutti quanti associativi a sinistra con pari precedenza. Quindi:

A B C

è sempre

(A B) C

[Vincenzo1968]

Mi sembra che manchi "solo" il lexer, pero' a quello si rimedia con un po' di intuito. Piu' che altro, cosi' a naso mi sembra che la grammatica sia ambigua o sbaglio ? Ad esempio a-b-c forse mi sembra interpretabile sia come (a-b)-c che come a-(b-c).
Usando un generatore dove si possa specificare direttamente l'associativita' la cosa si risolve, pero' andrebbe sistemata anche grammatica (sempre che sia effettivamente sbagliata...)

No, non è ambigua. Il parser della mia soluzione(che su quella grammatica è basato e costruito) effettua correttamente i calcoli(costruendo, dunque, nel modo adeguato l'AST):

Programmino 1:

begin
print "\n";
print "21 - (8 - 5) = ";
print 21 - (8 - 5);
print "\n";
end


Programmino 2:

begin
print "\n";
print "21 - 8 - 5 = ";
print 21 - 8 - 5;
print "\n";
end


http://img4.imageshack.us/img4/2918/contest17img08.jpg

Questo perché le espressioni tra parentesi vengono catturate dall'ultima regola grammaticale ed hanno dunque, la precedenza più alta.


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


Per quanto riguarda le regole grammaticali per la specifica di token come identificatori e costanti numeriche, di solito non vengono usate: dai un'occhiata ai file pdf del corso online che ho postato ma anche al libro che ho segnalato. Questa cosa viene lasciata al lexer, ed è quello che ho fatto.

;)

EDIT: le regole per il lexer le ho spiegate successivamente, qui (http://www.hwupgrade.it/forum/showpost.php?p=28534281&postcount=12) e qui (http://www.hwupgrade.it/forum/showpost.php?p=28534865&postcount=15).

[fero86]

Mi sembra che manchi "solo" il lexer, pero' a quello si rimedia con un po' di intuito. Piu' che altro, cosi' a naso mi sembra che la grammatica sia ambigua o sbaglio ? Ad esempio a-b-c forse mi sembra interpretabile sia come (a-b)-c che come a-(b-c).
Usando un generatore dove si possa specificare direttamente l'associativita' la cosa si risolve, pero' andrebbe sistemata anche grammatica (sempre che sia effettivamente sbagliata...) piu in generale per questa grammatica non é stata specificata una semantica, ma solo la sintassi. in teoria non sappiamo neanche il significato dell'if o del while, per esempio.

[Vincenzo1968]

piu in generale per questa grammatica non é stata specificata una semantica, ma solo la sintassi. in teoria non sappiamo neanche il significato dell'if o del while, per esempio.

La semantica mi pare risulti chiara dagli esempi postati. Ed è comune a quella dei linguaggi che siamo abituati a usare. Se non ti è chiaro il significato di qualche operatore o costrutto, chiedi pure ;)

EDIT: e in ogni caso qualcosina l'avevo specificata. Mi autoquoto:


...
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 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 [b]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

...

[marco.r]

Una volta specificata la parte lessicale un combinatore sembra masticarla senza problemi. D'altronde se non ricordo male gli "operatori convezionali" delle grammatiche libere dal contesto sono tutti quanti associativi a sinistra con pari precedenza. Quindi:

A B C

è sempre

(A B) C
Anche se gli operatori convenzionali funzionano in un certo modo, la grammatica non dovrebbe darlo per scontato. Quel che intendo dire e' che potrei implementare un parser che rispetta la grammatica indicata ma che associ sempre a destra. Da

expr - expr

posso derivare sia a-b-c che a-(b-c). Certo, basta dire al generatore di parser che il meno associa a sinistra e fa lui il lavoro sporco, ma a voler essere pignoli andava specificato in qualche modo :P.
Questo sempre che i miei vaghi ricordi dell'universita' siano ancora validi, ma questo esempio su wikipedia sembra darmi ragione:
http://en.wikipedia.org/wiki/Context-free_grammar#Example_3

[PGI-Bis]

Come nota a margine, io mi sto divertendo come un bambino con un parser di quel linguaggio. :D

Devo solo capire come gestire l'annidamento degli enunciati.

Aver adottato la metafora, famossisima nel campo dei linguaggi, dei "bogling che sputano nella palude" non aiuta :D.

[Vincenzo1968]

Anche se gli operatori convenzionali funzionano in un certo modo, la grammatica non dovrebbe darlo per scontato. Quel che intendo dire e' che potrei implementare un parser che rispetta la grammatica indicata ma che associ sempre a destra. Da

expr - expr

posso derivare sia a-b-c che a-(b-c). Certo, basta dire al generatore di parser che il meno associa a sinistra e fa lui il lavoro sporco, ma a voler essere pignoli andava specificato in qualche modo :P.
Questo sempre che i miei vaghi ricordi dell'universita' siano ancora validi, ma questo esempio su wikipedia sembra darmi ragione:
http://en.wikipedia.org/wiki/Context-free_grammar#Example_3

Effettivamente uno svantaggio delle grammatiche EBNF rispetto alle BNF è che non specificano l'associatività. Nelle grammatiche BNF l'associatività a sinistra viene specificata scrivendo regole di produzione ricorsive a sinistra. L'associatività a destra viene specificata scrivendo regole di produzione ricorsive a destra.

Nella nostra grammatica EBNF tutti gli operatori previsti hanno associatività a sinistra(è vero, avrei dovuto specificarlo prima :bimbo:).

Per gestire l'associatività tramite grammatiche EBNF (anche nel caso di parser implementati a mano) è possibile seguire alcune regole:

http://www.eg.bucknell.edu/~cs208/spring06/10.html

Per esempio, una semplice grammatica per espressioni aritmetiche che preveda i quattro operatori aritmetici +, -, *, / (tutti con associatività a sinistra) e un operatore di elevamento a potenza, ^, (associatività a destra), potrebbe essere la seguente:


expr: term { ('+'|'-') term }
term: factor { ('*'|'/') factor }
factor: ['-'] expon
expon: atom ['^' expon]
atom: '(' expr ')'
| number


Si noti la regola factor: ['-'] expon che specifica il meno unario(che ha precedenza inferiore rispetto all'operatore di elevamento a potenza).
L'associatività a destra, nell'esempio proposto, è specificata tramite la regola ricorsiva a destra:


expon: atom ['^' expon]


Questa è l'implementazione di un parser predittivi a discesa ricorsiva(in C):


static Token g_Token;

double Parse(char *szInput)
{
double ret;

GetNextToken(szInput, &g_Token);
ret = expr(szInput);

if ( g_Token.Type != EOL )
{
printf("Errore\n");
return 0;
}

return ret;
}

void match(char *szInput, TokenTypeEnum ExpectedToken)
{
if ( g_Token.Type == ExpectedToken )
GetNextToken(szInput, &g_Token);
else
{
printf("Errore di sintassi\n");
exit(1);
}
}

/* expr: term { (+|-) term } */
double expr(char *szInput)
{
double expr = term(szInput);

while( g_Token.Type == PLUS || g_Token.Type == MINUS )
{
if ( g_Token.Type == PLUS )
{
match(szInput, PLUS);
expr = expr + term(szInput);
}
else
{
match(szInput, MINUS);
expr = expr - term(szInput);
}
}

return expr ;
}

/* term: factor { (*|/) factor } */
double term(char *szInput)
{
double expr = factor(szInput);

while( g_Token.Type == MULT || g_Token.Type == DIV )
{
if ( g_Token.Type == MULT )
{
match(szInput, MULT);
expr = expr * factor(szInput);
}
else
{
double right;
match(szInput, DIV);
right = factor(szInput);
if ( right != 0.0 )
expr = expr / right;
else
{
printf("Errore: divisione per 0\n");
exit(1);
}
}
}

return expr ;
}

/* factor: [-] expon */
double factor(char *szInput)
{
double expr;

if ( g_Token.Type == MINUS )
{
match(szInput, MINUS);
expr = -expon(szInput);
}
else
{
expr = expon(szInput);
}

return expr;
}

/* expon: atom [^ expon] */
double expon(char *szInput)
{
double expr = atom(szInput);

if ( g_Token.Type == EXP )
{
match(szInput, EXP);
expr = pow(expr, expon(szInput));
}

return expr;
}

/*
atom: '(' expr ')'
| number
*/
double atom(char *szInput)
{
double atom;

if ( g_Token.Type == OPAREN )
{
GetNextToken(szInput, &g_Token);
atom = expr(szInput);
match(szInput, CPAREN);
return atom;
}
else
{
if ( g_Token.Type != VALUE )
{
printf("Errore: operando mancante\n");
exit(1);
}
atom = g_Token.Value;
GetNextToken(szInput, &g_Token);
return atom;
}
}

[Vincenzo1968]

Ho aggiunto, nel post che apre questo thread (http://www.hwupgrade.it/forum/showpost.php?p=28527264&postcount=1), un punto B: Invece di interpretare il sorgente, si si dovrà generare il cosiddetto three address code.

;)

EDIT: non è necessario, in questa prima parte del contest, che il codice a tre indirizzi sia ottimizzato(nella seconda parte, invece, vincerà chi riesce ad ottimizzare al massimo il codice prodotto dal compilatore).

EDIT 2: segnalo questo pdf che contiene esempi per la generazione di three address code:

http://www.dound.com/courses/cs143/handouts/17-TAC-Examples.pdf

Dallo stesso sito altri pdf interessanti su compilatori e interpreti:

http://www.dound.com/courses/cs143/handouts/

[Vincenzo1968]

La mia soluzione per il punto B:

Ho aggiunto(main.c) la funzione GenThreeAddressCode che attraversa l'AST prodotto dal parser e genera il codice a tre indirizzi.

Per generare il codice bisogna passare la stringa "tac" come secondo parametro dalla linea di comando(il primo parametro è il nome del file contenente il codice sorgente).
Se non si passa il parametro "tac" viene richiamato l'interprete.

Esempio:


int x, y;

begin
x = 5;
y = 2;

if (x & y )
print "true.";
else
print "false";
end


http://img11.imageshack.us/img11/6713/contest17img09.jpg

[Vincenzo1968]

Nel seguente link spiego l'implementazione dell'analizzatore lessicale che ho utilizzato:

http://www.hwupgrade.it/forum/showpost.php?p=28604499&postcount=18

[marco.r]

primo tentativo con l'interprete.
In realta' in un paio di punti "imbroglio" (floating point in notazione scientifica non sono accettati ad esempio) pero' per il resto non dovrebbe dare grossi problemi.
Ho provato a "compilare il compilatore", ma non mi riesce di farlo con SBCL :D.
Per chi vuole provare il software, la soluzione piu' semplice e' installare SBCL, scompattare lo zip in qualche cartella e dalla stella lanciare l'interprete lisp e scrivere:


(require 'contest-17)
(contest-17:execute "prog01.txt")


Per chi vuole, con

(contest-17:test-lexer "prog0n.txt"

vengono mostrati i token come vengono identificati, mentre con

(contest-17:parse "prog0n.txt")

viene mostrato a video l'albero di parsing. Una alternativa piu' chiara e'

(in-package :contest-17)
(parse "prog0n.txt")

[Vincenzo1968]

Ciao Marco,

io ho avuto qualche problemino con SBCL su windows; ma è dovuto soltanto alla mia scarsa conoscenza di questo compilatore.

Spiega l'algoritmo che hai utilizzato. Usi uno dei metodi classici o è qualcosa di tua invenzione? Puoi postare qualche screenshot? (soprattutto per la parte di stampa del parse tree, che mi sembra interessante).

[marco.r]

My bad, nello zip manca il file con le funzioni esportate.
Appena riavvio sotto linux provvedo ad aggiungerlo nell'archivio e a dare un po' di spiegazioni.

[marco.r]

ecco qua lo zip corretto.
Piccole istruzioni per l'uso ; ho dato per scontato la presenza del mio setup :P

*Prerequisiti*

Il programma usa la libreria cl-yacc, sotto linux il modo piu' semplice per installarla e' ovviamente quello di usare i paccheddi della distribuzione. Se non ci sono, potete usare asdf-install, (che se non ricordo male e' incluso in SBCL) e installarlo da voi con

(require 'asdf-install)
(asdf-install:install 'cl-yacc)

Vi verra' chiesto se installarlo come amministratore o nella vostra home, e si lamentera' che non avete la chiave pgp per scaricare il pacchetto. Fregatevene e installate :D
Per windows il discorso e' piu' complicato perche' non mi risulta che asdf-install sia supportato al momento sotto windows, e inoltre mancano i link simbolici. La soluzione piu' semplice e' installare manualmente ovvero:

Scaricare l'archivio da http://www.pps.jussieu.fr/~jch/software/cl-yacc/
Scompattare tutto il contenuto in $HOME\.sbcl\systems.

* Programma *
L'installazione del programma segue una procedura simile a quanto appena scritto: scompattate l'intero archivio in $HOME\.sbcl\systems.

* Esecuzione *

Come scritto sopra, con una aggiunta:

(require 'asdf)
(require 'contest-17)
(contest-17:execute "prog01.txt")



Ora comunque riavvio nuovamente sotto windows e verifico che tutto funzioni...


*Funzionamento*

Il lexer (old-lexer.lisp) e' scritto a mano, non ho trovato generatori che funzionassero con gli stream invece che con stringhe, e volevo almeno poter stampare riga e colonna dell'errore. L'output e' quello che potete vedere provando [i]test-lexer[i]. Ad esempio per "prog01.txt" si ottiene (ogni token e' una coppia "tipo" "valore", dove i due coincidono nel casi di simboli o keywords)

(INT INT)
(ID X)
(; ;)
(BEGIN BEGIN)
(ID X)
(= =)
(INT-VALUE 5)
(; ;)
(WHILE WHILE)
(( ()
(ID X)
(<= <=)
(INT-VALUE 5)
(& &)
(ID X)
(> >)
(INT-VALUE 0)
() ))
(BEGIN BEGIN)
(PRINT PRINT)
(STRING-VALUE x = )
(; ;)
(PRINT PRINT)
(ID X)
(; ;)
(PRINT PRINT)
(STRING-VALUE \n)
(; ;)
(ID X)
(= =)
(ID X)
(- -)
(INT-VALUE 1)
(; ;)
(END END)
(END END)



Per il parser invece ho usato un generatore (cl-yacc appunto), che funziona piu' o meno come i soliti yacc bison e compagnia, con la differenza che in lisp possono essere implementati come semplici macro, e non come linguaggi esterni.
Il parser genera un albero, che per il momento e' comunque abbastanza scarno di informazioni, diciamo il minimo per riuscire a trovarne il risultato. Per il programma di sopra l'albero generato e' il seguente

(PROGRAM ((INT X NIL NIL))
(BLOCK
((= (REF X) 5)
(WHILE (BIN-AND (<= (REF X) 5) (> (REF X) 0))
(BLOCK
((PRINT "x = ")
(PRINT (REF X))
(PRINT "
")
(= (REF X) (- (REF X) 1))))))))

Non avevo voglia/tempo di generare un output grafico, comunque gli elementi tra parentesi sono i nodi allo stesso livelllo, spero renda l'idea.

[marco.r]

Allora... sembra sia riuscito a farlo andare anche sotto windows.
Ho pure trovato il modo di generare un exe.
Intanto usate il nuovo zip che allego, in quello vecchio ci sono un paio di dipendenze che non servono e impediscono la compilazione.
Riassumendo la procedura per windows:

- Scompattare cl-yacc e il mio zip in $HOME\.sbcl\systems
- Entrare nella suddetta cartella e scrivere

type compile.lisp | c:\path\to\sbcl.exe

Questo dovrebbe generare un eseguibile contest-17.exe. L'eseguibile e' spartano, per farlo funzionare bisogna passare il file via pipe. Ad esempio

type prog01.txt | contest-17



Per inciso... ho trovato un altro punto in cui la grammatica mi sembra ambigua:


if ( x > 3 )
if ( x > 10 )
print "grande\n"
else
print "piccolo\n"

Come deve essere interpetato ? Con x=5 stampa piccolo o grande ?

[Y3PP4]

Per inciso... ho trovato un altro punto in cui la grammatica mi sembra ambigua:


if ( x > 3 )
if ( x > 10 )
print "grande\n"
else
print "piccolo\n"

Come deve essere interpetato ? Con x=5 stampa piccolo o grande ?

Ma, mi permetto di rispondere io.
Se ci mettessi le parentesi noti che:

if ( x > 3 ) {
if ( x > 10 ) {
print "grande"
}
else {
print "piccolo"
}
}


ho scordato che te avevi chiesto per x=5, leggi i due post successivi :)

Dato che si verifica la prima condizione di IF, non guarda nemmeno l'else. Pertanto stampa "grande" e salta il blocco ELSE.

:)
Ciao!

[DanieleC88]

Ma, mi permetto di rispondere io.
Se ci mettessi le parentesi noti che:

if ( x > 3 ) {
if ( x > 10 ) {
print "grande"
}
else {
print "piccolo"
}
}

Dato che si verifica la prima condizione di IF, non guarda nemmeno l'else. Pertanto stampa "grande" e salta il blocco ELSE.

:)
Ciao!

Hmm, no, a quel punto stampa "piccolo"... :D

[Y3PP4]

Hmm, no, a quel punto stampa "piccolo"... :D

x = 5, hai ragione scusa :s

Io stavo pensando al problema con x superiore a 3 e 10... e mi son scordato il valore di x per cui aveva chiesto.

[marco.r]

[QUOTE=Y3PP4;28614951]Ma, mi permetto di rispondere io.
Se ci mettessi le parentesi noti che:

if ( x > 3 ) {
if ( x > 10 ) {
print "grande"
}
else {
print "piccolo"
}
}

E perche' non

if ( x > 3 ) {
if ( x > 10 ) {
print "grande"
}
}
else {
print "piccolo"
}

?

[Y3PP4]

[QUOTE=Y3PP4;28614951]Ma, mi permetto di rispondere io.
Se ci mettessi le parentesi noti che:

if ( x > 3 ) {
if ( x > 10 ) {
print "grande"
}
else {
print "piccolo"
}
}

E perche' non

if ( x > 3 ) {
if ( x > 10 ) {
print "grande"
}
}
else {
print "piccolo"
}

?
Per questo anche nei semplici if bisogna usare sempre le parentesi.
L'else si riferisce SEMPRE all'ultimo if dichiarato.
Salvo uso di parentesi per nidificare, ovvio. - perchè in quel caso ogno blocco è distinto.

[||ElChE||88]

L'else si riferisce SEMPRE all'ultimo if dichiarato.
E perché mai? Dove sta scritto?
Dipende dalla grammatica, ed è questo che marco.r voleva dire quando ha parlato di ambiguità (sempre a meno che non mi sbagli).

[Y3PP4]

E perché mai? Dove sta scritto?
Dipende dalla grammatica, ed è questo che marco.r voleva dire quando ha parlato di ambiguità (sempre a meno che non mi sbagli).

Mah. Dove sta scritto? Cerca su google "l'else si riferisce sempre all'ultimo if"
e trovi più di qualcosa.
Ovviamente dipende sempre dal parser - compilatore o interprete - ma sono certo che sia una specie di standard.
Comunque basta che fai degli esempi in vari linguaggi e capirai cosa intendo.

Per logica anche, secondo me, ci si arriva. Se poi uno desidera espressamente qualcosa di diverso... ma un if apre un blocco di codice, se dentro c'è un'altro if ne crea un'altro, poi si chiude il blocco if, si apre un else - che rimane sempre dentro l'if. e infine si chiude il ciclo if esterno.

Questi sono tra gli errori più comuni nella programmazinoe ed è per quello che si usano sempre le parentesi. - o meglio si dovrebbe -.

[DanieleC88]

Mah. Dove sta scritto? Cerca su google "l'else si riferisce sempre all'ultimo if"
e trovi più di qualcosa.
Ovviamente dipende sempre dal parser - compilatore o interprete - ma sono certo che sia una specie di standard.
Comunque basta che fai degli esempi in vari linguaggi e capirai cosa intendo.

Per logica anche, secondo me, ci si arriva. Se poi uno desidera espressamente qualcosa di diverso... ma un if apre un blocco di codice, se dentro c'è un'altro if ne crea un'altro, poi si chiude il blocco if, si apre un else - che rimane sempre dentro l'if. e infine si chiude il ciclo if esterno.

Questi sono tra gli errori più comuni nella programmazinoe ed è per quello che si usano sempre le parentesi. - o meglio si dovrebbe -.

Be' ma finché non viene specificato dalla sintassi di un linguaggio, potrebbe anche riferirsi al primo blocco if, per quanto ti è dato sapere... :)

Non si può mai dare niente per scontato, anche se è chiaro che "in pratica" è come dici.

[Y3PP4]

Be' ma finché non viene specificato dalla sintassi di un linguaggio, potrebbe anche riferirsi al primo blocco if, per quanto ti è dato sapere... :)

Non si può mai dare niente per scontato, anche se è chiaro che "in pratica" è come dici.

Si hai perfettamente ragione. Riguardo al contest non sò come vogliano venga interpretato, a me sembrava una richiesta del tipo: "devo farlo, ma non sò cosa deve fare" e quindi ho detto come funziona sugli altri linguaggi.
È cosa indubbia che se viene specificato diversamente non funziona cosi... anche se la vedo dura fare il contrario - perchè senza parentesi che definiscano il blocco non posso dichiarare nuovi else oltre al primo, il secondo (a meno che non inverta le cose) si riferisce a un if non esistente. Nel caso tra parentesi, a quello più interno. -

[marco.r]

[QUOTE=marco.r;28615612]
Per questo anche nei semplici if bisogna usare sempre le parentesi.
L'else si riferisce SEMPRE all'ultimo if dichiarato.
Salvo uso di parentesi per nidificare, ovvio. - perchè in quel caso ogno blocco è distinto.
E' una scelta, ma non deriva direttamente dalla grammatica, che in un modo o nell'altro (anche informale) dovrebbe specificarlo

(lo so, sono un rompiballe, ma e' periodo di specifiche per cui mi sento pignolo in tutto quello che ha a che fare con la programmazione :p :D )

[Vincenzo1968]

Si,

è colpa mia che non ho specificato la semantica. Chiedo umilmente venia(e indosserò, per un'intera settimana, il mio bel sambenito :bimbo:).

Come nella maggior parte dei linguaggi di programmazione, nel nostro linguaggio, l'else è associato all'if più vicino. Dunque, nell'esempio di Marco, il valore da stampare è "piccolo".

Il costrutto if-then-else è, per sua natura, ambiguo. È possibile modificare la grammatica in modo da eliminare l'ambiguità. Ma, generalmente, si preferisce disambiguare inserendo le azioni appropriate nel parser(Yacc/Bison, di default, esegue uno shift e, dunque, l'else viene associato all'if più vicino anche nel caso di una grammatica ambigua. È possibile, se lo si desidera, cambiare questo comportamento specificando le opportune regole di associatività e precedenza; il manuale fornisce ottimi esempi sull'argomento ;)).

Il pdf (http://www.cs.unicam.it/tesei/didattica/LPC20032004/materiale/GramTopDown.pdf) che ho segnalato illustra bene(par. 3.2.3) questo problema e fornisce un esempio di grammatica non ambigua per il costrutto if-then-else.

Il seguente programma C, stampa "piccolo":

int x = 5;
if ( x > 3 )
if ( x > 10 )
printf("grande\n");
else
printf("piccolo\n");


;)

[Vincenzo1968]

Occhio,

nel nostro linguaggio non sono previste le parentesi graffe. I blocchi di codice vanno racchiusi tra le due keyword begin end. E l'istruzione print vuole il punto e virgola finale:

non così:

if ( x > 3 ) {
if ( x > 10 ) {
print "grande"
}
else {
print "piccolo"
}
}


ma così:

int x;

begin
x = 5;
if ( x > 3 )
begin
if ( x > 10 )
begin
print "grande\n";
end
else
begin
print "piccolo\n";
end
end
end


Il codice senza blocchi, è:


int x;

begin
x = 5;
if ( x > 3 )
if ( x > 10 )
print "grande\n";
else
print "piccolo\n";
end


;)

[marco.r]

ottimo, grazie per il chiarimento.
devo modificare cmq un attimo il parser allora

[Vincenzo1968]

ottimo, grazie per il chiarimento.
devo modificare cmq un attimo il parser allora

Ancora non ho installato CL-Yacc(ho qualche problemino su windows :cry:) ma, se le azioni di default corrispondono a quelle di Yacc/Bison, dovrebbe shiftare e, dunque, associare l'else all'if più vicino(senza bisogno di modificare la grammatica).

[Vincenzo1968]

Risolto :D

Ecco il programma di Marco all'opera:

http://img534.imageshack.us/img534/5912/contest17marcorimg03.jpg


prog01.txt:


int x;

begin
x = 5;

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


;)

[dierre]

Linguaggi di programmazione è il primo corso che ho in magistrale, ripasso verso dicembre :P

[marco.r]

Ancora non ho installato CL-Yacc(ho qualche problemino su windows :cry:) ma, se le azioni di default corrispondono a quelle di Yacc/Bison, dovrebbe shiftare e, dunque, associare l'else all'if più vicino(senza bisogno di modificare la grammatica).

No, il generatore di parser si inbufaliva dicendo che c'era una ambiguita' per cui per il momento ho aggiunto un token END extra alla grammatica per farlo stare zitto. Per "correggere correttamente" devo capire come farlo comportare cosi' ... oppure sistemare un attimo la grammatica opportunamente.
stasera provo

[Dr.z4r]

Ciao a tutti, sono nuovo del forum..e sono capitato in questo topic...googlando alla ricerca di una soluzione alla dichiarazione delle matrici!!!

Non avrò tempo per fare l'interprete del contest, ma tra yacc e lex mi sono fatto una discreta cultura!

Ho visto che la discussione principale in atto è sulla If-Else Ambiguity...
Yacc fa già la cosa giusta, ma lancia un warning "shift-reduce" che si risolve dando maggiore priorità a IF-ELSE piuttosto che a IF :)

Nel file per lo scanner ci saranno dichiarate:

"if" return T_KW_IF;
"else" return T_KW_ELSE;

Nel file per il parser:

%token T_KW_IF
%nonassoc IFX
%nonassoc T_KW_ELSE

%%

stmt: T_KW_IF expr stmt %prec IFX | T_KW_IF expr stmt T_KW_ELSE stmt;

%%


Ho letto molti interventi interessanti e spero di poter trarre benefici da questa collaborazione...soprattutto in vista del linguaggio ad oggetti :P

[Vincenzo1968]

Ciao Dr.z4r,

benvenuto nel forum :)

Effettivamente quel warning può essere ignorato ma è fastidioso da vedere. Col metodo che hai esposto si evita questo piccolo fastidio :D

[Y3PP4]

Giusto per interesse - dato che leggendo il thread non l'ho capito -

Dopo la keyword begin ci si aspetta un "a capo" oppure il programma potrebbe essere costruito tutto sulla stessa riga?

Per esempio il seguente - orribile - programma

int x; begin x=5; print "x equivale a "; print x; end

genera qualche tipo di eccezione ?

[Vincenzo1968]

Giusto per interesse - dato che leggendo il thread non l'ho capito -

Se hai dubbi, sulla grammatica, sugli algoritmi utilizzati o sul codice postato dai partecipanti, chiedi pure. In fondo, lo scopo principale dei nostri contest è proprio questo: discutere degli algoritmi utilizzati(anche se, qualche volta, in passato, è andata a finire a schifìo, con litigate clamorose tra i partecipanti).
:D


Dopo la keyword begin ci si aspetta un "a capo" oppure il programma potrebbe essere costruito tutto sulla stessa riga?

Per esempio il seguente - orribile - programma

int x; begin x=5; print "x equivale a "; print x; end

genera qualche tipo di eccezione ?

No, il tuo esempio non genera nessuna eccezione. È responsabilità del programmatore indentare il codice nel modo più appropriato.

Anche così va bene:

int
x
;
begin
x
=
5
;
print
"x equivale a "
;
print
x
;
end


Naturalmente, come dice Charles Petzold:

If you code like this, however, nobody will be your friend.

:D

Si potrebbe mettere, come terzo punto del contest, l'implementazione di un programmino gui che legga il sorgente e lo visualizzi formattato con la giusta indentazione(cosi come avviene, per esempio, con l'editor di Visual Studio per C#). Ma in questa prima parte non mi pare il caso. Ce ne occuperemo nella seconda parte del contest.

;)

[Y3PP4]

Se hai dubbi, sulla grammatica, sugli algoritmi utilizzati o sul codice postato dai partecipanti, chiedi pure. In fondo, lo scopo principale dei nostri contest è proprio questo: discutere degli algoritmi utilizzati(anche se, qualche volta, in passato, è andata a finire a schifìo, con litigate clamorose tra i partecipanti).
:D

:) Lo farò. Trovo molto affascinante -nonchè realmente utile- l'argomento trattato nel contest, e mi piacerebbe imparare a sviluppare un parser . Inoltre poter vedere le varie soluzioni all'opera è quanto di meglio si possa trovare.

Attualmente non credo di riuscire a partecipare in quanto è una cosa abbastanza tosta - per le mie attuali skills in materia parsing - ma proverò qualche metodo di parsing :)


No, il tuo esempio non genera nessuna eccezione. È responsabilità del programmatore indentare il codice nel modo più appropriato.

Chiarissimo.


Naturalmente, come dice Charles Petzold:
If you code like this, however, nobody will be your friend.
:D

Eheh, parole sante :D

Si potrebbe mettere, come terzo punto del contest, l'implementazione di un programmino gui che legga il sorgente e lo visualizzi formattato con la giusta indentazione(cosi come avviene, per esempio, con l'editor di Visual Studio per C#). Ma in questa prima parte non mi pare il caso. Ce ne occuperemo nella seconda parte del contest.

;)
Anche questo sarebbe, secondo me, di grande interesse - soprattuto per futuri contest o lavori in cui bisogna realizzare qualche specie di editor -.

Grazie mille per la risposta :)

Ciao!

[marco.r]

Domandone: c'è un formato particolare per il codice a 3 indirizzi ?
Ad esempio, produrre codice SSA che sia accettato da LLVM (http://llvm.org/docs/LangRef.html) in modo da poter fare prove di generazione di eseguibili senza dover scriversi la parte di generazione del codice macchina puo' essere una soluzione ragionevole ?

[Vincenzo1968]

Domandone: c'è un formato particolare per il codice a 3 indirizzi ?
Ad esempio, produrre codice SSA che sia accettato da LLVM (http://llvm.org/docs/LangRef.html) in modo da poter fare prove di generazione di eseguibili senza dover scriversi la parte di generazione del codice macchina puo' essere una soluzione ragionevole ?

Il formato dovrebbe essere quello specificato nel primo post(sono regole che ho preso dal dragon book (http://dragonbook.stanford.edu/)).
Ma, per il momento, puoi utilizzare anche il codice SSA.
Nella seconda parte del contest, invece, si dovrà obbligatoriamente utilizzare un formato comune per il codice intermedio prodotto dal front end del compilatore.
Vincerà chi riuscirà a ottimizzare al massimo il codice intermedio. Per il back end ognuno potrà regolarsi come crede. Partendo dal codice a tre indirizzi ottimizzato, ognuno potrà scegliere di produrre, per esempio, codice assembly per x86 o MIPS; o bytecode per la JVM o il .NET framework; o, ancora, codice per la LLVM.

;)

[Vincenzo1968]

Aggiunto punto C (http://www.hwupgrade.it/forum/showpost.php?p=28527264&postcount=1):


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://java.sun.com/docs/books/jvms/second_edition/html/VMSpecTOC.doc.html

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.


;)

[banryu79]

Aggiunto punto C:

The class File Format (http://java.sun.com/docs/books/jvms/second_edition/html/ClassFile.doc.html)
circa 28 pagine formato A4 di specifiche... alla faccia del contest per hobby :eek:
Buona lettura :D

[Vincenzo1968]

The class File Format (http://java.sun.com/docs/books/jvms/second_edition/html/ClassFile.doc.html)
circa 28 pagine formato A4 di specifiche... alla faccia del contest per hobby :eek:
Buona lettura :D

:D

Tra le macchine virtuali disponibili, la JVM m'è parsa(e non ho mai programmato in Java ;)) tra le più facili da capire e implementare. In fondo, data la semplicità del nostro linguaggio, si tratta di usare solo un sottoinsieme delle specifiche.

;)

[Vincenzo1968]

La mia soluzione per il punto C:

per generare il file class bisogna lanciare l'eseguibile con l'opzione "jvm" da riga di comando. Per esempio, se il sorgente è nel file "prog01.txt", il programma va lanciato così:


Contest17 prog01.txt jvm

Viene prodotto un file class con lo stesso nome del file che contiene il sorgente ma con estensione .class(nel nostro esempio, viene prodotto il file prog01.class).

Se non si specifica nulla dopo il nome del file sorgente, viene lanciato l'interprete; Se si specifica, al posto di "jvm", la stringa "tac", viene prodotto il codice a tre indirizzi.

Una volta creato il file class è possibile eseguirlo tramite JVM. Il seguente è l'output di uno dei file di test(prog01.txt):

http://www.filedropper.com/contest17test


http://img607.imageshack.us/img607/2829/contest17img11.jpg

[Vincenzo1968]

I file per la gestione dei file class sono i seguenti:

jvm.h
jvm.c
endianess.h
endianess.c

Come riportato nelle specifiche (http://java.sun.com/docs/books/jvms/second_edition/html/VMSpecTOC.doc.html), i dati multibyte vanno riportati nel formato big-endian. Il file endianess.h implementa delle macro utili per la conversione da little-endian a big-endian. Nel file endianess.c c'è l'implementazione della funzione isBigEndian() che utilizzo per sapere, a runtime, se sto operando su una macchina little-endian(se si, utilizzo le macro per la conversione prima di scrivere i dati sul file .class).

Esempio:


paramU2 = g_IndexBytecodeArray - segnaposto2 + 1;
if ( !isBigEndian() )
{
ARRAY_TO_U2(buff, paramU2);
}
memcpy(g_ArrayCode + segnaposto2, &paramU2, 2);


Il file jvm.h contiene una serie di macro che codificano gli opcode utilizzati dalla JVM:

http://java.sun.com/docs/books/jvms/second_edition/html/Mnemonics.doc.html

L'implementazione vera e propria, per la creazione del file class, si trova in jvm.c.

Nella funzione main() richiamo la funzione jvmStart passandogli il nome del file di input, l'AST creato in fase di analisi sintattica e la tabella dei simboli:


...
else if ( genJVM )
{
jvmStart(argv[1], pTree, &g_Scope);
}
...


Una volta creato il file .class, è possibile analizzare il bytecode prodotto utilizzando lo strumento javap fonnito col jdk.

Vediamo un esempio, col seguente programma:

prog01.txt

begin
end


che corrisponde al programma Java


class Prog01 {
public static void main(String[] args) {
return;
}
}


Compiliamo con


Contest17 prog01.txt jvm


otteniamo il file prog01.class

Utilizziamo lo strumento javap:


javap -verbose prog01


e otteniamo il seguente output:

http://img32.imageshack.us/img32/1241/contest17img12.jpg

[Vincenzo1968]

Qualche altro esempio.

prog02.txt

begin
print "\nCiao a tutti\n";
end


bytecode JVM

...
const #69 = String #70; // \nCiao a tutti\n
const #70 = Asciz \nCiao a tutti\n;

{
prog02();
Code:
Stack=1, Locals=1, Args_size=1
0: aload_0
1: invokespecial #10; //Method java/lang/Object."<init>":()V
4: return

public static void main(java.lang.String[]);
Code:
Stack=2, Locals=1, Args_size=1
0: getstatic #9; //Field java/lang/System.out:Ljava/io/PrintStream;
3: ldc #69; //String \nCiao a tutti\n
5: invokevirtual #14; //Method java/io/PrintStream.print:(Ljava/lang/String;)V
8: return

}


Le costanti stringa(nel nostro esempio, "\nCiao a tutti\n") vanno piazzate nella tabella constant pool.
L'istruzione ldc (load constant ;)) prende come parametro l'indice nella tabella constant pool relativo alla stringa.
Con ldc #69 carichiamo la stringa "\nCiao a tutti\n" in cima allo stack degli operandi.
L'istruzione invokevirtual #14 richiama la funzione java/io/PrintStream.print della libreria Java; questa stampa il valore contenuto in cima allo stack degli operandi.


prog03.txt

begin
print 1;
print 34;
print 31855;
print 1500000;
end


bytecode JVM

...
const #69 = int 1500000;

{
prog03();
Code:
Stack=1, Locals=1, Args_size=1
0: aload_0
1: invokespecial #10; //Method java/lang/Object."<init>":()V
4: return

public static void main(java.lang.String[]);
Code:
Stack=8, Locals=1, Args_size=1
0: getstatic #9; //Field java/lang/System.out:Ljava/io/PrintStream;
3: iconst_1
4: invokevirtual #60; //Method java/io/PrintStream.print:(I)V
7: getstatic #9; //Field java/lang/System.out:Ljava/io/PrintStream;
10: bipush 34
12: invokevirtual #60; //Method java/io/PrintStream.print:(I)V
15: getstatic #9; //Field java/lang/System.out:Ljava/io/PrintStream;
18: sipush 31855
21: invokevirtual #60; //Method java/io/PrintStream.print:(I)V
24: getstatic #9; //Field java/lang/System.out:Ljava/io/PrintStream;
27: ldc #69; //int 1500000
29: invokevirtual #60; //Method java/io/PrintStream.print:(I)V
32: return

}


Questo esempio illustra l'uso delle istruzioni per la gestione delle costanti numeriche.
Per le costanti numeriche di tipo int(a 32 bit) con valore compreso tra -1 e 5, si usano le seguenti istruzioni:


iconst_m1
iconst_0
iconst_1
iconst_2
iconst_3
iconst_4
iconst_5


Usando le istruzioni precedenti non c'è bisogno di specificare il valore numerico da piazzare in cima allo stack degli operandi. Il bytecode risulta, dunque, più compatto.
Per valori non compresi tra -1 e 5, si usa:

bipush per valori compresi tra -128 e 127
sipush per valori compresi tra -32768 to 32767

Per valori > 32767 si usa l'istruzione ldc come per le costanti stringa e, dunque, bisogna prima inserire la costante nella tabella constant pool:


...
const #69 = int 1500000;
...
...
27: ldc #69; //int 1500000
29: invokevirtual #60; //Method java/io/PrintStream.print:(I)V
...

[Vincenzo1968]

Esempio per illustrare l'uso dei frame (http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.html#17257) della JVM:

prog04.txt

int x;
real y, z;

begin
x = 5;
y = 21.8;
z = x + y;
print z;
end


bytecode JVM

const #69 = double 21.8d;

{
prog04();
Code:
Stack=1, Locals=1, Args_size=1
0: aload_0
1: invokespecial #10; //Method java/lang/Object."<init>":()V
4: return

public static void main(java.lang.String[]);
Code:
Stack=4, Locals=6, Args_size=1
0: iconst_5
1: istore_1
2: ldc2_w #69; //double 21.8d
5: dstore_2
6: iload_1
7: i2d
8: dload_2
9: dadd
10: dstore 4
12: getstatic #9; //Field java/lang/System.out:Ljava/io/PrintStream;
15: dload 4
17: invokevirtual #63; //Method java/io/PrintStream.print:(D)V
20: return

}


Per piazzare il valore di una variabile in cima allo stack si usano le istruzioni load:

iload per variabili di tipo int
dload per variabili di tipo real

Le variabili di tipo real, nello stack frame occupano due posizioni consecutive. Ecco perchè alla variabile z è assegnato l'indice 4:
Alla variabile x, di tipo int, viene assegnato l'indice 1; alla variabile y, di tipo real, viene assegnato l'indice 2; alla variabile z, di tipo real, viene assegnato l'indice 4(e non 3, perchè la variabile precedente, y di tipo real, occupa due posizioni).

Si noti l'uso dell'istruzione i2d. Serve per convertire il valore in cima allo stack degli operandi da intero a real. Nella JVM le istruzioni di somma, sottrazione, moltiplicazione e divisione debbono essere eseguite da istruzioni che operano su operandi dello stesso tipo. È necessario, dunque, convertire il valore in cima allo stack da intero a real prima di eseguire l'istruzione dadd
che estrae due valori di tipo real dallo stack, li somma e piazza il risultato in cima allo stack.

[Vincenzo1968]

Sto preparando il contest sui DBMS.

EDIT.

[fero86]

mi dispiace ma stavolta c'é caso che trionfino l'ignoranza e il menefreghismo :rolleyes:

il tuo compilatore e la tua base di dati te li realizzi da solo :asd:

PS: neanche avessi proposto poi di realizzare un pezzo ciascuno, no: secondo te nei prossimi contest bisognerá realizzare N DBMS diversi, con N = numero dei partecipanti :sofico:

[Vincenzo1968]

mi dispiace ma stavolta c'é caso che trionfino l'ignoranza e il menefreghismo :rolleyes:

il tuo compilatore e la tua base di dati te li realizzi da solo :asd:

PS: neanche avessi proposto poi di realizzare un pezzo ciascuno, no: secondo te nei prossimi contest bisognerá realizzare N DBMS diversi, con N = numero dei partecipanti :sofico:

Non dobbiamo realizzare un DBMS in grado di competere con quelli presenti oggi sul mercato. Si tratterà di realizzare un piccolo DBMS(stile SQLite); così, tanto per cercare di capire gli algoritmi utilizzati per l'implementazione fisica di un database.
Non mi pare una proposta assurda per un forum che si occupa di programmazione.
E non ho mai detto che ognuno dovrà realizzare un DBMS per conto suo.

[Vincenzo1968]

mi dispiace ma stavolta c'é caso che trionfino l'ignoranza e il menefreghismo :rolleyes:
...


E un'altra cosa: io non parlerei di menefreghismo e ignoranza visti i tanti pvt di gente che mi chiede informazioni sulla documentazione relativa ai compilatori.
L'argomento è un po' più complesso rispetto ai contest precedenti e in tanti, per mancanza di tempo, non possono partecipare. Ma pare proprio che il menefreghismo non c'entri niente.

;)

[wizard1993]

Si tratterà di realizzare un piccolo DBMS(stile SQLite).

alla faccia del piccolo...

[Vincenzo1968]

Poiché ogni tanto qualcuno mi contatta chiedendomi i sorgenti, ho aggiornato i link. Eccoli:

http://www.hwupgrade.it/forum/showpost.php?p=28533792&postcount=5

I link vecchi si riferivano al mio sito guidealgoritmi.it che non ho più.
;)

[Vincenzo1968]

Ho eliminato un bug insidiosissimo.
Compilato su Windows con Visual Studio andava tutto bene. Oggi ho voluto provare a compilarlo su Linux con GCC e mi dava errore di segmentazione. Mi ero dimenticato a impostare a NULL qualche puntatore.
A quanto pare GCC è più severo rispetto a Visual Studio :D

Adesso funziona perfettamente anche su Linux:

http://img690.imageshack.us/img690/3960/contest1701.jpg

http://img211.imageshack.us/img211/8607/contest1702.jpg

:yeah: :winner: :yeah:

[Vincenzo1968]

I file .class generati per il punto C funzionano con Java SE 6. Per Java SE 7 dovrei modificare il codice e adattarlo alle nuove specifiche della jvm:

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

[Vincenzo1968]

Sto modificando i sorgenti in modo da fargli produrre file .class per Java 7.