Universita’ degli studi di Roma

“Tor Vergata”

Facoltà di Ingegneria

Corso di laurea in ingegneria informatica

Tesi di laurea

Sviluppo di un compilatoreSviluppo di un compilatore

perper un linguaggio imperativo un linguaggio imperativo

Relatore Laureando

Prof. Alberto Pettorossi Fernando Iazeolla

Anno Accademico 2003-2004

2

Indice

1. Principi di funzionamento dei compilatori ….…...……… 5

1.1 Il lexical analizer …...………………………………. 7

1.2 Il parser .…………………………………………. 7

1.3 Il back end .…………………………………………. 12

2. Il punto di partenza ……………………………………….. 14

3. Progetto del compilatore…………………………………... 21

4. Uso e funzionamento del compilatore …………………… 32

5. Descrizione del codice sorgente ………………………….. 35

5.1 compiler …………………………………………... 35

5.2 lexan ……….………………………………………… 35

5.3 parser …………………………………………………. 39

5.4 symtab …………………………………………………. 45

5.5 encode …………………………………………………. 46

5.6 toIntel …………………………………………………. 53

5.7 assemble …………………………………………... 58

5.8 toStream …………………………………………... 64

5.9 toCode …………………………………………………. 66

6. Il codice sorgente ………………………………………….... 69

7. Conclusioni …………………………………………………... 81

3

Introduzione

Ad appassionarmi a questa disciplina sono stati gli argomenti trattati in un corso di

informatica del mio relatore.

Il professore ha trattato argomenti teorici sugli algoritmi di parsing e sulle teorie dei

linguaggi e grammatiche .

Al giorno d’oggi possiamo trovare diversi generatori di grammatiche e di parser (come ad

esempio Lex e Yacc [1]) in cui possiamo fornire in input una grammatica ed ottenere in

uscita un parser per la stessa grammatica.

Ad esempio se volessimo codificate la seguente grammatica con Yacc:

E E + T | T T T * F | F F (E) | digit digit 0|1|2|...|9

dove E è un’espressione T è un termine ed F è un fattore, basterà fornire al generatore di

parser, Yacc, il seguente programma:

4

%{ #include<ctype.h> %} %token DIGIT %% line: expr ‘\n’ { printf(“%d\n”,$1); } expr: expr ‘+’ term { $$=$1 + $3; } | term ; term: term ‘*’ factor { $$ = $1 * $3 ; } | factor ; factor: ‘(‘ expr ‘)’ { $$ = $2 ; } | DIGIT ; %% yylex() { int c; c=getchar(); if(isdigit(c)) { yylval=c-‘0’; return DIGIT; } return c; }

.

Tuttavia la cosa che mi interessava maggiormente era applicare le conoscenze acquisite

sull’argomento, e quindi la cosa migliore era partire da zero: progettare quindi un

compilatore dall’inizio alla fine, in tutte le sue componenti, una cosa che tempo fa

consideravo difficilissima che solo una persona con doti particolari potesse essere in grado

di fare.

Certo rimane il fatto che per progettare e sviluppare un compilatore occorre avere una

profonda conoscenza che spazia in quasi tutti i campi dell’informatica: sistemi operativi,

architetture dei calcolatori, elementi di programmazione e codici macchina.

5

Capitolo 1

Principi di funzionamento dei compilatori

Essenzialmente un compilatore è un programma che legge un programma scritto in un

linguaggio (il linguaggio sorgente) e lo traduce in un programma equivalente in un altro

linguaggio (di solito codice macchina o codice oggetto).

Figura 1. Compilatore visto come traduttore

Oggi esistono moltissimi compilatori per diversi linguaggi di programmazione. Ogni

linguaggio ha insita in sè una caratteristica principale che lo rende preferibile rispetto ad

un altro a seconda del tipo di progetto che si deve sviluppare. Così ad esempio il Fortran

ed il Pascal sono preferiti nello sviluppo di applicazioni scientifico-didattiche, il Prolog è

utilizzato nell’intelligenza artificiale, il Basic dai neofiti che si avvicinano per la prima

volta alla programmazione, il C e Java sono liguaggi general pur pose (il primo è usato per

programmazione di sistemi anche a basso livello, il secondo per progetti commerciali

basati sull’architettura inter-computer e platform independent).

In principio programmare un computer significava essere in grado di programmare in

linguaggio macchina (sequenze binarie {0,1}) su schede perforate da inserire

Compilatore Programma sorgente

Codice oggetto

6

nell’elaboratore che li eseguiva a seconda di come era programmato il suo job scheduler

(multi-programmato o meno). Il risultato era poi serializzato in output e se si presentava

un errore il programmatore doveva analizzare il suo programma (che era una sequenza di

0 e 1) riperforare una nuova scheda e richiedere di nuovo un tempo di CPU da dedicare

alla rielaborazione del job.

Stiamo parlando degli anni ’40 ed i computer erano macchine molto grandi che

occupavano intere stanze come ad esempio l’ENIAC (Electronic Numerical Integrator

And Calculator) al cui progetto partecipò J. von Neumann.

Nasce così l’esigenza di portare la fase di scrittura del codice verso linguaggi più vicini

all’uomo che alla macchina in modo da poter ottenere una maggiore efficienza,

robustezza, comprensibilità del codice e maggior facilità nel debugging.

Nacque così negli anni ’50 il Fortran (FORmula TRANslation). L’ideatore di questo

linguaggio fu John Backus. Lo scopo di questo linguaggio era quella di automatizzare

calcoli matematici e scientifici. Questo linguaggio ebbe molto successo e sulla sua scia

vennero progettati moltissimi altri linguaggi di alto livello.

Si cominciarono così ad affinare le tecniche di progettazione dei compilatori.

Diamo ora uno sguardo più approfondito ai compilatori.

Un compilatore può essere visto come diviso in due parti: il cosiddetto ‘front end’

(costituito da un lexical analizer, o scanner, e da un parser) e il ‘back end’.

Il front end legge il programma sorgente mentre il back end genera il programma

equivalente in codice macchina.

Figura 2. Schema più approfondito del compilatore

.

1.1 Il Lexical Analizer

Compilatore

Front end Back end

7

Il primo passo è senz’altro quello di leggere il file di testo in input cercando i simboli e

parole chiave del linguaggio. Questo è il compito del lexical analizer: leggere dall’input

stream e restituire una sequenza di token che il parser può utilizzare per l’analisi sintattica.

Gli elementi da riconoscere sono numeri, parole e simboli del linguaggio.

Il riconoscimento di tali elementi può essere rappresentato tramite espressioni regolari o

automi finiti.

- Numeri

Digit 0|1|2|3|4|5|6|7|8|9 Digits digit digit* Optional_fraction . digit | � Optional_ exponent (E (+ | - | � ) digits) | � Number digits optional_fraction optional exponent

- 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)*

- Relazioni e simboli aritmetici

Sym rel_op | op | rest rel_op <= | >= | == | != op + | - | * | / rest ( | ) | ; | . | && | “ | !

dove ε e’ la stringa vuota.

1.2 Il Parser

Una volta eseguita la scanzione del file di codice ed identificati tutti i token il controllo

passa al parser, il vero cuore del compilatore.

La sintassi del linguaggio di programmazione riconosciuta dal parser può essere descritta

dalle grammatiche context-free o dalla notazione BNF (Backus-Naur Form) .

Le grammatiche context-free hanno quattro componenti:

1. un insieme di simboli terminali (es. t)

2. un insieme di simboli non terminali (es. N)

3. un insieme di produzioni nella forma N N | t

4. un simbolo non terminale che prende il nome di simbolo di partenza.

8

Assumiamo il parser come una rappresentazione dell’albero di parsing per i token generati

dal lexical analizer.

Ad esempio sia data la seguente grammatica:

list list + digit list list – digit list digit digit 0|1|2|3|4|5|6|7|8|9

Figura 3. Linguaggio che riconosce somma e sottrazione

i simboli non terminali sono: list e digit, mentre i terminali sono + - 0 1 2 3 4 5 6 7 8

9 0 e list è detto simbolo iniziale perchè è definito per primo.

Se ora vogliamo fare il parsing della stringa ’9-5+2’ otteniamo il seguente albero di

parsing:

Figura 4 . Albero di parsing della stringa 9-5+2.

List

List Digit

List Digit

digit

9 - 5 + 2

9

gli alberi di parsing delle grammatiche context-free hanno le seguenti proprietà:

• la radice dell’albero è il simbolo iniziale

• ogni foglia finale è un terminale o ε (stringa vuota)

• ogni nodo interno (cioè non una foglia finale) è un non terminale.

• Se A è un non terminale e rappresenta un nodo all’interno dell’albero e se

X1,X2,…,Xn sono i Figli di quel nodo (che possono essere sia simboli terminale

che non terminali) da sinistra a destra allora A X1 X2 .. Xn è una produzione.

Bisogna fare attenzione però perchè se definiamo male una grammatica corriamo il

rischio di non poter determinare un solo albero di parsing. In questo caso siamo di

fronte a grammatiche dette ambigue.

Ad esempio, supponiamo di non distinguere tra list e digit come precedentemente

fatto e consideriamo la seguente grammatica:

string -> string + string | string – string | 0|1|2|3|4|5|6|7|8|9

e la seguente espressione: ‘9-5+2’. ora siamo di fronte a due alberi di parsing: (9-5)+2

e 9-(5+2) che danno risultati totalmente diversi.

Figura 5 . Due alberi di parsing generati dalla grammatica ambigua

Nella maggior parte dei linguaggi di programmazione le quattro operazioni aritmetiche

(addizione, sottrazione, moltiplicazione e divisione) sono left associative, cioè data

l’espressione 9+5+2 essa equivale a (9+5)+2 così come 9-5-2 equivale a (9-5)-2.

C’è tuttavia da stabilire l’ordine di precedenza degli operatori in quanto data

l’espressione 9+5*2 questa può dare luogo a due diverse interpretazioni: (9+5)*2 e

string

string string

string string string

9 - 5 + 2

string

string string

string string string

9 - 5 + 2

10

9+(5*2). L’associatività dell’addizione (+) e della moltiplicazione (*) non risolvono

questa ambiguità.

Bisogna stabilire due livelli di precedenza: la moltiplicazione e la divisione legano di

piu’ dell’addizione e della sottrazione.

Creiamo quindi due non terminali expr e term per i due livelli di precedenza piu’ un

altro non terminale factor che sono atomi nelle espressioni (digit o espressioni

racchiuse tra parentesi) .

La grammatica risultante sarà quindi:

expr expr + term | expr – term | term term term * factor | term / factor | factor factor digit | (expr) digit 0|1|2|3|4|5|6|7|8|9

Questa grammatica tratta un espressione come una lista di term separati da + o – e i

termini come una lista di factor separati da * o da / . Le espressione racchiuse tra

parentesi sono trattate come fattori così possiamo ottenere espressioni annidate.

Il parser ha il compito di verificare se una certa sequenza di token, passategli dal

lexical analizer, può essere generato da una grammatica.

Ci sono tre tipi principali di parser di grammatiche. Gli algoritmi di parsing quali il

Cocke-Younger-Kasami [3] e l’Earley [3] sono in grado di parsare qualsiasi tipo di

grammatica. Ma questi parser sono poco efficienti per essere implementati su

calcolatore. Così i compilatori vengono progettati con dei parser top-down , bottom-up

o predictive parser.

Il top-down parsing costruisce l’albero di parsing a partire dalla radice che è il simbolo

iniziale della grammatica.

data la seguente grammatica:

S cAd A ab | a

e il seguente input w=cad, vediamo col metodo top-down se tale stringa è generata

dalla grammatica.

La radice quindi corrisponde ad S e espandiamo tale radice in modo da ottenere

l’albero in Figura 6.

11

Figura 6 . Albero di parsing dopo la prima produzione

Visto che la foglia più a sinistra ‘c’ corrisponde con il primo simbolo di w, avanziamo

nell’input e consideriamo il secondo simbolo di w e la seconda foglia ‘A’ .

espandiamo A usando la prima alternativa nella grammatica ottenendo l’albero in

Figura sottostante.

Figura 7 . Albero di parsing dopo la seconda produzione

e vediamo che abbiamo la corrispondenza per il secondo simbolo di w. Avanziamo

quindi nell’input e consideriamo il suo terzo simbolo d. questo non corrisponde con la

terza foglia dell’albero. Andando in backtracking consideriamo l’albero di parsing con

la seconda alternativa della produzione di A come in Figura sottostante.

Figura 8 . Albero di parsing dopo il backtracking

S

c A d

S

c A d

a b

S

c A d

a

12

Abbiamo così la corrispondenza tra la stringa di input e le foglie dell’albero il che ci

dice che la stringa appartiene alla grammatica.

Una grammatica left-recursive può causare un loop infinito perchè una produzione del

tipo A Ab | a espande un non terminale con lo stesso non terminale senza dare

luogo a nessun terminale.

I bottom-up parser costruiscono l’albero di parsing dato una stringa di input a partire

dalle foglie a salire fino alla radice. Possiamo pensare agli algoritmi bottom-up come

delle riduzioni successive della stringa di input fino all’assioma di partenza della

grammatica (al simbolo non terminale iniziale della grammatica).

Ad ogni riduzione sostituiamo alla stringa di input la parte sinistra della produzione la

cui parte destra coincide con una sottostringa dell’input. Ad esempio consideriamo la

seguente grammatica:

S aABe A Abc | b B d

E sia la stringa di input la seguente: abbcde .

abbcde aAbcde aAde aABe S

Alla stringa di partenza applichiamo la riduzione Ab e la stringa diventa: aAbcde.

Poi dalla produzione AAbc la stringa diventa aAde. Dalla produzione Bd la

stringa diventa aABe. Infine applichiamo la seguente riduzione SaABe.

1.3 Il Back End

Una volta generato l’albero di parsing e le relative symbol table (le tabelle relative alle

variabili globali e locali), il back end può essere visto come la visita dell’albero di

parsing da cui poi si genera il codice oggetto (per i compilatori) e da cui vengono

interpretate le singole istruzioni una alla volta (per esempio negli interpreti).

Gli interpreti infatti eseguono una istruzione alla volta del codice sorgente senza

tradurlo in nessun altro programma equivalente. Molti anni fa ad esempio nel

interprete BASIC si leggeva una riga alla volta del programma che terminava con un

13

ritorno a capo, si analizzava la riga e la si eseguiva. Nei moderni interpreti di linguaggi

come ad esempio il Perl si legge tutto il programma generando l’albero di parsing in

memoria, e l’esecuzione del programma non è altro che la visita di tale albero. Ciò

consente di rilevare eventuali errori sintattici prima dell’esecuzione della prima

istruzione del programma sorgente nonchè consente una esecuzione più veloce del

programma in quanto già parzialmente codificato in memoria.

14

Capitolo 2 Il punto di partenza

Il punto di partenza di questa tesi è l’articolo di Sterling-Shapiro [2] nel quale si

introduce brevemente la possibilità di progettare un semplice compilatore scritto in

Prolog. Il linguaggio sorgente da loro considerato è un sottoinsieme del Pascal, il PL

ideato da loro stessi a scopo dimostrativo. Gli statement presenti nel loro linguaggio

sono pochissimi: abbiamo lo statement di assegnamento ad una variabile, uno

statement condizionale (if-then-else), uno statement di loop (while), e due di I/O (read

e write). Il PL ammette solo variabili globali, senza quindi la possibilità di definire

istanze di variabili locali, non tipate visto che è presente solo il tipo intero e non è

previsto l’utilizzo di funzioni e procedure.

Il PL si riduce quindi ad uno script-language.

program factorial; begin read value; count:=1; result:=1; while count < value do begin count:= count +1; result:=result*count; end; write result end.

Figura 9. Programma fattoriale scritto in PL.

La grammatica relativa al linguaggio PL è descritta qui sotto dove in grassetto sono

indicati i simboli terminali.

15

pl_program program identifier ; statement statement begin statement rest_statement statement identifier := expression statement if test then statement else statement statement while test do statement statement read identifier statement write expression rest_statement ; statement rest_statement rest_statement end. expression pl_constant | pl_constant aritmetic_op expression aritmetic_op + | - | * | / pl_constant identifier | pl_integer identifier word pl_integer int_number test expression comparison_op expression comparison_op = | < | > | >= | <= | =\= word letter | letter word letter a | b |…| z int_number -> digit | digit int_number digit 1 | 2 | …| 9 | 0 .

Il codice oggetto prodotto in uscita dal processo di compilazione è uno pseudo-

assembler sempre da loro stesso ideato. È un assembler che ha un solo registro

(accumulatore) che è implicito nell’istruzione, mentre l’altro operando che può essere

un intero, una costante, un indirizzo di una cella di memoria contenente dati o

istruzioni del programma, è esplicito.

Le istruzioni con il relativo significato sono elencate nella seguente tabella.

.

istruzione operando significato

addc cost add constant: addiziona cost all’accumulatore

subc cost sub constant: sottrae cost all’accumulatore

mulc cost mul constant: moltiplica cost all’accumulatore

divc cost div constant: dividi cost all’accumulatore

loadc cost load constant: metti il valore di cost nell’accumulatore

store mem immetti il valore dell’accumulatore nella cella di memoria puntata da mem

add mem somma il contenuto della cella di memoria mem all’accumulatore

add mem somma il contenuto della cella di memoria mem all’accumulatore

sub mem sottrai il contenuto della cella di memoria mem all’accumulatore

mul mem moltiplica il contenuto della cella di memoria mem con l’accumulatore

div mem divide l’accumulatore con il valore della cella di memoria mem

load mem immetti nell’accumulatore il contenuto della cella di memoria mem

write scrive su standard output il contenuto dell’accumulatore

read immetti nell’accumulatore il valore dello standard input

jump label salto incondizionato

16

Figura 10 . Target language instructions

Il programma fattoriale presentato in Figura 1 sarà quindi tradotto nel programma

mostrato nella seguente Figura.

symbol address instruction operand symbol

jumpeq label jump if equal

jumpne label jump if not equal

jumplt label jump if less then

jumpgt label jump if greater then

jumple label jump if less or equal

jumpge label jump if greater or equal

17

LABEL1 LABEL2 COUNT RESULT VALUE

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

READ LOADC STORE LOADC STORE LOAD SUB JUMPGE LOAD ADDC STORE LOAD MUL STORE JUMP LOAD WRITE HALT BLOCK

21 1 19 20 20 19 21 16 19 1 19 20 19 20 6 20 0 0 3

VALUE COUNT RESULT COUNT VALUE LABEL2 COUNT COUNT RESULT COUNT RESULT LABEL1 RESULT

Figura 11. Codice assembly del programma fattoriale

Dove halt termina il programma e block alloca un blocco di celle di memoria per le

variabili utilizzate dal programma pari al valore del suo operando.

Il processo di compilazione è di solito eseguito in cinque passi:

1) analisi lessicale, eseguita dal lexical analizer, in cui si esegue la scansione del

codice sorgente e si restituiscono al parser i token (identificatori di numeri , parole

e simboli).

2) Analisi sintattica, in cui il parser esamina i token fornitegli dal lexical analizer e

genera il relativo albero di parsing.

3) Generazione del codice oggetto, in cui tramite una visita dell’albero di parsing si

produce un codice oggetto rilocabile, cioè in cui gli indirizzi delle variabili o celle

di memoria non sono ancora definite in maniera assoluta.

4) Link, in cui si importano le eventuali funzioni di libreria del linguaggio e si

risolvono tutte le assegnazioni di memoria.

5) Output, in cui si scrive finalmente il codice su file generando anche le opportune

intestazioni per i relativi sistemi operativi qualora il tipo di file lo richieda.

L’articolo di Sterling-Shapiro si focalizza completamente sui tre passi centrali del

processo di compilazione, tralasciando del tutto gli altri aspetti.

18

Figura 12. Processo di compilazione

Quindi al parser passiamo già una lista di token.

Test_compiler(X,Y):- program (X,P), compile(P,Y). Program(test1,[program,test1,’;’,begin,write,x,’+’,y,’-‘,z,’/’,2,end). Program(test2,[program,test2,’;’,begin,ig,a,’>’,b,then,max,’:=’,a,else,max,’:=’,b,end]). Program(factorial, [program,factorial,’;’ ,begin ,read,value,’;’ ,count,’:=’,1,’;’ ,result,’:=’,1,’;’ ,while,count,’<’,value,do ,begin ,count,’:=’,count,’+’,1,’;’ ,result,’:=’,result,’*’,count end,’;’ ,write,resutl ,end]).

Una volta parsato l’input otteniamo i relativi output del processo di parsing:

program test1: write(expr(x,name(x),expr(-,name(y),expr(/,name(z),number(2)))));void

program test2:

Source text

Token list

Parse tree

Object structure

Object structure (absolute)

output

Lexical analysis

Syntax analysis

Code generation

output link

19

if(compare(>,name(a),name(b)),assign(max,name(a)),assign(max,name(b)));void

program test3 (factorial): read(value);assign(count,number(1));assign(result,number(1)); while(compare(<,name(count),name(value)), (assign(count,expr(+,name(count),number(1))); assign(result,expr(*,name(result),name(count)));void)); write(name(result));void

Questi alberi di parsing vengono poi dati in pasto all’encoder che genera il codice

oggetto rilocabile. L’output generato dall’encoder per i relativi programmi di test è il

seguente:

program test1: ((((instr(load,Z);instr(divc,2));instr(store,Temp); instr(load,Y);instr(sub,Temp));instr(add,X));instr(write,0));no_op

program test2: (((instr(load,A);instr(sub,B));instr(jumple,L1)); (instr(loadA);instr(store,Max));instr(jump,L2);label(L1); (instr(load,B);instr(store,Max));label(L2));no_op

program test3 (factorial): instr(read,Value);instr(loadc,1);instr(store,Count)); (instr(loadc,1);instr(store,Result));label(L1); ((instr(load,Count);instr(sub,Value));instr(jumpge,L2)); (((instr(load,Count);intr(addc,a));instr(store,Count)); ((instr(load,Result);instrmul,Count));instr(store,Result)); no_op);instr(jump,L1);label(L2));(instr(load,Result);instr(write,0));no_op

Ed infine l’assemblatore prende il codice oggetto non istanziato e genera il codice

finale.

program test1: instr(load,11);instr(divc,2);instr(store,12);instr(load,10); instr(sub,12);instr(add,9);instr(write,0);instr(halt,0);block(4)

program test2: instr(load,10);instr(sub,11);instr(jumple,7);instr(load,10); instr(store,12);instr(jum,9);instr(load,11);instr(store,12); instr(halt,0);block(3)

program test3 (factorial): instr(read,21);instr(loadc,1);instr(store,19);instr(loadc,1); instr(store,20);instr(load,19);instr(sub,21);instr(jumpge,16); instr(load,19);instr(addc,1);instr(store,19);instr(load,20); instr(mul,19);instr(store,20);instr(jump,6);instr(load,20);

20

instr(write,0);instr(halt,0);block(3)

21

Capitolo 3 Progetto del compilatore

Partendo dall’articolo di Sterling-Shapiro [2], il mio compito era di progettare e

realizzare un compilatore di un linguaggio imperativo stile C-like funzionante in tutte

le sue parti e ovviamente scritto in Prolog.

Il linguaggio da me creato ricalca quindi lo stile C ed ha le seguenti caratteristiche:

• ha l’aritmetica dei puntatori

• ha le funzioni con i parametri passati alle funzioni

• ha variabili globali

• ha variabili locali

• supporta tipi di dato interi, puntatori e stringhe

• è procedurale

• adotta una sintassi C like

L’aritmetica dei puntatori è implementata come in C attraverso i simboli & e * .

Ad esempio se x è una variabile intera, allora con &x si intende l’indirizzo di memoria

associato alla variabile, mentre con *x si intende la locazione di memoria puntata dal

valore di x.

Le funzioni si definiscono tramite la keyword sub seguita dall’identificatore (il nome

della funzione) e da eventuali parametri racchiusi tra parentesi tonde. Ad esempio la

funzione che somma due interi potrebbe essere così implementata: sub somma(a,b) { local(x); x=a+b; return(x); }

Nel mio linguaggio non serve dichiarare una variabile o una funzione prima di

utilizzarla, sarà il compilatore che risolve i nomi automaticamente.

Per chiamare una funzione si fa precedere l’identificatore dal simbolo del dollaro, così

per chiamare la funzione somma sopra implementata basterà fare:

22

val=$somma(val1,val2);

Le variabili globali si usano in qualsiasi parte del codice senza bisogno di dichiararle.

Es. x=12; while(x>0) { x=x-1; } y=x;

Per usare le variabili locali invece bisogna dichiararle come tali tramite la keyword

local all’inizio della funzione di riferimento.

Es. sub sum1(a,b) { local(var); var=a+b; write(var); } main() { var=1; $sum1(5,6); }

All’inizio dell’esecuzione del programma riportato qui sopra, la variabile var avrà

valore 1. Viene poi chiamata la funzione sum1 in cui si assegna alla variabile var il

valore della somma tra 5 e 6. La variabile locale che ha sede nello stack avrà valore 11

e manterrà tale valore fino al completamento della funzione sum1 e verrà poi distrutta e

sarà l’unica con tale nome che può essere utilizzata nello scope della funzione in cui è

dichiarata, mentre la variabile globale var che avrà un indirizzo di memoria nella zona

dati avrà valore 1 e manterrà tale valore fino alla fine del programma e si potrà fare

riferimento a tale variabile se in nessuna funzione in esecuzione sarà dichiarata una

variabile locale con tale nome. Le due variabili sono quindi due entità distinte.

Abbiamo quindi visto come utilizzare i tipi di dato interi e puntatori.

Per quanto riguarda le stringhe invece, queste non sono altro che un puntatore ad una

zona di memoria dove vi è memorizzata la stringa.

Se ad esempio vogliamo avere la stringa ‘mia_stringa' nella variabile x, allora

dobbiamo scrivere quanto segue: *x=”mia_stringa”;

ed in memoria corrisponde ad avere una locazione assegnata alla variabile x di

lunghezza 2 bytes (intero) che contiene il puntatore alla zona di memoria della stringa.

23

In uscita il compilatore qui sviluppato produce i seguenti tre diversi tipi di output.

1) Output in pseudo assembler. È una versione ampliata rispetto allo pseudo

assembler proposto da Sterling-Shapiro, in quanto si era di fronte alla necessità di

dover gestire lo stack per le variabili locali, puntatori, e accumulo e rilascio di

risorse necessarie alle funzioni.

2) Output in assembler per processori Intel 80x86.

3) Output direttamente in codice macchina per processori Intel 80x86.

Figura 13 . Output del mio compilatore

Prendiamo ad esempio il seguente programma sorgente per il mio compilatore e

vediamo come viene tradotto nei vari tipi di output.

x mia_stringa

Pseudo-assembler

Assembler sorgente Intel 80x86

Codice macchine Intel 80x86

sorgente

compilatore

24

main() { x=5; y=&x; *y=2; }

Figura 14 . Programma sorgente

1 2 3 4 5 6 7 8 9 10 11 12 13 14

jump 2 init_funz loadc 5 store 12 loadc 12 store 13 loadc 2 storep 13 halt destroy_local(0) end_funz dw 0 dw 0 block(3)

x y

Figura 15. Output in pseudo assembler

00000100 0E push cs 00000101 1F pop ds 00000102 E90000 jmp 0x5 00000105 90 nop 00000106 55 push bp 00000107 89E5 mov bp,sp 00000109 B80500 mov ax,0x5 0000010C A32D01 mov [0x12d],ax 0000010F B82D01 mov ax,0x12d 00000112 A32F01 mov [0x12f],ax 00000115 B80200 mov ax,0x2 00000118 89C2 mov dx,ax 0000011A BB2F01 mov bx,0x12f 0000011D 8B07 mov ax,[bx] 0000011F 50 push ax 00000120 5B pop bx 00000121 89D0 mov ax,dx 00000123 8907 mov [bx],ax 00000125 CD20 int 0x20 00000127 81C40000 add sp,0x0 0000012B 5D pop bp 0000012C C3 ret 0000012D 0000 add [bx+si],al 0000012F 0000 add [bx+si],al 00000131 90 nop

25

Figura 16. Output in codice e assembler Intel 80x86

Altro esempio , il programma ‘somma’.

sub somma(a,b) { local(z); z=a+b; return(z); } main() { x=$somma(1,3); }

jump 12 init_funz create_local(2) load stack_bp(6) add stack_bp(4) store stack_bp(-2) load stack_bp(-2) destroy_local(2) end_funz destroy_local(2) end_funz init_funz loadc 1 push 0 loadc 3 push 0 call 2 destroy_local(4) store 23 halt destroy_local(0) end_funz dw 0 block(2)

Figura 17. Programma 'somma’ e il suo output in pseudo-assembler

00000100 0E push cs 00000101 1F pop ds 00000102 E93400 jmp 0x39 00000105 90 nop 00000106 55 push bp 00000107 89E5 mov bp,sp 00000109 81EC0200 sub sp,0x2 0000010D 89EB mov bx,bp 0000010F 81C30600 add bx,0x6 00000113 8B07 mov ax,[bx] 00000115 89EB mov bx,bp

26

00000117 81C30400 add bx,0x4 0000011B 0307 add ax,[bx] 0000011D 89EB mov bx,bp 0000011F 81C3FEFF add bx,0xfffe 00000123 8907 mov [bx],ax 00000125 89EB mov bx,bp 00000127 81C3FEFF add bx,0xfffe 0000012B 8B07 mov ax,[bx] 0000012D 81C40200 add sp,0x2 00000131 5D pop bp 00000132 C3 ret 00000133 81C40200 add sp,0x2 00000137 5D pop bp 00000138 C3 ret 00000139 90 nop 0000013A 55 push bp 0000013B 89E5 mov bp,sp 0000013D B80100 mov ax,0x1 00000140 50 push ax 00000141 B80300 mov ax,0x3 00000144 50 push ax 00000145 E8BDFF call 0x5 00000148 81C40400 add sp,0x4 0000014C A35701 mov [0x157],ax 0000014F CD20 int 0x20 00000151 81C40000 add sp,0x0 00000155 5D pop bp 00000156 C3 ret 00000157 0000 add [bx+si],al 00000159 90 nop

Figura 18. Output in assembler intel del programma 'somma’

La prima istruzione del codice prodotto in pseudo-assembler è un salto

incondizionato alla funzione di ingresso (main). Ogni funzione inizia con init_funz

che ha lo scopo di settare lo stack per le eventuali allocazione future di variabili

locali.

La funzione main in questo caso, immette nello stack i valori da passare alla

funzione somma. Quindi esegue un push degli argomenti da sinistra a destra come

nella convenzione adottata dal linguaggio Pascal.

A questo punto esegue una chiamata alla funzione somma, tramite l’istruzione call.

Una volta terminata la funzione somma, a differenza della convenzione adottata nel

linguaggio Pascal dove è la funzione chiamata a liberare lo stack dai parametri di

ingresso, qui è la funzione chiamante che fa tale operazione tramite la pseudo

istruzione destroy_local(n) dove n rappresenta il numero di bytes da liberare.

Nel caso dell’applicazione di esempio avevamo due variabili intere da passare alla

funzione somma, quindi una volta terminata la funzione chiamata dobbiamo

27

eliminare 4 bytes dallo stack, visto che nei processori intel in modalità reale ogni

intero è codificato con due bytes usando la convenzione little-endian ossia scrivendo

in memoria prima il byte meno significativo e poi quello più significativo.

A questo punto viene salvato il valore di ritorno nella apposita variabile e viene

invocato l’uscita dal programma tramite la pseudo istruzione halt. Poi il programma

termina immediatamente.

Diamo uno sguardo più da vicino a quello che succede quando viene passato il

controllo alla funzione somma e vediamo come viene usato lo stack e come viene

tradotto lo pseudo codice in codice Intel 80x86.

Un indirizzo assoluto in modalità reale di un processore Intel 80x86 viene

rappresentato tramite una coppia di registri detti segmento (segment register SR) e

offset (offset register OR) entrambi di 16 bit. Il calcolo di tale indirizzo può essere

trovato tramite la formula SR*16+OR.

Lo stack è rappresentato tramite la coppia di registri SS (segmento) e SP (offset).

registro significato

ax bx cx dx si di bp sp ds es ss cs ip

registro accumulatore registro generico “ “ “ “ indice sorgente

indice destinazione base pointer stack pointer data segment extra segment stack segment code segment instruction pointer

Figura 19. I registri del processore intel 80x86 in modalità reale

È una convenzione scrivere la coppia segmento e offset separati da due punti: SS:SP

che quindi punta alla posizione attuale dello stack.

Se inseriamo un nuovo valore nello stack (ad esempio push ax) verranno eseguiti

dal processore i seguenti passi:

sottrai un byte a SP: SP=SP-2

immetti nella nuova posizione il valore di ax.

28

Se eliminiamo un valore dallo stack (ad esempio pop ax) verranno eseguiti dal

processore i seguenti passi:

immetti in ax il valore puntato dallo stack SS:SP

SP=SP+2.

Quindi lo stack è una pila il cui valore puntato da SP decrementa ogni volta che si

immette un valore e incrementa ogni volta che ne eliminiamo uno.

Seguiamo quindi l’andamento dello stack con l’evolversi del tempo così da poter

capire come il compilatore usa lo stack per le variabili locali ed i parametri passati

alle funzioni.

Notiamo innanzi tutto che stiamo lavorando in modalità reale del processore e che

tutte le chiamate alle funzioni del programma sono di tipo near, cioè tutto il

programma è racchiuso in un solo segmento e può essere al massimo di 64kb.

Questo significa che nell’identificare l’istruzione corrente in esecuzione possiamo

dare per scontato il segmento codice (CS) ed utilizzare solamente il puntatore

all’istruzione (IP). Essendo tutto il programma racchiuso in un solo segmento il

segmento dati (DS) sarà lo stesso del segmento codice (CS) e così anche per lo stack

(SS). Lo stack pointer (SP) parte dalla cima del segmento (FFFEh) mentre

l’instruction pointer (IP) parte all’indirizzo 100h. Infatti il compilatore produce in

output files di tipo .COM che sono file eseguibili in MS-DOS (o la shell di

windows) che stanno in un solo segmento. Ma questi vengono mappati in memoria a

partire dall’offset 100h in quanto il sistema operativo necessita di inserire in

memoria alcune informazione per il processo che stà per lanciare: il PSP (Program

Segment Prefix) che occupa 255 bytes.

29

Figura 20. Mappatura del file in memoria

Per referenziare lo spazio nello stack delle variabili locali legate al ciclo di vita della

propria funzione di appartenenza si usa il registro bp, il base pointer.

All’inizio della funzione si fa puntare il base pointer all’attuale stack pointer (SP), si

decrementa il valore dello stack pointer (SP) in modo da riservare spazio fisico per le

variabili, e dal base pointer si utilizzano degli offset per accedere alle proprie

variabili. Il base pointer viene poi ripristinato al valore precedente, che è quello della

funzione chiamante, una volta che termini la subroutine in esecuzione.

Appena fatto eseguire il programma la situazione del segmento relativo al

programma è mostrata in Figura 20. Lo stack è vuoto e lo stack pointer ha valore

FFFEh.

La pseudo istruzione init_funz allinea il base pointer (BP) in modo da puntare alla

finestra per accedere alle eventuali variabili locali. Questa corrisponde alle istruzioni

intel: push bp (salva il vecchio valore) mov bp,sp (lo spazio delle variabili locali

della funzione main parte da FFFEh) .

Si salvano da questo indirizzo i parametri per la funzione somma (loadc 1; push;

loadc 3;push, che sono tradotti in assembler intel 80x86 in mov ax,1; push ax;

mov ax,3; push ax) e si chiama la funzione somma (call) . Nella chiamata alla

funzione il processore mette nello stack l’indirizzo di ritorno, cioè l’indirizzo

successivo all’istruzione call (dal programma in Figura 18 è 148h). Essendo tutte le

30

chiamate a funzioni di tipo near necessitiamo solo di 2 bytes per il registro IP,

tralasciando il registro CS.

Figura 21. Istanza dello stack dopo la chiamata 'call'.

A questo punto siamo nella funzione somma.

E qui di nuovo init_funz setta lo stack per le variabili locali della funzione (push

bp; mov bp,sp).

Ora siccome la funzione ha due variabili locali, il compilatore ha generato la pseudo

istruzione create_local(2), che siccome lavoriamo solo con variabili a 16 bit si

traduce semplicemente in sub sp,2, cioè sottrai 2 allo stack pointer.

Ora i parametri delle funzioni sono sopra il base pointer mentre le variabili locali

sono sotto. Quindi per accedere ai parametri bisogna addizionare un offset al base

pointer, mentre per accedere alle variabili locali bisogna sottrarre un offset al base

pointer. Questo è quanto succede quando prendiamo i valori dei parametri della

funzione somma per addizionarli: load stack_bp(6) e load stack_bp(4) in

pseudo assembler che si traducono in assembler intel 80x86 in mov bx,bp; add

bx,6; mov ax,[bx] e mov bx,bp; add bx,4; mov ax,[bx].

Per quanto riguarda le variabili locali, invece, queste si trovano sotto il base pointer.

Quindi l’istruzione pseudo assembler sarà: load stack_bp(-2).

31

Figura 22. Istanza dello stack dopo l'inizializzazione della funzione somma.

I processori dei calcolatori lavorano in modulo 10000h, e per default sono tutti interi

positivi. Come rappresentare i numeri negativi dunque? Facciamo un esempio con

tre bit e supponiamo che il processore lavori in modulo 8 e quindi troncherà i bit

superiori al quarto. Perciò i numeri 101 e 1101 per il processore sono la stessa cosa,

anche se in realtà non è così.

Noi sappiano che -1 +1=0 . Trasportando il tutto in modulo 8 a tre bit come il nostro

processore ipotetico avremo che 111+1=0 ossia 7+1=0 perciò 7 equivale a -1 in

modulo 8.

Quindi per lo stesso motivo il numero -2 sarà tradotto dal processore come FFFEh.

Quindi la pseudo istruzione per accedere alla variabile locale del programma di

esempio di Fig 23 , load stack_bp(-2) sarà tradotta nella seguente sequenza di

istruzioni intel 80x86: mov bx,bp; add bx,FFFEh; mov ax,[bx].

Al termine della funzione somma (e di qualsiasi altra funzione in generale) il

compilatore pone la coppia di pseudo istruzioni: destroy_local(n) e end_funz.

destroy_local(n) , come si può intuire dal nome, elimina le variabili locali dallo

stack e n sta ad indicare il numero di bytes da liberare. Questa viene tradotta in

assembler intel 80x86 semplicemente con la seguente: add sp,n.

32

end_funz termina la funzione e il suo scopo è di ripristinare il vecchio base pointer.

Questa si traduce banalmente in assembler intel 80x86 con la seguente: push bp.

Nel nostro programma di esempio a questo punto siamo tornati alla funzione main e

vediamo che necessitiamo di liberare la memoria dello stack dai parametri passati

alla funzione somma. Tale operazione come detto prima, viene svolta dalla funzione

chiamante e si risolve banalmente come se si dovessero eliminare le variabili locali,

quindi con un destroy_local(n) dove n rappresenta sempre il numero di bytes da

liberare e che si traduce sempre in assembler intel 80x86 con un semplice add sp,n.

A questo punto il programma prosegue la sua esecuzione fino ad incontrare

l’istruzione che termina il programma (halt in pseudo assembler) che richiama

l’interrupt del DOS che esegue tale compito (int 20h in assembler intel 80x86).

Capitolo 4 Funzionamento ed uso del compilatore

Vediamo ora come usare il compilatore.

Il compilatore è stato scritto in linguaggio Prolog ed è composto dai seguenti files:

1. compiler: è il modulo principale.

2. lexan: è il lexical analizer del compilatore.

3. parser: è il parser del compilatore.

4. encode: è il primo modulo del back end. Produce codice oggetto rilocabile in cui

variabili fanno riferimento ancora alle symbol table e le etichette devono ancora essere

risolte.

33

5. assemble: dal codice rilocabile risolve tutti gli indirizzi di memoria e di variabili

producendo codice assoluto in doppio formato (pseudo assembler e assembler intel

80x86).

6. tostream: formatta l’output a video dei sorgenti assembler.

7. tointel: traduce il codice rilocabile prodotto da encode in codice rilocabile per intel

80x86 che poi deve essere sottoposto al processo di assemble.

8. tocode: traduce il sorgente di intel 80x86 assoluto prodotto da tointel+assemble nel

corrispondente codice macchine per processori intel 80x86 e scrive in output su file di

tipo .COM .

9. symtab: per la gestione dei parametri delle funzioni e variabili locali.

Come prima cosa fare eseguire l’interprete Prolog (io ho usato lo SWI-Prolog).

Caricare il file principale compiler.

Richiamare il goal ‘load’. Questo non fa altro che una serie di ‘consult’ di tutti gli

altri files elencati poco sopra. Cioè carica in memoria tutti i predicati necessario per

la compilazione con un solo input.

A questo punto siamo pronti per la compilazione.

Sia ‘prog1’ il programma sorgente che dobbiamo compilare. Il predicato ‘compile’

può eseguire quattro differenti tipi di output su standard output (schermo) o su file.

La sintassi è: compile(File,TipoOutput,Strem).

Dove File è ovviamente il file sorgente da compilare (prog1 nel nostro caso).

TipoOutput può assumere i seguanti valori:

pseudoasm: l’output sarà il codice in linguaggio pseudo assembler che abbiamo visto

nei capitoli precedenti,

intelSrc: l’output sarà in linguaggio assembler per processori intel 80x86. questa

opzione ci farà dunque vedere un sorgente in assembler per processori intel,

intelCode: l’output sarà direttamente il codice macchina per processori intel 80x86.

Stream può assumere i seguanti valori:

debug: solamente associato a pseudoasm. Questa opzione permette di visualizzare

l’albero di parsing e i codici intermedi nei vari passi del processo di compilazione.

Questa opzione è stata creata da me per un più facile debug in fase di creazione del

compilatore ed è stata poi lasciata per scopi didattici,

toScreen: l’output stream avviene su standard output , quindi se non è reindirizzato

viene stampato a video,

34

FileOut: specifica un nome di file per la scrittura del codice prodotto. Se il file

specificato esiste già, viene troncato a zero e riscritto dall’inizio.

Se il processo di compilazione va a buon fine l’interprete Prolog risponderà yes.

Se invece il programma sorgente non è scritto correttamente, allora il compilatore

non lo riconoscerà come un linguaggio generato dalla sua grammatica e terminerà

con un messaggio “not a valid program”.

A questo punto se si è scelto di generare un codice macchina (intelCode) il file

generato sarà un eseguibile MS-DOS (o shell di windows) in formato .COM che

come sappiamo non necessita di alcun heather su file e può essere lungo al massimo

64kb perchè dovrà essere contenuto in un solo segmento di memoria. Sarà quindi

l’immagine di ciò che verrà caricato in memoria a partire dall’offset 100h del

segmento scelto dal sistema operativo in quanto i primi 100h bytes sono riservati

dallo stesso sistema operativo.

Nota

Ho riscontrato un’anomalia nell’interprete SWI-Prolog in ambiente windows.

L’unica (ma letale) anomalia riguarda la scrittura del codice macchina. Più nello

specifico se eseguiamo un raw-write scrittura a basso livello del numero 10,

l’interprete aggiunge (di sua spontanea volontà) in numero 13 a seguire. Ciò non

avviene in ambiente Linux. Immagino che ciò abbia a che fare su come i sistemi

operativi gestiscano i ritorni a capo. In ambiente Linux questo è codificato tramite un

byte (10 appunto) , mentre in ambiente windows questo è codificato tramite due

bytes (10 line feed, e 13 carridge return). Quindi immagino che la scrittura del byte

10 venga interpretato dall’interpreto Prolog in ambiente windows come un tentativo

di ritorno a capo e di conseguenza l’interprete stesso aggiunge il byte 13 a seguire.

Questo comporta la non corretta esecuzione del codice macchina prodotto in quanto

tutti i riferimenti a locazione di memoria risulteranno sfasati.

Invece in ambiente linux tutto fila liscio: se gli si dice di scrivere su file il byte

10…magicamente viene scritto solo 10!

Questo errore comparirà sicuramente se nel codice sorgente vi è una istruzione per

stampare a video il valore di una variabile ad esempio write(x). Infatti come vedremo

in seguito nel codice macchina corrispondente si eseguirà un ciclo dove di dividerà

la variabile per 10 e si mette il risultato nello stack e poi finito il ciclo delle divisioni,

preleveremo dallo stack cifra per cifra il valore della variabile stampandolo a

35

schermo. Quindi nell’operazione di divisione per 10 avremo un problema di

sfasamento.

Questo avviene sempre ovunque compaia il numero 10 (x=10; y<10; ecc..).

Ho quindi scelto di lavorare al progetto in ambiente linux su ci ho installato un

emulatore di MS-DOS anzichè fare ogni volta il reboot per testare i programmi

compilati.

Capitolo 5 Descrizione del codice sorgente

5.1 Il file ‘compiler’

Abbiamo già visto nel capitolo precedente il funzionamento e l’utilità dei predicati

contenuti in tale file.

36

Riassumendo il predicato load carica tutti i predicati in memoria.

I predicati compile(File,Type,Out) compilano il file sorgente (File) producendo

differenti output (Out) secondo il tipo di compilazione desiderato (Type).

5.2 Il file ‘lexan’

Il lexical analizer.

Il lexical analizer prende come input il file di caratteri che è il sorgente del

programma da compilare, e ritorna una lista di token da parsare.

Prendiamo ad esempio come sorgente il file somma di Figura 23.

sub somma(a,b) { local(z); z=a+b; return(z); } main() { x=$somma(1,3); }

Figura 23. Programma di esempio: 'somma’.

Questo verrà letto come un carattere alla volta e una volta manipolato produrrà la

seguente lista di token. [sub, somma, (, a, (,), b,), {, local, (, z,), (;), z, =, a, +, b, (;), return, (, z,), (;), }, main, (,), {, x, =, $, somma, (, 1, (,), 3,), (;), }]

.

Vediamo come.

Si richiama il predicato toklist che ha due parametri File e Tl, rispettivamente il file

da leggere e la lista da restituire. Toklist(File,Tl):- see(File),get0(C), doSent(C,Tl),seen.

See(File) ridirige lo standard input in modo che il flusso di input sia il file File

anzichè lo standard (la tastiera).

Seen chiude la ridirezione creata da see e ripristina il flusso di input precedente, in

questo caso la tastiera.

Get0(C) prende un carattere dallo stream input e pone il suo valore nella variabile C.

37

doSent(C,Tl) prende il carattere di ingresso e restituisce la lista di token a partire

da quel carattere fino alla fine del flusso di caratteri in ingresso, in questo caso fino

alla fine del file. doSent(_,[]):- at_end_of_stream,!. doSent(Char,[W|W2]):- skip_blank(Char,X), readWord(X,W,C2), doSent(C2,W2).

Il predicato doSent forma quindi la lista di token a partire dal carattere Char.

Come prima cosa ignora tutti i caratteri di spaziatura tramite il predicato

skip_blank(Char,X), dove Char è il carattere da analizzare ed X sarà il primo

carattere utile che non sia una spaziatura (punteggiatura o alfanumerico).

A questo punto a partire dal carattere X, il predicato readWord legge la parola W e

ritorna C2 che è il carattere subito dopo la parola appena processata. E quindi ripete il

tutto con il secondo doSent della riga che a partire dal carattere C2 ritorna il resto

della lista dei token tramite un massiccio uso della ricorsione. A questo punto la lista

completa dei token sarà la concatenazione del token W e della lista dei rimanenti

token W2: [W|W2] che è il valore a toklist. blank_char(32). blank_char(8). blank_char(9). blank_char(10). blank_char(13). skip_blank(_,32):- at_end_of_stream,!. skip_blank(A,B):- blank_char(A),get0(V),skip_blank(V,B). skip_blank(A,B):- blank_char(A),get0(B). skip_blank(A,A).

Vediamo quindi come readWord riconosce i token.

Come detto nei capitoli precedenti il compilatore riconosce tre tipi di token:

punteggiatura (o simboli), numeri (interi) e identificatori (alfanumerici) .

La punteggiatura nel mio linguaggio prevede solo simboli a singolo o doppio

carattere (altri linguaggi come ad esempio il php prevedono anche tre simboli) .

Quindi c’è il rischio di sbagliare se per esempio incontriamo l’uguale (=). Come

interpretarlo? Come operatore di assegnazione che ha un singolo simbolo o come il

primo dell’operatore di comparazione che ha invece due simboli (==) ?

La tecnica più comunemente adottata analizza prima la punteggiatura con il maggior

numero di simboli, e se fallisce il pattern matching allora decrementa il numero di

simboli da analizzare fino ad arrivare ad un solo simbolo. Così il mio compilatore

prima analizza tutti i doppi simboli e poi in caso fa la stessa cosa con i singoli

simboli.

38

double_char(33,W,R):- peek_byte(61),get0(_),get0(R),name(W,[33,61]). % != double_char(43,W,R):- peek_byte(43),get0(_),get0(R),name(W,[43,43]). % ++ double_char(45,W,R):- peek_byte(45),get0(_),get0(R),name(W,[45,45]). % -- double_char(45,W,R):- peek_byte(62),get0(_),get0(R),name(W,[45,62]). % -> double_char(60,W,R):- peek_byte(61),get0(_),get0(R),name(W,[60,61]). % <= double_char(61,W,R):- peek_byte(61),get0(_),get0(R),name(W,[61,61]). % == double_char(62,W,R):- peek_byte(61),get0(_),get0(R),name(W,[62,61]). % >= double_char(42,W,R):- peek_byte(42),get0(_),get0(R),name(W,[42,42]). % **

Il predicato double_char analizza la punteggiatura a doppio carattere. Gli argomenti

del predicato sono: il primo carattere della punteggiatura (scritto esplicitamente)

come parametro di ingresso, mentre come parametri di uscita avremo il token W e il

prossimo carattere da analizzare R.

Notiamo che nel vedere se il secondo carattere appartiene alla punteggiatura doppia

utilizziamo il predicato peek_byte della libreria dell’interprete Prolog e solo nel

caso questo corrisponda allora lo preleviamo dall’input stream.

Il predicato name anch’esso della libreria standard del Prolog ha due parametri X,L e

ritorna vero se L è la lista dei caratteri ASCII che formano l’atomo X.

Ad esempio: name(ab,[96,97]) è yes. Oppure name(ab,[X,Y]) da X=96 e Y=97,

oppure name(X,[69,97]) da X=ab.

single_char(33,W,R):- get0(R),name(W,[33]). % ! single_char(34,W,R):- get0(R),name(W,[34]). % " single_char(35,W,R):- get0(R),name(W,[35]). % # single_char(36,W,R):- get0(R),name(W,[36]). % $ single_char(37,W,R):- get0(R),name(W,[37]). % % single_char(38,W,R):- get0(R),name(W,[38]). % & single_char(39,W,R):- get0(R),name(W,[39]). % ' single_char(40,W,R):- get0(R),name(W,[40]). % ( single_char(41,W,R):- get0(R),name(W,[41]). %) single_char(42,W,R):- get0(R),name(W,[42]). % * single_char(43,W,R):- get0(R),name(W,[43]). % + single_char(44,W,R):- get0(R),name(W,[44]). % , single_char(45,W,R):- get0(R),name(W,[45]). % - single_char(46,W,R):- get0(R),name(W,[46]). % . single_char(47,W,R):- get0(R),name(W,[47]). % / single_char(91,W,R):- get0(R),name(W,[91]). % [ single_char(92,W,R):- get0(R),name(W,[92]). % \ single_char(93,W,R):- get0(R),name(W,[93]). % ] single_char(94,W,R):- get0(R),name(W,[94]). % ^ single_char(58,W,R):- get0(R),name(W,[58]). %: single_char(59,W,R):- get0(R),name(W,[59]). % ; single_char(60,W,R):- get0(R),name(W,[60]). % < single_char(61,W,R):- get0(R),name(W,[61]). % =

39

single_char(62,W,R):- get0(R),name(W,[62]). % > single_char(63,W,R):- get0(R),name(W,[63]). % ? single_char(123,W,R):- get0(R),name(W,[123]). % { single_char(125,W,R):- get0(R),name(W,[125]). % }

Mentre nei predicati che verificano la punteggiatura singola mettiamo il carattere del

simbolo direttamente nella lista di un solo elemento in quanto ne verifichiamo

l’appartenenza direttamente nella firma del predicato e ritorniamo il carattere

successivo da analizzare R.

Quindi la lettura del token eseguita dal predicato readWord relativo alla

punteggiatura sarà: readWord(C,W,C2):- double_char(C,W,C2). readWord(C,W,C2):- single_char(C,W,C2).

Come abbiamo detto tale predicato analizzerà prima l’appartenenza alla

punteggiatura a doppio carattere e poi a un solo carattere.

Vediamo ora come il compilatore riconosce i numeri e gli identificatori.

Innanzi tutto dobbiamo istruire la base di conoscenza del Prolog e dirgli che cosa

sono le cifre e i caratteri: isAlNum(C):- isNum(C). isAlNum(C):- isChar(C). isNum(X):- X>47,X<58. % 0-9 isChar(X):- X>64,X<91. % A-Z isChar(X):- X>96,X<123. % a-z

Il predicato isNum(X) ritorna vero se l’argomento X è compreso tra 47 e 58 che sono

i codici ASCII delle cifre zero e nove.

Un carattere è definiti da isChar(X) e ritorna vero se X è compreso tra 64 e 91 o 96

e 123, ossia i codici ASCII delle lettere maiuscole e minuscole.

Definiamo ora un alfanumerico in quanto un identificatore è un carattere seguito da

zero o più alfanumerici: un alfanumerico è o un carattere o una cifra.

I token che sono numeri sono riconosciuti da: readWord(C,W,C2):- isNum(C),get0(C3),getNum(C3,W2,C2),name(W,[C|W2]).

e getNum(A,[],A):- \+isNum(A). getNum(A,[A|Num],F):- isNum(A),get0(B),getNum(B,Num,F).

Quindi partendo da readWord, se il primo carattere è una cifra allora prendi il

secondo carattere C3. il predicato getNum ritorna la lista delle cifre eventuali

adiacenti alla cifra C3 che formano il numero meno la prima cifra C. ed infine il

40

predicato name crea il token desiderato a partire dalla concatenazione della lista

formata dalla prima cifra C e il resto della lista formante il numero ([C|W2]).

La stessa cosa avviene per il riconoscimento degli identificatori. readWord(C,W,C2):- isChar(C),get0(C3),getWord(C3,W2,C2),name(W,[C|W2]).

e getWord(A,[],A):- \+isAlNum(A). getWord(A,[A|Word],F):- isAlNum(A),get0(B),getWord(B,Word,F).

Viene preso il primo carattere che deve essere una lettera. Poi viene costruita la lista

degli alfanumerici adiacenti al carattere iniziale e il predicato name ritorna

l’identificatore a partire dalla concatenazione della lista che ha come head il carattere

C e come tail la lista dei successivi alfanumerici W2: [C|W2].

5.3 Il file ‘parser’

Il parser prende in ingresso la lista di token generata dal lexical analizer e costruisce

la struttura che rappresenta l’albero di parsing.

Il parser è stato scritto usando una definite clause grammar (DCG) che è una

particolare sintassi riconosciuta dall’interprete Prolog con cui possiamo definire una

grammatica velocemente e in maniera semplice. La sintassi della DCG è molto

intuitiva ed è molto simile alla Backus-Naur Form, ed è particolarmente adatta a

codificare semplici grammatiche di tipo context-free.

Il simbolo di partenza della grammatica l’ho denominato iaz_proram ed è la prima

dell’insieme delle produzioni dichiarate. Quindi per quanto visto nei primi capitoli, il

linguaggio appartiene alla grammatica se partendo dal simbolo iniziale della

grammatica, applicando le produzioni, otteniamo che nelle foglie dell’albero di

parsing che ricordiamo è formato solo da simboli terminali, l’input del programma

sorgente. parse(Token,Structure):- iaz_program(Structure,Token,[]),!. parse(_,_):- write('not a valid program'),nl,halt.

Quindi il predicato parse prende come parametro di ingresso la lista dei token

Token e se il linguaggio appartiene alla grammatica ritorna la rappresentazione

dell’albero di parsing in Structure, altrimenti stampa a video il messaggio “not a

valid program” e termina l’esecuzione del compilatore. iaz_program((S;Ss;Sss)) --> subp(S),mainp(Ss),subp(Sss). iaz_program((S;Ss;Sss)) --> subp(S),mainp(Ss),subp(Sss),[void].

41

Ogni programma deve quindi avere la struttura di iaz_program e sarà composto da

delle subroutine (che vedremo poi poter essere opzionali) da una funzione main, che

è il punto di ingresso del programma e deve essere sempre presente, e chiude con

altre subroutine eventuali. mainp((funz(main,[]);S;halt;end_funz)) --> [main],['('],[')'],statement(S). mainp((funz(main,[]);S;halt;end_funz)) --> [main],['('],[')'],statement(S),[void].

La funzione di ingresso è così definita: il simbolo terminale main, una coppia di

parentesi tonde () (il mio linguaggio non prevede il passaggio di argomenti alla

funzione di ingresso a differenza del linguaggio C in cui potevamo passargli le

opzioni della riga di comando argv), e da statement eventuali che vedremo tra breve

come sono definiti.

In uscita il parser ritorna la struttura del relativo albero. Il predicato mainp ritorna

alla struttura del parsing la funzione main con zero argomenti (funz(main,[]))

una serie di statement eventuali (S), e la terminazione del programma (halt) e della

funzione (end_funz) che abbiamo visto libera lo spazio che aveva allocato alle

eventuali variabili locali. Quest’ultima cosa come vediamo non viene mai eseguita

perchè il programma termina prima di giungere a tale codice. L’ho messo solamente

per scopo didattico perchè ogni funzione al proprio termine del ciclo di vita deve

liberare la memoria stack associata alle variabili locali. subp(void)-->[]. subp((funz(X1,X2);S;end_funz;Ss))--> [sub],identifier(X1),['('],listargs(X2),statement(S),subp(Ss).

con listargs([])--> [')']. listargs([A|X])--> [','],identifier(A),listargs(X). listargs([A|X])--> identifier(A),listargs(X). identifier(X)-->[X],{atom(X)}.

Qui sopra vediamo come vengono definite le subroutines.

Possono non esserci nessuna subroutine (subp(void)-->[]), oppure se sono

presenti sono così definite: simbolo terminale sub, identificatore del nome della

subroutine, terminale apri parentesi tonda ‘(‘ una lista di argomenti eventuali

(listargs), degli statement eventuali, e infine ricorsivamente zero o più subroutine

(subp(Ss)).

42

Listargs come possiamo vedere mette in una lista Prolog tutti gli argomenti (che

sono solo identificatori di variabili)passati alla funzione che sono intervallati da una

virgola e termina con la chiusura della parentesi che indica la fine della lista di

variabili.

Alla struttura del parsing vengono passati: funz(X1,X2) dove X1 è il nome della

subroutine mentre X2 è la lista degli eventuali argomenti, poi vengono passati gli

statement della funzione (S), le operazioni della terminazione della funzione

(end_funz), e le eventuali altre subroutine (Ss).

Cominciamo a vedere i vari statement supportati dal mio linguaggio.

Abbiamo lo statement vuoto: statement(void)-->[void].

e statement(void)-->[';'].

Un blocco di statement racchiusi tra parentesi graffe è trattato come unico statement: statement((S;Ss))--> ['{'],statement(S),rest_statements(Ss). rest_statements((S;Ss))--> statement(S),rest_statements(Ss). rest_statements(void)-->['}']. rest_statements(void)-->[void].

Degli statement di assegnazione: statement(assign(X,V))--> identifier(X),['='],expression(V),[';']. statement(assign(p(X),V))--> ['*'],identifier(X),['='],expression(V),[';'].

e expression(X)--> iaz_constant(X). expression(expr(Op,X,Y))--> iaz_constant(X), arithmetic_op(Op), expression(Y). arithmetic_op('+')-->['+']. arithmetic_op('-')-->['-']. arithmetic_op('*')-->['*']. arithmetic_op('/')-->['/']. string(mstring(X))--> identifier(X). iaz_constant(name(X))--> identifier(X). iaz_constant(number(X))--> iaz_integer(X). identifier2(X)--> identifier(X). identifier2(X)--> iaz_integer(X). identifier(X)-->[X],{atom(X)}. iaz_integer(X)-->[X],{integer(X)}.

Il primo statement di assegnazione assegna li valore di una espressione alla variabile,

mentre il secondo statement assegna il valore di una espressione all’indirizzo puntato

dalla variabile.

43

Una espressione è definita ricorsivamente e può essere una costante (cioè un

identificatore o un intero) o una operazione aritmetica tra una costante e una

espressione.

Viene ritornato alla struttura del parsing o la costante o expr(Op,X,Y) dove Op è

l’operatore aritmetico, X è una costante e Y è una espressione codificata

ricorsivamente di expr(…).

Una semplice aritmetica dei puntatori: statement(assign(X,p1(name(V))))--> identifier(X),['='],['&'],identifier(V),[';']. statement(assign(X,p2(name(V))))--> identifier(X),['='],['*'],identifier(V),[';'].

Lo statement per le chiamate a funzioni: statement(callx(X1,X2);assignret(R))--> identifier(R),['='],['$'],identifier(X1),['('],listargs2(X2),[';']. statement(callx(X1,X2))--> ['$'],identifier(X1),['('],listargs2(X2),[';'].

e listargs2([])--> [')']. listargs2([A|X])--> [','],identifier2(A),listargs2(X). listargs2([A|X])--> identifier2(A),listargs2(X). identifier2(X)--> identifier(X). identifier2(X)--> iaz_integer(X).

che ritorna alla struttura del parsing callx(X1,X2) dove X1 è il nome della funzione

e X2 è la lista di eventuali parametri da passare alla funzione, e assignret(R) che

assegna alla variabile R l’eventuale valore di ritorno della funzione.

Il secondo statement di chiamata differisce dal primo solo per il fatto che ignoriamo

l’eventuale parametro di ritorno.

Notiamo che a differenza della dichiarazione delle funzioni in cui necessitavamo del

predicato listagrs per la lista di parametri che accetta solo identificatori, qui abbiamo

bisogno di un altro predicato in quanto nel richiamare una funzione, gli possiamo

passare sia variabili sia numeri. Il predicato listargs2, a differenza di listagrs,

accetta variabili e numeri.

Costrutti condizionali e di loop: statement(if(T,S1,S2))--> [if],['('],test(T),[')'],statement(S1),[else],statement(S2). statement(if(T,S,void))--> [if],['('],test(T),[')'],statement(S). statement(while(T,S))--> [while],['('],test(T),[')'],statement(S).

44

e test(compare(Op,X,Y))-->expression(X),comparison_op(Op),expression(Y). comparison_op('==')-->['==']. comparison_op('!=')-->['!=']. comparison_op('>')-->['>']. comparison_op('<')-->['<']. comparison_op('>=')-->['>=']. comparison_op('<=')-->['<='].

Gli statement di output: statement(write_crlf)-->[write],['('],[crlf],[')'],[';']. statement(write(X))--> [write],['('],expression(X),[')'],[';']. statement(write_str(X))--> [write],['('],['"'],string(X),['"'],[')'],[';']. statement(write_str(X))-->[write_str],['('],['"'],string(X),['"'],[')'],[';'].

dove il primo è il ritorno a capo, il secondo stampa a video il valore di una variabile

in base decimale, il terzo e il quarto stampano a video una stringa puntata dalla

variabile.

Lo statement che ritorna un valore di una espressione da una funzione: statement(return(X))--> [return],['('],expression(X),[')'],[';'].

Ed infine lo statement che dichiara variabili locali: statement(local(X))--> [local],['('],listargs(X),[';'].

Che sfrutta il predicato listargs il quale raccoglie la lista di variabili che sono solo

identificatori.

Vediamo ora come viene codificata la struttura del programma somma di Figura 23. (funz(somma, [a, b]); (local([z]);assign(z, expr(+, name(a), name(b)));return(name(z));void);end_funz;void); (funz(main, []); ((callx(somma, [1, 3]);assignret(x));void);halt;end_funz);void

Vediamo ora un programma più completo e vediamo di nuovo cosa produce il

parser. sub foo() { return(5); } sub fattoriale(a) { local(x,y,z); if(a==1) return(1); z=a-1; y=$fattoriale(z); x=y*a; return(x); } main() {

45

local(x,z); write("prog1"); write(crlf); x=$fattoriale(3); write(x); write(crlf); if(x>100) { z=4; } else { z=$foo(); } while(z>0) { write(z); write(crlf); z=z-1; } }

Figura 24. Programma di esempio: 'prog1' (fattoriale).

darà (funz(foo, []); (return(number(5));void);end_funz;funz(fattoriale, [a]); (local([x, y, z]);if(compare(==, name(a), number(1)), return(number(1)), void);assign(z, expr(-, name(a), number(1))); (callx(fattoriale, [z]);assignret(y));assign(x, expr(*, name(y), name(a)));return(name(x));void);end_funz;void); (funz(main, []); (local([x, z]);write_str(mstring(prog1));write_crlf; (callx(fattoriale, [3]);assignret(x));write(name(x));write_crlf;if(compare(>, name(x), number(100)), (assign(z, number(4));void), ((callx(foo, []);assignret(z));void));while(compare(>, name(z), number(0)), (write(name(z));write_crlf;assign(z, expr(-, name(z), number(1)));void));void);halt;end_funz);void

.

5.4 Il file ‘symtab’

In questo file sono presenti quattro predicati tre dei quali sono utilizzati dal file

encode per la codifica dell’albero di parsing. tdstrip((Code1;Code2),(X,Y)):- tds(Code1,X),tds(Code2,Y). tds(no_op,''). tds(C,C).

È l’unico a non essere utilizzato dall’encoder e serve solo a pulire il codice dai

no_op (no operation) istruzioni che non fanno nulla. Migliora la leggibilità del

codice. setlocalpar(X,Funz):- length(X,N), N1 is (N+1)*2,slp(X,Funz,N1,_).

46

slp([],_,N,N). slp([X|L],Funz,N,N2):- slp2(X,Funz,N,N1),slp(L,Funz,N1,N2). slp2(X,Funz,N,N1):- assert(lvar(X,Funz,N)), N1 is N-2.

Il predicato setlocalpar costruisce una tabella in memoria relativa ai parametri

passati alla funzione.

La tabella di nome lvar ha tre parametri: in nome della variabile X, la funzione di

riferimento Funz e l’indirizzo dello stack relativo al base pointer (BP).

Siccome come abbiamo visto al cap 3, i parametri delle funzioni si trovano ad un

indirizzo più grande del base pointer relativo alla funzione, viene calcolato lo

spiazzamento massimo che verrà assegnato alla prima variabile della lista (N+1)*2,

dove all’indirizzo BP della funzione viene sommato uno spiazzamento che è dovuto

al fatto che sono presenti nello stack anche il BP e l’indirizzo di ritorno della

funzione chiamante, e poi si moltiplica per 2 in quanto ogni variabile (sempre di tipo

intero) necessita di due bytes.

La tabella lvar viene riempita per ogni variabile e l’indirizzo relativo alle variabili

viene decrementato 2 due ad ogni inserimento nella tabella. setlocalvar(X,Funz):- length(X,N), N1 is -N*2,slv(X,Funz,N1,_). slv([],_,N,N). slv([X|L],Funz,N,N2):- slv2(X,Funz,N,N1),slv(L,Funz,N1,N2). slv2(X,Funz,N,N1):- assert(lvar(X,Funz,N)), N1 is N+2. getlocalvar(_).

Lo stesso discorso vale per le variabili locali che condividono la stessa tabella lvar.

In questo caso però gli spiazzamenti relativi al BP sono negativi in quanto come

abbiamo visto al cap 3 le variabili locali si trovano ad indirizzi più bassi rispetto al

base pointer. Il calcolo del massimo spiazzamento viene fatto semplicemente

moltiplicando il numero delle variabili per 2 (due bytes per ogni variabile) e preso in

valore negativo (-N*2). Ad ogni inserimento in tabella di una variabile della lista

l’indirizzo associato verrà incrementato di due. codepush([],_,no_op). codepush([X|L],Gv,(X1;X2)):- codepush2(X,Gv,X1),codepush(L,Gv,X2). codepush2(X,_,(instr(loadc,X);instr(push,0))):- number(X). codepush2(X,Gv,(instr(load,Addr);instr(push,0))):- lookup2(X,Gv,Addr,_,_).

Il predicato codepush genera il codice che salva nello stack le variabili da passare

alla relativa funzione prima di chiamarla.

Per ogni elemento della lista di variabili se questa è un numero allora si carica nel

registro accumulatore tale numero (loadc num) altrimenti se è un identificatore si

47

carica nell’accumulatore il valore di tale variabile (load Addr), ed infine si immette

il valore desiderati nello stack (push). Per sapere il valore di una variabile si fa uso

del predicato lookup2 che spiegherò tra brevissimo nel prossimo paragrafo.

5.5 Il file ‘encode’

Prima di vedere e di commentare il codice sorgente del file dell’encoder vorrei

soffermarmi a spiegare il funzionamento degli alberi binari incompleti che è la

tecnica utilizzata dal mio compilatore per la memorizzazzione e l’utilizzo delle

variabili globali e nomi di funzioni.

Introduciamo ora una struttura dati incompleta basata su dizionario di cui vediamo

un codice di esempio: lookup(Key,[(Key,Value)|Dict],Value):- !. lookup(Key,[(Key1,Value1)|Dict],Value):- Key\==Key1,lookup(Key,Dict,Value).

Questo è un semplice database basato su dizionario, la variabile Dict che tiene

traccia delle varie coppie Key e Value.

Consideriamo la seguente istanza di Dict: [(mark,122),(john,101),(susy,222)|Xs].

Se noi interroghiamo il database secondo il dizionario Dict con la seguente query:

lookup(mark,Dict,X) la risposta sarà X=122. Possiamo inserire una nuova voce

nella tabella con la query: lookup(frank,Dict,333). Sintatticamente sembrerebbe

cercare il valore associato alla key frank, ma gli effetti sono tuttaltri: la query

ritorna true e la nuova istanza del dizionario Dict sarà

[(mark,122),(john,101),(susy,222),(frank,333)|Xs] e possiamo quindi

inserire una nuova voce nella tabella se la Key della query non è già presente,

altrimenti possiamo ottenerne il valore associato.

Consideriamo allora la query: lookup(john,Dict,102). Il valore dalla chiave è già

presente ma il valore è diverso. In questo caso la query fallisce a causa della

condizione Key\==Key1.

Questo tipo di memorizzazione dati che sfrutta strutture dati incomplete viene

utilizzato dal mio compilatore per le tabelle delle variabili globali e delle funzioni.

Le due tabelle sono tenute separate per mezzo di dizionari diversi: per le variabili

globali utiliziamo il dizionario Gv (global variable), mentre per le funzioni utiliziamo

il dizionario Fv.

48

Nel codice utilizzato nel mio compilatore ho preferito adottare una variante del

codice sopra descritto perchè se le tabelle diventano molto grandi diventa poco

efficiente la ricerca di elementi in una lista lineare.

Ho utilizzato quindi una variante che memorizza la tabella tramite un albero binario

ordinato di cui vediamo qui sotto l’equivalente del codice visto per le liste lineari. Lookup(Key,dict(Key,X,Left,Right),Value):- !,X=Value. Lookup(Key,dict(Key1,X,Left,Right),Value):- Key<Key1,lookup(Key,Left,Value). Lookup(Key,dict(Key1,X,Left,Right),value):- Key>Key1,lookup(Key,Right,Value).

Ma i risultati sono gli stessi.

Il codice utilizzato nel mio compilatore per la gestione delle tabelle delle variabili

globali e delle funzioni è il seguente: lookup(Key,dict(Key,X,Y,Z,_,_),Value,Type,Val):- !,X = Value,Y=Type,Z=Val. lookup(Key,dict(Key1,_,_,_,Left,_),Value,Type,Val):- Key@<Key1, lookup(Key,Left,Value,Type,Val). lookup(Key,dict(Key1,_,_,_,_,Right),Value,Type,Val):- Key@>Key1, lookup(Key,Right,Value,Type,Val).

Infatti non essendoci nessuna dichiarazione di variabili globali ne di intestazioni di

funzioni nel mio linguaggio, necessitavo di questo tipo di struttura per la loro

gestione così potevo accedere al relativo valore in tabella se questo era presente

oppure creava una nuova voce in caso contrario, con una sola chiamata del predicato

senza dovermi preoccupare di verificare se la voce desiderata era già creata.

Per le variabili locali e i parametri delle funzioni questo non andava bene perchè

avendo una modalità di accesso e una ubicazione in memoria differente

necessitavano di essere dichiarati prima e quindi vi accediamo tramite il predicato

lvar creato da setlocalpar e setlocalvar in cui ritorna vero solo se la voce

desiderata è presente, e falso altrimenti senza creare nessuna nuova voce

implicitamente.

Per automatizzare il processo di recupero delle informazioni relative alle variabili

(globali o locali che siano) nonchè l’inserimento di nuove variabili globali usiamo il

predicato lookup2. lookup2(Nome,_,stack_bp(Addr),nostr,_):- lvar(Nome,_,Addr). lookup2(Nome,Alf,Addr,Type,Val):- lookup(Nome,Alf,Addr,Type,Val).

Questo semplicemente controlla nell’ordine prima la tabella delle variabili locali

(lvar) e poi la tabella delle variabili globali (Gv) tramite lookup.

49

Mentre per le variabili globali il predicato ritorna l’indirizzo assoluto della locazione

di memoria, per le variabili locali sarà ritornato stack_bp(Addr) dove Addr, già

calcolato in tabella dal predicato setlocalvar, sarà uno spiazzamento positivo o

negativo a seconda che si tratti di un parametro di funzione o variabile locale.

Il predicato di ingresso dell’encoder è: encode2(X,Gv,Fv,(instr(jump,A);Y)):- lookup(main,Fv,A,nostr,_),encode(X,Gv,Fv,Y).

Come prima cosa crea nella tabella delle funzioni (Fv) la voce per la funzione main a

cui associa l’indirizzo A che verrà risolto dall’assemblatore, e poi codifica il resto del

programma ricorsivamente tramite il predicato encode.

Quindi X è la struttura passategli dal parser Gv è la tabella delle variabili globali, Fv

delle funzioni e Y è il codice rilocabile prodotto.

La funzione encode2 ritorna Y alla cui testa pone un salto incondizionato al punto di

ingresso del programma (main) perchè come abbiamo visto dall’analisi della

grammatica la funzione di ingresso può anche non essere la prima nell’ordine.

Il predicato encode quindi è nella forma encode (X,Gv,Fv,Y) dove X è l’input da

codificare e Y è il codice codificato. encode((X;Xs),Gv,Fv,(Y;Ys)):- encode(X,Gv,Fv,Y),

encode(Xs,Gv,Fv,Ys).

Il primo encode che troviamo si richiama ricorsivamente in modo da poter

processare un nodo della struttura dell’albero di parsing alla volta. encode(void,_,_,no_op).

alla foglia vuota dell’albero corrisponderà nessuna operazione (no_op). encode(halt,_,_,halt). encode(write_crlf,_,_,instr(write_crlf,0)).

Ad halt corrisponde halt. La stessa cosa con il ritorno a capo. encode(funz(Funz,X2),_,Fv,(label(Address);init_funz)):- setlocalpar(X2,Funz),lookup(Funz,Fv,Address,nostr,_),assert(lvarn(0)).

Ad una dichiarazione di funzione, ritorniamo un’etichetta (label) relativa al punto di

ingresso della funzione e init_funz che come abbiamo visto nel cap 3 inizializza

l’indirizzo dello stack per le eventuali variabili locali.

Viene anche aggiornata la tabella delle variabili locali con gli eventuali parametri

della funzione (setlocalpar), viene aggiornata la tabella delle funzioni con il nome

50

della funzione e la relativa label (lookup(Funz,Fv,Address,nostr,_)), e si

suppone per il momento nessuna variabile locale (assert(lvanr(0))). encode(local(X),_,_,create_local(N1)):- length(X,N),N1 is N*2,setlocalvar(X,_),retract(lvarn(0)),assert(lvarn(N1)).

Questo predicato sopra viene chiamato se si incontrano dichiarazioni di variabili

locali e ritorna all’encoder create_local(N1) dove N1 è la dimensione in bytes per

l’allocazione delle variabili nello stack.

Il predicato aggiunge le voci necessarie alla tabella delle variabili locali tramite

setlocalvar e aggiorna il predicato lvarn che tiene traccia della dimensione in

bytes delle variabili. encode(end_funz,_,_,(destroy_local(X);end_funz)):- lvarn(X),retractall(lvarn(_)),retractall(lvar(_,_,_)).

Questo predicato sopra viene chiamato quanto incontriamo la fine di una funzione.

All’encoder viene ritornato destroy_local(X) che come abbiamo visto cap 3

recupera lo spazio dallo stack delle variabili locali, e end_funz che recupera il base

pointer della funzione chiamante.

Il predicato cancella tutte le variabili dalla tabella della variabili locali lvar. encode(assign(E,Ex),Gv,_,(Code;instr(storep,Address))):- E=..[p,R|_],lookup2(R,Gv,Address,nostr,0),encode_expression(Ex,Gv,Code). encode(assign(Name,E),Gv,_,(Code;instr(store,Address))):- E=..[p1,R|_],lookup2(Name,Gv,Address,nostr,0),encode_ptr1(R,Gv,Code). encode(assign(Name,E),Gv,_,(Code;instr(store,Address))):- E=..[p2,R|_],lookup2(Name,Gv,Address,nostr,0),encode_ptr2(R,Gv,Code). encode(assign(Name,E),Gv,_,(Code;instr(store,Address))):- lookup2(Name,Gv,Address,nostr,0),encode_expression(E,Gv,Code).

I predicati sopra elencati codificano le assegnazioni di espressioni a variabili.

I primi tre sono dedicati ai puntatori mentre l’ultimo alle variabili semplici.

Vediamo come funziona la codifica per le assegnazioni a variabili semplici visto che

i principi sono gli stessi anche per i puntatori.

assign(Name,E) assegna a Name il valore dell’espressione E.

Come prima cosa recuperiamo l’indirizzo della variabile tramite il predicato

lookup2 codifichiamo la sequenza di operazioni per risolvere l’espressione tramite

encode_expression(E,Gv,Code) dove Code sarà tale codice.

51

Il predicato ritorna all’encoder la sequenza di istruzione per risolvere l’espressione

seguito dall’assegnazione di tale valore (che stà implicito nel registro accumulatore)

nella locazione della variabile (store Address).

Riportiamo di seguito i predicati che generano la sequenza di codice per la

risoluzione delle espressioni: encode_expression(mstring(X),Gv,instr(loadc,Address)):- lookup2(X,Gv,Address,mstring,X). encode_expression(number(C),_,instr(loadc,C)). encode_expression(name(X),Gv,instr(load,Address)):- lookup2(X,Gv,Address,nostr,_). encode_expression(expr(Op,E1,E2),Gv,(Load;Instruction)):- single_instruction(Op,E2,Gv,Instruction),encode_expression(E1,Gv,Load). encode_expression(expr(Op,E1,E2),Gv,Code):- \+single_instruction(Op,E2,Gv,_),single_operation(Op,E1,Gv,E2Code,Code),encode_expression(E2,Gv,E2Code). single_instruction(Op,number(C),_,instr(OpCode,C)):- literal_operation(Op,OpCode). single_instruction(Op,name(X),Gv,instr(OpCode,A)):- memory_operation(Op,OpCode),lookup2(X,Gv,A,_,_). single_operation(Op,E,Gv,Code,(Code;Instruction)):- commutative(Op),single_instruction(Op,E,Gv,Instruction). single_operation(Op,E,Gv,Code,(Code;instr(store,Address);Load;instr(OpCode,Address))):- \+commutative(Op),lookup('$temp',Gv,Address,_,_),encode_expression(E,Gv,Load),op_code(E,Op,OpCode). op_code(number(_),Op,OpCode):- literal_operation(Op,OpCode). op_code(name(_),Op,OpCode):- memory_operation(Op,OpCode). literal_operation('+',addc). literal_operation('-',subc). literal_operation('*',mulc). literal_operation('/',divc). memory_operation('+',add). memory_operation('-',sub). memory_operation('*',mul). memory_operation('/',div). commutative('+'). commutative('*').

Di seguito riportiamo i predicati relativi ai costrutti condizionali e ai loop: encode(if(Test,Then,Else),Gv,Fv,(TestCode;ThenCode;instr(jump,L2);label(L1);ElseCode;label(L2))):- encode_test(Test,L1,Gv,TestCode),encode(Then,Gv,Fv,ThenCode),encode(Else,Gv,Fv,ElseCode). encode(while(Test,Do),Gv,Fv,(label(L1);TestCode;DoCode;instr(jump,L1);label(L2))):- encode_test(Test,L2,Gv,TestCode), encode(Do,Gv,Fv,DoCode).

e

52

encode_test(compare(Op,E1,E2),Label,Gv,(Code;instr(OpCode,Label))):- comparison_opcode(Op,OpCode),encode_expression(expr('-',E1,E2),Gv,Code). comparison_opcode('==',jumpne). comparison_opcode('>',jumple). comparison_opcode('<',jumpge). comparison_opcode('!=',jumpeq). comparison_opcode('>=',jumplt). comparison_opcode('<=',jumpgt).

La codifica del costrutto condizionale if viene codificato con un test sulla

condizione, se questa è vera esegue ThenCode altrimenti esegue ElseCode.

Anche per il costrutto di loop la codifica ritornata all’encode è molto chiara: finche

la condizione Test è vera esegue il codice compreso tra label(L1) e

instr(jump,L1) altrimenti salta al punto di uscita L2.

L’output su schermo viene codificato semplicemente come vediamo dal codice

sottostante: encode(write(mstring(E)),Gv,_,(instr(loadc,Address);instr(write_str,0))):- name(E,W),append(W,[36],T),name(E2,T),lookup2(E2,Gv,Address,mstring,E2). encode(write(E),Gv,_,(Code;instr(write,0))):- encode_expression(E,Gv,Code). encode(write_str(mstring(E)),Gv,_,(instr(loadc,Address);instr(write_str,0))):- name(E,W),append(W,[36],T),name(E2,T),lookup2(E2,Gv,Address,mstring,E2).

Se l’elemento da stampare è una stringa allora appendi il carattere dollaro alla fine

della stringa (perchè nel codice macchina intel 80x86 utiliziamo l’interrupt 21 del

dos che stampa a video una stringa terminante con il carattere dollaro) aggiorniamo

le tabelle delle variabili con lookup2. in uscita all’encoder avremo lo pseudocodice

loadc Address e write_str che stamperà il contenuto del puntatore Address.

Se invece desideriamo stampare il valore di una variabile o di una espressione allora

risolviamo tale valore tramite il predicato encode_expression a cui apponiamo in

coda la pseudoistruzione per la stampa del valore di una variabile write.

Per la chiamata a funzione utiliziamo il seguente predicato. encode(callx(X1,X2),Gv,Fv,(Codepush;instr(call,A);destroy_local(N))):- lookup(X1,Fv,A,_,_),length(X2,M),N is M*2,codepush(X2,Gv,Codepush).

Questo come prima cosa risolve il nome della funzione tramite la tabella delle

funzioni (Fv) e calcolala lunghezza in bytes dei parametri da passare alla funzione

(N).

53

Il predicato ritorna all’encoder la serie di istruzioni che mettono i parametri nello

stack (codepush come abbiamo visto nella sezione precedente), la chiamata alla

funzione (instr(call,A)) ed infine la funzione chiamante deve liberare lo spazio

dello stack precedentemente assegnato ai parametri della funzione tramite destroy_local(N). Qualora la funzione debba ritornare un valore il seguente predicato viene invocato:

encode(return(X),Gv,_,(Code;destroy_local(N1);end_funz)):- encode_expression(X,Gv,Code),lvarn(N1).

In tale predicato si risolve il valore dell’espressione da ritornare, si distruggono le

variabili locali della funzione e si ripristina il valore del BP della funzione

chiamante.

Una volta tornati alla funzione chiamante il valore viene poi assegnato alla variabile

tramite il seguente predicato: encode(assignret(X),Gv,_,(instr(store,Address))):- lookup2(X,Gv,Address,nostr,0).

Si risolve l’indirizzo associato alla variabile nella tabella della variabili (lookup2) e

si assegna finalmente il valore a tale indirizzo (store Address).

Vediamo ora come l’encoder codifica l’albero di parsing rispettivamente per i

programmi somma e fattoriale di Figura 23 e 24: instr(jump, _G1053); ((label(_G1071);init_funz); (create_local(2); ((instr(load, stack_bp(6));instr(add, stack_bp(4)));instr(store, stack_bp(-2))); (instr(load, stack_bp(-2));destroy_local(2);end_funz);no_op); (destroy_local(2);end_funz);no_op); ((label(_G1053);init_funz); (((((instr(loadc, 1);instr(push, 0)); (instr(loadc, 3);instr(push, 0));no_op);instr(call, _G1071);destroy_local(4));instr(store, _G1250));no_op);halt;destroy_local(0);end_funz);no_op

e instr(jump, _G2182); ((label(_G2200);init_funz); ((instr(loadc, 5);destroy_local(0);end_funz);no_op); (destroy_local(0);end_funz); (label(_G2254);init_funz); (create_local(6); (((instr(load, stack_bp(4));instr(subc, 1));instr(jumpne, _G2337)); (instr(loadc, 1);destroy_local(6);end_funz);instr(jump, _G2332);label(_G2337);no_op;label(_G2332)); ((instr(load, stack_bp(4));instr(subc, 1));instr(store, stack_bp(-2))); ((((instr(load, stack_bp(-2));instr(push, 0));no_op);instr(call, _G2254);destroy_local(2));instr(store, stack_bp(-4))); ((instr(load, stack_bp(-4));instr(mul, stack_bp(4)));instr(store, stack_bp(-6))); (instr(load, stack_bp(-6));destroy_local(6);end_funz);no_op); (destroy_local(6);end_funz);no_op); ((label(_G2182);init_funz); (create_local(4); (instr(loadc, _G2551);instr(write_str,

54

0));instr(write_crlf, 0); ((((instr(loadc, 3);instr(push, 0));no_op);instr(call, _G2254);destroy_local(2));instr(store, stack_bp(-4))); (instr(load, stack_bp(-4));instr(write, 0));instr(write_crlf, 0); (((instr(load, stack_bp(-4));instr(subc, 100));instr(jumple, _G2677)); ((instr(loadc, 4);instr(store, stack_bp(-2)));no_op);instr(jump, _G2672);label(_G2677); (((no_op;instr(call, _G2200);destroy_local(0));instr(store, stack_bp(-2)));no_op);label(_G2672)); (label(_G2750); ((instr(load, stack_bp(-2));instr(subc, 0));instr(jumple, _G2764)); ((instr(load, stack_bp(-2));instr(write, 0));instr(write_crlf, 0); ((instr(load, stack_bp(-2));instr(subc, 1));instr(store, stack_bp(-2)));no_op);instr(jump, _G2750);label(_G2764));no_op);halt;destroy_local(4);end_funz);no_op

5.6 Il file ‘toIntel’

Il file toIntel raccoglie output dell’encoder che è pseudoassembler rilocabile e lo

trasforma in codice sorgente assembler per processori intel 80x86. Il codice generato

è ancora di tipo rilocabile, cioè fa riferimento alla tabella delle variabili anzichè ai

valori assoluti di zone di memoria che sono ancora da assegnare. Ad ogni pseudo

istruzione in ingresso si faranno corrispondere in uscita una o più istruzioni intel

80x86.

Il predicato di ingresso ha lo stesso nome del file di appartenenza toIntel. toIntel(Code,XCode2):- adj(Code,XCode),toIntel2(XCode,XCode2). adj(X,instr(push,cs);instr(pop,ds);X).

Come prima cosa il predicato toIntel chiama il predicato adj che tramite le

istruzione (push cs e pop ds) poste in cima al codice, assicura che il segmento dati

(DS) e il segmento codice (CS) corrispondano.

Ricordiamo che questo è necessario per il tipo di file prodotto dal mio compilatore.

Successivamente viene richiamato ricorsivamente il predicato toIntel2 che

converte tutto lo pseudo assembler in linguaggio assembler per processori della

famiglia intel 80x86. toIntel2((Code1;Code2),(X1;X2)):- toIntel2(Code1,X1),toIntel2(Code2,X2).

Il codice scritto sopra richiama ricorsivamente il predicato toIntel2 in modo da

processare una pseudo istruzione alla volta.

Il seguente predicato viene chiamato nel caso si voglia conoscere l’indirizzo di una

variabile locale, e tale valore è da ricercare nello stack tramite il base pointer.

55

toIntel2(instr(loadc,stack_bp(A)),(mov(ax,bp);add(ax,A))):- number(A).

Il predicato carica nel registro accumulatore il valore dell’indirizzo cercato.

Il seguente predicato carica nell’accumulatore il valore della variabile locale

desiderata: toIntel2(instr(load,stack_bp(A)),(mov(bx,bp);add(bx,A);mov(ax,[bx]))):- number(A).

dove A è un intero positivo o negativo ed è lo spiazzamento da sommare al registro

base pointer (BP).

Il seguente è lo stesso di quello sopra visto con la differenza che si lavora con

variabili puntatori anzichè intere: toIntel2(instr(loadp,stack_bp(A)),(mov(ax,bp);add(ax,A);mov(bx,ax);mov(ax,[bx]);mov(bx,ax);mov(ax,[bx]))):- number(A).

Il seguente predicato inserisce nella variabile locale il valore del registro

accumulatore: toIntel2(instr(store,stack_bp(A)),(mov(bx,bp);add(bx,A);mov([bx],ax))):- number(A).

I seguenti predicati convertono nell’ordine le seguenti pseudoistruzioni: addizionare

il contenuto dell’accumulatore con l’indirizzo della variabile locale, addizionare il

contenuto dell’accumulatore con il valore della variabile locale, sottrarre il contenuto

dell’accumulatore con l’indirizzo della variabile locale, sottrarre il contenuto

dell’accumulatore con il valore della variabile locale, moltiplicare il valore

dell’accumulatore con l’indirizzo della variabile locale, moltiplicare il valore

dell’accumulatore con il valore della variabile locale, dividere il valore

dell’accumulatore con l’indirizzo della variabile locale, ed infine dividere il valore

dell’accumulatore con il valore della variabile locale. toIntel2(instr(addc,stack_bp(A)),(mov(bx,bp);add(bx,A);add(ax,bx))):- number(A). toIntel2(instr(add,stack_bp(A)),(mov(bx,bp);add(bx,A);add(ax,[bx]))):- number(A). toIntel2(instr(subc,stack_bp(A)),(mov(bx,bp);add(bx,A);sub(ax,bx))):- number(A). toIntel2(instr(sub,stack_bp(A)),(mov(bx,bp);add(bx,A);sub(ax,[bx]))):- number(A). toIntel2(instr(mulc,stack_bp(A)),(mov(bx,bp);add(bx,A);mov(dx,0);instr(mul,bx))). toIntel2(instr(mul,stack_bp(A)),(instr(push,ax);mov(bx,bp);add(bx,A);mov(ax,[bx]);mov(bx,ax);mov(dx,0);instr(pop,ax);instr(mul,bx))):- number(A).

56

toIntel2(instr(divc,stack_bp(A)),(mov(bx,bp);add(bx,A);mov(dx,0);instr(div,bx))):- number(A). toIntel2(instr(div,stack_bp(A)),(instr(push,ax);mov(bx,bp);add(bx,A);mov(ax,[bx]);mov(bx,ax);mov(dx,0);instr(pop,ax);instr(div,bx))):- number(A).

dove A è di tipo intero positivo o negativo ed è lo spiazzamento da sommare al

registro base pointer (BP).

I seguenti predicati convertono nell’ordine le seguenti pseudoistruzioni:

carica nel registro accumulatore l’indirizzo di una variabile globale, carica nel

registro accumulatore il valore di una variabile globale. toIntel2(instr(loadc,A),mov(ax,A)). toIntel2(instr(load,A),mov(ax,[A])).

dove A è l’indirizzo di memoria della variabile.

I seguenti predicati convertono in assembler intel l’istruzione di salto incondizionato

e l’istruzione di chiamata a funzione: toIntel2(instr(jump,A),instr(jmp,A)). toIntel2(instr(call,A),instr(call,A)).

dove A è un indirizzo di memoria.

I seguenti predicati, dove A rappresenta un indirizzo di memoria relativo ad una

variabile globale, convertono in assembler intel le seguenti istruzioni nell’ordine:

caricare nel registro accumulatore il valore della locazione di memoria puntata dal

contenuto della variabile, inserire nella locazione di memoria della variabile il valore

dell’accumulatore, ed infine inserire nella locazione di memoria puntata dal valore

della variabile il valore dell’accumulatore. toIntel2(instr(loadp,A),(mov(bx,[A]);mov(ax,[bx]))). toIntel2(instr(store,A),mov([A],ax)). toIntel2(instr(storep,A),(mov(dx,ax);mov(bx,A);mov(ax,[bx]);instr(push,ax);instr(pop,bx);mov(ax,dx);mov([bx],ax))).

Il seguente predicato inserisce nello stack il valore dell’accumulatore: toIntel2(instr(push,0),instr(push,ax)).

I seguenti predicati convertono semplici operazioni aritmetiche tra accumulatore ed

indirizzo di una variabile globale. Il significato è identico alle operazione eseguite

dalle variabili locali. toIntel2(instr(addc,A),add(ax,A)). toIntel2(instr(add,A),add(ax,[A])). toIntel2(instr(subc,A),sub(ax,A)). toIntel2(instr(sub,A),sub(ax,[A])). toIntel2(instr(mulc,A),(mov(dx,0);mov(bx,A);instr(mul,bx))). toIntel2(instr(mul,A),(mov(dx,0);mov(bx,[A]);instr(mul,bx))).

57

toIntel2(instr(divc,A),(mov(dx,0);mov(bx,A);instr(div,bx))). toIntel2(instr(div,A),(mov(dx,0);mov(bx,[A]);instr(div,bx))).

Il seguente predicato converte in assembler intel l’istruzione di stampa a video del

valore di una variabile. toIntel2(instr(write,_),(mov(bx,10);xor(cx,cx);label(W1);xor(dx,dx);instr(div,bx);instr(push,dx);instr(inc,cx);or(ax,ax);instr(jumpne,W1);label(W2);instr(pop,dx);add(dl,48);mov(ah,2);instr(int,33);instr(loop,W2))).

Il principio su cui si basa è molto semplice. Tramite una seria di divisioni successive

per 10 (perchè vogliamo l’output in formato decimale) finche il dividendo è

maggiore di zero, mettiamo il resto della divisione nello stack.

A questo punto ci troveremo nello stack il numero da stampare cifra per cifra dalla

più significativa a quella meno significativa, che è proprio l’ordine in cui dobbiamo

stamparle. Ora con una serie di prelievi dallo stack stampiamo una cifra alla volta.

Il seguente predicato stampa a video una stringa: toIntel2(instr(write_str,_),(mov(dx,ax);mov(ah,9);instr(int,33))).

Basterà porre nel registro dx l’indirizzo di memoria da cui inizia la stringa da

stampare (che ricordiamo deve terminare con un carattere dollaro) e poi fare una

chiamata a funzione del sistema operativo MS-DOS tramite l’apposito int21h.

Ed infine le conversione necessarie alla gestione delle variabili locali nello stack

nonchè le istruzioni da eseguire ad ogni inizio e fine di una funzione sono già state

ampiamente spiegate nel cap 3: toIntel2(destroy_local(N),add(sp,N)). toIntel2(end_funz,(instr(pop,bp);instr(ret,0))). toIntel2(create_local(N),sub(sp,N)). toIntel2(init_funz,(instr(push,bp);mov(bp,sp))).

L’operazione di terminazione del programma halt viene tradotta anch’essa tramite

una chiamata a funzione del sistema operativo MS-DOS: l’int 20h che termina

immediatamente l’esecuzione del processo in corso. toIntel2(halt,instr(int,32)).

Vediamo qui di seguito l’output del predicato toIntel rispettivamente per i

programmi somma e fattoriale di Figura 23 e 24: instr(push, cs);instr(pop, ds);instr(jmp, _G1164); ((label(_G1182);instr(push, bp);mov(bp, sp)); (sub(sp, 2); (((mov(bx, bp);add(bx, 6);mov(ax, [bx]));mov(bx, bp);add(bx, 4);add(ax, [bx]));mov(bx, bp);add(bx, -2);mov([bx], ax)); ((mov(bx, bp);add(bx, -2);mov(ax, [bx]));add(sp, 2);instr(pop,

58

bp);instr(ret, 0));no_op); (add(sp, 2);instr(pop, bp);instr(ret, 0));no_op); ((label(_G1164);instr(push, bp);mov(bp, sp)); (((((mov(ax, 1);instr(push, ax)); (mov(ax, 3);instr(push, ax));no_op);instr(call, _G1182);add(sp, 4));mov([_G1361], ax));no_op);instr(int, 32);add(sp, 0);instr(pop, bp);instr(ret, 0));no_op

e instr(push, cs);instr(pop, ds);instr(jmp, _G2293); ((label(_G2311);instr(push, bp);mov(bp, sp)); ((mov(ax, 5);add(sp, 0);instr(pop, bp);instr(ret, 0));no_op); (add(sp, 0);instr(pop, bp);instr(ret, 0)); (label(_G2365);instr(push, bp);mov(bp, sp)); (sub(sp, 6); ((((mov(bx, bp);add(bx, 4);mov(ax, [bx]));sub(ax, 1));instr(jumpne, _G2448)); (mov(ax, 1);add(sp, 6);instr(pop, bp);instr(ret, 0));instr(jmp, _G2443);label(_G2448);no_op;label(_G2443)); (((mov(bx, bp);add(bx, 4);mov(ax, [bx]));sub(ax, 1));mov(bx, bp);add(bx, -2);mov([bx], ax)); (((((mov(bx, bp);add(bx, -2);mov(ax, [bx]));instr(push, ax));no_op);instr(call, _G2365);add(sp, 2));mov(bx, bp);add(bx, -4);mov([bx], ax)); (((mov(bx, bp);add(bx, -4);mov(ax, [bx]));instr(push, ax);mov(bx, bp);add(bx, 4);mov(ax, [bx]);mov(bx, ax);mov(dx, 0);instr(pop, ax);instr(mul, bx));mov(bx, bp);add(bx, -6);mov([bx], ax)); ((mov(bx, bp);add(bx, -6);mov(ax, [bx]));add(sp, 6);instr(pop, bp);instr(ret, 0));no_op); (add(sp, 6);instr(pop, bp);instr(ret, 0));no_op); ((label(_G2293);instr(push, bp);mov(bp, sp)); (sub(sp, 4); (mov(ax, _G2662);mov(dx, ax);mov(ah, 9);instr(int, 33)); (mov(dl, 13);mov(ah, 2);instr(int, 33);mov(dl, 10);mov(ah, 2);instr(int, 33)); ((((mov(ax, 3);instr(push, ax));no_op);instr(call, _G2365);add(sp, 2));mov(bx, bp);add(bx, -4);mov([bx], ax)); ((mov(bx, bp);add(bx, -4);mov(ax, [bx]));mov(bx, 10);cx xor cx;label(_G3588);dx xor dx;instr(div, bx);instr(push, dx);instr(inc, cx);or(ax, ax);instr(jumpne, _G3588);label(_G3629);instr(pop, dx);add(dl, 48);mov(ah, 2);instr(int, 33);instr(loop, _G3629)); (mov(dl, 13);mov(ah, 2);instr(int, 33);mov(dl, 10);mov(ah, 2);instr(int, 33)); ((((mov(bx, bp);add(bx, -4);mov(ax, [bx]));sub(ax, 100));instr(jumple, _G2788)); ((mov(ax, 4);mov(bx, bp);add(bx, -2);mov([bx], ax));no_op);instr(jmp, _G2783);label(_G2788); (((no_op;instr(call, _G2311);add(sp, 0));mov(bx, bp);add(bx, -2);mov([bx], ax));no_op);label(_G2783)); (label(_G2861); (((mov(bx, bp);add(bx, -2);mov(ax, [bx]));sub(ax, 0));instr(jumple, _G2875)); (((mov(bx, bp);add(bx, -2);mov(ax, [bx]));mov(bx, 10);cx xor cx;label(_G3895);dx xor dx;instr(div, bx);instr(push, dx);instr(inc, cx);or(ax, ax);instr(jumpne, _G3895);label(_G3936);instr(pop, dx);add(dl, 48);mov(ah, 2);instr(int, 33);instr(loop, _G3936)); (mov(dl, 13);mov(ah, 2);instr(int, 33);mov(dl, 10);mov(ah, 2);instr(int, 33)); (((mov(bx, bp);add(bx, -2);mov(ax, [bx]));sub(ax, 1));mov(bx, bp);add(bx, -2);mov([bx], ax));no_op);instr(jmp, _G2861);label(_G2875));no_op);instr(int, 32);add(sp, 4);instr(pop, bp);instr(ret, 0));no_op

5.7 Il file ‘assemble’

L’assemblatore.

59

L’assemblatore ha lo scopo di risolvere tutte le occorrenze in cui vi sia riferimento

ad una variabile o ad una zona di memoria.

Come input tutti i nomi delle variabili globali e delle funzioni fanno riferimento alle

relative tabelle di simboli. E tutte le istruzioni di salto fanno ancora riferimento ad

etichette generiche che devono essere ancora assegnate a locazioni corrette di

memoria.

L’assemblatore deve quindi sapere come viene mappato il file in memoria, qual’è

l’indirizzo di partenza e il peso di ciascuna istruzione del codice. Con pesi di una

istruzione intendo il numero di bytes necessari per la codifica ti tale istruzione in

codice macchina.

Una volta a conoscenza di questi dati, l’assemblatore è in grado di risolvere tutte le

occorrenze di variabili, funzioni e etichette.

In ingresso l’assemblatore accetta codice generato dall’encoder (encode) o dalla

conversione in assembler intel (toIntel) e in uscita produce il codice sia pseudo che

intel mappato coi giusti riferimenti delle variabili, funzioni e label a cui aggiunge in

coda le istruzione di allocazione per variabili globali interi o stringhe che siano.

L’assemblatore ha due porzioni di codice separate. La prima si riferisce

all’assemblaggio di pseudo codice preso dall’encoder, la seconda allo pseudocodice

convertito tramite il predicato toIntel.

L’assemblatore ha quindi due predicati di ingresso: assemble che si riferisce allo

pseudocodice e assemble2 che assembla codice intel.

La differenza principale tra i due assemblatori è che tutte le istruzione dello

pseudocodice hanno pesi di un byte, mentre le istruzioni intel possono avere pesi che

variano tra uno e quattro bytes.

Analizziamo gli assemblatori separatamente partendo da quello che assembla lo

pseudocodice (assemble). assemble(Code,D,_,TidyCode;Db;block(L)):- tidy_and_count(Code,1,N,TidyCode),N1 is N, allocate(D,N1,N2),L is N2-N1+1,getCode(D,Db),!.

Come si vede l’assemblaore di pseudocodice richiama tre predicati:

tidy_and_count che conta il numero di bytes dell’intero programma (N bytes) in

base al peso delle singole istruzioni e risolvendo i valori delle etichette e delle

funzioni, allocate che assegna alle variabili globali i giusti riferimenti in memoria,

ed infine getCode che letteralmente attacca lo spazio per le variabili globali in coda

al codice eventualmente assegnandogli il corretto valore di partenza.

60

Andiamo a vedere nel dettaglio questi tre predicati. tidy_and_count((Code1;Code2),M,N,SS;SS1):- tidy_and_count(Code1,M,M1,SS),tidy_and_count(Code2,M1,N,SS1).

tidy_and_count si richiama ricorsivamente in modo da processare una istruzione

alla volta.

M è l’indirizzo di partenza che essendo un linguaggio astratto che non può essere

eseguito da nessuna macchina pongo uguale ad 1 per una buona legibilità del codice,

N è il valore dell’ultimo byte di codice +1. tidy_and_count(instr(X,Y),N,N1,instr(X,Y)):- N1 is N+1. tidy_and_count(nop,N,N1,nop):- N1 is N+1. tidy_and_count(init_funz,N,N1,init_funz):- N1 is N+1. tidy_and_count(create_local(X),N,N1,create_local(X)):- N1 is N+1. tidy_and_count(destroy_local(X),N,N1,destroy_local(X)):- N1 is N+1. tidy_and_count(end_funz,N,N1,end_funz):- N1 is N+1. tidy_and_count(halt,N,N1,halt):- N1 is N+1.

Lo pseudo codice ha poche istruzioni appartenenti al suo linguaggio e la

maggiorparte elencata qui sopra ha peso 1.

La pseudo istruzione label ha peso zero, cioè non è considerata nel processo di

assemblaggio in quanto il valore del secondo argomento e quello del terzo

argomento del predicato hanno lo stesso valore, cioè ha una codifica di zero bytes. Il

predicato tidy_and_count applicato a tale pseudo istruzione risolve il valore

dell’etichetta: tidy_and_count(label(N),N,N,no_op).

L’istruzione no_op ha anch’essa peso zero (secondo e terzo parametro sono uguali) e

viene semplicemente ignorata: tidy_and_count(no_op,N,N,no_op).

Il predicato allocate visita l’albero binario che rappresenta la tabella delle variabili

globali, che ricordiamo è ordinato, ed assegna loro i valori della locazione di

memoria a partire dal byte successivo all’ultima istruzione del codice assemblato

incrementando il valore da assegnare alla successiva variabile dell’albero di 2 bytes

se si tratta di una variabile intera o puntatore, della lunghezza della stringa se la voce

della tabella è una stringa. allocate(void,N,N). allocate(dict(_,N1,mstring,V,Before,After),N0,N):- strlen(V,A),allocate(Before,N0,N1),N2 is N1+A,allocate(After,N2,N). allocate(dict(_,N1,_,_,Before,After),N0,N):- allocate(Before,N0,N1), N2 is N1+1, allocate(After,N2,N). strlen(X,Y):- name(X,F),length(F,Y).

61

Infine il predicato getCode, che è lo stesso per il processo di assemblaggio di pseudo

codice e codice intel, rivisita nuovamente l’albero binario ordinato delle variabili

globali e per ogni voce aggiunge in code al codice una istruzione che riserva tale

locazione di memoria alla variabile, istanziandola nel caso al valore corretto.

Il codice per gli interi che sono 2 bytes (1 parola) è dw: define word.

Il codice il byte è: db, define byte.

Il codice per le stringhe è: ds, define string. getCode(void,instr(db,0)). getCode(dict(_,_,mstring,V,void,void),instr(ds,V)). getCode(dict(_,_,nostr,V,void,void),instr(dw,V)). getCode(dict(_,_,mstring,V,void,After),(instr(ds,V);Db)):- getCode(After,Db). getCode(dict(_,_,nostr,V,void,After),(instr(dw,V);Db)):- getCode(After,Db). getCode(dict(_,_,mstring,V,Before,void),(Db;instr(ds,V))):- getCode(Before,Db). getCode(dict(_,_,nostr,V,Before,void),(Db;instr(dw,V))):- getCode(Before,Db). getCode(dict(_,_,mstring,V,Before,After),(Db1;instr(ds,V);Db2)):- getCode(Before,Db1),getCode(After,Db2). getCode(dict(_,_,nostr,V,Before,After),(Db1;instr(dw,V);Db2)):- getCode(Before,Db1),getCode(After,Db2).

Il codice per l’assemblaggio di un sorgente per processori intel percorre gli stessi

passi logici di quelli visti fino a qui dal predicato assemble. Tuttavia si utilizzano i

predicati: assemble2, tidy_and_count2, allocate2, mentre getCode rimane

invariato. assemble2(Code,Gv,_,TidyCode;Db;block(L)):- tidy_and_count2(Code,256,N,TidyCode),N1 is N, allocate2(Gv,N1,N2),L is N2-N1+1,getCode(Gv,Db),!.

Questi nuovi predicati riconoscono le parole del linguaggio intel e danno il giusto

peso alle singole istruzioni. tidy_and_count2((Code1;Code2),M,N,SS;SS1):- tidy_and_count2(Code1,M,M1,SS),tidy_and_count2(Code2,M1,N,SS1). tidy_and_count2(instr(push,X),N,N1,instr(push,X)):- N1 is N+1. tidy_and_count2(instr(pop,X),N,N1,instr(pop,X)):- N1 is N+1. tidy_and_count2(instr(int,X),N,N1,instr(int,X)):- N1 is N+2. tidy_and_count2(instr(jmp,X),N,N1,instr(jmp,X-N1)):- N1 is N+3. tidy_and_count2(instr(call,X),N,N1,instr(call,X-N1)):- N1 is N+3. tidy_and_count2(instr(loop,X),N,N1,instr(loop,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumpne,X),N,N1,instr(jumpne,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumple,X),N,N1,instr(jumple,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumpge,X),N,N1,instr(jumpge,X-N1)):- N1 is N+2.

62

tidy_and_count2(instr(jumpeq,X),N,N1,instr(jumpeq,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumplt,X),N,N1,instr(jumplt,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumpgt,X),N,N1,instr(jumpgt,X-N1)):- N1 is N+2. tidy_and_count2(instr(ret,A),N,N1,instr(ret,A)):- N1 is N+1. tidy_and_count2(instr(div,X),N,N1,instr(div,X)):- N1 is N+2. tidy_and_count2(instr(mul,X),N,N1,instr(mul,X)):- N1 is N+2. tidy_and_count2(instr(inc,A),N,N1,instr(inc,A)):- N1 is N+1. tidy_and_count2(instr(X,Y),N,N1,instr(X,Y)):- N1 is N+2. tidy_and_count2(label(N),N,N1,nop):- N1 is N+1. tidy_and_count2(no_op,N,N,no_op).%:- N1 is N+1. tidy_and_count2(nop,N,N1,nop):- N1 is N+1. tidy_and_count2(mov([A],ax),N,N1,mov([A],ax)):- \+number(A),nonvar(A),N1 is N+2. tidy_and_count2(mov([A],ax),N,N1,mov([A],ax)):- var(A),N1 is N+3. tidy_and_count2(mov(ax,A),N,N1,mov(ax,A)):- var(A),N1 is N+3. tidy_and_count2(mov(bx,A),N,N1,mov(bx,A)):- var(A),N1 is N+3. tidy_and_count2(mov(ah,X),N,N1,mov(ah,X)):- N1 is N+2. tidy_and_count2(mov(dl,A),N,N1,mov(dl,A)):- N1 is N+2. tidy_and_count2(mov(A,[B]),N,N1,mov(A,[B])):- \+number(A),var(B),nonvar(A),N1 is N+3. tidy_and_count2(mov(A,B),N,N1,mov(A,B)):- \+number(A),\+number(B),nonvar(A),nonvar(B),N1 is N+2. tidy_and_count2(mov(X,Y),N,N1,mov(X,Y)):- N1 is N+3. tidy_and_count2(sub(ax,[A]),N,N1,sub(ax,[A])):- \+number(A),nonvar(A),N1 is N+2. tidy_and_count2(sub(ax,bx),N,N1,sub(ax,bx)):- N1 is N+2. tidy_and_count2(sub(sp,A),N,N1,sub(sp,A)):- N1 is N+4. tidy_and_count2(sub(bx,A),N,N1,sub(bx,A)):- N1 is N+4. tidy_and_count2(sub(A,B),N,N1,sub(A,B)):- N1 is N+3. tidy_and_count2(add(dl,A),N,N1,add(dl,A)):- N1 is N+3. tidy_and_count2(add(sp,A),N,N1,add(sp,A)):- N1 is N+4. tidy_and_count2(add(bx,A),N,N1,add(bx,A)):- N1 is N+4. tidy_and_count2(add(ax,[A]),N,N1,add(ax,[A])):- \+number(A),nonvar(A),N1 is N+2. tidy_and_count2(add(ax,[bx]),N,N1,add(ax,[bx])):- N1 is N+2. tidy_and_count2(add(ax,bx),N,N1,add(ax,bx)):- N1 is N+2. tidy_and_count2(add(A,B),N,N1,add(A,B)):- N1 is N+3. tidy_and_count2(addr(A,B),N,N1,addr(A,B)):- N1 is N+2. tidy_and_count2(xor(A,B),N,N1,xor(A,B)):- N1 is N+2. tidy_and_count2(or(A,B),N,N1,or(A,B)):- N1 is N+2.

Come vediamo ogni istruzione ha un peso diverso a seconda di quanti bytes

serviranno per la sua codifica in linguaggio macchina per processori intel 80x86.

Ho scelto di codificate le istruzioni di label dando loro peso 1 e traducendole

nell’istruzione nop (no operation).

Da notare che alcune istruzioni del codice intel adottano un sistema di

indirizzamento relativo anzichè assoluto. Ciò avviene nelle istruzioni di salto

condizionato, incondizionato, chiamate a funzioni (call)e in loop.

Il principio di indirizzamento di queste istruzioni si basa su uno spiazzamento

positivo o negativo a partire dalla loro istruzione successiva.

Ad esempio sia:

63

100-mov ax,5 103-cmp ax,4 106-jne 1 108-inc ax 109-int 21h

dove i numeri a sinistra rappresentano gli indirizzi di memoria relativi all’istruzione.

All’indirizzo 106 abbiamo un salto condizionato di 1 byte a partire dall’istruzione

successiva (108) a quella del salto(106) se il valore del registro ax è 4, e quindi si

salterà all’indirizzo 109.

Nel processo di assembleggio al linguaggio assembler di intel ho scelto di

rappresentare tale indirizzo relativo tramite una differenza di indirizzi assoluti che

verrà poi risolta definitivamente nel processo di scrittura del codice macchina su file.

Quindi se abbiamo ad esempio una chiamata al predicato tidy_and_count2 con

instr(jmp,X) come istruzione da assemblare e N come indirizzo di tale istruzione e

X è un valore di memoria assoluto (sia X che N sono già istanziati!), allora viene

calcotalo N1=N+3 cioè il peso della istruzione di salto e N1 è il l’indirizzo della

prossima istruzione, e in uscita avremo instr(jmp,X-N1) che da uno spiazzamento

positivo o negativo a seconda dei valori della variabili in gioco, il cui valore verrà

effettivamente calcolato in fase di scrittura del codice macchina intel.

Molto importante è stato stabilire l’ordine corretto in cui trascrivere i predicati

tidy_and_count2 nella base di conoscenza del Prolog. Infatti qui si lavora ancora

con variabili Prolog e il non corretto ordine dei predicati nella base di conoscenza del

Prolog darebbe una errata scelta del predicato successivo da scegliere nel processo di

ricorsione. allocate2(void,N,N). allocate2(dict(_,N1,mstring,V,Before,After),N0,N):- strlen(V,A),allocate2(Before,N0,N1),N2 is N1+A,allocate2(After,N2,N). allocate2(dict(_,N1,_,_,Before,After),N0,N):- allocate2(Before,N0,N1), N2 is N1+2, allocate2(After,N2,N).

Il predicato allocate2 differisce da quello usato nell’assemblaggio dello

pseudocodice solo per il fatto che ad ogni variabile globale intera vengono assegnati

2 locazioni di memoria anziche 1.

Riportiamo qui di seguito l’output generato dall’assemblatore rispettivamente

nell’ordine per i programmi somma (pseudocodice poi intel) e

fattoriale(pseudocodice poi intel) di Figura 23 e 24: (instr(jump, 12); ((no_op;init_funz); (create_local(2); ((instr(load, stack_bp(6));instr(add, stack_bp(4)));instr(store,

64

stack_bp(-2))); (instr(load, stack_bp(-2));destroy_local(2);end_funz);no_op); (destroy_local(2);end_funz);no_op); ((no_op;init_funz); (((((instr(loadc, 1);instr(push, 0)); (instr(loadc, 3);instr(push, 0));no_op);instr(call, 2);destroy_local(4));instr(store, 23));no_op);halt;destroy_local(0);end_funz);no_op);instr(dw, 0);block(2)

e (instr(push, cs);instr(pop, ds);instr(jmp, 313-261); ((nop;instr(push, bp);mov(bp, sp)); (sub(sp, 2); (((mov(bx, bp);add(bx, 6);mov(ax, [bx]));mov(bx, bp);add(bx, 4);add(ax, [bx]));mov(bx, bp);add(bx, -2);mov([bx], ax)); ((mov(bx, bp);add(bx, -2);mov(ax, [bx]));add(sp, 2);instr(pop, bp);instr(ret, 0));no_op); (add(sp, 2);instr(pop, bp);instr(ret, 0));no_op); ((nop;instr(push, bp);mov(bp, sp)); (((((mov(ax, 1);instr(push, ax)); (mov(ax, 3);instr(push, ax));no_op);instr(call, 261-328);add(sp, 4));mov([343], ax));no_op);instr(int, 32);add(sp, 0);instr(pop, bp);instr(ret, 0));no_op);instr(dw, 0);block(3)

e (instr(jump, 33); ((no_op;init_funz); ((instr(loadc, 5);destroy_local(0);end_funz);no_op); (destroy_local(0);end_funz); (no_op;init_funz); (create_local(6); (((instr(load, stack_bp(4));instr(subc, 1));instr(jumpne, 17)); (instr(loadc, 1);destroy_local(6);end_funz);instr(jump, 17);no_op;no_op;no_op); ((instr(load, stack_bp(4));instr(subc, 1));instr(store, stack_bp(-2))); ((((instr(load, stack_bp(-2));instr(push, 0));no_op);instr(call, 8);destroy_local(2));instr(store, stack_bp(-4))); ((instr(load, stack_bp(-4));instr(mul, stack_bp(4)));instr(store, stack_bp(-6))); (instr(load, stack_bp(-6));destroy_local(6);end_funz);no_op); (destroy_local(6);end_funz);no_op); ((no_op;init_funz); (create_local(4); (instr(loadc, 68);instr(write_str, 0));instr(write_crlf, 0); ((((instr(loadc, 3);instr(push, 0));no_op);instr(call, 8);destroy_local(2));instr(store, stack_bp(-4))); (instr(load, stack_bp(-4));instr(write, 0));instr(write_crlf, 0); (((instr(load, stack_bp(-4));instr(subc, 100));instr(jumple, 52)); ((instr(loadc, 4);instr(store, stack_bp(-2)));no_op);instr(jump, 55);no_op; (((no_op;instr(call, 2);destroy_local(0));instr(store, stack_bp(-2)));no_op);no_op); (no_op; ((instr(load, stack_bp(-2));instr(subc, 0));instr(jumple, 65)); ((instr(load, stack_bp(-2));instr(write, 0));instr(write_crlf, 0); ((instr(load, stack_bp(-2));instr(subc, 1));instr(store, stack_bp(-2)));no_op);instr(jump, 55);no_op);no_op);halt;destroy_local(4);end_funz);no_op);instr(ds, prog1$);block(7)

e (instr(push, cs);instr(pop, ds);instr(jmp, 411-261); ((nop;instr(push, bp);mov(bp, sp)); ((mov(ax, 5);add(sp, 0);instr(pop, bp);instr(ret, 0));no_op); (add(sp, 0);instr(pop, bp);instr(ret, 0)); (nop;instr(push, bp);mov(bp, sp)); (sub(sp, 6); ((((mov(bx, bp);add(bx, 4);mov(ax, [bx]));sub(ax,

65

1));instr(jumpne, 313-301)); (mov(ax, 1);add(sp, 6);instr(pop, bp);instr(ret, 0));instr(jmp, 314-313);nop;no_op;nop); (((mov(bx, bp);add(bx, 4);mov(ax, [bx]));sub(ax, 1));mov(bx, bp);add(bx, -2);mov([bx], ax)); (((((mov(bx, bp);add(bx, -2);mov(ax, [bx]));instr(push, ax));no_op);instr(call, 280-346);add(sp, 2));mov(bx, bp);add(bx, -4);mov([bx], ax)); (((mov(bx, bp);add(bx, -4);mov(ax, [bx]));instr(push, ax);mov(bx, bp);add(bx, 4);mov(ax, [bx]);mov(bx, ax);mov(dx, 0);instr(pop, ax);instr(mul, bx));mov(bx, bp);add(bx, -6);mov([bx], ax)); ((mov(bx, bp);add(bx, -6);mov(ax, [bx]));add(sp, 6);instr(pop, bp);instr(ret, 0));no_op); (add(sp, 6);instr(pop, bp);instr(ret, 0));no_op); ((nop;instr(push, bp);mov(bp, sp)); (sub(sp, 4); (mov(ax, 642);mov(dx, ax);mov(ah, 9);instr(int, 33)); (mov(dl, 13);mov(ah, 2);instr(int, 33);mov(dl, 10);mov(ah, 2);instr(int, 33)); ((((mov(ax, 3);instr(push, ax));no_op);instr(call, 280-447);add(sp, 2));mov(bx, bp);add(bx, -4);mov([bx], ax)); ((mov(bx, bp);add(bx, -4);mov(ax, [bx]));mov(bx, 10);cx xor cx;nop;dx xor dx;instr(div, bx);instr(push, dx);instr(inc, cx);or(ax, ax);instr(jumpne, 472-483);nop;instr(pop, dx);add(dl, 48);mov(ah, 2);instr(int, 33);instr(loop, 483-494)); (mov(dl, 13);mov(ah, 2);instr(int, 33);mov(dl, 10);mov(ah, 2);instr(int, 33)); ((((mov(bx, bp);add(bx, -4);mov(ax, [bx]));sub(ax, 100));instr(jumple, 533-519)); ((mov(ax, 4);mov(bx, bp);add(bx, -2);mov([bx], ax));no_op);instr(jmp, 549-533);nop; (((no_op;instr(call, 261-537);add(sp, 0));mov(bx, bp);add(bx, -2);mov([bx], ax));no_op);nop); (nop; (((mov(bx, bp);add(bx, -2);mov(ax, [bx]));sub(ax, 0));instr(jumple, 633-564)); (((mov(bx, bp);add(bx, -2);mov(ax, [bx]));mov(bx, 10);cx xor cx;nop;dx xor dx;instr(div, bx);instr(push, dx);instr(inc, cx);or(ax, ax);instr(jumpne, 577-588);nop;instr(pop, dx);add(dl, 48);mov(ah, 2);instr(int, 33);instr(loop, 588-599)); (mov(dl, 13);mov(ah, 2);instr(int, 33);mov(dl, 10);mov(ah, 2);instr(int, 33)); (((mov(bx, bp);add(bx, -2);mov(ax, [bx]));sub(ax, 1));mov(bx, bp);add(bx, -2);mov([bx], ax));no_op);instr(jmp, 550-633);nop);no_op);instr(int, 32);add(sp, 4);instr(pop, bp);instr(ret, 0));no_op);instr(ds, prog1$);block(7)

.

5.8 Il file ‘toStream’

Dopo la fase di assemblaggio svolta dai predicati assemble o assemble2 a seconda

che si voglia rispettivamente uno pseudocodice assembler o un codice assembler per

processori intel, si possono scegliere due strade: la prima trasforma il sorgente

assembler per intel direttamente in codice macchina scrivendo su file, la seconda

strada stampa a video il sorgente assembler pseudo o intel indifferentemente.

Quest’ultimo compito è svolto dal predicato toStream che prende in ingresso

indipendentemente lo pseudoassembler o l’assembler di intel e lo stampa a video

riformattandolo.

Il predicato di ingresso è: toStream((Code1;Code2)):- toStream(Code1),toStream(Code2).

66

che si richiama ricorsivamente processando una istruzione alla volta. toStream(instr(X,Y)):- write(X),write(' '),write(Y),nl.

Il predicato scritto sopra stampa a video la generica istruzione (pseudo o intel). Tale

istruzione è composta dai parametri della funzione instr. Quindi sia instr(push,0)

l’istruzione da processare, si stamperà a video ‘push 0’.

I seguenti predicati processano istruzioni esclusivamente intel: toStream(X):- X=..[mov,A,B|_],write('mov '),write(A),write(','),write(B),nl. toStream(X):- X=..[sub,A,B|_],write('sub '),write(A),write(','),write(B),nl. toStream(X):- X=..[add,A,B|_],write('add '),write(A),write(','),write(B),nl. toStream(X):- X=..[xor,A,B|_],write('xor '),write(A),write(','),write(B),nl. toStream(X):- X=..[or,A,B|_],write('or '),write(A),write(','),write(B),nl. toStream(X):- X=..[movr,A,B|_],write('mov '),write(A),write(','),write(B),nl. toStream(X):- X=..[addr,A,B|_],write('add '),write(A),write(','),write(B),nl.

Qui si fa uso del predicato Prolog univ (=..) che scompone un predicato e i suoi

argomenti in una lista. Prendiamo ad esempio il predicato p(a,b). Applicando su di

esso il predicato Prolog univ lo scomponiamo nella seguente lista [p,a,b].

Quindi i predicati sopra scritti scompongono l’istruzione in una lista e ne stampa a

video gli elementi formattandoli.

Infine il seguente predicato stampa il resto delle istruzioni assembler che non

richiedono una riformattazione di output: toStream(X):- write(X),nl.

5.9 Il file ‘toCode’

l’ultimo file del compilatore prende in input il codice sorgente per processori di tipo

intel 80x86 e ne produce il codice macchina scrivendo su file.

Come abbiamo più volte detto il file prodotto è un eseguibile in ambiente MS-DOS o

shell di windows di tipo .COM, cioè un tipo di file senza alcun heather che viene

mappato semplicemente in memoria.

Il predicato di ingresso è.

67

toCode(I,File):- tell(File),tc(I),told.

Tale predicato ridirige l’output su file (tell(File)), ci scrive il codice macchina

(tc(I)), e chiude il file ripristinando lo standard output (told).

Il seguente predicato (tc) si richiama ricorsivamente processando una istruzione alla

volta: tc((Code1;Code2)):- tc(Code1),tc(Code2).

Come si vede dai seguenti predicati, ogni istruzione del sorgente assembler intel

viene tradotto nel relativo codice macchina, e questo viete scritto su file tramite il

predicato Prolog put. tc(instr(push,cs)):- put(14). tc(instr(push,ax)):- put(80). tc(instr(pop,ds)):- put(31). tc(instr(push,bp)):- put(85). tc(instr(pop,bp)):- put(93). tc(mov(bx,ax)):- put(137),put(195). tc(mov(ax,bp)):- put(137),put(232). tc(mov(ax,bx)):- put(137),put(216). tc(mov(ax,dx)):- put(137),put(208). tc(mov(bx,bp)):- put(137),put(235). tc(mov(bx,[A])):- put(139),put(30),splitta(A,H,L),put(L),put(H). tc(mov(bx,A)):- put(187),splitta(A,H,L),put(L),put(H). tc(mov(ax,[bx])):- put(139),put(7). tc(mov(ax,[A])):- put(161),splitta(A,H,L),put(L),put(H). tc(mov(ax,A)):- put(184),splitta(A,H,L),put(L),put(H). tc(mov([bx],ax)):- put(137),put(7). tc(mov([A],ax)):- put(163),splitta(A,H,L),put(L),put(H). tc(instr(jmp,A)):- put(233),Y is A,splitta(Y,H,L),put(L),put(H). tc(instr(call,A)):- put(232),Y is A,splitta(Y,H,L),put(L),put(H). tc(instr(ret,0)):- put(195). tc(nop):- put(144). tc(block(_)):- put(144). tc(instr(int,A)):- put(205),put(A). tc(mov(dx,ax)):- put(137),put(194). tc(mov(dx,A)):- put(186),splitta(A,H,L),put(L),put(H). tc(mov(ah,A)):- put(180),put(A). tc(mov(bp,sp)):- put(137),put(229). tc(mov(sp,bp)):- put(137),put(236). tc(instr(mul,bx)):- put(247),put(227). tc(instr(div,bx)):- put(247),put(243). tc(addr(ax,dx)):- put(1),put(208). tc(add(ax,[bx])):- put(3),put(7). tc(add(ax,bx)):- put(1),put(216). tc(add(ax,A)):- put(5),splitta(A,H,L),put(L),put(H). tc(add(sp,A)):- put(129),put(196),splitta(A,H,L),put(L),put(H). tc(add(bx,A)):- put(129),put(195),splitta(A,H,L),put(L),put(H). tc(sub(ax,[bx])):- put(41),put(7). tc(sub(ax,bx)):- put(41),put(8). tc(sub(ax,[A])):- put(43),put(6),splitta(A,H,L),put(L),put(H). tc(sub(ax,A)):- put(45),splitta(A,H,L),put(L),put(H). tc(add(ax,[A])):- put(3),put(6),splitta(A,H,L),put(L),put(H). tc(sub(sp,A)):- put(129),put(236),splitta(A,H,L),put(L),put(H). tc(sub(ax,A)):- put(129),put(235),splitta(A,H,L),put(L),put(H). tc(instr(dw,A)):- splitta(A,H,L),put(L),put(H). tc(instr(ds,A)):- write(A). tc(instr(db,A)):- put(A). tc(instr(jumpne,A)):- put(117),Y is A,neg_byte(Y,B),put(B).

68

tc(instr(jumple,A)):- put(126),Y is A,neg_byte(Y,B),put(B). tc(instr(jumpge,A)):- put(125),Y is A,neg_byte(Y,B),put(B). tc(instr(jumpeq,A)):- put(116),Y is A,neg_byte(Y,B),put(B). tc(instr(jumplt,A)):- put(124),Y is A,neg_byte(Y,B),put(B). tc(instr(jumpgt,A)):- put(127),Y is A,neg_byte(Y,B),put(B). tc(mov(dl,A)):- put(178),neg_byte(A,B),put(B). tc(instr(pop,bx)):- put(91). tc(instr(inc,cx)):- put(65). tc(instr(push,dx)):- put(82). tc(xor(dx,dx)):- put(49),put(210). tc(xor(cx,cx)):- put(49),put(201). tc(or(ax,ax)):- put(9),put(192). tc(instr(pop,dx)):- put(90). tc(add(dl,A)):- put(128),put(194),neg_byte(A,B),put(B). tc(instr(loop,A)):- put(226),Y is A,neg_byte(Y,B),put(B). tc(mov(cx,[bx])):- put(139),put(15). tc(instr(inc,bx)):- put(67). tc(instr(push,cx)):- put(81). tc(instr(pop,cx)):- put(89). tc(instr(pop,ax)):- put(88). tc(no_op).

Il predicato Prolog put(Char) scrive sull’output corrente (nel nostro caso è stato

ridiretto al file) il valore (Char) ed è stato pensato per scrivere simboli tramite il

corrispondente codice ASCII. Quindi il valore di Char è compreso tra zero e 255. Ad

esempio put(65) scriverà il valore 65 che ad esempio è il codice ASCII della lettera

A.

Nella scrittura del codice macchina bisogna fare attenzione all’architettura del

calcolatore. In particolare a come vengono trattati i numeri negativi e a come

vengono memorizzati gli interi che corrispondono a 2 bytes.

Il calcolatore per natura memorizza una sequenza di bit che codificano in base due

un numero naturale (intero positivo) . per interpretare come negativo si dedica il bit

più significativo al ruolo di bit di segno, così se tale bit è settato ad uno il numero in

questione è negativo, altrimenti è positivo.

Facciamo un esempio e supponiamo che un calcolatore lavori a tre bit che codificano

i numeri da zero (000) a sette (111). Allora i numeri positivi avranno il bit più

significativo a zero (0[000], 1[001], 2[010], 3[011]) e i numeri positivi avranno il bit

di segno settato ad uno (-3[111], -2[110], -1[101], -4[100]) e l’intervallo riconosciuto

dal calcolatore sarà compreso tra -4 e +3.

Siccome lavorare con i bit in Prolog è molto malsano, possiamo pensare che il

calcolatore ipotetico visto qui sopra lavori in modulo 8.

Quindi riconosca tutti i numeri tra 0 e 7 e ad 8 è congruo a zero (8=0 mod 8).

Noi sappiamo che -1+1=0. se lavoriamo in modulo 8 avremo che 7+1=8=0.

Quindi in modulo otto, 7 è congruo a -1.

69

Questo è il principio che adotta il predicato neg_byte del mio compilatore per

codificate i numeri negativi in codice macchina intel.

Sia X uni numero negativo compreso tra -128 e -1 allora questo viene codificato

tramite l’espressione 256-X. Cioè per rappresentare i bytes negativi lavoriamo in

modulo 256. Per rappresentare gli interi negativi lavoreremo in modulo 65536. neg_byte(A,B):- A<0, B is 256+A. neg_byte(A,A).

L’ultimo punto da illustrare è come il calcolatore memorizza gli interi (che sono

composti da 2 bytes).

I processori intel sono detti little endian, cioè dei due bytes che compongono la

parola, viene memorizzato prima il byte meno significativo e poi il byte più

significativo.

Quindi se dobbiamo memorizzare il numero decimale 7973 che corrisponde al

numero 1F25 esadecimale, dove 1F è il byte più significativo e 25 è il byte meno

significativo, questo verrà memorizzato così: 251F.

Questo è il lavoro svolto dal predicato splitta: splitta(N,Hi,Lo):- N<0, N1 is 65536+N, Hi is N1//256, Lo is N1 mod 256. splitta(N,Hi,Lo):- Hi is N//256, Lo is N mod 256.

che accetta tre parametri: N è il numero da convertire, Hi è il relativo byte più

significativo, e Lo è il relativo byte meno significativo.

70

Capitolo 6 Il codice sorgente

1) Il file ‘assemble’. assemble(Code,D,_,TidyCode;Db;block(L)):- tidy_and_count(Code,1,N,TidyCode),N1 is N, allocate(D,N1,N2),L is N2-N1+1,getCode(D,Db),!. tidy_and_count((Code1;Code2),M,N,SS;SS1):- tidy_and_count(Code1,M,M1,SS),tidy_and_count(Code2,M1,N,SS1). tidy_and_count(instr(X,Y),N,N1,instr(X,Y)):- N1 is N+1. tidy_and_count(label(N),N,N,no_op).%:- N1 is N+1. tidy_and_count(no_op,N,N,no_op).%:- N1 is N+1. tidy_and_count(nop,N,N1,nop):- N1 is N+1. tidy_and_count(init_funz,N,N1,init_funz):- N1 is N+1. tidy_and_count(create_local(X),N,N1,create_local(X)):- N1 is N+1. tidy_and_count(destroy_local(X),N,N1,destroy_local(X)):- N1 is N+1. tidy_and_count(end_funz,N,N1,end_funz):- N1 is N+1. tidy_and_count(halt,N,N1,halt):- N1 is N+1. allocate(void,N,N). allocate(dict(_,N1,mstring,V,Before,After),N0,N):- strlen(V,A),allocate(Before,N0,N1),N2 is N1+A,allocate(After,N2,N). allocate(dict(_,N1,_,_,Before,After),N0,N):- allocate(Before,N0,N1), N2 is N1+1, allocate(After,N2,N). strlen(X,Y):- name(X,F),length(F,Y). %%%%% assemble2(Code,Gv,_,TidyCode;Db;block(L)):- tidy_and_count2(Code,256,N,TidyCode),N1 is N, allocate2(Gv,N1,N2),L is N2-N1+1,getCode(Gv,Db),!. tidy_and_count2((Code1;Code2),M,N,SS;SS1):- tidy_and_count2(Code1,M,M1,SS),tidy_and_count2(Code2,M1,N,SS1). tidy_and_count2(instr(push,X),N,N1,instr(push,X)):- N1 is N+1. tidy_and_count2(instr(pop,X),N,N1,instr(pop,X)):- N1 is N+1. tidy_and_count2(instr(int,X),N,N1,instr(int,X)):- N1 is N+2. tidy_and_count2(instr(jmp,X),N,N1,instr(jmp,X-N1)):- N1 is N+3. tidy_and_count2(instr(call,X),N,N1,instr(call,X-N1)):- N1 is N+3. tidy_and_count2(instr(loop,X),N,N1,instr(loop,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumpne,X),N,N1,instr(jumpne,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumple,X),N,N1,instr(jumple,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumpge,X),N,N1,instr(jumpge,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumpeq,X),N,N1,instr(jumpeq,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumplt,X),N,N1,instr(jumplt,X-N1)):- N1 is N+2. tidy_and_count2(instr(jumpgt,X),N,N1,instr(jumpgt,X-N1)):- N1 is N+2. tidy_and_count2(instr(ret,A),N,N1,instr(ret,A)):- N1 is N+1.

71

tidy_and_count2(instr(div,X),N,N1,instr(div,X)):- N1 is N+2. tidy_and_count2(instr(mul,X),N,N1,instr(mul,X)):- N1 is N+2. tidy_and_count2(instr(inc,A),N,N1,instr(inc,A)):- N1 is N+1. tidy_and_count2(instr(X,Y),N,N1,instr(X,Y)):- N1 is N+2. tidy_and_count2(label(N),N,N1,nop):- N1 is N+1. tidy_and_count2(no_op,N,N,no_op).%:- N1 is N+1. tidy_and_count2(nop,N,N1,nop):- N1 is N+1. tidy_and_count2(mov([A],ax),N,N1,mov([A],ax)):- \+number(A),nonvar(A),N1 is N+2. tidy_and_count2(mov([A],ax),N,N1,mov([A],ax)):- var(A),N1 is N+3. %tidy_and_count2(mov(ax,A),N,N1,mov(ax,A)):- length(,N1 is N+3. tidy_and_count2(mov(ax,A),N,N1,mov(ax,A)):- var(A),N1 is N+3. tidy_and_count2(mov(bx,A),N,N1,mov(bx,A)):- var(A),N1 is N+3. tidy_and_count2(mov(ah,X),N,N1,mov(ah,X)):- N1 is N+2. tidy_and_count2(mov(dl,A),N,N1,mov(dl,A)):- N1 is N+2. tidy_and_count2(mov(A,[B]),N,N1,mov(A,[B])):- \+number(A),var(B),nonvar(A),N1 is N+3. tidy_and_count2(mov(A,B),N,N1,mov(A,B)):- \+number(A),\+number(B),nonvar(A),nonvar(B),N1 is N+2. %tidy_and_count2(movr(dx,ax),N,N1,movr(dx,ax)):- N1 is N+2. %tidy_and_count2(mov(bp,sp),N,N1,mov(bp,sp)):- N1 is N+2. %tidy_and_count2(mov(sp,bp),N,N1,mov(sp,bp)):- N1 is N+2. %tidy_and_count2(mov(ax,bp),N,N1,mov(ax,bp)):- N1 is N+2. %tidy_and_count2(mov(bx,bp),N,N1,mov(bx,sp)):- N1 is N+2. %tidy_and_count2(mov(ax,bx),N,N1,mov(ax,bx)):- N1 is N+2. %tidy_and_count2(mov(bx,ax),N,N1,mov(bx,ax)):- N1 is N+2. tidy_and_count2(mov(X,Y),N,N1,mov(X,Y)):- N1 is N+3. tidy_and_count2(sub(ax,[A]),N,N1,sub(ax,[A])):- \+number(A),nonvar(A),N1 is N+2. tidy_and_count2(sub(ax,bx),N,N1,sub(ax,bx)):- N1 is N+2. tidy_and_count2(sub(sp,A),N,N1,sub(sp,A)):- N1 is N+4. tidy_and_count2(sub(bx,A),N,N1,sub(bx,A)):- N1 is N+4. tidy_and_count2(sub(A,B),N,N1,sub(A,B)):- N1 is N+3. tidy_and_count2(add(dl,A),N,N1,add(dl,A)):- N1 is N+3. tidy_and_count2(add(sp,A),N,N1,add(sp,A)):- N1 is N+4. tidy_and_count2(add(bx,A),N,N1,add(bx,A)):- N1 is N+4. tidy_and_count2(add(ax,[A]),N,N1,add(ax,[A])):- \+number(A),nonvar(A),N1 is N+2. tidy_and_count2(add(ax,[bx]),N,N1,add(ax,[bx])):- N1 is N+2. tidy_and_count2(add(ax,bx),N,N1,add(ax,bx)):- N1 is N+2. tidy_and_count2(add(A,B),N,N1,add(A,B)):- N1 is N+3. tidy_and_count2(addr(A,B),N,N1,addr(A,B)):- N1 is N+2. tidy_and_count2(xor(A,B),N,N1,xor(A,B)):- N1 is N+2. tidy_and_count2(or(A,B),N,N1,or(A,B)):- N1 is N+2. allocate2(void,N,N). allocate2(dict(_,N1,mstring,V,Before,After),N0,N):- strlen(V,A),allocate2(Before,N0,N1),N2 is N1+A,allocate2(After,N2,N). allocate2(dict(_,N1,_,_,Before,After),N0,N):- allocate2(Before,N0,N1), N2 is N1+2, allocate2(After,N2,N). getCode(void,instr(db,0)). getCode(dict(_,_,mstring,V,void,void),instr(ds,V)). getCode(dict(_,_,nostr,V,void,void),instr(dw,V)). getCode(dict(_,_,mstring,V,void,After),(instr(ds,V);Db)):- getCode(After,Db). getCode(dict(_,_,nostr,V,void,After),(instr(dw,V);Db)):- getCode(After,Db). getCode(dict(_,_,mstring,V,Before,void),(Db;instr(ds,V))):- getCode(Before,Db).

72

getCode(dict(_,_,nostr,V,Before,void),(Db;instr(dw,V))):- getCode(Before,Db). getCode(dict(_,_,mstring,V,Before,After),(Db1;instr(ds,V);Db2)):- getCode(Before,Db1),getCode(After,Db2). getCode(dict(_,_,nostr,V,Before,After),(Db1;instr(dw,V);Db2)):- getCode(Before,Db1),getCode(After,Db2).

2) Il file ‘compiler’ load:- consult('lexan'),consult('parser2'),consult('encode2'),consult('assemble2'),consult('tostream'), consult('tointel'),consult('tocode'),consult('symtab'),assert(lvar(zar,_,_)),retract(lvar(zar,_,_)). compile(File,warren,debug):- toklist(File,Tl),write(Tl),nl,parse(Tl,Temp1),write(Temp1),nl,encode2(Temp1,Gv,Fv,Code),write(Code),nl,assemble(Code,Gv,Fv,Out),write(Out),nl,!. compile(File,warren,toScreen):- toklist(File,A),parse(A,B),encode2(B,Gv,Fv,C),assemble(C,Gv,Fv,E),toStream(E). compile(File,intelSrc,toScreen):- toklist(File,A),parse(A,B),encode2(B,Gv,Fv,C),toIntel(C,H),assemble2(H,Gv,Fv,E),toStream(E). compile(File,intelCode,FileOut):- toklist(File,A),parse(A,B),encode2(B,Gv,Fv,C),toIntel(C,H),assemble2(H,Gv,Fv,E),toCode(E,FileOut). compile(File,X,Y):- tell(Y),compile(File,X,toScreen),told.

3) Il file ‘encode2’ lookup2(Nome,_,stack_bp(Addr),nostr,_):- lvar(Nome,_,Addr). lookup2(Nome,Alf,Addr,Type,Val):- lookup(Nome,Alf,Addr,Type,Val). lookup(Key,dict(Key,X,Y,Z,_,_),Value,Type,Val):- !,X = Value,Y=Type,Z=Val. lookup(Key,dict(Key1,_,_,_,Left,_),Value,Type,Val):- Key@<Key1, lookup(Key,Left,Value,Type,Val). lookup(Key,dict(Key1,_,_,_,_,Right),Value,Type,Val):- Key@>Key1, lookup(Key,Right,Value,Type,Val). %lookup(Key,[(Key,Value)|Dict],Value):- !. %lookup(Key,[(Key1,Value1)|Dict],Value):- Key\==Key1,lookup(Key,Dict,Value). %mstring(X):- atom(X). encode2(X,Gv,Fv,(instr(jump,A);Y)):- lookup(main,Fv,A,nostr,_),encode(X,Gv,Fv,Y). encode((X;Xs),Gv,Fv,(Y;Ys)):- encode(X,Gv,Fv,Y), encode(Xs,Gv,Fv,Ys). encode(void,_,_,no_op). encode(halt,_,_,halt). encode(write_crlf,_,_,instr(write_crlf,0)). encode(funz(Funz,X2),_,Fv,(label(Address);init_funz)):- setlocalpar(X2,Funz),lookup(Funz,Fv,Address,nostr,_),assert(lvarn(0)). encode(local(X),_,_,create_local(N1)):- length(X,N),N1 is N*2,setlocalvar(X,_),retract(lvarn(0)),assert(lvarn(N1)). %encode(end_funz,_,_,no_op):- lvarn(0). encode(end_funz,_,_,(destroy_local(X);end_funz)):- lvarn(X),retractall(lvarn(_)),retractall(lvar(_,_,_)). encode(assign(E,Ex),Gv,_,(Code;instr(storep,Address))):- E=..[p,R|_],lookup2(R,Gv,Address,nostr,0),encode_expression(Ex,Gv,Code).

73

encode(assign(Name,E),Gv,_,(Code;instr(store,Address))):- E=..[p1,R|_],lookup2(Name,Gv,Address,nostr,0),encode_ptr1(R,Gv,Code). encode(assign(Name,E),Gv,_,(Code;instr(store,Address))):- E=..[p2,R|_],lookup2(Name,Gv,Address,nostr,0),encode_ptr2(R,Gv,Code). encode(assign(Name,E),Gv,_,(Code;instr(store,Address))):- lookup2(Name,Gv,Address,nostr,0),encode_expression(E,Gv,Code). encode(if(Test,Then,Else),Gv,Fv,(TestCode;ThenCode;instr(jump,L2);label(L1);ElseCode;label(L2))):- encode_test(Test,L1,Gv,TestCode),encode(Then,Gv,Fv,ThenCode),encode(Else,Gv,Fv,ElseCode). encode(while(Test,Do),Gv,Fv,(label(L1);TestCode;DoCode;instr(jump,L1);label(L2))):- encode_test(Test,L2,Gv,TestCode), encode(Do,Gv,Fv,DoCode). encode(read(X),Gv,_,instr(read,Address)):- lookup2(X,Gv,Address,nostr,_). encode(write(mstring(E)),Gv,_,(instr(loadc,Address);instr(write_str,0))):- name(E,W),append(W,[36],T),name(E2,T),lookup2(E2,Gv,Address,mstring,E2). encode(write(E),Gv,_,(Code;instr(write,0))):- encode_expression(E,Gv,Code). encode(write_str(mstring(E)),Gv,_,(instr(loadc,Address);instr(write_str,0))):- name(E,W),append(W,[36],T),name(E2,T),lookup2(E2,Gv,Address,mstring,E2). encode(callx(X1,X2),Gv,Fv,(Codepush;instr(call,A);destroy_local(N))):- lookup(X1,Fv,A,_,_),length(X2,M),N is M*2,codepush(X2,Gv,Codepush). encode(return(X),Gv,_,(Code;destroy_local(N1);end_funz)):- encode_expression(X,Gv,Code),lvarn(N1). encode(assignret(X),Gv,_,(instr(store,Address))):- lookup2(X,Gv,Address,nostr,0). encode_ptr1(mstring(X),Gv,instr(loadc,Addr)):- lookup2(X,Gv,Addr,mstring,X). encode_ptr1(name(X),Gv,instr(loadc,Addr)):- lookup2(X,Gv,Addr,nostr,0). encode_ptr2(mstring(X),Gv,instr(loadp,Addr)):- lookup2(X,Gv,Addr,mstring,X). encode_ptr2(name(X),Gv,instr(loadp,Addr)):- lookup2(X,Gv,Addr,nostr,0). encode_expression(mstring(X),Gv,instr(loadc,Address)):- lookup2(X,Gv,Address,mstring,X). encode_expression(number(C),_,instr(loadc,C)). encode_expression(name(X),Gv,instr(load,Address)):- lookup2(X,Gv,Address,nostr,0). encode_expression(expr(Op,E1,E2),Gv,(Load;Instruction)):- single_instruction(Op,E2,Gv,Instruction),encode_expression(E1,Gv,Load). encode_expression(expr(Op,E1,E2),Gv,Code):- \+single_instruction(Op,E2,Gv,_),single_operation(Op,E1,Gv,E2Code,Code),encode_expression(E2,Gv,E2Code). single_instruction(Op,number(C),_,instr(OpCode,C)):- literal_operation(Op,OpCode). single_instruction(Op,name(X),Gv,instr(OpCode,A)):- memory_operation(Op,OpCode),lookup2(X,Gv,A,_,_). single_operation(Op,E,Gv,Code,(Code;Instruction)):- commutative(Op),single_instruction(Op,E,Gv,Instruction).

74

single_operation(Op,E,Gv,Code,(Code;instr(store,Address);Load;instr(OpCode,Address))):- \+commutative(Op),lookup('$temp',Gv,Address,_,_),encode_expression(E,Gv,Load),op_code(E,Op,OpCode). op_code(number(_),Op,OpCode):- literal_operation(Op,OpCode). op_code(name(_),Op,OpCode):- memory_operation(Op,OpCode). literal_operation('+',addc). literal_operation('-',subc). literal_operation('*',mulc). literal_operation('/',divc). memory_operation('+',add). memory_operation('-',sub). memory_operation('*',mul). memory_operation('/',div). commutative('+'). commutative('*'). encode_test(compare(Op,E1,E2),Label,Gv,(Code;instr(OpCode,Label))):- comparison_opcode(Op,OpCode),encode_expression(expr('-',E1,E2),Gv,Code). comparison_opcode('==',jumpne). comparison_opcode('>',jumple). comparison_opcode('<',jumpge). comparison_opcode('!=',jumpeq). comparison_opcode('>=',jumplt). comparison_opcode('<=',jumpgt).

4) Il file ‘lexan’ toklist(File,Tl):- see(File),get0(C),doSent(C,Tl),seen. doSent(_,[]):- at_end_of_stream,!. doSent(Char,[W|W2]):- skip_blank(Char,X),readWord(X,W,C2),doSent(C2,W2). blank_char(32). blank_char(8). blank_char(9). blank_char(10). blank_char(13). skip_blank(_,32):- at_end_of_stream,!. skip_blank(A,B):- blank_char(A),get0(V),skip_blank(V,B). skip_blank(A,B):- blank_char(A),get0(B). skip_blank(A,A). double_char(33,W,R):- peek_byte(61),get0(_),get0(R),name(W,[33,61]). % != double_char(43,W,R):- peek_byte(43),get0(_),get0(R),name(W,[43,43]). % ++ double_char(45,W,R):- peek_byte(45),get0(_),get0(R),name(W,[45,45]). % -- double_char(45,W,R):- peek_byte(62),get0(_),get0(R),name(W,[45,62]). % -> double_char(60,W,R):- peek_byte(61),get0(_),get0(R),name(W,[60,61]). % <= double_char(61,W,R):- peek_byte(61),get0(_),get0(R),name(W,[61,61]). % == double_char(62,W,R):- peek_byte(61),get0(_),get0(R),name(W,[62,61]). % >= double_char(42,W,R):- peek_byte(42),get0(_),get0(R),name(W,[42,42]). % **

75

single_char(33,W,R):- get0(R),name(W,[33]). % ! single_char(34,W,R):- get0(R),name(W,[34]). % " single_char(35,W,R):- get0(R),name(W,[35]). % # single_char(36,W,R):- get0(R),name(W,[36]). % $ single_char(37,W,R):- get0(R),name(W,[37]). % % single_char(38,W,R):- get0(R),name(W,[38]). % & single_char(39,W,R):- get0(R),name(W,[39]). % ' single_char(40,W,R):- get0(R),name(W,[40]). % ( single_char(41,W,R):- get0(R),name(W,[41]). % ) single_char(42,W,R):- get0(R),name(W,[42]). % * single_char(43,W,R):- get0(R),name(W,[43]). % + single_char(44,W,R):- get0(R),name(W,[44]). % , single_char(45,W,R):- get0(R),name(W,[45]). % - single_char(46,W,R):- get0(R),name(W,[46]). % . single_char(47,W,R):- get0(R),name(W,[47]). % / single_char(91,W,R):- get0(R),name(W,[91]). % [ single_char(92,W,R):- get0(R),name(W,[92]). % \ single_char(93,W,R):- get0(R),name(W,[93]). % ] single_char(94,W,R):- get0(R),name(W,[94]). % ^ single_char(58,W,R):- get0(R),name(W,[58]). % : single_char(59,W,R):- get0(R),name(W,[59]). % ; single_char(60,W,R):- get0(R),name(W,[60]). % < single_char(61,W,R):- get0(R),name(W,[61]). % = single_char(62,W,R):- get0(R),name(W,[62]). % > single_char(63,W,R):- get0(R),name(W,[63]). % ? single_char(123,W,R):- get0(R),name(W,[123]). % { single_char(125,W,R):- get0(R),name(W,[125]). % } isAlNum(C):- isNum(C). isAlNum(C):- isChar(C). isNum(X):- X>47,X<58. % 0-9 isChar(X):- X>64,X<91. % A-Z isChar(X):- X>96,X<123. % a-z readWord(C,W,C2):- double_char(C,W,C2). readWord(C,W,C2):- single_char(C,W,C2). readWord(C,W,C2):- isNum(C),get0(C3),getNum(C3,W2,C2),name(W,[C|W2]). readWord(C,W,C2):- isChar(C),get0(C3),getWord(C3,W2,C2),name(W,[C|W2]). readWord(_,void,C2):- get0(C2). getNum(A,[],A):- \+isNum(A). getNum(A,[A|Num],F):- isNum(A),get0(B),getNum(B,Num,F). getWord(A,[],A):- \+isAlNum(A). getWord(A,[A|Word],F):- isAlNum(A),get0(B),getWord(B,Word,F). readRest(_):- at_end_of_stream,!. readRest(C,[W1|W2]):- readWord(C,W1,C2),skip_blank(C2,C3),readRest(C3,W2).

5) Il file ‘parser2’ parse(Tokens,Structure):- iaz_program(Structure,Tokens,[]),!. parse(_,_):- write('not a valid program'),nl,halt. iaz_program((S;Ss;Sss)) --> subp(S),mainp(Ss),subp(Sss). iaz_program((S;Ss;Sss)) --> subp(S),mainp(Ss),subp(Sss),[void]. mainp((funz(main,[]);S;halt;end_funz)) --> [main],['('],[')'],statement(S). mainp((funz(main,[]);S;halt;end_funz)) --> [main],['('],[')'],statement(S),[void]. subp(void)-->[].

76

subp((funz(X1,X2);S;end_funz;Ss))--> [sub],identifier(X1),['('],listargs(X2),statement(S),subp(Ss). statement((S;Ss))--> ['{'],statement(S),rest_statements(Ss). statement(assign(X,V))--> identifier(X),['='],expression(V),[';']. statement(assign(X,V))--> ['*'],identifier(X),['='],['"'],string(V),['"']. statement(assign(p(X),V))--> ['*'],identifier(X),['='],expression(V),[';']. statement(assign(X,p1(name(V))))--> identifier(X),['='],['&'],identifier(V),[';']. statement(assign(X,p2(name(V))))--> identifier(X),['='],['*'],identifier(V),[';']. statement(callx(X1,X2);assignret(R))--> identifier(R),['='],['$'],identifier(X1),['('],listargs2(X2),[';']. statement(if(T,S1,S2))--> [if],['('],test(T),[')'],statement(S1),[else],statement(S2). statement(if(T,S,void))--> [if],['('],test(T),[')'],statement(S). statement(while(T,S))--> [while],['('],test(T),[')'],statement(S). statement(read(X))--> [read],['('],identifier(X),[')'],[';']. statement(write_crlf)-->[write],['('],[crlf],[')'],[';']. statement(write(X))--> [write],['('],expression(X),[')'],[';']. statement(write_str(X))--> [write],['('],['"'],string(X),['"'],[')'],[';']. statement(write_str(X))-->[write_str],['('],['"'],string(X),['"'],[')'],[';']. statement(local(X))--> [local],['('],listargs(X),[';']. statement(callx(X1,X2))--> ['$'],identifier(X1),['('],listargs2(X2),[';']. statement(return(X))--> [return],['('],expression(X),[')'],[';']. statement(void)-->[';']. statement(void)-->[void]. rest_statements((S;Ss))--> statement(S),rest_statements(Ss). rest_statements(void)-->['}']. rest_statements(void)-->[void]. expression(X)--> iaz_constant(X). expression(expr(Op,X,Y))--> iaz_constant(X), arithmetic_op(Op), expression(Y). arithmetic_op('+')-->['+']. arithmetic_op('-')-->['-']. arithmetic_op('*')-->['*']. arithmetic_op('/')-->['/']. string(mstring(X))--> identifier(X). iaz_constant(name(X))--> identifier(X). iaz_constant(number(X))--> iaz_integer(X). identifier2(X)--> identifier(X). identifier2(X)--> iaz_integer(X). identifier(X)-->[X],{atom(X)}. iaz_integer(X)-->[X],{integer(X)}. test(compare(Op,X,Y))-->expression(X),comparison_op(Op),expression(Y). comparison_op('==')-->['==']. comparison_op('!=')-->['!=']. comparison_op('>')-->['>']. comparison_op('<')-->['<']. comparison_op('>=')-->['>=']. comparison_op('<=')-->['<=']. listargs([])--> [')']. listargs([A|X])--> [','],identifier(A),listargs(X). listargs([A|X])--> identifier(A),listargs(X). listargs2([])--> [')'].

77

listargs2([A|X])--> [','],identifier2(A),listargs2(X). listargs2([A|X])--> identifier2(A),listargs2(X).

6) Il file ‘symtab’ setlocalpar(X,Funz):- length(X,N), N1 is (N+1)*2,slp(X,Funz,N1,_). slp([],_,N,N). slp([X|L],Funz,N,N2):- slp2(X,Funz,N,N1),slp(L,Funz,N1,N2). slp2(X,Funz,N,N1):- assert(lvar(X,Funz,N)), N1 is N-2. getlocalpar(_). setlocalvar(X,Funz):- length(X,N), N1 is -N*2,slv(X,Funz,N1,_). slv([],_,N,N). slv([X|L],Funz,N,N2):- slv2(X,Funz,N,N1),slv(L,Funz,N1,N2). slv2(X,Funz,N,N1):- assert(lvar(X,Funz,N)), N1 is N+2. getlocalvar(_). tdstrip((Code1;Code2),(X,Y)):- tds(Code1,X),tds(Code2,Y). tds(no_op,''). tds(C,C). codepush([],_,no_op). codepush([X|L],Gv,(X1;X2)):- codepush2(X,Gv,X1),codepush(L,Gv,X2). codepush2(X,_,(instr(loadc,X);instr(push,0))):- number(X). codepush2(X,Gv,(instr(load,Addr);instr(push,0))):- lookup2(X,Gv,Addr,_,_).

7) Il file ‘tocode’ neg_byte(A,B):- A<0, B is 256+A. neg_byte(A,A). splitta(N,Hi,Lo):- N<0, N1 is 65536+N, Hi is N1//256, Lo is N1 mod 256. splitta(N,Hi,Lo):- Hi is N//256, Lo is N mod 256. toCode(I,File):- tell(File),tc(I),told. tc((Code1;Code2)):- tc(Code1),tc(Code2). tc(instr(push,cs)):- put(14). tc(instr(push,ax)):- put(80). tc(instr(pop,ds)):- put(31). tc(instr(push,bp)):- put(85). tc(instr(pop,bp)):- put(93). tc(mov(bx,ax)):- put(137),put(195). tc(mov(ax,bp)):- put(137),put(232). tc(mov(ax,bx)):- put(137),put(216). tc(mov(ax,dx)):- put(137),put(208). tc(mov(bx,bp)):- put(137),put(235). tc(mov(bx,[A])):- put(139),put(30),splitta(A,H,L),put(L),put(H). tc(mov(bx,A)):- put(187),splitta(A,H,L),put(L),put(H). tc(mov(ax,[bx])):- put(139),put(7). tc(mov(ax,[A])):- put(161),splitta(A,H,L),put(L),put(H). tc(mov(ax,A)):- put(184),splitta(A,H,L),put(L),put(H). tc(mov([bx],ax)):- put(137),put(7). tc(mov([A],ax)):- put(163),splitta(A,H,L),put(L),put(H). tc(instr(jmp,A)):- put(233),Y is A,splitta(Y,H,L),put(L),put(H). tc(instr(call,A)):- put(232),Y is A,splitta(Y,H,L),put(L),put(H). tc(instr(ret,0)):- put(195). tc(nop):- put(144). tc(block(_)):- put(144). tc(instr(int,A)):- put(205),put(A). tc(mov(dx,ax)):- put(137),put(194).

78

tc(mov(dx,A)):- put(186),splitta(A,H,L),put(L),put(H). tc(mov(ah,A)):- put(180),put(A). tc(mov(bp,sp)):- put(137),put(229). tc(mov(sp,bp)):- put(137),put(236). tc(instr(mul,bx)):- put(247),put(227). tc(instr(div,bx)):- put(247),put(243). tc(addr(ax,dx)):- put(1),put(208). tc(add(ax,[bx])):- put(3),put(7). tc(add(ax,bx)):- put(1),put(216). tc(add(ax,A)):- put(5),splitta(A,H,L),put(L),put(H). tc(add(sp,A)):- put(129),put(196),splitta(A,H,L),put(L),put(H). tc(add(bx,A)):- put(129),put(195),splitta(A,H,L),put(L),put(H). tc(sub(ax,[bx])):- put(41),put(7). tc(sub(ax,bx)):- put(41),put(8). tc(sub(ax,[A])):- put(43),put(6),splitta(A,H,L),put(L),put(H). tc(sub(ax,A)):- put(45),splitta(A,H,L),put(L),put(H). tc(add(ax,[A])):- put(3),put(6),splitta(A,H,L),put(L),put(H). tc(sub(sp,A)):- put(129),put(236),splitta(A,H,L),put(L),put(H). tc(sub(ax,A)):- put(129),put(235),splitta(A,H,L),put(L),put(H). tc(instr(dw,A)):- splitta(A,H,L),put(L),put(H). tc(instr(ds,A)):- write(A). tc(instr(db,A)):- put(A). tc(instr(jumpne,A)):- put(117),Y is A,neg_byte(Y,B),put(B). tc(instr(jumple,A)):- put(126),Y is A,neg_byte(Y,B),put(B). tc(instr(jumpge,A)):- put(125),Y is A,neg_byte(Y,B),put(B). tc(instr(jumpeq,A)):- put(116),Y is A,neg_byte(Y,B),put(B). tc(instr(jumplt,A)):- put(124),Y is A,neg_byte(Y,B),put(B). tc(instr(jumpgt,A)):- put(127),Y is A,neg_byte(Y,B),put(B). tc(mov(dl,A)):- put(178),neg_byte(A,B),put(B). tc(instr(pop,bx)):- put(91). tc(instr(inc,cx)):- put(65). tc(instr(push,dx)):- put(82). tc(xor(dx,dx)):- put(49),put(210). tc(xor(cx,cx)):- put(49),put(201). tc(or(ax,ax)):- put(9),put(192). tc(instr(pop,dx)):- put(90). tc(add(dl,A)):- put(128),put(194),neg_byte(A,B),put(B). tc(instr(loop,A)):- put(226),Y is A,neg_byte(Y,B),put(B). tc(mov(cx,[bx])):- put(139),put(15). tc(instr(inc,bx)):- put(67). tc(instr(push,cx)):- put(81). tc(instr(pop,cx)):- put(89). tc(instr(pop,ax)):- put(88). tc(no_op).

8) Il file ‘tointel’ adj(X,instr(push,cs);instr(pop,ds);X). toIntel(Code,XCode2):- adj(Code,XCode),toIntel2(XCode,XCode2). toIntel2((Code1;Code2),(X1;X2)):- toIntel2(Code1,X1),toIntel2(Code2,X2). toIntel2(instr(loadc,stack_bp(A)),(mov(ax,bp);add(ax,A))):- number(A). toIntel2(instr(load,stack_bp(A)),(mov(bx,bp);add(bx,A);mov(ax,[bx]))):- number(A). toIntel2(instr(loadp,stack_bp(A)),(mov(ax,bp);add(ax,A);mov(bx,ax);mov(ax,[bx]);mov(bx,ax);mov(ax,[bx]))):- number(A). toIntel2(instr(store,stack_bp(A)),(mov(bx,bp);add(bx,A);mov([bx],ax))):- number(A). toIntel2(instr(addc,stack_bp(A)),(mov(bx,bp);add(bx,A);add(ax,bx))):- number(A).

79

toIntel2(instr(add,stack_bp(A)),(mov(bx,bp);add(bx,A);add(ax,[bx]))):- number(A). toIntel2(instr(subc,stack_bp(A)),(mov(bx,bp);add(bx,A);sub(ax,bx))):- number(A). toIntel2(instr(sub,stack_bp(A)),(mov(bx,bp);add(bx,A);sub(ax,[bx]))):- number(A). toIntel2(instr(mulc,stack_bp(A)),(mov(bx,bp);add(bx,A);mov(dx,0);instr(mul,bx))). toIntel2(instr(mul,stack_bp(A)),(instr(push,ax);mov(bx,bp);add(bx,A);mov(ax,[bx]);mov(bx,ax);mov(dx,0);instr(pop,ax);instr(mul,bx))):- number(A). toIntel2(instr(divc,stack_bp(A)),(mov(bx,bp);add(bx,A);mov(dx,0);instr(div,bx))):- number(A). toIntel2(instr(div,stack_bp(A)),(instr(push,ax);mov(bx,bp);add(bx,A);mov(ax,[bx]);mov(bx,ax);mov(dx,0);instr(pop,ax);instr(div,bx))):- number(A). toIntel2(instr(loadc,A),mov(ax,A)). toIntel2(instr(load,A),mov(ax,[A])). toIntel2(instr(jump,A),instr(jmp,A)). toIntel2(instr(call,A),instr(call,A)). toIntel2(instr(loadp,A),(mov(bx,[A]);mov(ax,[bx]))). toIntel2(instr(store,A),mov([A],ax)). toIntel2(instr(storep,A),(mov(dx,ax);mov(bx,A);mov(ax,[bx]);instr(push,ax);instr(pop,bx);mov(ax,dx);mov([bx],ax))). toIntel2(instr(push,0),instr(push,ax)). toIntel2(instr(addc,A),add(ax,A)). toIntel2(instr(add,A),add(ax,[A])). toIntel2(instr(subc,A),sub(ax,A)). toIntel2(instr(sub,A),sub(ax,[A])). toIntel2(instr(mulc,A),(mov(dx,0);mov(bx,A);instr(mul,bx))). toIntel2(instr(mul,A),(mov(dx,0);mov(bx,[A]);instr(mul,bx))). toIntel2(instr(divc,A),(mov(dx,0);mov(bx,A);instr(div,bx))). toIntel2(instr(div,A),(mov(dx,0);mov(bx,[A]);instr(div,bx))). toIntel2(instr(write,_),(mov(bx,10);xor(cx,cx);label(W1);xor(dx,dx);instr(div,bx);instr(push,dx);instr(inc,cx);or(ax,ax);instr(jumpne,W1);label(W2);instr(pop,dx);add(dl,48);mov(ah,2);instr(int,33);instr(loop,W2))).%write toIntel2(instr(write_str,_),(mov(dx,ax);mov(ah,9);instr(int,33))).%write_str toIntel2(instr(read,A),(mov(dx,A);mov(ah,10);instr(int,33))).%read toIntel2(instr(write_crlf,_),(mov(dl,13);mov(ah,2);instr(int,33);mov(dl,10);mov(ah,2);instr(int,33))). toIntel2(instr(X,Y),instr(X,Y)). toIntel2(no_op,no_op). toIntel2(block(L),block(L)). toIntel2(label(N),label(N)). toIntel2(nop,nop). toIntel2(destroy_local(N),add(sp,N)). toIntel2(end_funz,(instr(pop,bp);instr(ret,0))). toIntel2(create_local(N),sub(sp,N)). toIntel2(init_funz,(instr(push,bp);mov(bp,sp))). toIntel2(halt,instr(int,32)).

9) Il file ‘tostream’ toStream((Code1;Code2)):- toStream(Code1),toStream(Code2). toStream(instr(X,Y)):- write(X),write(' '),write(Y),nl. toStream(nop):- write(nop),nl. toStream(no_op). toStream(block(L)):- write(block(L)),nl.

80

toStream(X):- X=..[mov,A,B|_],write('mov '),write(A),write(','),write(B),nl. toStream(X):- X=..[sub,A,B|_],write('sub '),write(A),write(','),write(B),nl. toStream(X):- X=..[add,A,B|_],write('add '),write(A),write(','),write(B),nl. toStream(X):- X=..[xor,A,B|_],write('xor '),write(A),write(','),write(B),nl. toStream(X):- X=..[or,A,B|_],write('or '),write(A),write(','),write(B),nl. toStream(X):- X=..[movr,A,B|_],write('mov '),write(A),write(','),write(B),nl. toStream(X):- X=..[addr,A,B|_],write('add '),write(A),write(','),write(B),nl. toStream(halt):- write(halt),nl. toStream(X):- write(X),nl. toStream2((Code1;Code2)):- toStream2(Code1),toStream2(Code2). toStream2(instr(X,Y)):- write(X),write(Y). toStream2(nop):- write(90). toStream2(block(L)):- write(block(L)).

81

Capitolo 7 Conclusioni

In questa tesi abbiamo sviluppato un compilatore per un sottoinsieme del linuaggio C

che compila files eseguibili in ambiente DOS/Windows. Il compilatore può essere

utilizzato per scopi didattici e in ambiente accademico. Il progetto del compilatore può

essere completato e migliorato nel futuro aggiungendovi nuove funzionalità quali, ad

esempio, il riconoscimento di primitive per la programmazione a oggetti, o la

creazione di una interfaccia grafica, o la produzione di files eseguibili per altri

ambienti (calcolatori e/o sistemi operativi).

11 nov 2004

82

Riferimenti

1. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers. Principles, Techniques,

and Tools. Addison Wesley, 1988.

2. Leon Sterling, Ehud Shapiro. The Art of Prolog. The MIT Press Second Edition,

1994.

3. Alberto Pettorossi. Theory of Computation Vol II and IV. Aracne 2002.

4. Alberto Pettorossi, Maurizio Proietti. First Order Predicate Calculus and Logic

Programming. Aracne 2002.

5. Intel 80386 programmer’s reference manual. Intel Corporation 1986.