Università degli studi di Roma
“Tor Vergata”
Facoltà di Ingegneria
Corso di laurea in Ingegneria Informatica
Sviluppo di un compilatore
per un linguaggio
imperativo.
Relatore
Laureando
Prof. Alberto Pettorossi
Fernando Iazeolla
Anno Accademico 2003-2004
Cosa e’ un compilatore

E’ un programma che traduce un
programma (sorgente) in un altro
programma equivalente
compilatore
sorgente
codice
Struttura di un compilatore
Front end


Back end
Front end = lexical analizer + parser
Back end = encoder + linker
Lexical analizer (1)

Riconosce i token dell’input stream

Token:



Numeri
Identificatori
Simboli (punteggiatura)
Lexical analizer (2)

Numeri
digit  0|1|2|3|4|5|6|7|8|9
digits  digit digit*
optional_fraction  . digits | ε
optional_ exponent  ( E ( + | - | ε ) digits) | ε
number  digits optional_fraction optional_exponent
Lexical analizer (3)

Identificatori
letter  A|B|C|…|Z|a|b|c|…|z
digit  0|1|2|3|4|5|6|7|8|9
id  letter (letter | digit )*
parser (1)

Il linguaggio e’ riconosciuto dal parser
tramite grammatiche ‘context-free’ o
BNF

Assumiamo il parser come una
rappresentazione di un albero di
parsing per i token generati dal lexical
analizer
Parser (2)
Programma
Grammatica
programopt_sub mainp opt_sub
opt_subε | sub id ( listargs ) statement opt_sub
sub out(a)
{
write(a);
mainpmain ( ) statement
statement{ statement } |ε
statementwrite ( id ) ;
}
main()
{
statement$ id ( listargs ) ;
$out(1);
}
Albero di parsing
program
opt_sub
sub
id
out
a
(
id
lstarg
)
{
write
ε
stmt
stmt
(
opt_sub
mainp
id
a
main
{
}
)
(
;
$
out
)
stmt
(
ε
stmt
}
lstarg
1
)
;
Il mio compilatore







ha l’aritmetica dei puntatori
ha le funzioni con parametri
ha variabili globali
ha variabili locali
ha tipi di dato : interi, puntatori, stringhe
e’ procedurale
adotta una sintassi C-like
Output del mio compilatore
Pseudo assembler
sorgente
compilatore
Assembler sorgente intel 80x86
Codice macchina intel 80x86
esempio

Programma sorgente
sub somma(a,b)
{
local(z);
z=a+b;
return(z);
}
main()
{
x=$somma(1,3);
}

Pseudo assembler
1-jump 12
2- init_funz
3- create_local(2)
4- load stack_bp(6)
5- add stack_bp(4)
6- store stack_bp(-2)
7- load stack_bp(-2)
8- destroy_local(2)
9- end_funz
10- destroy_local(2)
11- end_funz
12- init_funz
13- loadc 1
14- push 0
15- loadc 3
16- push 0
17- call 2
18- destroy_local(4)
19- store 23
20- halt
21- destroy_local(0)
22- end_funz
23- dw 0
24- block(2)
esempio
FFFF h
old bp
1
3
148 h
bp main
z
0
bp somma
00000100
00000101
00000102
00000105
00000106
00000107
00000109
0000010D
0000010F
00000113
00000115
00000117
0000011B
0000011D
0000011F
00000123
00000125
00000127
0000012B
0000012D
00000131
00000132
00000133
00000137
00000138
00000139
0000013A
0000013B
0000013D
00000140
00000141
00000144
00000145
00000148
0000014C
0000014F
00000151
00000155
00000156
00000157
00000159
0E
1F
E93400
90
55
89E5
81EC0200
89EB
81C30600
8B07
89EB
81C30400
0307
89EB
81C3FEFF
8907
89EB
81C3FEFF
8B07
81C40200
5D
C3
81C40200
5D
C3
90
55
89E5
B80100
50
B80300
50
E8BDFF
81C40400
A35701
CD20
81C40000
5D
C3
0000
90
push cs
pop ds
jmp 0x39
nop
push bp
mov bp,sp
sub sp,0x2
mov bx,bp
add bx,0x6
mov ax,[bx]
mov bx,bp
add bx,0x4
add ax,[bx]
mov bx,bp
add bx,0xfffe
mov [bx],ax
mov bx,bp
add bx,0xfffe
mov ax,[bx]
add sp,0x2
pop bp
ret
add sp,0x2
pop bp
ret
nop
push bp
mov bp,sp
mov ax,0x1
push ax
mov ax,0x3
push ax
call 0x5
add sp,0x4
mov [0x157],ax
int 0x20
add sp,0x0
pop bp
ret
add [bx+si],al
nop
Funzione somma
Funzione main
Esempio (2)

Programma fattoriale
sub foo()
{
main()
{
return(5);
local(x,z);
write("fattoriale");
write(crlf);
x=$fattoriale(8);
write(x);
write(crlf);
if(x>100)
{
z=4;
}
else
{
z=$foo();
}
write("ciclo");
write(crlf);
while(z>0)
{
write(z);
write(crlf);
z=z-1;
}
}
sub fattoriale(a)
{
local(x,y,z);
if(a==1) return(1);
z=a-1;
y=$fattoriale(z);
x=y*a;
return(x);
}
}
Esempio (2)
Output del programma fattoriale
Conclusioni

Conclusioni




Compilatore funzionante
Eseguibili DOS/Windows
Linguaggio C-like
Sviluppi futuri



Estenzione per un linguaggio ad oggetti
eseguibile per altri sistemi operativi
Sviluppare interfaccia grafica