Linguaggio di Programmazione

Generalità
• Linguaggio e Macchina Astratta
• M.A.: struttura e stati dell’esecutore
• Costruire M.A.: Interprete, Compilatore
• Interprete: dentro
• Compilatore: il supporto RTS
• Compilatore: Macchine di sviluppo e Gerarchia
• Macchine Intermedie: costruzioni miste
Linguaggi, Macchine Astratte,
Interpreti & Compilatori
Definizioni:
linguaggio e formalismo
linguaggio di (programmazione) =
= formalismo per esprimere
(applicazioni di funzioni calcolabili)
formalismo = sintassi (forma delle costruzioni permesse)
+
semantica (significato loro associato)
Esempio: Linguaggio di
Programmazione
L = <S, SEM> e’ un linguaggio di progr.
1) per ogni PS, SEM(P) {N N}
2) per ogni f {N  N}, esiste P S, tale che:
per ogni n N, f(n) = SEM(P)(n)
[dove: {N  N} = funzioni calcolabili]
Definizioni:
Macchina Astratta
Macchina astratta =
Linguaggio (L=<S,SEM>)
+
Esecutore (EL)
Per ogni PS,
SEM(P) EL(P)
P
EL(P)
EL
Java Virtual Machine
Landin’s SECD
Control frame
Data-Control Stack
Heap
Esempio: Macchina Astratta,
Linguaggio ed Esecutore
• LM = <S, SEM> è un linguaggio di programmazione
• EM è un esecutore di applicazioni di programmi
• M = <LM,EM>
EM: A  A*
per ogni P  S, n  N
P,n
SEM
I
SEM(P)(n)
linguaggio
O
AP,n
EM
A*P,n
[dove I,O funzioni iniettive su A e A* risp.]
Macchina
Astratta
Macchina Astratta: Struttura e Stati
dell’Esecutore
Programma
Dati
Memoria
Interprete
Op1
Ciclo di interpretazione
…
Fetch istruzione
Controllo sequenza
Fetch operandi
Controllo dati
Gestione memoria
Modello statico-dinamico
controllo
Macchina astratta - Esecutore
Opk
Macchina Astratta:
Memoria, Controllo
Memoria: strutturata secondo un modello che
dipende dal linguaggio della macchina
• array di parole, registri, stack
• heap - L. con allocazione dinamica (Pascal, C, C++, …,Java,
• grafo - L. con condivisione di strutture (funzionali)
Controllo: gestisce lo stato della macchina
• trova il successivo statement o espressione
• trova i dati su cui tale stat. o espr. opera
• gestisce la memoria
Macchina Astratta:
Interprete - cliclo di interpretazione
start
fetch statement
decodifica
fetch operandi
seleziona
Op1
Opn
halt
stop
Costruire Macchine Astratte
Utiliziamo macchine astratte gia definite
• Sia L0=(S0,SEM0) il nostro linguaggio
• Sia M1= (L1=<S1,SEM1>,EL1) una macchina
inteprete
definiamo l’esecutore EL0 come programma di L1.
compilatore
trasformiamo ogni struttura (programma) di L0
in una equivalente struttura (programma) di L1.
Interprete
P,n S0
ELO,(P,n) S1
SEM(P)(n)
ELO
EL1(ELO,(P,n))
EL1
Eseguire una APPLICAZIONE (P,n) di L 0, consiste:
nell'eseguire l'applicazione EL0 ,(P,n) di L 1
Interprete: dentro EL0
Una collezione di procedure che realizzano:
• i passi (decodifica) del ciclo di interpretazione per L0
• il modello di memoria di dati e programmi di L0
• l’unità di controllo per fetch di codice e di dati di L0
• un implementazione delle primitive di L0
Compilatore
P
S0
CL0,P
CL0(P)
ELO
S1
EL1(CL0,P)
EL1
Il compilatore non opera su applicazioni bensì
su strutture (programmi: P)
CLO preserva la semantica:
SEMO(P) = SEM1(CLO(P))
C011
Compilatore:
Il Run Time Support
• Non dipende dallo specifico programma compilato
• Utilizzabile dall’oggetto di ogni sorgente
Una collezione di procedure che realizzano:
• il modello di memoria di dati e programmi di L0
• strutture per trasferimento controllo
• un’implementazione delle primitive di L0
Compilatore:
La Macchina Sottostante
EL0(P,n)
PS0
CL0(P)S1
CL0(P),n
RTS
CL0
EL1
EL0
EL1(CL0(P),n)
Compilatore:
La Macchina di Sviluppo
PS0
sorgente di L0
CL0(P)S1
CL0(P),n EL1(CL0(P),n)
oggetto per L1
RTS
CL0
Linguaggio target
(object language)
metalinguaggio
EL2
EL1
Macchina Host
Macchina Target
EL0
C012
Gerarchia di Macchine
nello sviluppo
Gerarchia di Macchine
• riduce ad ogni livello l’espressivitá
• semplifica la costruzione della macchina di un linguaggio
molto espressivo
Linguaggio meno espressivo ha:
- molti costrutti ma elementari
- un esecutore piú semplice
Quando la macchina target è concreta
• nessuna differenza concettuale tra astratta e concreta
• abbiamo però un esecutore effettivo per ogni macchina della
gerarchia
Gerarchia di Macchine
nella struttura
Linguaggi di Rete
Macchina Rete
Linguaggi di
Browser
Macchina WEB
Java
Scala
Macchina Java
Macchina Scala
Java Bytecode
Macchina Intermedia
Linguaggio di Sistema
Sistema Operativo
Linguaggio Microporgrammazione
Firmware
Linguaggio Macchina
Hardware
Classi di Macchine Concrete
In corrispondenza alle molte classi di linguaggi
• Imperativi
• Applicativi
• Object oriented
Differiscono per il linguaggio e di conseguenza per:
• struttura dello stato, ovvero:
- modello di memoria
- metodi di fetch e di decodifica
- operazioni primitive
Macchina Intermedia:
Costruzioni Miste
L0:Linguaggio sorgente
Macchina di L0
compilatore
LI:Ling. Intermedio
Macchina di LI
interprete
L1:Linguaggio target
Macchina di L1
Vantaggi:
• sviluppo ridotto
• portabilità aumentata
• dimensione c. oggetto:
• occ. memoria
• tempo esecuzione
Compilatore, Interprete:
contesto, struttura componenti
• contesto operativo: preprocessing e loading
• Compilatore: Struttura, fasi e passi
• Interprete: Struttura standard
• Visitiamo le fasi: un esempio
• Compiler-Compiler: semplifichiamo la stesura
• Bootstrapping
Compilatore, Interprete:
contesto, struttura componenti
• contesto operativo: preprocessing e loading
• Compilatore: Struttura, fasi e passi
• Interprete: Struttura standard
• Visitiamo le fasi: un esempio
• Compiler-Compiler: semplifichiamo la stesura
• Bootstrapping
Struttura dei moduli
Contesto del
Compilatore:
Font-end
Back-end
Preprocessor
Link e macros
Source program
Compiler
Object program
Assembler
Codice rilocabile
Link-Loader
Assoluto eseguibile
Librerie
rts
Compilatore: struttura, fasi e passi
Analisi Lessicale
Analisi Sintattica
Analisi Statica
Tabella
Simboli
Errori
Codice Intermedio
Fasi e Passi:
6 fasi
k(≥1) passi
Ottimizzazione
Codice target
Interprete: La struttura standard
Analisi Lessicale
Analisi Sintattica
Analisi Statica
Tabella
Simboli
Fasi e Passi:
4 fasi
k(≥1) passi
Errori
Emulatore su
Codice target
Compilatore: Una struttura per
analisi di correttezza avanzate
Analisi Lessicale
Analisi Sintattica
Analisi Statica
Tabella
Simboli
Codice Intermedio
Correttezza
Terminazione - proprieta’ varie
Fasi e Passi:
8 fasi
k(≥1) passi
Codice Intermedio
Ottimizzazione
Codice target
Errori
Compiler-Compiler: ridurre i
metalinguaggi e semplificare la
stesura di un compilatore
Lo sviluppo di un compilatore (interprete), da un linguaggio L0 a Lt,
coinvolge altri linguaggi Lm.
I metalinguaggi sono utilizzati per esprimere le procedure di analisi e traduzione,
e condizionano il compilatore che può essere eseguito solo sul meta scelto
Distinguere tra: C0tm e C0tn
Combiniamo interprete e compilatore
Bootstrapping
• costruiamo un interprete E0m (che valuta programmi di L0
su una macchina Mm): strumento di sviluppo
• costruiamo compilatore C0t0 : Il compilatore è scritto nel
linguaggio L0 stesso.
• eseguiamo: E0m(C0t0)(C0t0) otteniamo C0tt
Bootstrapping (m ≤ t)
Il prodotto è ora indipendente dal meta
In questo corso
Semantica formale e RTS
• Linguaggi studiati da 2 punti di vista:
• Semantica formale
• RTS: supporto a run time
• Semantica Formale
• sempre in forma eseguibile, (i.e. un interprete formalmente derivato)
• implementata ad altissimo livello (i.e. con il massimo di astrazioni possibili)
• definizione rigorosa (precisa, non ambigua) indipendente dall’implementazione:
• Progettista: la definisce
• Implementatore: la usa come specifica del linguaggio da implementare
• Programmatore: la usa come documentazione indipendente dall’implementazione
• scrivere programmi corretti e
• provare proprietà del programma, semplificazioni e modifiche
• RTS
• focalizza le caratteristiche essenziali del linguaggio e della sua M.A.
• Progettista: sono le strutture semantiche con cui dare significato ai programmi del linguaggio
• Implementatore: le strutture base da realizzare
• Programmatore: le strutture da conoscere per usare bene il linguaggio