	Biologie	Chimie	Didactica	Fizica	Geografie	Informatica
	Istorie	Literatura	Matematica	Psihologie

Calculatoare

Index » educatie » » informatica » Calculatoare
» Compilator pentru limbajul de descriere hardware LOLA

Compilator pentru limbajul de descriere hardware LOLA

PROIECT LA TEHNICI DE COMPILARE

Compilator pentru limbajul de descriere hardware

LOLA

CUPRINS:

1. Limbajul de descriere hardware Lola

1.1. Prezentarea limbajului Lola

1.2. Sintaxa limbajului Lola

2. Compilatorul de Lola

2.1. Utilizare

2.2. Particularitati ale limbajului. Mod de abordare

2.3. Note de implementare

2.4. Interfata compilatorului cu alte programe

( Structura de date oferita de compilator + operatiile asupra acestei structuri )

3. Simulatorul "Sim"

( mod de intrebuintare + exemple -> in limba Engleza )

4. Cloncuzii

Anexa A

Reprezentarea instructiunilor in arborele sintactic

Anexa B

Lista Header-elor

[MR1]

1. Limbajul de descriere hardware Lola

1.1. Prezentarea limbajului Lola

Lola este un limbaj pentru specificarea circuitelor numerice sincrone.

Pentru a evidentia radacinile acestui limbaj, mentionam faptul ca Lola a fost creat de prof. N. Wirth la Institute for Computer System, ETH Zurich.

Prof. N. Wirth este cel care in anul 1970 a creat unul din cele mai populare limbaje de programare: Pascal. Limbajul Pascal face parte dintr-o familie de limbaje a caror stramos este limbajul Algol 60 (1960), familie care mai cuprinde limbajele Modula-2 (1979) si Oberon (1988).

Ca sintaxa, Lola se aseamana cu limbajele din familia Algol si in mod special cu limbajul Oberon. Pentru cei care nu sunt familiarizati cu limbajul Oberon, precizam faptul ca el este descendentul limbajelor Pascal si Modula-2 avand o sintaxa foarte asemanatoare cu acestea (practic in plus fata de limbajul Pascal este introdus conceptul de "MODUL" precum si unele facilitati pentru proictarea orientata pe obiecte).

Prezentarea limbajului o realizam prin intermediul unui exemplu. Exemplul consta dintr-un sumator pe N biti. S-a folosit un tip compus, celula sumator complet, pentru a descrie un sumator pe 2 biti. Acest tip a fost instantiat in N exemplare formand elementele unui tablou si apoi aceste instante de celule sumator au fost cuplate pentru a forma un sumator pe N biti.

Schema hardware a circuitului de insumare este:

Z₇

Z₁

Z₀

MODULE Sumator;

TYPE Celula; (* tip compus ce descrie o celula sumator *)

IN x,y,ci:BIT; (* semnalele de intrare *)

OUT z,co:BIT; (* semnalele de iesire *)

BEGIN

z:=x-y-ci;

co:=x*y+x*ci+y*ci;

END Celula;

CONST N:=8;

IN X,Y:[N]BIT; ci:BIT; (* semnale de intrare in modul *)

OUT Z:[N]BIT; co:BIT; (* semnale de iesire din modul *)

VAR S:[N]Celula; (* semnale interne + instante ale tipurilor compuse *)

BEGIN

S.0(X.0, Y.0, ci); (*precizarea intrarilor in cel. 0*)

FOR i:=1..N-1 DO

S.i(X.i,Y.i,S[i-1].co);

END;

FOR i:=0..N-1 DO

Z.i:=S.i.z;

END;

co:=S.7.co;

END Sumator;

Se fac urmatoarele observatii:

- limbajul Lola este "case sensitive";

- operatorii limbajului reprezinta porti logice (operatii logice):

+ = SAU

- = SAU-EXCLUSIV

* = SI

~ = NOT

- exista cuvinte cheie pentru a declara bistabile D (REG), multiplexoare (MUX), circuite latch (LATCH), bistabil set-reset (SR);

- declaratiile de tablouri se fac ca si in limbajul C precizandu-se doar dimensiunea, indicele luand valori in intervalul 0..N-1;

- exista 3 tipuri de semnale: BIT - pentru liniile de semnal simple, TS - pentru liniile de semnal din magistrale, OC - pentru magistralele de tip open colector;

- precizarea semnalelor de intrare intr-un tip sau modul se face in sectiune de declaratii IN, in sectiunea OUT specificandu-se semnalele de iesire;

- pentru specificarea semnalelor de intrare intr-o instanta a unui tip se utilizeaza o forma asemanatoare cu un apel de procedura;

- pentru utilizarea semnalelor de iesire dintr-o instanta a unui tip se foloseste notatia cu punct ca si in cazul articolelor (RECORD) din limbajele de nivel inalt;

- pentru specificarea indicilor unui tablou se poate folosi atat notatia cu punct cat si notatia cu paranteze drepte (S.i este echivalent cu S[i]);

- deoarece "i" este un indice numeric el nu trebuie declarat in sectiunea de variabile (VAR) in aceasta sectiune declarandu-se doar semnale si instante de tipuri

1.2. Sintaxa limbajului Lola

identifier = letter ['''].

integer = digit .

LogicValue = ''0' | ''1'.

BasicType = 'BIT' | 'TS' | 'OC'.

SimpleType = BasicType | identifier ['(' ExpressionList ')'].

ExpressionList = expression .

type = SimpleType.

ConstDeclaration = identifier ':=' expression ';'.

VarDeclaration = IdList ':' type ';'.

IdList = identifier .

selector = .

factor = identifier selector | LogicValue | integer |

'~' factor | '(' expression ')' |

'MUX' '(' expression ':' expression ',' expression ')' |

'SR' '(' expression ',' expression ')' |

'LATCH' '(' expression ',' expression ')' |

'REG' '(' [expression ':'][expression ','] expression ')' .

term = factor .

expression = term .

assignment = identifier selector ':=' [condition '|'] expression.

condition = expression.

relation = expression ('=' | '#' | '<' | '<=' | '>' | '>=') expression.

IfStatement = 'IF' relation 'THEN' StatementSequence

['ELSE' StatementSequence]

'END' .

ForStatement = 'FOR' identifier ':=' expression '..' expression 'DO'

StatementSequence 'END' .

UnitAssignment = identifier selector '(' ExpressionList ')'.

statement = [assignment | UnitAssignment | IfStatement | ForStatement].

StatementSequence = statement .

InType = 'BIT'.

InOutType = ('TS' | 'OC').

OutType = ('BIT' | 'TS' | 'OC').

ImportList = 'IMPORT' identifier ';' .

module = 'MODULE' identifier ';' [ImportList]

['CONST' ]

['IN' ]

['INOUT' ]

['OUT' ]

['VAR' ]

['CLOCK' expression ';']

['BEGIN' StatementSequence]

'END' identifier '.' .

TypeDeclaration = 'TYPE' identifier ['*'] ['(' IdList ')'] ';'

['CONST' ]

['IN' ]

['INOUT' ]

['OUT' ]

['VAR' ]

['BEGIN' [StatementSequence]

'END' identifier.

2. Compilatorul de Lola

2.1. Utilizare

Compilatorul de Lola realizat este unul "on-line", fiind necesara editarea fisierului sursa cu un editor si apoi invocarea compilatorului din linia de comanda.

Linia de comanda va avea urmatoarea forma:

lola <fname.hdl> [-t<Digit>] [-e] [-show]

unde:

fname.hdl - reprezinta fisierul sursa (Hardware Description Language)

t - seteaza numarul de spatii folosit pentru afisarea caracterului Tab in editorul cu care a fost editat fisierul sursa ( valoarea implicita este 8)

e - redirecteaza tiparirea erorilor intr-un fisier avand numele <fname.ler> (Lola Errors)

show - permite vizualizarea circuitului descris in forma ASCII in fisierul <fname.shw> (pentru fiecare semnal se afiseaza expresia aferenta)

Fisierul de iesire numit <fname.lds> (Lola Data Structure) va contine circuitul sub forma unei reuniuni de arbori avand in nodurile intermediare porti si circuite predefinite (bistabile, multiplexoare,), iar in frunze semnalele aferente. Radacina fiecarui arbore este un semnal iar arborele descrie implementarea semnalului respectiv.

Exemplu:

Linia de comanda "lola counter.hdl -e -show" va creea urmatoarele fisiere:

- "counter.ler" care contine erorile

- "counter.shw" care contine expresiile pentru semnale

- "counter.lds" care este fisierul de iesire si contine structura de date Lola.

2.2. Particularitati ale limbajului. Mod de abordare

Limbajul Lola fiind un limbaj de descriere hardware static (se descriu circuite digitale si interconexiunile dintre acestea) nu conteaza ordinea in care instructiunile sunt executate, neexistand efecte colaterale in urma executiei unei instructiuni. De exemplu o instructiune de atribuire x:=y precizeaza faptul ca linia de semnal x va fi "lipita" la linia de semnal y.

Compilatorul limbajului Lola va trebui sa produca la iesire o reprezentare a circuitului descris. Ca si forma de reprezentare au fost alese urmatoarele structuri de date:

- lista simplu inlantuita multinivel care contine semnalele din modulul descris

- pentru ficare semnal se foloseste un arbore care va descrie implementarea semnalului respectiv. Arborele va avea ca si radacina nodul din lista semnalelor corespunzator semnalului descris, nodurile intermediare vor reprezenta porti sau circuite predefinite (bistabile, multiplexoare), iar frunzele vor fi tot noduri din lista semnalelor reprezentand semnalele care intra in expresia semnalului curent.

In Figura 1 s-a incercat o reprezentare grafica a unei astfel de structuri de date.

Prin lista multinivel s-a specificat faptul ca o variabila din lista care reprezinta un tablou sau un tip compus este radacina unei alte liste care contine semnalele din tablou sau din tipul compus.

Lista de semnale din interiorul unui modul are ca si radacina un nod ce reprezinta o variabila de tip compus virtuala care desemneaza modulul in ansamblu.

Aceasta structura de date poate constitui atat baza pentru simularea circuitului descris cat si pentru o implementare automata a circuitului.

Simulatorul poate fi vazut ca si Backend-ul compilatorului prin intermediul careia utilizatorul poate determina corectitudinea logica a circuitului descris (se poate echivala simulatorul cu un executiv pentru compilatoarele care scot la iesire un cod virtual).

In vederea implementarii compilatorului s-au prevazut 2 etape:

- in prima etapa se realizeaza crearea arborelui sintactic;

- in a 2-a etapa se realizeaza expandarea circuitului logic utilizand informatia din arborele sintactic;

A fost necesara prevederea a doua etape deoarece limbajul contine structuri repetitive si structuri selective. Pentru a nu fi necesara reparcurgerea codului sursa, s-a optat pentru crearea arborelui sintactic.

Pentru reprezentarea arborelui sintactic s-au folosit aceleasi structuri de date ca si pentru reprezentarea semnalelor digitale adica liste multinivel si arbori. Mai mult listele multinivel si arborii din cele 2 structuri au aceleasi campuri.

In Anexa A s-au reprezentat cateva din modalitatile de reprezentare a intructiunilor in arborele sintactic folosind doar doua tipuri de noduri: Signal si Variable (vezi paragraful urmator).

2.4. Note de implementare

Pentru implementare s-a folosit limbajul C++.

Ierarhia de clase este urmatoarea:

Memory

Signal

HeadVar

LolaE

LolaC

clasa Memory - sta la baza tuturor variabilelor si semnalelor din structura de date Lola. Este utilizata atat pentru alocarea/dezalocarea blocurilor in memoria principala cat si pentru linearizarea structurilor de arbore si lista multinivel in vederea stocarii lor intr-un fisier. Dintre metodele cele mai importante amintim:

clasa Signal - reprezinta un semnal fara nume in structura de date Lola. Sta la baza clasei Variable care reprezinta un semnal identificat printr-un nume, un tablou de semnale sau un tip compus. Clasa are urmatoarele campuri importante:

clasa Variable - reprezinta un semnal, un tablou de semnale sau o instanta a unui tip compus. Clasa este derivata din Signal, deci pe langa campurile fct, val, x, y cu semnificatia:

dsc - pointer spre descendentii variabilei (in cazul in care variabila este tablou sau instanta de tip compus)

next - pointer spre urmatorul semnal/variabila de pe acelasi nivel (spre urmatorul element de tablou sau spre urmatorul camp dintr-un tip compus)

clasa LDS reprezinta structura de date Lola (Lola Data Structure). Dintre campurile si metodele importante amintim:

Origin - pointer spre o variabila care este originea intregii structuri de date

Clasele descrise pana aici formeaza interfata compilatorului cu alte aplicatii care vor utiliza structura de date Lola oferita de compilator (de exemplu simulatorul de circuite digitale)

clasa TextFile - gestioneaza buffer-ul pentru citirea dintr-un fisier text. Dintre metodele importante amintim:

clasa ErrSystem - afiseaza mesajele corespunzatoare erorilor. Mesajele sunt continute intr-un fisier text ("lola.err"). Metoda cea mai importanta este:

GetErrMsg - returneaza mesajul corespunzator unei erori specificate prin numar

GetCN - returneaza ultima constanta numerica intalnita (Current Numeric Constant)

clasa HeadVar - reprezinta un nod din arborele sintactic folosit pentru descrierea modulului si a tipurilor compuse. Contine campurile:

clasa LolaC - reprezinta compilatorul propiu-zis care transforma specificatia Lola intr-un arborele sintactic corespunzator. Compilatorul foloseste analiza sintactica cu descendenti recursivi. Are campurile:

Org - pointer spre structura ce contine instructiunile si variabilele din corpul principal al modulului

IfStatement, , StatementSequence, expression, factor, - proceduri folosite pentru fiecare productie a gramaticii ce sunt apelate recursiv

Verify - procedura pentru afisarea variabilelor din modul folosita in perioada de depanare a compilatorului

clasa LolaE - genereaza pornind de la arborele sintactic structura de date ce reprezinta circuitul digital descris. Clasa are urmatoarele metode:

Expand - realizeaza expandarea intregii structuri de date corespunzatoare circuitului descris

ExpandVar, ExpandAllVar, ExpandType - pentru expandarea unei variabile sau a unei instante a unui tip compus

ConvertExp - realizeaza conversia unei expresii ce reprezinta implementarea unui semnal din arborele sintactic intr-un arbore ce va fi inclus in structura de date a circuitului digital

assign, ExecAssigment, ExecIf, ExecFor, ExecUnit, ExecInstrList - executa instructiunile respective sau lista de instructiuni

Error - realizeaza afisarea erorilor ce survin in cadrul procesului de expandare

Compilatorul ofera la iesire descrierea circuitului sub forma unei structuri de date combinate cuprinzand o lista multinivel cu semnalele din modul si o colectie de arbori ce reprezinta implementarile (expresiile) pentru fiecare semnal. Structura de date este furnizata intr-un fisier in forma binara. Pentru a facilita utilizarea acestei structuri de date se pun la dispozitie fisierele "lola-ext.h" si "lola-ext.obj" care cuprind declaratiile si implementarile claselor Signal, Variable si LSD (vezi paragraful anterior).

Utilizatorul acestei structuri de date va trebui sa faca uz de campurile si metodele puse la dispozitie de clasa LDS si anume:

Origin - reprezinta un pointer la radacina intregii structuri de date. Aceasta radacina este o variabila virtuala de tip compus care are ca si nume numele modulului descris.

FindId - procedura ce cauta un Identificator printre numele variabilelor descendente din variabila specificata ca si parametru

FindVar - procedura recursiva ce returneaza un pointer spre variabila cautata (sau NULL in caz ca variabila nu exista) . Variabila cautata va trebui sa aiba ca stramos o alta variabila specificata ca si parametru

GetVarName - returneaza numele complet al unei variabile specificate ca si parametru

IsIOVar - functie care specifica daca o variabila reprezinta un semnal de intrare sau iesire pentru modul

Load, Store - realizeaza incarcarea in memorie respectiv salvarea pe disk a structurii de date ce reprezinta circuitul

Pentru campurile claselor Signal si Variable rugam a se consulta paragraful anterior. Mentionam ca atat clasa Signal cat si clasa Variable poseda o metoda numita WhatAmI care returneaza tipul nodului specificat ca si parametru.

Node_Types - cu valorile SIGNAL sau VARIABLE si arata tipul unui nod din structura de date ce descrie circuitul (se folosesc pentru functia WhatAmI)

Prezentam in continuare pe scurt structura de date care reprezinta circuitul digital:

Structura este compusa dintr-o lista multinivel (de fapt un arbore binar) de Variabile avand ca radacina variabila LDS::Origin. Campul Variable::name reprezinta numele variabilei iar campul Signal::fct tipul variabilei. Daca variabila este un tablou (Signal::fct=F_array) sau o instanta a unui tip compus (Signal::fct=F_record) campul Variable::dsc denota o lista de variabile, care reprezinta componentele tabloului sau tipului, legate prin campul Variable::next.

"Implementarea" unei variabile este reprezentata printr-un arbore cu radacina in campul Signal::x. Acest arbore exte compus din elemente de tip Signal. Fiecare nod reprezinta un operator (poarta/circuit digital) specificat prin campul Signal::fct, iar operanzii sunt dati de campurile Signal::x si Signal::y. Un nod de tipul F_not utilizeaza campul Signal::y ca si operand. Implementarea unei variabile de tip TS care are asignata expresiile e0, e1, este o lista de noduri cu Signal::fct=F_tsg (tri-state gate), legate prin campul Signal::y. Campul Signal::x din fiecare nod reprezinta expresiile e0, e1, . La fel pentru tipul OC.

The input file is a Lola Data Structure file which has been generated by the Lola compiler. Ussualy it has the extension 'lds'.

When the '>' prompt is displayed, the simulator is waiting for a command. When the ':' prompt is displayed, the simulator is waiting for a signal name.

The ':' prompt will be displayed after the 'set' or 'select' command. To end these commands, the '~' character must be used.

This command is used when no clock signal is involved, i.e. the circuit described by the Lola module consists of gates,multiplexer and latches (no D flip-flops). All signals are evalueted, and the selected signal are displayed on screen. However, this command can be used even when the Lola module includes D flip-flops (REG declarations) but no clock pulse are generated, i.e. all D flip-flops remains at previous state.

This command is used when we want to evaluate the Lola module signals after a clock pulse. The D flip-flop from the module will change their states. The STEP command has a numeric parameter which specifies the number of clock pulses to be generated.

The predefined clock signal for the STEP command is the Lola global clock CK. To select another input signal to be the clock signal for the STEP command use STEPCLOCK command.

This command is used to select an input signal to be the clock signal for the STEP command. That means that the STEP command will generate clock pulses on that input signal.

The predefined clock signal for the STEP command is the Lola global clock CK. To set again the Lola global clock signal CK to be the clock for the STEP command, type STEPCLOCK CK'.

This command generates only a clock pulse on an input signal specified as parameter. This commans is used when we need one or few clock pulse on an input signal.

DESELECT command is used to deselect all signals that have been selected with SELECT command.

One important feature that we offer is that you can select the bits of an array only by specifying the name of the array. If the parameter is a record, the SELECT command will select all signals from that record which are not arrays or records.

The last parameter of the SELECT command must be the character '~'. The SELECT command will display which signals have been found in the Lola Data Structure and which not. You can press Enter after each signal name to be sure that the signal(s) have been found in Lola Data Structure. After each signal, the simulator will display the prompt ':' and will wait for another signal name or for the character '~' which will end the parameter list.

This command is used to set values for the input signals. To set a value for an array, you can use the name of the array and a decimal number.

The last parameter of this command must be the character '~'. The SET command will display which signals have been found in the Lola Data Structure and which not. You can press Enter after each signal name to be sure that the signal(s) have been found in Lola Data Structure. After each signal, the simulator will display the prompt ':' and will wait for another signal name or for the character '~' which will end the parameter list.

This command is used to bring all signals to ZERO. This is the initial state of the Lola module.

We present an example of how to use the simulator. We will simulate a counter that will count from 0 to a limit which is held in a loadable register.

:>clock load (* generates a clock pulse on signal 'load' which will load the register *)

Desi este la inceput de drum, din spectrul deosebit de larg al limbajelor de descriere hardware, limbajul Lola atrage atentia prin simplitate. Pentru un programator familiarizat cu limbajul Pascal asimilarea sintaxei limbajului se face foarte rapid, fiind necesara doar intelegerea modului in care se face legatura intre un circuit digital si declaratiile prin care acest circuit este descris in limbaj. Singurul lucru care se poate reprosa limbajului este ca descrie doar dispozitive statice, comportarea dinamica a circuitelor fiind mai greu, uneori imposibil de ilustrat.

Lola nu poate fi incadrat doar in familia de limbaje ce descriu circuitele la nivel de poarta, descriere pentru care Lola ofera suport, deoarece introducerea tipurilor compuse si in special a tipurilor compuse parametrizate face posibila descrierea circuitelor atat la nivel de registre cat si la nivele de abstractizare mai inalte. Nu poate fi vorba insa de a se putea descrie izolat comportarea unui circuit (behavior) si de aceea poate ca urmatorul pas este largirea sintaxei limbajului cu declaratii care sa puna in evidenta comportarea in timp a circuitului.

Utilitatea limbajului a fost scoasa in evidenta prin utilizarea sa impreuna cu dispozitivele FPGA si in special cu dispozitivul AT6002. Pentru configurarea dispozitivului FPGA se poate utiliza un editor grafic, urmand a se compara descrierea grafica cu descrierea realizata in limbajul Lola in scopul demonstrarii corectitudini circuitului. In prezent este in lucru o unealta care sa realizeze o implementare automata a unui circuit direct din descrierea sa realizata cu ajutorul limbajului Lola.

Pentru a putea realiza o descriere mai simpla si mai intuitiva a unor circuite digitale (de exemplu decodificatoarele) propunem introducerea unor tipuri compuse parametrizate recursive. Vom ilustra pe un exemplu modul de definire a unor astfel de tipuri.

TYPE Decoder(N>=1); (* if N<1 the compiler will not generate a data structure for decoder*)