Analisi Semantica e
Generazione Codice
Nicola Fanizzi
Corso di Linguaggi di Programmazione
Dipartimento di Informatica
Università degli Studi di Bari
7 maggio 2014
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
1 / 35
1
Analisi Semantica guidata dalla Sintassi
Introduzione
Estensione
2
Grammatiche ad Attributi
Regole Semantiche
Classi di Attributi
Tipi di Grammatiche ad Attributi
3
Tavola dei Simboli ed Errori
Tavola dei Simboli
Errori Semantici
Procedura Gestione Errori
4
Ottimizzazione
Costanti
Codice
Espressioni
Cicli
Varie
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
2 / 35
Analisi Semantica guidata dalla Sintassi
1
Analisi Semantica guidata dalla Sintassi
Introduzione
Estensione
2
Grammatiche ad Attributi
Regole Semantiche
Classi di Attributi
Tipi di Grammatiche ad Attributi
3
Tavola dei Simboli ed Errori
Tavola dei Simboli
Errori Semantici
Procedura Gestione Errori
4
Ottimizzazione
Costanti
Codice
Espressioni
Cicli
Varie
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
3 / 35
Analisi Semantica guidata dalla Sintassi
Introduzione
Analisi Semantica
La verifica dei vincoli contestuali e di semantica statica di un
linguaggio di prog. generalmente si coordina con il parsing:
token
albero
albero
grafo
⇒
⇒
⇒
stream
parsing
annotato
dipendenze
Si prenderà in considerazione una forma di analisi semantica
guidata dalla analisi sintattica:
traduzione guidata dalla sintassi
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
4 / 35
Analisi Semantica guidata dalla Sintassi
Introduzione
Funzionalità
1
2
raccolta informazioni sugli identificatori nella tavola dei
simboli occorre progettare il contenuto interno della tavola
organizzando le informazioni da includere
verifica della correttezza nell’impiego degli identificatori e
dei costrutti del linguaggio in generale controlli statici (a
compile-time):
identificatori dichiarati prima dell’uso ed in modo univoco
compatibilità operandi
chiamate congruenti con le dichiarazioni (visibilità)
3
N. Fanizzi
segnalazione degli eventuali errori semantici non appena
possibile per evitare di segnalare errori in cascata
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
5 / 35
Analisi Semantica guidata dalla Sintassi
Estensione
Estensione
L’analisi sintattica può fare da guida per l’analisi semantica e la
traduzione in codice intermedio
Le grammatiche libere vanno estese con
l’associazione di attributi ai simboli della grammatica e
l’integrazione delle regole sintattiche con azioni semantiche
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
6 / 35
Grammatiche ad Attributi
1
Analisi Semantica guidata dalla Sintassi
Introduzione
Estensione
2
Grammatiche ad Attributi
Regole Semantiche
Classi di Attributi
Tipi di Grammatiche ad Attributi
3
Tavola dei Simboli ed Errori
Tavola dei Simboli
Errori Semantici
Procedura Gestione Errori
4
Ottimizzazione
Costanti
Codice
Espressioni
Cicli
Varie
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
7 / 35
Grammatiche ad Attributi
Attributi
Ogni simbolo di una grammatica può avere degli
attributi
simili a variabili di un linguaggio di programmazione
con un proprio
nome
tipo
L’albero sintattico viene annotato (o decorato):
in ciascun nodo,
si riportano i valori degli attributi del simbolo
calcolati da regole semantiche associate a quelle sintattiche
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
8 / 35
Grammatiche ad Attributi
Regole Semantiche
Regole Semantiche
In genere sono poste a destra di una produzione
e racchiuse tra i metasimboli { e }
All’interno, sequenze di istruzioni (tipicamente assegnazioni)
dette
azioni semantiche
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
9 / 35
Grammatiche ad Attributi
Classi di Attributi
Classi di Attributi I
attributi ereditati
e
attributi sintetizzati
Data una produzione N −→ x1 x2 . . . xn ,
un’azione associata
a := f (z1 , z2 , . . . , zm )
può assegnare un valore all’attributo a:
a attr. sintetizzato di N
con ciascuno zi attributo ereditato di N
o sintetizzato di xj (1 ≤ j ≤ n)
a attr. ereditato di xj (1 ≤ j ≤ n)
e ciascun zi è attributo ereditato di N
o sintetizzato di xj (1 ≤ j ≤ n)
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
10 / 35
Grammatiche ad Attributi
Classi di Attributi
Classi di Attributi II
Osservazioni.
Nell’albero sintattico un NT/nodo può ricevere attraverso un
attributo ereditato un’informazione dipendente da un
attributo ereditato del nodo padre e da qualche attributo
sintetizzato di altri nodi aventi lo stesso padre
Un attributo ereditato porta informazione dal contesto del
nodo ricevente (flusso discendente)
Un attributo sintetizzato determina un flusso ascendente di
informazione elaborata da qualche discendente
Simboli terminali = foglie
possono avere solo attributi sintetizzati (forniti dallo scanner)
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
11 / 35
Grammatiche ad Attributi
Classi di Attributi
Classi di Attributi III
Nomenclatura.
attributi indicati con la notazione
nomeSimbolo.nomeAttributo
se uno stesso simbolo compare più volte in una regola
sintattica, nella regola semantica le varie istanze vengono
numerate progressivamente
gli attributi sintetizzati associati ai terminali rappresentano
l’informazione fornita dallo scanner
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
12 / 35
Grammatiche ad Attributi
Classi di Attributi
Classi di Attributi IV
Esempio.
regola sintattica
S −→ E
E −→ E+T
E −→ T
E −→ -T
T −→ T *F
T −→ F
F −→ (E)
F −→ n
N. Fanizzi
Linguaggi di prog.+Lab
regola semantica
{S.V := E.V}
{E1.V := E2.V+T.V}
{E.V := T.V}
{E.V := -T.V}
{T1.V := T2.V*F.V}
{T.V := F.V}
{F.V := E.V}
{F.V := n.IVAL}
Analisi Semantica e Generazione Codice
7 maggio 2014
13 / 35
Grammatiche ad Attributi
Classi di Attributi
Classi di Attributi V
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
14 / 35
Grammatiche ad Attributi
Tipi di Grammatiche ad Attributi
Tipi di Grammatiche ad Attributi
Attributi:
normali: il risultato semantico prodotto è dato dal valore
degli attributi sintetizzati del simbolo iniziale della
grammatica S
opzionali: grammatiche che producono effetti collaterali
es. scrittura di un valore calcolato {print(E.V)}
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
15 / 35
Grammatiche ad Attributi
Tipi di Grammatiche ad Attributi
Alberi sintattici astratti
Un albero sintattico astratto (abstract syntax tree, AST),
forma semplificata dell’albero di parsing in cui la struttura del
codice vede in ogni nodo un costrutto del sorgente
minore dettaglio rispetto alla sintassi del linguaggio
Esempio
istruzione condizionale:
<if-then-else> −→
if <condizione> then <istruzione1 >
else <istruzione2 >
<if-then-else>
.
↓
&
<condizione> <istruzione1 > <istruzione2 >
Gli AST servono a disaccoppiare il parsing dalla traduzione
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
16 / 35
Grammatiche ad Attributi
Tipi di Grammatiche ad Attributi
Calcolo degli Attributi I
Ordine di calcolo dell’albero sintattico astratto:
costruzione totale:
costruzione parziale: ordine top-down o bottom-up
Calcolo attributi: Azione semantica possibile quando le
informazioni sono disponibili ossia quando tutti gli attributi
necessari sono avvalorati
Ordine azioni semantiche 6= Ordine tra regole sintattiche
(si utilizza una tecnica basata sul grafo delle dipendenze tra
attributi)
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
17 / 35
Grammatiche ad Attributi
Tipi di Grammatiche ad Attributi
Calcolo degli Attributi II
Esempio.
regola sintattica
D −→ L:T
T −→ integer
T −→ real
L1 −→ L2 ,i
L −→ i
regola semantica
{l.ty := t.ty}
{t.ty := 1}
{t.ty := 2}
{l2.ty := l1.ty; print(i.name, l1.ty)}
{print(i.name, l.ty)}
Osservazioni
t.ty attr. sintetizzato intero
l.ty attr. ereditato intero
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
18 / 35
Grammatiche ad Attributi
Tipi di Grammatiche ad Attributi
Calcolo degli Attributi III
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
19 / 35
Grammatiche ad Attributi
Tipi di Grammatiche ad Attributi
Restrizioni sugli Attributi
Grammatiche ad attributi di tipo S:
contengono solo attributi sintetizzati
Grammatiche ad attributi di tipo L:
esclusivo il flusso di informazioni da sinistra a destra
per ogni regola
X −→ x1 x2 · · · xn
gli attributi ereditati da ciascun xi possono dipendere
da quelli sintetizzati dei simboli xj con j < i e
da quelli ereditati di X
Per le grammatiche di tipo S e di tipo L è sufficiente considerare
l’informazione sintattica contenuta su stack
Pertanto si possono applicare le tecniche di analisi LL o LR
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
20 / 35
Tavola dei Simboli ed Errori
1
Analisi Semantica guidata dalla Sintassi
Introduzione
Estensione
2
Grammatiche ad Attributi
Regole Semantiche
Classi di Attributi
Tipi di Grammatiche ad Attributi
3
Tavola dei Simboli ed Errori
Tavola dei Simboli
Errori Semantici
Procedura Gestione Errori
4
Ottimizzazione
Costanti
Codice
Espressioni
Cicli
Varie
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
21 / 35
Tavola dei Simboli ed Errori
Tavola dei Simboli
Tavola dei Simboli/3
Tavola dei Simboli: formata da descrittori di identificatori
chiave = nome identificatore
tipo pre-definito: occupazione di memoria
tipo puntatore:
occupazione memoria
puntatore al descrittore del tipo puntato
costanti
intere o assimilabili
reali
tipo array:
occupazione di memoria
puntatore ad un descrittore di array
numero indici
valore parte costante
puntatore al descrittore del tipo dell’array
puntatore ai descrittori degli indici (inf,sup)
tipo record:
N. Fanizzi
occupazione memoria
Analisi Semantica e Generazione Codice
Linguaggi di prog.+Lab
7 maggio 2014
22 / 35
Tavola dei Simboli ed Errori
Errori Semantici
Errori Semantici
id. non dichiarato
numero parametri errato
id. già dichiarato
operando non intero o reale
tipo non valido
operando non booleano
estremi indice non validi
tipi non compatibili
operando non valido
operatore non ammesso
tipi non uguali
operando non puntatore
nome tipo non valido
argomento non valido
indice non valido
campo record non valido
numero di indici errato
operando non array
espressione non valida
operando non record
assegnazione errata
parametro attuale di tipo errato
nome sottoprogramma errato
passaggio parametro in modo errato
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
23 / 35
Tavola dei Simboli ed Errori
Procedura Gestione Errori
Procedura Gestione Errori
error(codice_errore, id )
Se il parametro id ha valore NULL_ID
allora il messaggio d’errore viene sempre stampato
altrimenti viene consultata una lista di errori e si stampa il
messaggio se il codice non vi appartiene già
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
24 / 35
Ottimizzazione
1
Analisi Semantica guidata dalla Sintassi
Introduzione
Estensione
2
Grammatiche ad Attributi
Regole Semantiche
Classi di Attributi
Tipi di Grammatiche ad Attributi
3
Tavola dei Simboli ed Errori
Tavola dei Simboli
Errori Semantici
Procedura Gestione Errori
4
Ottimizzazione
Costanti
Codice
Espressioni
Cicli
Varie
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
25 / 35
Ottimizzazione
Ottimizzazione
Il codice prodotto dall’Analisi Semantica può essere migliorato
prima della traduzione in codice oggetto
Obiettivi:
ridurre il numero di istruzioni nel formato intermedio
(quadruple)
ridurre il fabbisogno di memoria temporanea
rendere più efficiente l’esecuzione
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
26 / 35
Ottimizzazione
Costanti
Uso Immediato e Propagazione delle Costanti
Insieme alla fase di analisi semantica:
sostituzione del riferimento di una costante simbolica con il
suo valore effettivo
conversioni di tipo
calcolo espressioni aritmetiche (o logiche) che coinvolgono
solo costanti:
Esempio
const int pi = 3.14;
...
perimetro = 2*pi*r;
porta alla generazione delle quadruple:
(*,6.28,R,T1)
(MOV,T1,-,perimetro)
Ciò equivale all’espansione di macro (constant folding)
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
27 / 35
Ottimizzazione
Codice
Eliminazione del Codice Inutile
Blocchi di codice che non saranno mai eseguiti:
Esempio
const int debug = FALSE;
...
if (debug) {...}
// if eliminabile
La propagazione delle costanti può rivelare tali blocchi inutili
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
28 / 35
Ottimizzazione
Espressioni
Manipolazione delle Espressioni
Codice più efficiente, trasformando le espressioni in forme
equivalenti.
Esempio
z = (-x-y)/(p-q);
tradotta (per risparmiare una operazione di negazione):
z = (x+y)/(q-p);
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
29 / 35
Ottimizzazione
Espressioni
Eliminazione delle Espressioni Comuni
Una espressione può comparire più volte senza cambiar valore in
un blocco di codice;
pertanto la si calcola una sola volta:
Esempio
x = y*y-w*(p+q);
z = y*y+2+8/(p+q);
diventa
t1 = y*y;
t2 = p+q;
x = t1-w*t2;
z = t1+2+8/t2;
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
30 / 35
Ottimizzazione
Espressioni
Eliminazione delle copie
copia = assegnazione del valore da una variabile ad un’altra
Esempio
v2 = v1
Se v2 non verrà più usata, si elimina la copia e
si sostituiscono le occorrenze di v2 con v1
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
31 / 35
Ottimizzazione
Cicli
Ottimizzazione dei Cicli
L’analisi statistica del codice indica che la maggior parte del
tempo spesa nei cicli.
1. Spostamento codice costante (invariante rispetto al ciclo):
Esempio
for (i=1; i<=50; i++) {
delta = x + y;
a[i] = a[i]+delta;
}
diventa
delta = x +y;
for (i=1; i<=50; i++)
a[i] = a[i] + delta;
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
32 / 35
Ottimizzazione
Cicli
Ottimizzazione: Cicli/2
2. Variabili indotte: assumono valori che dipendono dalle
var.-indice del ciclo
Si possono spesso eliminare o se ne può facilitare il calcolo:
Esempio
for (j=1; j<=20; j++) {
alfa = j * 5;
a[alfa] = b;
}
alfa = 0;
for (j=1; j<=20; j++)} {
alfa = alfa + 5;
a[alfa] = b;
}
N. Fanizzi
Linguaggi di prog.+Lab
// NB: + invece di *
Analisi Semantica e Generazione Codice
7 maggio 2014
33 / 35
Ottimizzazione
Varie
Ottimizzazione: Varie I
Fattorizzazione del codice comune:
Una istruzione (semplice o complessa) può essere presente in
rami alternativi del flusso di controllo.
Essa può essere estratta e spostata prima della diramazione:
Esempio
if (i>j)
x = a + b;
else
y = a + b;
N. Fanizzi
Linguaggi di prog.+Lab
t = a + b;
if (i>j)
x = t;
else
y = t;
Analisi Semantica e Generazione Codice
7 maggio 2014
34 / 35
Ottimizzazione
Varie
Ottimizzazione: Varie II
Calcolo parte costante indirizzo di elemento di array
Valutazione accorciata di espressioni logiche
N. Fanizzi
Linguaggi di prog.+Lab
Analisi Semantica e Generazione Codice
7 maggio 2014
35 / 35
© Copyright 2024 ExpyDoc
