Post on 18-Feb-2019
transcript
Architettura degli Elaboratori
© 2007 F. Bergenti 1
© 2007 F. Bergenti Architettura degli Elaboratori 280
Livello Micro-Architettura
“The Pentium Pro processor and Pentium II processor may contain design defects or errors known as errata…Pentium Pro and Pentium II
processors include a feature called reprogrammable microcode, which allows certain types of errata to be
worked around via microcode updates”Fonte Ufficiale Intel
© 2007 F. Bergenti Architettura degli Elaboratori 281
Architettura di Sistema
� La CPU non è l’unico componente di un calcolatore� Le comunicazioni avvengono mediante� Bus dati� Bus indirizzi� Bus di controllo
© 2007 F. Bergenti Architettura degli Elaboratori 282
Architettura di una CPU (1/2)� Due blocchi principali� Parte operativa (o datapath)� ALU, registri, ... qualsiasi componente che elabora i dati� Parte di controllo� Acquisisce lo stato dalla parte operativa� Attiva i componenti della parte operativa� In generale, la parte di controllo coordina i componenti della parte operativa� Legge le variabili di condizionamento� Attiva le variabili di controllo� Le due parti operano in modo sincrono mediante un unico clock condiviso
© 2007 F. Bergenti Architettura degli Elaboratori 283
Variabili dicontrollo
Architettura di una CPU (2/2)
parte di controllo
Memoria Centrale
ALU Registri
MARMDR
struttura dicomunicazione
Variabili dicondizionamento
parte operativa
CS/RD/OE
Dispositivi di I/O
CPU
Architettura degli Elaboratori
© 2007 F. Bergenti 2
© 2007 F. Bergenti Architettura degli Elaboratori 284
Interfaccia con la Memoria Centrale� La CPU si interfaccia con la memoria centrale mediante� Memory Address Register (MAR), contiene l’indirizzo di lettura o scrittura� Memory Data Register (MDR), contiene il dato letto o scritto� Variabili di controllo CS (Chip Select), RD (Read), OE (Output Enabled)� Operazione di scrittura mem[a] = d� MAR viene caricato con a� MDR viene caricato con d� CS=1, RD=0, OE=0� ...attesa di completamento...� Operazione di lettura d=mem[a]� MAR viene caricato con a� CS=1, RD=1, OE=1� ...attesa di completamento...� MDR contiene d
© 2007 F. Bergenti Architettura degli Elaboratori 285
Parte Operativa di una CPU (1/2)� Può essere considerata una rete logica sequenziale sincrona (una FSM)� Lo stato è contenuto nei registri� Gli ingressi sono le variabili di controllo� C’è un unico clock βck� Di solito si individuano due tipi di variabile di controllo� Tipo α, che controllano le reti combinatorie� E.g., quale operazione deve compiere la ALU� Tipo β, che controllano la lettura/scrittura nei registri� Vengono usate per mascherare il segnale di clock βck
© 2007 F. Bergenti Architettura degli Elaboratori 286
Parte Operativa di una CPU (2/2)
Architettura a singolo bus
Architettura a triplo bus
© 2007 F. Bergenti Architettura degli Elaboratori 287
Parte di Controllo di una CPU� Responsabile della corretta attivazione delle variabili di controllo (sia α che β)� Sfrutta le variabili di condizionamento per decidere quali variabili di controllo attivare� Può essere considerata una rete logica sequenziale sincrona (una FSM) � Con un insieme di stati di solito semplice
Architettura degli Elaboratori
© 2007 F. Bergenti 3
© 2007 F. Bergenti Architettura degli Elaboratori 288
CPU General Purpose La parte di controllo di una CPU general purpose esegue il ciclo di fetch/execute Attiva le variabili di controllo che leggono il prossimo codice
operativo Attiva le variabili di controllo che � Decodificano il codice operativo� Leggono gli eventuali operandi Attiva le variabili di controllo che realizzano l’operazione richiesta Attiva le variabili di controllo che salvano il risultato dell’operazione eseguita Si possono individuare varie fasi (sono gli stati della FSM): Fetch Decodifica Elaborazione Salvataggio dei risultati
© 2007 F. Bergenti Architettura degli Elaboratori 289
Variabili dicondizionamento
Temporizzazione Polifase (1/2)
Fetch
Decodifica
Esecuzione
Salvataggio
Fetch
Decodifica
Esecuzione
Salvataggio
Gestionedello stato
Parte di controllo
α, β
α, β
α, β
α, β
© 2007 F. Bergenti Architettura degli Elaboratori 290
Clock
Fetch
Decodifica
Esecuzione
Salvataggio (Write Back)
Temporizzazione Polifase (2/2)
© 2007 F. Bergenti Architettura degli Elaboratori 291
Sintesi della Parte di Controllo� Due approcci alla progettazione della parte di controllo Hardwired (cablata) Micro-programmata� Per entrambi gli approcci Lo stato è rappresentato solo dalla fase di
elaborazione È sufficiente progettare una rete combinatoria che, fissata la fase, generi le variabili di controllo in funzione della variabili di condizionamento
Architettura degli Elaboratori
© 2007 F. Bergenti 4
© 2007 F. Bergenti Architettura degli Elaboratori 292
Parte di Controllo Hardwired (1/2)
© 2007 F. Bergenti Architettura degli Elaboratori 293
Parte di Controllo Hardwired (2/2)� Nell’approccio hardwired, la parte di controllo viene progettata come una rete combinatoria� Si progetta usando le tecniche già viste� Vantaggi� Massima libertà nelle scelte progettuali� Massima possibilità di minimizzare i costi� Svantaggi� La rete è molto complessa (elevato numero di ingressi e di
uscite)� La rete è difficilmente modificabile (e.g., per correggere degli errori o per realizzare delle ottimizzazioni)� Questa tecnica oggi è poco (quasi mai) utilizzata
© 2007 F. Bergenti Architettura degli Elaboratori 294
Parte di Controllo Micro-programmata (1/2)� In ogni istante, l’uscita della parte di controllo (le variabili di controllo) formano una singola operazione atomica minima che la CPU esegue� Queste operazioni vengono dette micro-istruzioni� Possiamo pensare di programmare il comportamento della CPU usando le micro-operazioni� In ogni istante, la CPU eseguirà una micro-istruzione di un
micro-programma� Si parla di firmware� La parte di controllo della CPU è una ROM che contiene il micro-programma da fare eseguire alla CPU� Ogni cella della ROM contiene una sola micro-istruzione� L’indirizzo di lettura viene stabilito dalla fase e dalle variabili di
condizionamento
© 2007 F. Bergenti Architettura degli Elaboratori 295
Parte di Controllo Micro-programmata (2/2)
Architettura degli Elaboratori
© 2007 F. Bergenti 5
© 2007 F. Bergenti Architettura degli Elaboratori 296
Accumulator
ALU
Register B
PC
MAR
MDR
RAM
IR
Control
8
8
12
12
12
12
12
12
12
4
12
Bus
RW
LM
IPLPEP
LDED
LAEA
SAEU
LB
LIEI
La CPU di Eckert (1/2)
© 2007 F. Bergenti Architettura degli Elaboratori 297
La CPU di Eckert (2/2)� L = Load� Il registro ricevere un dato dal bus� E = Export to bus� Il registro copia il suocontenuto sul bus� IP = Increment PC� A/S = Add/Subtract� R/W = Read/Write
ACC
ALU
B
PC
MAR
MDR
RAM
IR
ControlBus
RW
LM
IPLPEP
LD
ED
LAEA
S
AEU
LB
LIEI
© 2007 F. Bergenti Architettura degli Elaboratori 298
Linguaggio Macchina della CPU di Eckert
Micro-istruzioniMnemonicoAzioneCodice
OperativoMnemonico
Stop Clock8-15HLT
NF : EI,LP1. PC �IR if NF is setPC �MemIf NF flag is set
7JN
EI,LP1. PC �IRPC �Mem6JMP
EA,LB1. B �AB �A5MBA
S,EU,LA1. A �ALU(Sub)A �A-B4SUB
EP,LMRED,LI,IP
1. MAR �PC2. MDR �M(MAR)3. IR � MDR
IR �Next Instruction“Fetch”
A,EU,LA1. A �ALU(Add)A �A+B3ADD
EI,LMEA,LDW
1. MAR �IR2.MDR �A3. M(MAR) � MDR
(Mem) �A2STA
Store Accumulator
EI,LM
RED,LA
1. MAR �IR2. MDR �M(MAR)3. A �MDR
A �(Mem)1
LDALoad Accumulator
© 2007 F. Bergenti Architettura degli Elaboratori 299
Controllo Hardwired (1/2)
IR
Decodificadel codiceoperativo
Matrice diControllo
LDASTA
ADDSUB
MBAJMP
JN
Passo
NF
T5 T1
Halt
Opcode
Variabili diControllo
CLK
Architettura degli Elaboratori
© 2007 F. Bergenti 6
© 2007 F. Bergenti Architettura degli Elaboratori 300
Controllo Hardwired (2/2)
T3*F
T3*F
JN
T3T3JMP
T3T3T3SUB
T3T3T3ADD
T3T3MBA
T4T3T4T5T3STA
T5T3T5T4T3LDA
T2T2T1T0T0T2Fetch
LBEUSAEALAEILIEDLDWRLMEPLPIP
© 2007 F. Bergenti Architettura degli Elaboratori 301
Matrice di Controllo� Tipicamente realizzata con una o piùPLA� Può avere una struttura gerarchica� Per reti
complesse
© 2007 F. Bergenti Architettura degli Elaboratori 302
Interprete delle Micro-Istruzioni (1/2)
Variabili diControlloHLT
IRGeneratoreIndirizzo di
Inizio
µPC
Memoria diControllo
CLK
+1
µIR
+NF
& CDMAP
1*
01
00
32 x 24
Indirizzo di saltodalla Control ROM
4-bit opcode
Variabili diCondizionamento
© 2007 F. Bergenti Architettura degli Elaboratori 303
Interprete delle Micro-Istruzioni (2/2)� Ogni micro-istruzione contiene due parti� Indirizzo della prossima micro-istruzione da eseguire� Variabili di controllo da inviare alla parte operativa� L’architettura è composta da� Una memoria di controllo che contiene i micro-programmi relativi ai codici operativi del linguaggio macchina� Un generatore di indirizzo d’inizio che associa ad ogni codice operativo un micro-programma� Registri µPC e µIR per caricare la prossima micro-istruzione da eseguire� Una logica per stabilire qual’è l’indirizzo della prossima micro-istruzione da eseguire
Architettura degli Elaboratori
© 2007 F. Bergenti 7
© 2007 F. Bergenti Architettura degli Elaboratori 304
Salti In-/Condizionati� Il µPC consente di scandire sequenzialmente il micro-programma� Serve spesso poter fare salti in-/condizionati (e.g., per implementare JZ)� La logica dice dove andare a prendere l’indirizzo della prossima micro-istruzione
� � � � � � �� � !→ " # $ $� � %→ � � & & � ' () * � +(, � * - . ( � / �0 � & � � ) � / � ( . ( � / � � �10
� � � � � � � & & � ' () * � +(, � * - . ( � / �0 � & � � ( / ) � / � ( . ( � / � � �00
� � � � � � � & & 1 2 3*1
4 5 6 7 8 7 9 9 :; <= > ?© 2007 F. Bergenti Architettura degli Elaboratori 305
070000001000001000000062STA
08000000000100001000007
00000000001000000000008
XX10000000000000000001FFHLT
10-1E8-EExpansion
0000001000000010000000F
0000000000000000000000E
0F00100000000000000000D7JN
0000001000000010000000C6JMP
0000000000000000100010B5MBA
0000000000000001001100A4SUB
000000000000000101010093ADD
00000000000010010000005
05000000010000000000004
040000001000001000000031LDA
XX010100000011000000002
020000000100000000000010Fetch01000001100000000000000
Instruction Op-Code Address Control Signals CD MAP HLT Next
LB
EU
SAEA
LA
EI
LI
ED
LD
WRLM
EP
LP
IP
© 2007 F. Bergenti Architettura degli Elaboratori 306
070000001000001000000062STA
08000000000100001000007
00000000001000000000008
XX10000000000000000001FFHLT
10-1E8-EExpansion
0000001000000010000000F
0000000000000000000000E
0F00100000000000000000D7JN
0000001000000010000000C6JMP
0000000000000000100010B5MBA
0000000000000001001100A4SUB
000000000000000101010093ADD
00000000000010010000005
05000000010000000000004
040000001000001000000031LDA
XX010100000011000000002
020000000100000000000010Fetch01000001100000000000000
Instruction Op-Code Address Control Signals CD MAP HLT Next
LB
EU
SAEA
LA
EI
LI
ED
LD
WRLM
EP
LP
IP
MBA1. MAR @PC2. MDR @M(MAR)3. IR @MDR4. B @A
© 2007 F. Bergenti Architettura degli Elaboratori 307
070000001000001000000062STA
08000000000100001000007
00000000001000000000008
XX10000000000000000001FFHLT
10-1E8-EExpansion
0000001000000010000000F
0000000000000000000000E
0F00100000000000000000D7JN
0000001000000010000000C6JMP
0000000000000000100010B5MBA
0000000000000001001100A4SUB
000000000000000101010093ADD
00000000000010010000005
05000000010000000000004
040000001000001000000031LDA
XX010100000011000000002
020000000100000000000010Fetch01000001100000000000000
Instruction Op-Code Address Control Signals CD MAP HLT Next
LB
EU
SAEA
LA
EI
LI
ED
LD
WRLM
EP
LP
IP
JNZ (con flag a 0)1. MAR @PC2. MDR @M(MAR)3. IR @MDR4. CD @1
Architettura degli Elaboratori
© 2007 F. Bergenti 8
© 2007 F. Bergenti Architettura degli Elaboratori 308
070000001000001000000062STA
08000000000100001000007
00000000001000000000008
XX10000000000000000001FFHLT
10-1E8-EExpansion
0000001000000010000000F
0000000000000000000000E
0F00100000000000000000D7JN
0000001000000010000000C6JMP
0000000000000000100010B5MBA
0000000000000001001100A4SUB
000000000000000101010093ADD
00000000000010010000005
05000000010000000000004
040000001000001000000031LDA
XX010100000011000000002
020000000100000000000010Fetch01000001100000000000000
Instruction Op-Code Address Control Signals CD MAP HLT Next
LB
EU
SAEA
LA
EI
LI
ED
LD
WRLM
EP
LP
IP
JNZ (con flag a 1)1. MAR APC2. MDR AM(MAR)3. IR AMDR4. CD A1
© 2007 F. Bergenti Architettura degli Elaboratori 309
Formato delle Micro-Istruzioni (1/3)B Quale formato scegliere per le micro-istruzioni?C Risposta breve...non importaB Nell’esempio della CPU di EckertC Un bit per ogni variabile di controlloC L’ordine dei bit non è influenteC Le micro-istruzioni tendono ad essere largheD La parola della memoria di controllo è largaB La larghezza della parola della memoria di controllo è usata maleC Solo pochi bit sono a 1 contemporaneamenteC Questo schema è detto orizzontale
© 2007 F. Bergenti Architettura degli Elaboratori 310
Formato delle Micro-Istruzioni (2/3)E Nello schema verticale si codificano i bit in modo da sfruttare al meglio il parallelismoF Alcune variabili di controllo sono tra loro
mutuamente esclusiveF Alcune variabili di controllo sono sempre a 0 o a 1 insiemeE Necessità di un decoder per pilotare le
singole variabili di controlloF Costo aggiuntivo a fronte del risparmio di area dato dalla riduzione della larghezza delle parole di controllo
© 2007 F. Bergenti Architettura degli Elaboratori 311
Formato delle Micro-Istruzioni (2/3)
IRRete di
Condizionamento
µPC
Variabili diControllo
Input dispositivi periferici
Variabili di condizionamento
Rete di Decodifica
+1
Memoria di Controllo
Architettura degli Elaboratori
© 2007 F. Bergenti 9
© 2007 F. Bergenti Architettura degli Elaboratori 312
Hardwired vs Micro-ProgrammaG Le unità di controllo hardwired sono tipicamenteH Più velociH Più difficili da progettare/correggereG Le unità di controllo micro-programmate sono tipicamenteH Ideali quando il set di istruzioni è fissato (emulazione per
compatibilità)H Quando le istruzioni della CPU sono complesse (CISC)G Nella realtà, vengono usati entrambi gli approcci in parti diverse di una stessa CPU
© 2007 F. Bergenti Architettura degli Elaboratori 313
Micro-Programma vs Software (1/2)I Ogni macchina può essere emulata su un’altra macchina mediante uno strato softwareJ VMware, VirtualPC, ...I I micro-programmi possono essere usati per realizzare in firmware l’emulazioneJ IBM System/360 (architectura a 32 bit, registri a 16 bit)K La maggior parte delle implementazioni sono a 8 bitK Micro-programmi che implementano il set di istruzioni e che
emulano le risorse hardwareI Nel 1992 la International Meta Systems (IMS) annuncia il3250J Progettato per emulare in firmware le architetture IA-32,
Motorola 68K e NMOS 6502J Non è mai stato messo in produzione
© 2007 F. Bergenti Architettura degli Elaboratori 314
Micro-Programma vs Software (2/2)I Alcune CPU permettono di scrivere la memoria di controllo (writable control store)J VAX 8800, PDP-11/60, IBM System/370I Anche le recenti architetture IA-32J Linux offre microcode_ctl per modificare (in modo non
permanente) la memoria di controlloJ Permette di correggere errori del firmware“The Pentium Pro processor and Pentium II processor may contain design defects or errors known as errata that may cause the product to deviate from published specifications…Pentium Pro and Pentium II processors include a feature called reprogrammable microcode, which allows certain types of errata to be worked around via microcode updates. The microcode updates reside in the system BIOS and are loaded into the processor by the system BIOS during the Power-On Self Test”
© 2007 F. Bergenti Architettura degli Elaboratori 315
Gestione dell’I/O (1/2)G La CPU è collegata a dei dispositivi periferici(o periferiche)G Invio/ricezione di datiH A specifici indirizziH Mediante un insieme di
possibili variabili di controlloG Due approcci principali
alla gestione delle perifericheH I/O mappedH Memory mapped
Architettura degli Elaboratori
© 2007 F. Bergenti 10
© 2007 F. Bergenti Architettura degli Elaboratori 316
Gestione dell’I/O (2/2)L Dispositivi I/O-mappedM Vengono indirizzati mediante specifiche porte di I/O della CPUM La CPU mette a disposizione dei codici operativi per la lettura/scrittura sulle porte (e.g., out, in, wait, ...)L Dispositivi memory-mappedM Vengono visti come parte della memoria centraleM Invio/ricezione dati avviene mediante scrittura/lettura in indirizzi di memoria dedicati (mappati)M Non vengono usate le porte di I/O della CPU (chepotrebbe non averle per niente)M Non vengono usati i codici operativi per il read/write sulleporte (che potrebbero non esserci)
© 2007 F. Bergenti Architettura degli Elaboratori 317
Dispositivi Memory-MappedN Tipico esempio è Apple ][O La CPU è una variante del NMOS 6502 che non ha porte di I/ON Tutti i dispositivi sono
memory-mappedO In modo testo, ogni byte nella zona di memoria da 0x400genera la scrittura di un carattere a videoO In modo grafico (monocromatico), ogni bit a partire da 0x2000 disegna un pixelO Il buffer di tastiera contiene un solo tasto premuto
© 2007 F. Bergenti Architettura degli Elaboratori 318
Sincronizzazione dell’I/OP L’invio di comandi ad una periferica può richiedere centinaia di cicli di clockP La lettura/scrittura di dati può richiedere milioni di cicli di clockP L’input dall’esterno può arrivare in ognimomentoP Necessità di tecniche di sincronizzazione per impiegare al meglio il tempo richiesto per l’accesso alle periferiche
© 2007 F. Bergenti Architettura degli Elaboratori 319
PollingQ Un programma è in attesa di un cambiamento di stato di una perifericaR Per avere la conferma dell’avvenuta scrittura dei datiR Per ottenere dei dati richiestiR ...Q Il programma entra in una fase di polling mediante un ciclo di attesa temporizzato (ciclo di attesa attiva o busy waiting)while(il registro di stato è immutato) {
sleep(periodo di polling);}Q Vengono impiegate molte risorseR La CPU è impegnata ad eseguire il cicloR Il bus di collegamento con la periferica è impegnato dalla lettura
del registro di stato
Architettura degli Elaboratori
© 2007 F. Bergenti 11
© 2007 F. Bergenti Architettura degli Elaboratori 320
Interrupt (1/3)S La CPU offre delle linee di ingresso che le periferiche usano per notificare un cambiamento di stato
© 2007 F. Bergenti Architettura degli Elaboratori 321
Interrupt (2/3)T La ricezione di un interrupt forza la CPU aU Completare l’esecuzione del codice operativo correnteU Salvare il proprio stato in uno stackU Mettersi in modalità supervisore (modalità protetta)U Disabilitare la ricezione degli interrupt (gli interrupt vengonomascherati)U Eseguire una procedura di gestione (interrupt handler)T Al termine della procedura di gestione, la CPU ripristina il
proprio stato e riprende da dove è stata interrottaT Gli handler sono implementati dal sistema operativo che poi notifica (mediante scambio di messaggi) i processi in attesa degli eventiU I processi utente non gestiscono mai direttamente l’hardware
© 2007 F. Bergenti Architettura degli Elaboratori 322
Interrupt (3/3)T Le sorgenti di interrupt possono essere varieU Anche generate dalla
CPU stessa mediante un codice operativo specifico (INT in IA-32)T Nel caso molti dispositivi
contividano la stessa linea di richiesta interrupt (Interrupt ReQuest, IRQ), la Interrupt Service Request(IRS) idenfica il dispositivo che ha prodotto la notifica
© 2007 F. Bergenti Architettura degli Elaboratori 323
Direct Memory Access (1/2)V Molti dispositivi periferici possono solo leggere/scrivere nella memoria centraleW Tipicamente, le memorie di massaV Non è conveniente tenere impegnata la CPU per tutto il ciclo di lettura/scritturaV Conviene che la CPU comandi l’operazione che poi viene eseguita in modo autonomo dalla periferica e dalla memoria centrale
Architettura degli Elaboratori
© 2007 F. Bergenti 12
© 2007 F. Bergenti Architettura degli Elaboratori 324
Direct Memory Access (2/2)X Senza DMAX Con DMAX Il DMA controller èl’arbitro dell’accesso al bus
© 2007 F. Bergenti Architettura degli Elaboratori 325
Introduzione ai Compilatori
“Ogni linguaggio naturale ha un numero di frasi potenzialmente illimitato. Anche se il numero dei suoni e delle parole è
finito, il numero dei modi in cui possono essere composti è illimitato”
N. Chomsky
© 2007 F. Bergenti Architettura degli Elaboratori 326
Compilatore (1/3)Y Un compilatore è un programma traduttoreche trasforma un programma per una macchina
Z [ in uno semanticamente equivalente per una macchina
Z \Y Di solito] È un programma per la macchina
_̂(ma
esistono anche i cross-compiler)]̀̂ è ad un livello di sistema immediatamente superiore ad
_̂] Di solito, il compilatore è scritto in
a b c
© 2007 F. Bergenti Architettura degli Elaboratori 327
Compilatore (2/3)Y Nell’uso comune, il termine compilatore si riferisce ad un traduttore da un linguaggio di programmazione ad alto livello (e.g., C o C++) in assembly] Spesso l’assemblatore è invocato in modo
trasparente e silenziosoY I compilatori sono programmi complessi perché] I linguaggi sorgente e destinazione (o oggetto)
sono complessi] È pensato per ottimizzare il codice generato
Architettura degli Elaboratori
© 2007 F. Bergenti 13
© 2007 F. Bergenti Architettura degli Elaboratori 328
Compilatore (3/3)d Essendo un programma complesso e dovendo fornire garanzie riguardo l’equivalenza semantica tra testo sorgente e testo destinazione, i compilatori seguono tutti rigidamente una strutturae Divisa in fasi successivee Ogni fase è una analisi o una traduzioned Analizzeremo una struttura semplificata in modo non troppo approfonditoe Altri corsi approfondiranno questa introduzione
mediante la teoria dei linguaggi formali
© 2007 F. Bergenti Architettura degli Elaboratori 329
Fasi del Compilatore (1/3)
AnalisiLessicale
AnalisiSintattica
AnalisiSemantica
GenerazioneCodice Intermedio
codicesorgente
OttimizzazioneGenerazione
Codice Destinazione
codicedestinazione
© 2007 F. Bergenti Architettura degli Elaboratori 330
Fasi del Compilatore (2/3)f Le varie fasi condividonog Strutture dati che vengono arricchite da una fase alla successivah E.g., la tabella dei simbolig Procedure e funzioni comunih E.g., per l’indicazione degli errori all’utentef Prima di procedere alla traduzione, il compilatore si
assicura (fasi di analisi) che il codice sorgente sia correttof Oltre a verificare la correttezza, le fasi di analisi raccolgono le informazioni necessarie per la generazione del codice destinazione
© 2007 F. Bergenti Architettura degli Elaboratori 331
Fasi del Compilatore (3/3)d Ogni fase di analisi si occupa di aspetti diversi riguardo la correttezza del codice sorgented Le fasi di analisi possono generaree Errori, il compilatore non genera il codice
destinazionee Avvisi (warning), il compilatore assume delle ipotesi e genera comunque il codiced Ci occuperemo principalmente di analisi
lessicale, sintattica e di generazione di codice destinazione
Architettura degli Elaboratori
© 2007 F. Bergenti 14
© 2007 F. Bergenti Architettura degli Elaboratori 332
Alfabeto e Linguaggio (1/2)i Riprendiamo cose già discussei Un insieme non vuoto e finito di simboli è un alfabetoj k
= { a, b, c, ..., z },
k
= {
l
,
m
,
n
,
o
, ..., p }, ...i Dato un alfabeto
q
,
q
* è l’insieme delle sequenze finite generabili con i simboli di
qj Le sequenze vengo dette stringhej Non poniamo limite alla lunghezza delle stringhej La stringa vuota ε∈ k
* e ε∉ k+i Un linguaggio
r
su un alfabeto
q
è un sottoinsieme di
q
* o
q+
© 2007 F. Bergenti Architettura degli Elaboratori 333
Alfabeto e Linguaggio (2/2)i Un linguaggio
r
può essere definitoj In modo estensionale, cioè per enumerazionej In modo intensionales Mediante una serie di regole d’appartenenza, che prendono il nome di grammaticai Consideriamo l’alfabeto
q
= { sin, cos }j È composto da due simbolij Ogni simbolo è (per comodità) rappresentato con 3 simboli di un altro alfabeto (
t
= { a, b, c, ..., z })j Se si vuole trattare questa distinzione,
kviene detto
lessico (o vocabolario) e t semplicemente alfabeto terminale
© 2007 F. Bergenti Architettura degli Elaboratori 334
Generazione e Riconoscimentou Descrivere un linguaggio
vsignifica fornire
un criterio per stabilire se una stringa s∈ vu La semplice enumerazione non basta maiw Descrizione generativa, descrizione di una macchina che produce tutte le stringhe validew Descrizione riconoscitiva, descrizione di una macchina che riceve in ingresso una stringa da riconoscere e produce in uscita un’indicazione di avvenuto riconoscimentou Le macchine devono essere realizzabili
© 2007 F. Bergenti Architettura degli Elaboratori 335
Grammaticai Un modo per realizzare un generatore di un linguaggio
rè mediante la descrizione di un
insieme di regole da utilizzare per formare (tutte e sole) le stringhe di
rj Questo insieme di regole è detto grammatica di xi L’idea di grammatica si applica anche ai riconoscitorij Insieme di regole (di riscrittura) che permettono di
trasformare una stringa di ingresso in una stringa di uscita (e.g., appartiene/non appartiene)i Serve un modo per descrivere le grammatiche (sia
in senso generativo che riconoscitivo)
Architettura degli Elaboratori
© 2007 F. Bergenti 15
© 2007 F. Bergenti Architettura degli Elaboratori 336
La Grammatica di L y (1/3)z Dato l’alfabeto
{
= { 0, 1, 2, ..., 9 } sia
| }⊆ {
* il linguaggio dei “numeri interi divisibili per 5”~ Tutte e sole le stringhe che terminano con 0 o 5 (0, 5, 10,
15, 20, 25, 30, ...)z Un insieme di regole per generare questo linguaggio potrebbero essere~ Un numero divisibile per 5 si ottiene:
Scrivendo 0, oppure scrivendo 5, oppure scrivendo una sequenza di cifre seguita da un numero divisibile per 5~ Una sequenza di cifre si ottiene:Scrivendo un simbolo di
�
, oppure scrivendo un simbolo di �
seguito da una sequenza di cifre
© 2007 F. Bergenti Architettura degli Elaboratori 337
La Grammatica di L y (2/3)
z Per scrivere questo insieme di regole abbiamo usato~ {<div5>, <sequenza>} detto insieme dei simboli non
terminali~ I simboli di
� � detto insieme dei simboli terminali~ Assumiamo di partire a generare da <div5>
<div5> → 0 | 5 | <sequenza> <div5>
<sequenza> → 0 | 1 | ... | 9 |
0 <sequenza> | 1 <sequenza> | ... |
9 <sequenza>
oppure
genera
© 2007 F. Bergenti Architettura degli Elaboratori 338
La Grammatica di L y (3/3)z Le regole ci consentono di generare 1305? Sì<div5> →<sequenza> <div5> →1 <sequenza> <div5> →1 3 <sequenza> <div5> →1 3 0 <div5> →1 3 0 5z Le regole ci consentono di generare 1304? No, basta provare tutte le possibilità, nessuna ci porta a completare la stringa
Derivazione
© 2007 F. Bergenti Architettura degli Elaboratori 339
Grammatiche BNFz Una grammatica in formato BNF (Backus Normal Form) è una quadrupla
G = <VT, VN, P, S>VT insieme finito di simboli terminaliVN insieme finito di simboli non terminali (o categorie sintattiche)P insieme finito di regole di produzione (o produzioni)s∈VN simbolo iniziale (o simbolo distinto)z Le produzioni sono coppie <α,β> scritte α→β~ α è la parte sinistra e contiene almeno un non terminale~ β è la parte destra
Architettura degli Elaboratori
© 2007 F. Bergenti 16
© 2007 F. Bergenti Architettura degli Elaboratori 340
Classificazione di Chomsky (1/3)� Chomsky classifica i linguaggi in base a delle restrizioni sulle grammatiche che li generano� Grammatiche di tipo 0: nessuna restrizione sulle produzioni� Grammatiche di tipo 1 (contestuali): le produzioni hanno la forma
γAδ→γβδcon β, γ, δ∈(VN∪VT)*, A∈VN, β≠εIn sostanza, γ e δ individuano il contesto in cui èlecito che A generi β
© 2007 F. Bergenti Architettura degli Elaboratori 341
Classificazione di Chomsky (2/3)� Grammatiche di tipo 2 (non contestuali o libere dal contesto): le produzioni hanno la forma
A→βcon β∈(VN∪VT)*, A∈VN, β≠ε� Una grammatica delle espressioni aritmetiche (con + e *) ènon contestuale<espressione> → <espressione> + <termine> |
<termine><termine> → <termine> * <fattore> | <fattore><fattore> → (<espressione>) | <numero><numero> → <cifra> <numero> | <cifra><cifra> → 0 | 1 | ... | 9
© 2007 F. Bergenti Architettura degli Elaboratori 342
Classificazione di Chomsky (3/3)� Grammatiche di tipo 3 (regolari): le produzioni hanno la forma
A→aB oppure A→acon A, B∈VN, a∈VT� Esempi di linguaggi regolari definiti sull’alfabeto
�={a,b} sono�
= { s∈ �* : s=anb con n
�0 }�
= { s∈ �* : s=a(ba)n con n
�0 }
© 2007 F. Bergenti Architettura degli Elaboratori 343
FSM Riconoscitori di Linguaggi (1/2)� Le FSM possono essere utilizzate come riconoscitori di linguaggi � Data s, per sapere se s∈ �
si può costruire un FSM che, partendo da uno stato iniziale e scandendo s un simbolo alla volta, arrivi in alcuni stati (detti di accettazione) se e solo se s∈ �� In modo equivalente, è possibile identificare gli stati di
rifiuto� È importante notare che� Le FSM possono riconoscere solo linguaggi regolari� Ogni linguaggio regolare ammette almeno una FSM riconoscitore
Architettura degli Elaboratori
© 2007 F. Bergenti 17
© 2007 F. Bergenti Architettura degli Elaboratori 344
FSM Riconoscitori di Linguaggi (2/2)
� Riconoscitore di
�
= { s∈ �
* : s=a(ba)n con n
�
0 }� q0 stato iniziale, q1 stato di accettazione, qr stato di rifiuto
q0 qR q1
a
b
b
a
a
b
© 2007 F. Bergenti Architettura degli Elaboratori 345
Derivazione Canonica (1/2)� I linguaggi di programmazione più diffusi sono descritti mediante grammatiche non contestuali� ALGOL 60 è stato il primo� Backus ha introdotto la notazione BNF per
descrivere la grammatica dell’ALGOL 60� Nelle grammatiche non contestuali, una parte destra può contenere più simboli non terminali� Quale espandere in una derivazione?� Possiamo trovare una regola generale?
© 2007 F. Bergenti Architettura degli Elaboratori 346
Derivazione Canonica (2/2)
S→2001100S→20011005. A→10
S→500110SS→50S11004. A→SS
S→2001ASS→30S1A03. A→S1A
S→30S1ASS→20A02. S→0
S→10ASS→10AS1. S→0AS
Derivazione canonica sinistra di
s=001100
Derivazione canonica destra di
s=001100
Grammatica
© 2007 F. Bergenti Architettura degli Elaboratori 347
Albero Sintattico� Per le grammatiche non contestuali, fissato un ordine di derivazione si possono costruire gli alberi sintattici (o alberi di derivazione, o parse tree)� Nodi interni sono simboli
non terminali� Le foglie sono simboli terminali o ε� Esempio
<e>→<e> + <e><e>→<e> * <e><e>→(<e>)<e>→n s = (n + n) * n
e
e
e
e e
e
( )
*
n
+
nn
Architettura degli Elaboratori
© 2007 F. Bergenti 18
© 2007 F. Bergenti Architettura degli Elaboratori 348
Grammatiche Ambigue (1/2)� Una grammatica non contestuale è detta ambigua se ammette più derivazioni canoniche destre (o sinistre) diverse� Esiste almeno un non terminale che, durante la
derivazione, può essere espanso in più modi distinti� È importante notare che� Esistono grammatiche di questo tipo� Non è sempre possibile rimuovere le ambiguità� La rimozione delle ambiguità (anche quando possibile) non è in generale automatizzabile
© 2007 F. Bergenti Architettura degli Elaboratori 349
Grammatiche Ambigue (2/2)� Partiamo dalla grammatica delle espressioni aritmetiche<e> → <e>+<e> | <e>-<e> | <e>*<e> |
<e>/<e> | (<e>) | -<e> | n� Possiamo renderla non ambigua esplicitando l’ordine di valutazione<e>→<e>+<t> | <e>-<t> | <t><t> →<t>*<f> | <t>/<f> | <f><f> →-<f> | <a><a>→(<e>) | n� In generale, si parla sempre di grammatiche (rese) non ambigue
© 2007 F. Bergenti Architettura degli Elaboratori 350
Grammatiche LR ed LL� Assumiamo di scandire l’insieme dei simboli di ingresso (una sola volta) da sinistra a destra� Se adottiamo una derivazione canonica destra, si parla di
grammatiche LR (Left to right scan, Rightmost derivation)� Se adottiamo una derivazione canonica sinistra, si parla di grammatiche LL (Left to right scan, Leftmost derivation)� Le grammatiche LL sono in generale più semplici
da trattare (gli analizzatori sono più semplici) e quindi vengono spesso preferite� Sono comunque meno espressive delle LR� Per molti linguaggi di programmazione vanno comunque
bene
© 2007 F. Bergenti Architettura degli Elaboratori 351
Grammatiche LL(k)� Una grammatica è LL(k) se, ad ogni passo, èsufficiente guardare a destra (in avanti) di al più ksimboli per individuare la corretta produzione da applicare tenendo anche conto delle informazioni già acquisite� Esempio, la seguente grammatica è LL(3)S→bAbBbS→aAaBbA→aA→abB→aBB→a
È necessario leggere almeno un simbolo per decidere quale espansione di S scegliere
È necessario leggere due simboli per deciderequale espansione di B scegliere
È necessario leggere tre simboli per deciderequale espansione di A scegliere
Architettura degli Elaboratori
© 2007 F. Bergenti 19
© 2007 F. Bergenti Architettura degli Elaboratori 352
Grammatiche LL(1)� Una grammatica è LL(1) se è sufficiente leggere un solo simbolo per decidere con sicurezza quale produzione espandere� Rivestono molta importanza pratica perché sono � Molto utilizzate come base dei linguaggi di
programmazione� Semplici da trattare (gli analizzatori sono efficaci e simplici da realizzare)� Ad ogni produzione è possibile associare un
insieme guida formato dai terminali con cui una derivazione corretta della produzione può iniziare� Data due produzioni A→α e A→β in G, in G è LL(1) se e
solo se i due insiemi guida sono disgiunti
© 2007 F. Bergenti Architettura degli Elaboratori 353
Analisi Ricorsiva Discendente (1/2)� Si usa con le grammatiche LL(1)� Semplice da realizzare con linguaggi che supportano la ricorsione (C, Pascal, ...)� Si associa una procedura (ricorsiva) parseX ad ogni non terminale X� Chiamare parseX equivale a richiedere che in ingresso sia presente una stringa derivabile da X� Se una produzione è del tipo A→ Z1 Z2 ... Zn, allora� Se Zi è un non terminale, si chiama parseZ i� Se Zi è un terminale, si verifica che il simbolo corrente sia proprio Zi e si avanza al simbolo successivo� Essendo una grammatica LL(1), la gestione delle produzioni
tipo A→ A1 | A2 ... | An prevedono che il simbolo corrente consenta di scegliere quale Ai derivare� Gli insiemi guida delle Ai sono disgiunti
© 2007 F. Bergenti Architettura degli Elaboratori 354
Analisi Ricorsiva Discendente (2/2)
void parseS() {if(symbol ∈ { ‘a’, ‘c’, ‘d’ }) { /* S →Ac */
parseA(); check(‘c’); next();} else if(symbol ∈ { ‘e’ }) { /* S →eS */
next(); parseS();} else errorAndExit();
}
void parseA() {switch (symbol) {case ‘b’, ‘c’: break; /* A →ε */case ‘a’:
next(); parseA(); /* A →aAb */ check(‘b’); next(); break;
case ‘d’: next(); break; /* A →d */default: errorAndExit();}
}
main() {next(); parseS();
}dA→d
aA→aAb
b,cA→ε
eS→eS
a,c,dS→Ac
Insieme guida
Produzione
Avanza di un simbolo,errore se la stringa è finita
Errore se il simbolo correntenon è quello atteso
© 2007 F. Bergenti Architettura degli Elaboratori 355
Analizzatori e Traduttori (1/2)� Un traduttore genera una stringa di uscita in �’ per ogni stringa di ingresso corretta di
�� Un modo semplice per realizzare un traduttore è aggiungere delle azioni semantiche alle produzioni di una grammatica� L’azione viene eseguita tutte le volte che la
produzione è derivata con successo� Alle volte si ammettono delle azioni semantiche anche per produzioni derivate solo parzialmente
Architettura degli Elaboratori
© 2007 F. Bergenti 20
© 2007 F. Bergenti Architettura degli Elaboratori 356
Analizzatori e Traduttori (2/2)� Nel caso di analizzatori ricorsivi discendenti, le azioni semantiche sono aggiunte ad ogni ramo delle funzioni parseX� Questo approccio può essere usato anche per creare l’albero sintattico� Ad esempio, produrre in uscita il conteggio delle volte in cui la produzione S è stata derivatavoid parseS() {
if(symbol ∈ { ‘a’, ‘c’, ‘d’ }) { /* S →Ac */parseA(); check(‘c’); next();
} else if(symbol ∈ { ‘e’ }) { /* S →eS */next(); parseS();
} else errorAndExit();
counter++;}
Contatore delle derivazioni di S Incrementato tutte le volte che S è derivata con successo
© 2007 F. Bergenti Architettura degli Elaboratori 357
femptoC e fcc fcc è un piccolo compilatore didattico di un ridotto sottoinsieme del C ANSI chiamato femptoC¡ Solo tipo int� Non ci sono puntatori, strutture dati e aritmetica in virgola
mobile¡ Nessun preprocessore fcc genera codice assembly per IA-32 inter-operabile con codici assembly e oggetto generati dal GCC¡ Analisi sintattica ricorsiva discendente¡ L’analisi semantica viene svolta all’interno dell’analisi
sintattica¡ Nessun codice intermedio o fase di ottimizzazione
© 2007 F. Bergenti Architettura degli Elaboratori 358
Analisi Lessicale (1/2)¢ La fase di analisi lessicale£ Scandisce il codice sorgente un carattere alla volta (dall’inizio alla fine)£ Individua i singoli elementi del lessico del linguaggio sorgente£ Per ogni elemento del lessico del linguaggio sorgente, genera untoken¢ Un token è una coppia <tipo,lexema> che associa ad ogni
elemento individuato un tipo che ne individua una categoria lessicale¢ Ad esempio, scandendo un programma in linguaggio C£ 1234→<COSTANTE_INTERA, “1234”>£ 33.45f→<COSTANTE_FLOAT, “33.45f”>£ contatore→<IDENTIFICATIVO, “contatore”>£ if→<PAROLA_CHIAVE_IF, “if”>£ {→<SIMBOLO_SPECIALE_BLOCCO_APERTO, “{”>
© 2007 F. Bergenti Architettura degli Elaboratori 359
Analisi Lessicale (2/2) L’analizzatore lessicale (o scanner o lexer) traduce una sequenza di caratteri in una sequenza di token Viene fatto un token alla volta, su richiesta dell’analizzatore sintattico È la funzione next() di un analizzatore sintattico ricorsivo discendente
AnalizzatoreLessicale
i f ( i = =Analizzatore
Sintattico
1. next()
2. <PAROLA_CHIAVE_IF, “if”>
testina di lettura
Architettura degli Elaboratori
© 2007 F. Bergenti 21
© 2007 F. Bergenti Architettura degli Elaboratori 360
Analisi Lessicale in fcc¤ È tutto contenuto in scanner.h e scanner.c¤ La funzione scan() legge il prossimo token della stringa di input e riempie le variabili globali tokenLexeme e tokenType¤ Le categorie lessicali disponibili sono¥ Identificatori (iniziano con una lettera e contengono lettere, cifre e ‘_’)¥ Costanti intere (iniziano con una cifra e contengono solo cifre)¥ Simboli di blocco aperto e chiuso (‘{’ e ‘}’)¥ Simbolo di assegnamento ‘=’¥ Simboli ‘(’, ‘)’, ‘;’, ‘,’¥ Simboli aritmetici (‘+’, ‘-’, ‘*’, ‘/’)¥ Simboli di relazioni (‘==’, ‘!=’, ‘>’, ‘>=’, ‘<’, ‘<=’)¥ Simboli per i connetivi logici (‘&&’, ‘||’, ‘!’)¥ Parole chiave ‘extern’, ‘return’, ‘int’, ‘if’, ‘else’ e ‘while’¤ Per identificare la categoria sintattica¥ Spesso basta leggere un solo carattere¥ Per casi particolari (e.g., per distinguere ‘=’ da ‘==’) è necessario leggere anche il
carattere successivo¤ Per ogni categoria c’è una costante TOKEN_TYPE_Xin scanner.h
© 2007 F. Bergenti Architettura degli Elaboratori 361
Analisi Sintattica¦ L’analizzatore sintattico (o parser)§ Scandisce la stringa di token uno alla volta§ Costruisce la tabella dei simboli§ Costruisce l’albero sintattico§ Genera il codice intermedio¦ La tabella dei simboli§ Viene usata per raccogliere tutte le informazioni riguardo i simboli scelti dal programmatore¨ Nomi di variabili, funzioni, procedure, ...§ Associa ad ogni simbolo delle informazioni (attributi)¨ Il suo token¨ Altre informazioni che dipendono dal tipo di simbolo§ Viene condivisa da molte fasi del compilatore
© 2007 F. Bergenti Architettura degli Elaboratori 362
Tabella dei Simboli in fcc (1/2)¤ È tutto contenuto in table.h e table.c¤ I simboli possono essere di vario tipo (variabile, parametro o funzione)¤ I simboli sono strutture con parte variabiletypedef struct {
char lexeme[MAX_LEXEME_LENGTH + 1];SYMBOL_TYPE type;union {
/* type == SYMBOL_TYPE_VARIABLEtype == SYMBOL_TYPE_PARAMETERPosizione nello stack frame corrente */
int offset;/* type == SYMBOL_TYPE_FUNCTION
Numero di parametri */int parameters;
};} SYMBOL;
Parte variabile
Sostituibile con l’uso della
ereditarietà
© 2007 F. Bergenti Architettura degli Elaboratori 363
Tabella dei Simboli in fcc (2/2)¨ Le funzioni per lavorare sulla tabella dei simboli (globale al programma) sono le seguenti¨ BOOL enterScope()Apre un nuovo ambiente (scope)¨ BOOL exitScope()Chiude lo scope corrente e libera lo spazio nella tabella¨ SYMBOL* addSymbol(char* lexeme, SYMBOL_TYPE type)Aggiunge un simbolo alla tabella (se non già presente) e indica un errore in caso di simbolo già presente nello scope corrente¨ SYMBOL* getSymbol(char* lexeme)Legge un simbolo dalla tabella in base al lexema passatoViene ritornato il simbolo più profondo (relativo allo scope più interno)
Architettura degli Elaboratori
© 2007 F. Bergenti 22
© 2007 F. Bergenti Architettura degli Elaboratori 364
Analisi Sintattica in fcc (1/2)© È tutto contenuto in parser.h e parser.c© Analizza un sottoinsieme della grammatica dell’ANSI C con un analizzatore sintattico ricorsivo discendenteª Una funzione parseX() per ogni non terminale <X>ª Il punto d’ingresso è parse che deriva il simbolo distinto
della grammatica translation_unit© Controlla direttamente il generatore di codice oggettoª Non genera l’albero sintatticoª Non genera il codice intermedio (e quindi non ottimizza)
© 2007 F. Bergenti Architettura degli Elaboratori 365
Analisi Sintattica in fcc (2/2)« Con l’opzione --verbose , fcc genera un tracciato delle analisi lessicale e sintattica¬ Come commenti del codice generato¬ Se iniziano con Read sono dell’analizzatore
lessicale Tra parentesi tonde viene indicato il tipo del token¬ Se iniziano con Enter /Exit indicano gli ingressi/uscite dalle produzioni Tra parentesi tonde viene indicato il simbolo corrente
© 2007 F. Bergenti Architettura degli Elaboratori 366
Grammatica di fcc (1/4)© Le grammatiche dei linguaggi che derivano dal C sono strutturate inª Dichiarazioni® Di variabili, funzioni, tipi, strutture, ... a vari livelli di scope
con relative regole di accessoª Statement (e statement composti)® Che guidano il flusso di esecuzione (in modo sequenziale o in base al risultato prodotto dalle espressioni)ª Espressioni® Che vengono valutate e producono un risultato® L’assegnamento è un’espressione© La grammatica dei linguaggi tipo C è strutturata
tenendo conto di questi tre tipi di categorie sintattiche
© 2007 F. Bergenti Architettura degli Elaboratori 367
Grammatica di fcc (2/4)
and_expression → equality_expression ;exclusive_or_expression → and_expression ;inclusive_or_expression → exclusive_or_expression ;logical_and_expression → inclusive_or_expression
| logical_and_expression '&&' inclusive_or_expressio n ;logical_or_expression → logical_and_expression
| logical_or_expression '||' logical_and_expression ;conditional_expression → logical_or_expression ;
assignment_expression → conditional_expression| unary_expression '=' assignment_expression ;
expression → assignment_expression| expression ',' assignment_expression ;
jump_statement → 'return' expression ';' ;
Architettura degli Elaboratori
© 2007 F. Bergenti 23
© 2007 F. Bergenti Architettura degli Elaboratori 368
Grammatica di fcc (3/4)
shift_expression → additive_expression ;
relational_expression → shift_expression| relational_expression '<' shift_expression| relational_expression '>' shift_expression| relational_expression '>=' shift_expression| relational_expression '<=' shift_expression ;
equality_expression → relational_expression| equality_expression '==' relational_expression| equality_expression '!='relational_expression ;
© 2007 F. Bergenti Architettura degli Elaboratori 369
Grammatica di fcc (4/4)
primary_expression → IDENTIFIER | INTEGER_CONSTANT | '(' expression ')' ;
postfix_expression → primary_expression| …
unary_operator → '+' | '-' | '!' ;unary_expression → postfix_expression
| unary_operator cast_expression ;cast_expression → unary_expression ;
multiplicative_expression → cast_expression| multiplicative_expression '*' cast_expression| multiplicative_expression '/' cast_expression ;
additive_expression → multiplicative_expression| additive_expression '+' multiplicative_expression| additive_expression '-' multiplicative_expression ;
Grammatica delle chiamate a funzione
© 2007 F. Bergenti Architettura degli Elaboratori 370
{ return a + 1; } in fcc
Enter compound_statement ({) Enter declaration_list (return) Exit declaration_list (return) Enter statement (return) Enter jump_statement (return) Enter expression (a) Enter assignment_expression (a) Enter conditional_expression (a) Enter logical_or_expression (a) Enter logical_and_expression (a) Enter inclusive_or_expression (a) Enter exclusive_or_expression (a) Enter and_expression (a) Enter equality_expression (a) Enter relational_expression (a) Enter shift_expression (a) Enter additive_expression (a) Enter multiplicative_expression (a) Enter cast_expression (a) Enter unary_expression (a) Enter postfix_expression (a) Enter primary_expression_identifier (a) Enter argument_expression (a) Exit argument_expression (+) Exit primary_expression_identifier (+) Exit postfix_expression (+) Exit unary_expression (+) Exit cast_expression (+) Exit multiplicative_expression (+)
Enter multiplicative_expression (1) Enter cast_expression (1) Enter unary_expression (1) Enter postfix_expression (1) Exit postfix_expression (;) Exit unary_expression (;) Exit cast_expression (;) Exit multiplicative_expression (;) Exit additive_expression (;) Exit shift_expression (;) Exit relational_expression (;) Exit equality_expression (;) Exit and_expression (;) Exit exclusive_or_expression (;) Exit inclusive_or_expression (;) Exit logical_and_expression (;) Exit logical_or_expression (;) Exit conditional_expression (;) Exit assignment_expression (;) Exit expression (;) Exit jump_statement (}) Exit statement (}) Exit compound_statement ()
© 2007 F. Bergenti Architettura degli Elaboratori 371
Analisi Semantica (1/2)¯ Per semplicità, l’analisi sintattica è sempre pensata per grammatiche non contestuali° Che sono prime approssimazioni delle
grammatiche “vere” del linguaggio° Ad esempio, la grammatica del C ANSI non specifica che uno stesso identificatore di variabile non può apparire due volte in una stessa dichiarazione¯ L’analisi semantica si occupa di verificare
che le restrizioni non espresse nella grammatica siano effettivamente rispettate
Architettura degli Elaboratori
© 2007 F. Bergenti 24
© 2007 F. Bergenti Architettura degli Elaboratori 372
Analisi Semantica (2/2)± Tipicamente si occupa di² Verificare che uno stesso identificatore non sia dichiarato più volte in uno stesso ambiente (scope)² Verificare che all’atto di una chiamata venga rispettata la segnatura (signature) delle funzioni³ La segnatura di una funzione è l’insieme del suo nome, dei
tipi dei suoi parametri e del tipo del valore di ritorno² Verificare che le espressioni e gli assegnamenti lavorino su tipi convertibili³ Ad esempio, float x = 1 è convertibile, float y = “123” non lo è² Gestire l’overloading di operatori e la conversione dei tipi² Verificare le peculiarità di alcuni statement³ Ad esempio, case multipli o return mancanti² Individuare statement inutili o irraggiungibili
© 2007 F. Bergenti Architettura degli Elaboratori 373
Codice Intermedio´ Esistono vari tipi di codici intermedi utilizzabiliµ AST (Abstract Syntax Tree)µ Liste di quadruple´ Scopo del codice intermedio è supportare efficacemente la successiva ottimizzazioneµ La scelta del tipo di codice intermedio facilita
alcune ottimizzazioni e ne complica delle altre´ La scelta di un buon codice intermedio influenza la portabilità del compilatore
© 2007 F. Bergenti Architettura degli Elaboratori 374
Alberi di Sintassi Astratta¶ Alberi in cui· Nodi intermedi sono “operatori” del linguaggio· Foglie sono costanti o identificativi¶ Sono ottenuti per
manipolazione dagli alberi di derivazione· Togliendo i dettagli
sintattici (zucchero sintattico)· Realizzando una versione astratta del codice sorgente
(n + n) * n
*
n n
n+
© 2007 F. Bergenti Architettura degli Elaboratori 375
Liste di Quadruple (1/2)¶ Liste di quadruple del tipo <op, o1, o2, d> che vanno intese come la valutazione di un’operazione binaria seguito da un assegnamento
d=op(o1, o2)¶ È un formalismo pensato per valutare espressioni aritmetiche· Si adatta bene anche a statement più complessi· È simile all’assembly e quindi vicino al codice oggetto¶ Ad esempio A=(A+B)*(C-D) è tradotto in<+,A,B,T1><-,C,D,T2><*,T1,T2,A>
Architettura degli Elaboratori
© 2007 F. Bergenti 25
© 2007 F. Bergenti Architettura degli Elaboratori 376
Liste di Quadruple (2/2)
i=0
while(i*i < q) {
i++
}
...105
<=,0,_,i>100
<jmp,101,_,>104
<inc,i,_,_>103
<bge,T 1,q,105>102
<*,i,i,T 1>101
QuadruplaContatore
Nota:
bge – Branch if Greater or Equal
jmp – Jump
inc – Increment
© 2007 F. Bergenti Architettura degli Elaboratori 377
Generatore di Codice¸ In generale, possiamo pensare che un compilatore generi codice assembly¹ Viene poi passato ad un assemblatore e ad un
linker¸ La traduzione tra codice intermedio e codice oggetto è semplice¹ L’ottimizzatore ha prodotto un codice intermedio
pronto per essere tradotto¹ Molte scelte già compiute dall’ottimizzatore: registri usare, come usarli, ...
© 2007 F. Bergenti Architettura degli Elaboratori 378
Valutazione di Espressioni in fccº %eax viene usato come accumulatore» Contiene l’ultimo valore
calcolato» Contiene l’argomento sinistro degli operatori binariº %ebx contiene l’argomento
destro degli operatori binariº Lo stack contiene i valori intermedi» Salva (push) gli argomenti
destri degli operatori binariº Esempio: 2 * (1 + 3 * f(a, b))
movl $2, %eaxpushl %eax
movl $1, %eaxpushl %eax
movl $3, %eaxpushl %eax
...call f...
popl %ebximull %ebx, %eax
popl %ebxaddl %ebx, %eax
popl %ebximull %ebx, %eax
© 2007 F. Bergenti Architettura degli Elaboratori 379
Generazione di Chiamate in fccº Vengono generati pre-/post-amboloº I valori degli argomenti vengono messi in %eaxº Il risultato è in %eaxº Esempio f(a, b)º Coerente con la valutazione delle espressioni» Gli argomenti possono
essere il risultato della valutazione di un’espressione» Il valore di ritorno può essere parte della valutazione di una espressione
# riserva lo spazio per # gli argomentisubl $8, %esp
# salva amovl -4(%ebp), %eaxmovl %eax, 0(%esp)# salva bmovl -8(%ebp), %eaxmovl %eax, 4(%esp)# chiama fcall f
# libera lo spazio per gli# argomentiaddl $8, %esp
Architettura degli Elaboratori
© 2007 F. Bergenti 26
© 2007 F. Bergenti Architettura degli Elaboratori 380
Generatore di Codice in fcc (1/3)¼ È tutto contenuto in emitter.h e emitter.c, nelle seguenti funzioni¼ void initializeEmitter()Inizializza la generazione del codice¼ void enableEmitter() , void disableEmitter()Usate per attivare/disattivare la generazione di codice (in caso di errore, il generatore di codice viene disattivato)¼ void emitUnitHeader(char* name) , void emitUnitFooter()Usati per marcare l’inizio e la fine di un’unità di compilazione (file oggetto)¼ void emitFunctionHeader(char* name) ,void emitFunctionFooter()Emettono pre-/post-ambolo di una funzione¼ void emitFunctionLocals(int localsCount)Riserva lo spazio nello stack fram per localsCount variabili locali
© 2007 F. Bergenti Architettura degli Elaboratori 381
Generatore di Codice in fcc (2/3)¼ int reserveLabel()Richiede un indice per una nuova label nel codice; l’indice viene poi passato alle funzioni che emettono i salti (condizionati o incondizionati)¼ void emitReturn() ,void emitIfTest(int elseLabel) ,void emitWhileTest(int elseLabel) ,void emitGotoLabel(int label)Emettono il codice per i relativi statement¼ void emitCallHeader(int arguments) ,void emitCallArgument(int counter) ,void emitCallFooter(char* name, int arguments)Emettono il codice relativo ad una chiamata a procedura (push degli argomenti, chiamata, pop degli argomenti)
© 2007 F. Bergenti Architettura degli Elaboratori 382
Generatore di Codice in fcc (3/3)½ void emitAssignment(SYMBOL* lvalue)Emette il codice di assegnamento al simbolo (che è garantito essere un l-value, quindi variabile o argomento)½ void emitVariableExpression(SYMBOL* symbol) ,void emitArgumentExpression(SYMBOL* symbol) ,void emitIntegerConstantExpression(char* value)Emettono il codice per i terminali delle espressioni½ void emitProduct() , void emitDivision() , void emitSum() , void emitDifference() , void emitNegation() , emitLogicAnd() , emitLogicOr()Emettono il codice relativo agli operatori nelle espressioni
© 2007 F. Bergenti Architettura degli Elaboratori 383
Gestione degli Errori¾ In generale esistono tre categorie di errori e warning¿ Lessicali: identificatori troppo lunghi, caratteri non
consentiti, ...¿ Sintattici: espressioni non riconducibili alla grammatica¿ Semantici: identificatori non dichiarati, costanti fuori range, istruzioni irraggiungibili, ...¾ Il compilatore dovrebbe fornire il maggior numero
possibile di errori prima di fermarsi¿ Cercando di evitare l’effetto valanga definendo dei punti di ripristino (e.g., la chiusura di un blocco o di una funzione)¿ Alcuni compilatori fanno due passate prima di indicare un errore
Architettura degli Elaboratori
© 2007 F. Bergenti 27
© 2007 F. Bergenti Architettura degli Elaboratori 384
Gestione degli Errori in fccÀ È tutto contenuto in error.h e error.cÀ Viene definito un tipo enumetativo RESULTche identifica i possibili errori e warningÁ Per ogni valore enumerativo viene indicata una
stringa leggibileÀ Le funzioni per generare errori e warning sono RESULT error(RESULT result) , RESULT warning(RESULT result)Á In caso di errore, non viene più generato codiceÁ Non viene fissato un numero massimo di errori
che forza la terminazione della compilazione
© 2007 F. Bergenti Architettura degli Elaboratori 385
Compilatori di Compilatori Sono programmi che leggono una grammatica tipo BNF e producono il sorgente (in un opportuno linguaggio oggetto) di una procedura di analisi sintattica della grammaticaà Permettono di includere le azioni semantiche direttamente
nella grammatica come blocchi di codice nel linguaggio oggettoà Spesso generano anche l’analizzatore lessicale Ne esistono vari (per vari linguaggi oggetto, per vari
tipi di BNF, ...)Ã Per il C/C++: YACC (Yet Another Compiler Compiler), Bison, ...Ã Per Java: JavaCC (Java Compiler Compiler), ...