Università degli Studi di Bologna
Facoltà di Ingegneria
EasyDLX
Un linguaggio che realizza un
sottoinsieme dell’Instruction Set
Architecture del DLX
Progetto per l’esame di
Linguaggi e Modelli Computazionali LS
Realizzato da
Daniele Biagi
Docente
Prof. E.Denti
Obiettivi del progetto



Sviluppare un linguaggio che consenta di
simulare delle operazioni su un processore DLX.
Realizzare un interprete per questo linguaggio
che possa aggiornare lo stato interno di una
macchina virtuale.
Realizzare un’interfaccia grafica dotata di un
editor per la scrittura di codice e che possa
mostrare passo passo lo stato della macchina
virtuale.
7 Dicembre 2011
EasyDLX - Daniele Biagi
2
Principali caratteristiche del
DLX (1/2)





Istruzioni di tipo RISC (Reduced Instruction Set
Computer)
Le istruzioni sono sempre allineate ad indirizzi
multipli di 4
Program Counter (PC) per tenere
dell’inidirizzo della prossima istruzione
traccia
32 registri general purpose da 32 bit (R0..R31,
R0=0)
32 registri da 32 bit ed un registro di stato sono
dedicati per operazioni floating point.
7 Dicembre 2011
EasyDLX - Daniele Biagi
3
Principali caratteristiche del
DLX (2/2)




Gli operandi immediati, dove previsti, sono codificati
con 16 bit
Lo spazio di indirizzamento è di 4 GigaByte (32bit)
Una sola modalità di indirizzamento: registro +
offset (di 16 bit)
I numeri negativi sono rappresentati in complemento
a due, mentre quelli positivi in segno-valore assoluto
7 Dicembre 2011
EasyDLX - Daniele Biagi
4
Il set di istruzioni del DLX
Le istruzioni possono essere suddivise in 3 classi:
Istruzioni aritmetiche e logiche che possono prevedere anche
un operando immediato (I) e tipo unsigned (U):
1.
◦
Istruzioni logiche: AND(I), OR(I), XOR(I)
◦
Istruzioni aritmetiche: ADD(U)(I), SUB(U)(I), MULT(U), DIV(U)
◦
Istruzioni di shift logico (a destra o a sinistra): SLL(I), SRL(I)
◦
Istruzioni di set condition, le quali se verificata una certa
condizione inseriscono un 1 nel registro di destinazione, o altrimenti
uno 0: SEQ(I) (=), SNE(I) (≠), SLT (I) (<), SGT (>), SLE (≤) , SGE (≥)
Istruzioni di trasferimento dati:
2.
◦
Trasferimento dalla memoria (Load): LB(U), LH(U), LW
◦
Trasferimento verso la memoria (Store): SB, SH, SW
Istruzioni di trasferimento del controllo:
3.
◦
Istruzioni di salto condizionato: BNEZ, BEQZ
◦
Istruzioni di salto incondizionato diretto e indiretto: J, JR
◦
Istruzioni di chiamata a procedura: JAL, JALR
7 Dicembre 2011
EasyDLX - Daniele Biagi
5
Linguaggio: esempio

LOOP: ADD R1,R2,R3;

ADDI R1, R2,3;
R1  R2+3

ADD R1, R5, R0;
R1  R5

SLT R1, R2, R3;
estensione
del R1
segno
se R2<R3 R1  1, altrimenti
0

LB R1,40(R3);
R1  (MEM[40+R3]7)24##(MEM[40+R3])

LBU R1,40(R3);
R1  (0)24## (MEM[40+R3])

SW 10(R5), R7;
MEM[10+R5]  R7

JAL alfa;
R31  PC+4, PC  (PC+4)+OFFSET(alfa)

BEQZ R4,LOOP; se R4=0 PC  PC+4+OFFSET(LOOP)

NOP;
R1  R2+R3
7 Dicembre 2011
EasyDLX - Daniele Biagi
6
Realizzazione
Dal progetto sono state escluse le operazioni ed i
registri floating point.
 Non vengono gestite le interruzioni

◦ Le istruzioni RFE, CLI, STI e TRAP non sono state
implementate

Ma, il linguaggio sviluppato
comprende
tutte
le
istruzioni delle 3 classi
viste precedentemente e
l’istruzione NOP.
7 Dicembre 2011
EasyDLX - Daniele Biagi
7
Grammatica: i token

utilizzata
nella
definizione
delle
etichette
es. LOOP:...
Le parole chiave per le etichette, numeri e
separatori:
utilizzata nelle
<LABELJ: <LETTER> (<LETTER> | <DIGIT>)*>
istruzioni di salto
es. BEQZ R4,LOOP;
<LABEL_COLON: <LABELJ> ":">
<NUMBER: (<SIGN>)? ["1"-"9"] (<DIGIT>)* | "0">
<DIGIT: ["0"-"9"]>
<COMMA: ",">
<OPEN_BRACKET: "(">
<CLOSE_BRACKET: ")">
<SIGN: "+" | "-">
<SEMICOLON: ";">
<LETTER: ["a"-"z","A"-"Z","_"]>
7 Dicembre 2011
EasyDLX - Daniele Biagi
8
Grammatica: non terminali

Lo scopo della grammatica:
<Goal> ::= ( <Label> )? <Instruction> <SEMICOLON>
<Label> ::= <LABEL_COLON>
<Instruction> ::= <Instr3Regs>
|
<Instr2RegImm>
|
<InstrLoad>
|
<InstrStore>
|
<InstrBranch>
|
<InstrJumpReg>
|
<InstrJumpLab>
|
<Nop>
7 Dicembre 2011
In base al numero di
operandi ed al tipo,
possiamo dividere le
istruzioni in 8 tipi
diversi
EasyDLX - Daniele Biagi
9
Grammatica: non terminali

Istruzioni aritmetiche e logiche:
<Instr3Regs> ::= <Op3Regs> <Register> <COMMA> <Register>
Con 3 registri
<COMMA> <Register>
es. ADD R1,R2,R3
<Op3Regs> ::= ADD | ADDU | SUB | SUBU | MULT | MULTU |
DIV | DIVU | AND | OR | XOR | SLL | SRL | SLT | SGT | SLE |
SGE | SEQ | SNE
<Instr2RegImm> ::= <Op2RegsImm> <Register> <COMMA>
Con 2 registri ed un immediato
<Register> <COMMA> <Immed>
es. ADDI R1,R2,3
<Op2RegsImm> ::= ADDI | ADDUI | SUBI | SUBUI | ANDI | ORI
| XORI | SLLI | SRLI | SLTI | SGTI | SLEI | SGEI | SEQI |
SNEI
7 Dicembre 2011
EasyDLX - Daniele Biagi
10
Grammatica: non terminali

Istruzioni di traferimento dati e di salto:
<InstrLoad> ::= <OpLoad> <Register> <COMMA> <Immed>
<OPEN_BRACKET> <Register> <CLOSE_BRACKET>
Load
es. LB R1,16(R2)
<OpLoad> ::= LB | LBU | LH | LHU | LW
<InstrStore> ::= <OpStore> <Immed> <OPEN_BRACKET> <Register>
<CLOSE_BRACKET> <COMMA> <Register>
Store
es. SB 16(R2),R1
<OpStore> ::= SB | SH | SW
<InstrBranch> ::= <OpBranch> <Register> <COMMA> <LABELJ>
<OpBranch> ::= BEQZ | BNEZ
<InstrJumpReg> ::= <OpJumpReg> <Register>
<OpJumpReg> ::= JR | JALR
<InstrJumpLab> ::= <OpJumpLab> <LABELJ>
<OpJumpLab> ::= J | JAL
7 Dicembre 2011
Branch
es. BEQZ R2,LOOP
Jump con registro
es. JR R31
Jump con etichetta
es. J LABEL
EasyDLX - Daniele Biagi
11
Grammatica: non terminali

Istruzione NOP, operando immediato e registri:
<Nop> ::= NOP
<Immed> ::= <NUMBER>
<Register> ::= R0 | R1 | R2 | R3 | R4 | R5 | R6 | R7 | R8 | R9 | R10
| R11 | R12 | R13 | R14 | R15 | R16 | R17 | R18 | R19 | R20 | R21 |
R22 | R23 | R24 | R25 | R26 | R27 | R28 | R29 | R30 | R31

Ma quali proprietà ha
questa grammatica?
7 Dicembre 2011
EasyDLX - Daniele Biagi
12
Grammatica: proprietà (1/2)

Proprietà della grammatica:
◦ non ci sono produzioni che accorciano la forma di frase
corrente
◦ le parti sinistre di tutte le produzioni presentano un
solo simbolo non terminale
◦ le produzioni non sono vincolate alle forme lineari

Quindi, secondo la classificazione di Chomsky, la
grammatica è di tipo 2 (context-free), in quanto
tutte le produzioni risultano essere nella forma:
A→α
con α ∈ VT ∪ VN ∗ , A ∈ VN
7 Dicembre 2011
EasyDLX - Daniele Biagi
13
Grammatica: proprietà (2/2)



La grammatica è LL(1), quindi basta un solo simbolo
della frase per scegliere la produzione da applicare
In particolare, la grammatica non contiene ε-rules,
quindi per verificare che sia LL(1) è sufficiente
verificare che la condizione sugli Starter Symbols
sia soddisfatta
Il linguaggio generato è regolare (tipo 3), poichè la
grammatica non contiene self-embedding
7 Dicembre 2011
EasyDLX - Daniele Biagi
14
Architettura del sistema:
interpretazione (1/2)
editor
caratteri
Analisi Lessicale
(Scanner o Lexer)
Analisi
Semantica
(Visitor)
AST
token
rappresentazione
della frase
Analisi Sintattica
(Parser)
7 Dicembre 2011
EasyDLX - Daniele Biagi
15

Architettura del sistema:
interpretazione
(2/2)
generato da
Package parser:
JavaCC
◦ EasyDLXParserTokenManager è lo
Scanner che individua i singoli token
◦ EasyDLXParser è il Parser che effettua
l’Analisi Sintattica
generato da
Package sintaxtree:
JTB
Le classi visitor
◦ contiene tutte le classi che possono
estendono
essere usate per la costruzione
dell’ AST
DepthFirstVisitor
 Package easyDLXVisitor: generata da JTB

◦ contiene tutti i visitor
che vengono utilizzati
per l’interpretazione e
per il controllo
semantico
...perchè 3 visitor?
7 Dicembre 2011
EasyDLX - Daniele Biagi
16
Problema delle forward
references

E se avessi bisogno di fare un salto ad un’istruzione
prima della definizione della sua etichetta?
J LABEL;
...
LABEL: ADD R1,R2,R3;

Prima di simulare l’esecuzione
delle istruzioni, viene eseguito
un passo in cui viene associato
un PC ad ogni istruzione.
◦ di conseguenza viene assegnato
anche un PC ad ogni etichetta che
viene definita
7 Dicembre 2011
EasyDLX - Daniele Biagi
17
Analisi Semantica
(Primo passo)

Al primo passo l’applicazione analizza le istruzioni
nell’ordine in cui sono state inserite, ed esegue dei
controlli semantici attraverso EasyDLXVisitorReferences:
◦ gli immediati con segno devono essere compresi fra -32768 e
32767
◦ gli immediati senza segno devono essere compresi fra 0 e
65535
◦ la stessa etichetta deve essere definita soltanto una volta
◦ R0 non può essere la destinazione
◦ Jump o Branch a riferimenti mai definiti

Successivamente avviene la simulazione passo-passo,
dove il contenuto dei registri e della memoria viene
modificato sfruttando EasyDLXVisitorSimulation
7 Dicembre 2011
EasyDLX - Daniele Biagi
18
Analisi Semantica
(Secondo passo)

Ora nel caso di un salto o di un branch taken si va ad
eseguire l’istruzione al nuovo PC.

Tuttavia, attraverso l’interfaccia grafica l’utente può
controllare:
◦
◦
◦
◦
◦

la prossima istruzione
quando eseguire la prossima istruzione
il contenuto dei registri
l’albero sintattico generato dal terzo visitor EasyDLXVisitorTree
il contenuto della memoria
Inoltre, ci sono le condizioni per effettuare ulteriori
controlli semantici:
◦ load e store non possono coinvolgere gli indirizzi dove sono
memorizzare le istruzioni
◦ l’indirizzo di una load deve riferirsi ad un’area di memoria dove è stato
scritto qualcosa
◦ gli indirizzi nelle LH ed SH devono essere pari
◦ gli inidirizzi nelle LW e SW devono essere multipli di 4
7 Dicembre 2011
EasyDLX - Daniele Biagi
19
Architettura del sistema:
interfaccia grafica e simulazione

L’applicazione è inoltre composta dei seguenti
package:
◦ easyDLXGUI: contiene le classi per
l’interfaccia grafica
◦ easyDLXsimulation: contiene le classi
che modellano la macchina
◦ easyDLXeditor: contiene le classi per
costruire l’editor del codice
7 Dicembre 2011
EasyDLX - Daniele Biagi
20
Interfaccia Utente

Aspetto dell’interfaccia utente durante la simulazione:
controllo
step-by-step
stato dei
registri
prossima
istruzione
che verrà
eseguita
albero
sintattico
editor
tabella
corrispondenze
etichetta-PC
area di
notifica
7 Dicembre 2011
EasyDLX - Daniele Biagi
stato della
memoria
21
Test e collaudi

Per verificare la correttezza dell’analisi sintattica e
semantica sono stati dati in input:
◦ file con errori sintattici
◦ file con errori semantici

Per accertare la correttezza delle operazioni che
simulano il DLX, gli operandi sono stati generati in
maniera casuale
◦ in questo modo i test sono attendibili e garantiscono un ottimo
grado di copertura
7 Dicembre 2011
EasyDLX - Daniele Biagi
22
Strumenti utilizzati

Linguaggio di programmazione
◦ Java (jdk1.7.0_01)

Ambiente di sviluppo
◦ Eclipse Indigo

Generazione parser e scanner
◦ JavaCC 5.0

Generazione AST e visitor
◦ Java Tree Builder 1.3.2

Ambiente di test
◦ Junit 4.8.2
7 Dicembre 2011
EasyDLX - Daniele Biagi
23
Limiti e sviluppi futuri...

Limiti:
◦ L’applicazione in caso di overflow non avvisa l’utente:
◦ Non è possibile mappare alcuna periferica
◦ Non è possibile visualizzare i bit delle aree di memoria
dove sono presenti le istruzioni

Oltre ai limiti dell’applicazione, ulteriori spunti per
sviluppi futuri sono:
◦ introduzione delle operazioni floating point
◦ introduzione delle interruzioni
7 Dicembre 2011
EasyDLX - Daniele Biagi
24
Demo
7 Dicembre 2011
EasyDLX - Daniele Biagi
25