EasyDLX Università degli Studi di Bologna Facoltà di Ingegneria Un linguaggio che realizza un...

EasyDLX

Università degli Studi di BolognaFacoltà di Ingegneria

Un linguaggio che realizza un sottoinsieme dell’Instruction Set Architecture del DLX

Realizzato daDaniele Biagi

Progetto per l’esame di Linguaggi e Modelli Computazionali

LS

DocenteProf. E.Denti

EasyDLX - Daniele Biagi 2

Obiettivi del progettoSviluppare 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


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 traccia dell’inidirizzo della prossima istruzione

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


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


Il set di istruzioni del DLXLe istruzioni possono essere suddivise in 3 classi:1. Istruzioni aritmetiche e logiche che possono prevedere

anche un operando immediato (I) e tipo unsigned (U):◦ 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 (≥)

2. Istruzioni di trasferimento dati:◦ Trasferimento dalla memoria (Load): LB(U), LH(U), LW

◦ Trasferimento verso la memoria (Store): SB, SH, SW

3. Istruzioni di trasferimento del controllo:◦ Istruzioni di salto condizionato: BNEZ, BEQZ

◦ Istruzioni di salto incondizionato diretto e indiretto: J, JR

◦ Istruzioni di chiamata a procedura: JAL, JALR7 Dicembre 2011


Linguaggio: esempioLOOP: ADD R1,R2,R3; R1 R2+R3

ADDI R1, R2,3; R1 R2+3

ADD R1, R5, R0; R1 R5

SLT R1, R2, R3; se R2<R3 R1 1, altrimenti R1 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;

7 Dicembre 2011

estensione del segno


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

7 Dicembre 2011

Ma, il linguaggio sviluppato comprende tutte le istruzioni delle 3 classi viste precedentemente e l’istruzione NOP.


Grammatica: i token Le parole chiave per le etichette, numeri e

separatori:

7 Dicembre 2011

<LABELJ: <LETTER> (<LETTER> | <DIGIT>)*>

<LABEL_COLON: <LABELJ> ":">

<NUMBER: (<SIGN>)? ["1"-"9"] (<DIGIT>)* | "0">

<DIGIT: ["0"-"9"]>

<COMMA: ",">

<OPEN_BRACKET: "(">

<CLOSE_BRACKET: ")">

<SIGN: "+" | "-">

<SEMICOLON: ";">

<LETTER: ["a"-"z","A"-"Z","_"]>

utilizzata nelle istruzioni di salto

es. BEQZ R4,LOOP;

utilizzata nella

definizione delle

etichette es.

LOOP:...


Grammatica: non terminali Lo scopo della grammatica:

7 Dicembre 2011

<Goal> ::= ( <Label> )? <Instruction> <SEMICOLON>

<Label> ::= <LABEL_COLON>

<Instruction> ::= <Instr3Regs>

| <Instr2RegImm>

| <InstrLoad>

| <InstrStore>

| <InstrBranch>

| <InstrJumpReg>

| <InstrJumpLab>

| <Nop>

In base al numero di operandi ed al tipo, possiamo

dividere le istruzioni in 8 tipi

diversi


Grammatica: non terminali Istruzioni di traferimento dati e di salto:

7 Dicembre 2011

<InstrLoad> ::= <OpLoad> <Register> <COMMA> <Immed> <OPEN_BRACKET> <Register> <CLOSE_BRACKET>

<OpLoad> ::= LB | LBU | LH | LHU | LW

<InstrStore> ::= <OpStore> <Immed> <OPEN_BRACKET> <Register> <CLOSE_BRACKET> <COMMA> <Register>

<OpStore> ::= SB | SH | SW

<InstrBranch> ::= <OpBranch> <Register> <COMMA> <LABELJ>

<OpBranch> ::= BEQZ | BNEZ

<InstrJumpReg> ::= <OpJumpReg> <Register>

<OpJumpReg> ::= JR | JALR

<InstrJumpLab> ::= <OpJumpLab> <LABELJ>

<OpJumpLab> ::= J | JAL

Loades. LB

R1,16(R2)

Storees. SB

16(R2),R1

Branches. BEQZ R2,LOOP

Jump con registroes. JR R31

Jump con etichetta

es. J LABEL


Grammatica: non terminali Istruzione NOP, operando immediato e registri:

7 Dicembre 2011

<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?


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:

con

7 Dicembre 2011


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


Architettura del sistema: interpretazione (1/2)

7 Dicembre 2011

caratteriAnalisi Lessicale

(Scanner o Lexer)

editor

token

Analisi Sintattica(Parser)

rappresentazione della frase

AST

Analisi Semantica

(Visitor)


Architettura del sistema: interpretazione (2/2)

Package parser:◦ EasyDLXParserTokenManager è lo

Scanner che individua i singoli token◦ EasyDLXParser è il Parser che effettua

l’Analisi Sintattica

Package sintaxtree:◦ contiene tutte le classi che possono

essere usate per la costruzione dell’ AST

Package easyDLXVisitor:

7 Dicembre 2011

◦ contiene tutti i visitor che vengono utilizzati per l’interpretazione e per il controllo semantico

...perchè 3 visitor?

generato da JavaCC

generato da JTB

Le classi visitor estendono

DepthFirstVisitor generata da JTB


Problema delle forward references

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

J LABEL;

...

LABEL: ADD R1,R2,R3;

E se avessi bisogno di fare un salto ad un’istruzione prima della definizione della sua etichetta?


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


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 47 Dicembre 2011


Architettura del sistema: interfaccia grafica e

simulazione

7 Dicembre 2011

◦ 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

L’applicazione è inoltre composta dei seguenti package:


Interfaccia Utente

7 Dicembre 2011

editor

prossima istruzione che verrà eseguita

Aspetto dell’interfaccia utente durante la simulazione: controllo

step-by-step

albero sintattico

area di notifica

stato dei registri

tabella corrispondenze etichetta-PC

stato della memoria


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


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


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


Demo

7 Dicembre 2011

EasyDLX Università degli Studi di Bologna Facoltà di Ingegneria Un linguaggio che realizza un...

Documents

Transcript of EasyDLX Università degli Studi di Bologna Facoltà di Ingegneria Un linguaggio che realizza un...