3 Macchine compilatori e interpreti

ESECUTORE ED ALGORITMI

Per scrivere una soluzione nella forma definitiva è necessario sapere chi la eseguirà.

L’esecutore di riferimento per il nostro studio è ovviamente il calcolatore elettronico. Un

calcolatore reale è in grado di comprendere solo soluzioni codificate nel proprio

linguaggio, cioè in linguaggio macchina; Il linguaggio macchina non è di uso pratico, né di

facile comprensione. E dunque vi sono due opportunità:

Visto che l’esecutore finale è una macchina reale M si può scrivere la soluzione nel

1) suo linguaggio LM.

Si può adoperare un linguaggio L più “amichevole”, un linguaggio di

2) programmazione ad alto livello:

Si scrive l’algoritmo nel linguaggio L;

a. Si traduce (per mezzo di un compilatore) la soluzione codificata nel

b. linguaggio L in un’altra (ad essa equivalente) codificata nel linguaggio LM

della macchina;

Oppure si esegue l’algoritmo per mezzo di un intermediario (detto

c. interprete) che opera sulla macchina M senza necessità di traduzioni.

COMPILATORI E INRERPRETI

COMPILATORE

1) I

L e L sono linguaggi di programmazione. Un compilatore è un traduttore che trasforma

I

algoritmi scritti nel linguaggio L in algoritmi equivalenti scritti nel linguaggio L .

Un compilatore è un programma che può essere eseguito da una certa macchina M e che

I

esegue la trasformazione prescritta; il linguaggio L è spesso il linguaggio macchina di M,

ma non è obbligatorio!

INTERPRETE

2)

L è un linguaggio di programmazione, M una macchina. Un interprete del linguaggio L è

un esecutore, cioè un programma per la macchina M, in grado di eseguire (senza tradurli)

programmi scritti nel linguaggio L.

In pratica, un interprete è un programma che simula il comportamento di una macchina

diversa (astratta o concreta che sia).

SITUAZIONI IBRIDE

3) I

Un programma scritto nel linguaggio L (codice sorgente) pu esser compilato nel

linguaggio L e il risultato (codice intermedio) eseguito dall’interprete VL (detto anche

macchina virtuale).

Un esempio è Java, che traduce il codice sorgente in un linguaggio per macchina astratta

(compilatore) e realizza in modo "virtuale" la macchina astratta ed è in grado di

comprendere ed eseguire algoritmi in codice intermedio (interprete).

IL COMPILATORE: L'INTERPRETE:

Gli algoritmi sono scritti in linguaggio Java e Il codice prodotto dal compilatore (il codice

memorizzati in un file che ha l’estensione .java. intermedio) è contenuto in un file che prende lo

Il codice sorgente non è eseguibile: viene stesso nome del codice sorgente, ma con

tradotto in un linguaggio intermedio, noto con il l’estensione .class. L’interprete, la Java Virtual

nome bytecode, e memorizzato in un file con Machine (JVM), comprende il codice intermedio

estensione .java. Il compilatore Java è e pu eseguirlo. Il comando java consente di

associato al comando javac: javac “invocare” l’interprete: javac <nomefile>

<nomefile>.java

LA MACCHINA ASTRATTA

Che cosa fa esattamente un algoritmo scritto in pseudo codice? Per saperlo dobbiamo

dire come reagisce l’esecutore di riferimento matematico. Descriveremo allora un

esecutore astratto (matematico), ma molto simile ad un esecutore reale.

La macchina astratta è il modello matematico a cui

fa riferimento l'interprete. È composta da:

• memoria: insieme illimitato di celle che possono

contenere numeri interi;

• processore: dispositivo in grado di eseguire

istruzioni di un linguaggio specifico della

macchina;

• input: sequenza illimitata di numeri interi;

• output: sequenza finita, ma potenzialmente illimitata, di numeri interi.

MEMORIA: divisa in celle (o locazioni) di memoria, ognuna delle quali può

1. contenere un numero intero qualunque. In un istante solo un numero finito di celle è

usato dalla macchina.

Ogni singola cella di memoria può contenere un numero intero arbitrario.

a. Le celle di memoria usate sono sempre in numero finito, ma non c’è un limite

b. a quante ne possiamo usare: in pratica, le estensioni della memoria sono

“gratis”.

Il numero associato ad una cella si chiama indirizzo e ci permette di

c. ritrovare quello che abbiamo messo da parte nella memoria.

PROCESSORE: è un dispositivo che:

2. Riconosce un numero finito di istruzioni “di basso livello”;

a. Agisce sulla macchina secondo le indicazioni dell’istruzione corrente;

b. Opera in modo discreto, ossia in un tempo finito esegue un numero finito di

c. passi di calcolo (istruzioni);

Opera in modo

d. deterministico.

L'istruzione corrente è

individuata da una speciale cella,

il program counter, che è

"incorporata" nel processore.

L'esecuzione di un'istruzione del

processore modifica la memoria,

ossia lo stato della macchina.

INPUT

3. L'input rappresenta il flusso di

dati provenienti dall'esterno. In

matematica è una sequenza

ordinata di interi di lunghezza illimitata. L'accesso all'input è strettamente

sequenziale: il processore può leggere SOLO il primo elemento che viene poi tolto

dall'elenco.

OUTPUT

4. L'output rappresenta il flusso di dati restituiti all'esterno. In struttura matematica,

esso è una sequenza ordinata di numeri interi di lunghezza finita ma

potenzialmente illimitata. L'accesso all'output è strettamente sequenziale: il

processore può aggiungere un nuovo elemento in coda che non è più modificabile.

IL CODICE MACCHINA

Un programma scritto per la macchina (astratta) è una sequenza finita di istruzioni

macchina. Le istruzioni della macchina astratta sono essenzialmente di tre tipi:

istruzioni che agiscono sulla

- memoria e su input e output;

istruzioni aritmetiche;

- istruzioni di controllo.

-

La macchina esegue il programma

secondo un procedimento detto ciclo della

macchina.

La Sintassi delle Istruzioni Macchina

SINTASSI DELLE ISTRUZIONI MACCHINA

Una generica istruzione macchina ha il seguente formato:

cod op1 op2