Záznam - cvičení DU5

Úvodní kurz překladačů se soustřeďuje zejména na teoretické i praktické základy konstrukce přední části překladače. Součástí předmětu je i cvičení zaměřující se na základy práce s nástroji pro konstrukci překladačů. Po absolvování tohoto kurzu bude posluchač schopen sestrojit vlastní překladač do mezikódu nebo jiného jazyka.
ps
Matfyz(ák|ačka) level III
Příspěvky: 137
Registrován: 1. 6. 2006 08:47
Typ studia: Informatika Mgr.
Bydliště: Praha 4
Kontaktovat uživatele:

Záznam - cvičení DU5

Příspěvek od ps »

bez záruky

Kód: Vybrat vše

ICM

 Projekt virtuálního stroje, interpret mezikódu. Má jedinou pamět - zásobník,
 ten začíná na adrese 0. V tomto základním provedení nemá ani registry, je to
 zásobníkový stroj. Všechny proměnné tedy musíme držet na zásobníku.

 Každá položka zásobníku je ostře typovaná (pamatuje si svůj typ), obvyklé
 základní typy - integer, byte, real, string, pointer, fp (frame pointer,
 návratová adresa při skoku do procedury).

 SP (Stack pointer) - ukazatel na vrchol zásobníku.
 GP - ukazatel na dno zásobníku, pomocí něj se na začátku do zásobníku nasypají
 globální proměnné. Pak se přes GP k nim přistupuje (na to budeme potřebovat znát
 offsety těchto globálních proměnných).
 FP (frame pointer) - ukazatel na hranici mezi paramety volané funkce a začátkem
 lokálních proměnných (FP se pohybuje při volání/návratu z procedury).


Instrukce INIT<typ>

 Tyto instrukce vyhradí na zásobníku krabičku daného typu, ale bez definované
 hodnoty. Takto se vyrábí proměnné.

 Ale to nemusíme vůbec dělat, protože o globální a lokální proměnné se samy
 postarají tabulky překladače. My si jen budeme muset z tabulek zjistit, kde
 jsou proměnné uloženy.
 
 Jediná situace, kdy INIT potřebujeme, je vytvoření krabičky pro návratovou
 hodnotu funkce.


Instrukce DTOR<typ>

 Destruktor krabičky daného typu (z vrcholu zásobníku). U proměnných opět
 automaticky, ale musíme použít u návratové hodnoty funkce.


Volání funkcí

 function F(I: int; R: real):string;
 A := F(V1,V2);
 
 Postup:
 1. zavolat INITS pro vytvoření krabičky pro návratovou hodnotu
 2. spočítat V1, výsledná hodnota musí zůstat na zásobníku
 3. spočítat V2, výsledná hodnota musí zůstat na zásobníku
 4. Vygenerujeme instrukci call, ta si uloží FP
 5. ...nyní pracuje funkce
 6. zavolá se instrukce RET (nemusíme psát, vygeneruje se sama)
    Tato instrukce umaže ze zásobníku lokální proměnné
 7. DTORR - smazat 2. parametr ze zásobníku
 8. DTORI - smazat 1. parametr ze zásobníku
 
 Na zásobníku nám zůstane návratová hodnota volané funkce.
 
 Rozdíl mezi funkcí a procedurou je ten, že procedure nevolá na začátku
 INIT pro místo na návratovou hodnotu.
 

Získání konstanty:
 LDLIT<typ> - parametrem je ukazatel do tabulky kde je daná hodnota
 LDLITB - očekává přímo číslo 0 nebo 1
 
 CVRTIR - sežere z vršku zásobníku integer a místo něj vloží real,
  tedy konverze int -> real
  
Obvyklé instrukce pro čísla:
 ADDI
 ADDR
 MULI

ADDS - binární plus na stringy, zřetězení

pLDx - to jsou operace LOAD, něco přečtou a dají na vrchol zásobníku, parametrem
      je offset
 p = pointer, můžeme si vybrat:
     - GLDx (adresuji vůči GP)
     - LLDx (vůči FP, čeká se znaménkové číslo)
     - SLDx (vůči SP)
 x = typ

pSTx - operace STORE, sežere položku ze zásobníku



Jak generovat kód v překladači?

 To co je mezi begin a end funkce si musíme někde udržet, tj. ve všech
 neterminálech (v jejich atributech), které jsou pod begin a end (neplatí pro
 begin end u příkazů, platí jen pro hlavní begin a end programů a funkce). Až
 po překladu celé funkci vložíme celý její kód na výstup.
 
 Typ položky pro držení mezikódu: icblock_pointer
 
 symbol_tables::set_main_code
 symbol_tables::subprogram
 
  - parametrem těchto funkcí je vygenerovaný mezikód daného hlavního programu
    nebo podprogramu.
   
 icblock_create - vyrobí prázdný mezikód (držák na mezikód)
 icblock_append_delete - slepí 2 bloky mezikódu do nového a uvolní původní
  
 icblock_pointer má metodu append_instruction() pro přidávání jednotlivých
 instrukcí, append_instruction_with_target() pro potřebu skoku. Parametrem
 těchto funkcíje třída pro danou instrukci. Každá instrukce, které byly zmíněny,
 mají své třídy. Jejich konstruktory očekávají příslušné parametry instrukce
 (pokud jsou nějaké potřeba, čassto ne protože se pracuje s argumenty na
 zásobníku).
 
 variable_symbol::address() - získávání offsetů (globálních a lokálních)
 proměnných z tabulek
 
 Instrukce CALL přijímá parametr, který získáme voláním subprogram_symbol::code()
 
RECORDY

 Typ record_type má metodu find() pro hledání položek záznamu. Pokud daná
 položka existuje, vrátí se nám typ field_entry. Z toho opět potřebuju zjistit
 typ položky recordu a offset (pozice položky ve struktuře). Offset přičteme
 k adrese počátku recordu.
 
 record_type má metody begin() a end(), které vrací iterátory, abychom mohli
 projít všechny položky struktury. To potřebujeme při přiřazení struktury. V
 takové situaci musíme překopírovat jednu položku po druhé (nejprve load
 na vrchol zásobníku, pak store do cílového místa). Položka struktury může
 být samozřejm opět struktura.


PŘÍKLAD: VÝRAZ A SČÍTÁNÍ

 %type<V> factor, nasobeni, scitani, konstanta
 
 konstanta:   UINT { $$.ic = icblock_create();
                     $$.ic.append_instruction(new LDLITI($1)); }
            | STRING  { ... }
  ;
 
 factor: konstanta { $$.ic = $1.ic; }
         | promenna { // najit kde lezi
                      append_instruction(new LLDI) }
         | ( vyraz )  { ... }
  ;

scitani: scitani ADDOPER nasobeni { $$.ic = $1.ic;
                                    icblock_append_delete($ii.ic,$3.ic);
                                    // na zasobniku nyni lezi vysledek scitani
                                    //a nasobeni
                                    $$.ic.append_instruction(new ADDI);
                                    }
         | nasobeni


Až dointegruju, chci do sběru
qwertie
Matfyz(ák|ačka) level III
Příspěvky: 103
Registrován: 4. 6. 2005 15:49
Typ studia: Informatika Bc.
Bydliště: Vyšehrad

Re: Záznam - cvičení DU5

Příspěvek od qwertie »

A ted jeste muj zaznam - je to slabsi, prisel jsem pozde a nebyl jsem uplne v kondici..

Kód: Vybrat vše

jak ma vypadat kod fce..

INITS (pripravim misto na zasobniku)
par 1 (V1 - mezikod ke spocitani parametru 1.)
par 2 (V1 - mezikod ke spocitani parametru 2.)
CALL
DTORR (destrukce 2. parametru)
DTORI (destrukce 1. parametru)


LDLITx (I, neco...)  -par index do tabulek
LDLITB - ceka 1 nebo 0 podle pravdivosti
CVRTIR - prevede int na real (na vrsku zasobniku)

ADDI,ADDR -scitani
SUBx,DIVx,MULx

ADDS - zretezeni stringu  - scitani stringu

pLDx - loady - odnekud neco precte a vrati na zasobnik.. - p je pointer 
	(resp jeho typ - G - globalni - od GLOBAL POITERU , L -lokalni - muze byt i zaporny - vuci FP, S - vuci stack pointeru ), x je typ
	, parametr je cislo
	
pSTx - ulozi to co mam na zasobniku - argument - to kde se nachazi misto k ulozeni (bere vrch na zasobniku)


!@ jak generovat mezikod?
-porad transportuju mezikod (resp lepim).. - kdyz mam cely (mezi begin a end) - ulozim..
icblock_pointer - to je typ ktery drzim..

symbol_tables::set_main_code - ulozeni mezikodu k programu

symbol_tables::set_subprogram_code - ulozeni mezikodu k fci

icblock_create -vyrobi prazdny mezikod

icblock_append_delete - 2. parametr prilepi k prvnimu a pak druhy zrusi ..

append_instruciton(INSTRUKCE) - prilepi ke kodu instrukci

append_instruciton_with_target() - na skoky, cally

add_label - cil skoku.. - pouzije se v 6

kazda instrukce ma vlastni tridu - ta ma konstruktor... takze muzu psat new ADDI(), new LDLID(index)

- jak sehnat cislo pro LLDI A GLDI apod..

kdyz vim ze symbol je promena - tak muzu nad typem variable_symbol -> address() vrati adresu..

na zacatku fce automaticky tabulky vytvori lokalni promenne pro vsechny parametry..

instrukce CALL - parametr = uchylnej typ, 

fce - zeptam se tabulek vim ze je to fce - subprogram_symbol->code() to vrazim do CALL()

STRUKTURY - a.b
	a.b - je a promenna?, pretypuju na variable_symbol, zjistim typ promenne - mam odkaz do typ tabyulek
	- zjistim adresu a cka a k nemu prictu offset b cka - mam adresu bcka
	variable_type->address(), record_type->find/begin/end, field_entry -> offset()
	prirazeni struktur - a=b - polozky i a r - LLDI offset i v a , LSTI offset i v b, LLDR offset r v a , LSTR offset r v b
	
Priklad	


%type<ic> nasobeni,faktor,scitani, konstanta
	- musim udrzet. typ, mezikod, kde to lezi(adresu)
	
	/** jen priklad lisi se gramatikou*/
konstanta: UINT {$$.ic=icblock.create();
		 $$.ic.append_instruction(new LDLITI($1));
		 }
	  |STRING {$$.ic=icblock.create();
		 $$.ic.append_instruction(new LDLITS($1));
		 
		 
faktor: konstanta {$$.ic$1.ic;}
	|promenna {@*.@@@#@#@#!@#!@#!@#!@#!#@#@ append_int(new LLDI());}
	|(vyraz) {-//- typ apod, no moc jsem to nechytil..}
	
scitani : scitani ADDOPER nasobeni {$$.ic=$1.ic;
				icblock_append_delete($$.ic$,$3.ic);
				zjistim typ operace, zjistim a zkontroluju typ..
				$$.ic.apend_instruction(new ADDI());
				}
	| nasobeni {$$.ic$1.ic;}

volani fci s par odkazem - to je z du 6 - ne LLD ale ulozeni - kde to lezi.. (LLD se pak vola az na miste)
Uživatelský avatar
Angel
Matfyz(ák|ačka) level III
Příspěvky: 121
Registrován: 9. 9. 2005 19:28
Typ studia: Informatika Mgr.
Bydliště: Znojmo / Praha
Kontaktovat uživatele:

Re: Záznam - cvičení DU5

Příspěvek od Angel »

Mnohe diky panove za Vasi stedrost a dobrosrdecnost v dobe Vanocni pro Ty, jez byli lini jiti na cviko :-)
maccage
Matfyz(ák|ačka) level I
Příspěvky: 4
Registrován: 17. 6. 2006 12:57
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Záznam - cvičení DU5

Příspěvek od maccage »

Prikladám svoje poznámky (z cvičenia u doktora Yaghoba).

Kód: Vybrat vše

### CO JE ULOHA ###

na 100 bodov
============
uloha je vyhdnotit vyraz
- premenna = nieco;
- to nieco je vyraz;
  - moze obsahovat volanie funkcie
  - zvladnut aj procedury

- zatial predavanie hodnotou (v procedurach a funkciach)

unarni operator (pro int a real)
binarni plus (pro int, real A STRINGY (concaterace)!! );
binary minus a nasobenie (int a real)
binarni deleni ( 
  - delenie lomitkom (vysledok je vzdy real), 
  - delenie div (integer div integer = integer );

NEROBI SA:
boolean (AND, OR)

konverzia  
!! real + int = real  // nedojde ku ziadnemu, automaticka konverzia
!! int / int = real   // nedojde ku ziadnemu warningu, automaticka konverzia
!! konverzia aj na urovni procedur a funkcii pri volani
ide to aj opacne, z realu do integeru s varovanim ale nie je to potrebne urobit

na 150 bodov je rozsirenie o struktury
napriklad a.b.c
vyriesit priradenie struktur
je zakazane predavanie struktury hodnotou a ani vystup funkcie nie je struktura

### ICM ###
ICM je simulator medzikody (abstraktny stroj, ktory spracuvava medzikod)
co ma tento stroj k dispozicii:
- zasobnik

    +-------+
  0 |       | <-- GP         +-------+
  1 |       |                |  IP   |
  2 |       |                +-------+
  3 |       | <-- FP
  4 |       |
  5 |       |
  6 |       | -2
  7 |       | -1
  8 |       | 0 <-- SP
  9 |       | +1
 10 |       | +2
 11 |       |
   
   zasobnik je jedina pamat, ktoru mame k dispozicii (ziadne adresy, ziadne 
   registre)
      - kazda bunka je ostre typovana (Bool,Integer,String,Real)
      - berieme ze typy maju rovnaku velkost
      - dalej mimo bool, integer, real a string je este poiter, framepointer 
        a beztyp (nieco typu prazdne ?! )
      - pozn: instrukcie kontroluju typ a vedia zistit ci je mozno citat 
        (ak tam je nieco zapisane)
   zasobnik obsahuje tri ukazatele
      - stack pointer: koniec zasobniku
      - frame pointer
      - globalny pointer: ukazuje na nulu
      -
   instrukcie
--------------------------------------------------------------------------------   
INIT x          
     B
     I
     S
     R 
   - na vrchol zasobniku prida krabicku na koniec zasobniku (v podstate 
     deklaracia premennyc)
   - INIT na zaciatku nevolame, to spravia same tabulky (netreba implementovat)
      - starat sa mame len o veci medzi BEGIN a END
   - pridava na vrchol zasobniku   
--------------------------------------------------------------------------------
DTOR x
   - znici krabicku
   - maze z vrcholu
--------------------------------------------------------------------------------
LDLIT x 
   - nacitanie konstant
   - prida
   - i,r,s ocakava hodnut
     b ocakava rovno 0/1
--------------------------------------------------------------------------------   
CWRT ir
     ri
   - vezme krabicku, spravi v nej konverziu integer -_> real a zase ulozi
--------------------------------------------------------------------------------
instrukcie na na binarne operacie,   
MINUSI
MINUSR
ADDI
ADDR
DIVI
DIVR
MODI
MULI
MULR
SUBI
ADDS
- pracuje to v zmysle, vezme dve krabicky z vrcholu, spocita a vysledok vrazi 
  na do jednej na vrchol
--------------------------------------------------------------------------------
pLDx
vezme bunku, pointer, offset a co tam najde okopiruje na vrchol
vlastne dve parametre, pointer a offset
x -> integer, real, string
p -> je pointer
G = GP
L = FP
S = SP

G sa pouzije na globalne premenn
L sa pouzije na lokalne premenne
S na vlastne 
--------------------------------------------------------------------------------   
pSTx
opacne, z vrcholu vezme krabicku a ulozi ju na offset od pointeru
           
skoky:
CALL 
  - tu budeme generovat


AKO TO MAME ROBIT
==================
icbock_pointer (je to ukazatel na labeled_icblock)

co s nim mozeme robit ?
existuje globalna funkce

icblock_create()
  - vytvori prazdny blok medzikodu

ake opreracie mozno robit na icblock->
  - append_clear_block(b2)
    napriklad b1->append_clear_block(b2): prilepi b2 za b1 a b2 zrusi
  
  - append_instruction()
    - ako parameter je instrukcia
    - ku kazdej instrukcii je priradena trieda v projekte 
    - priklad 
      b1->append_instruction(new ADDI() )
      - konstruktor v triede konstrukcie caka parametre, ktore odpovedaju
        operandom instrukcie
       
      
ukazka: 
##########
vyraz je najkomplikovanejsie cast
pamatame si
-> kod ktory to generuje
-> typ
-> kde to lezi (v tejto ulohe si mozeme )


scitani: nasobeni { $$.ic = $1.ix; $$.typ = $1.typ;} 
       | scitani ADDOPER nasobeni {
          switch($2) {
            case PLUS: 
                 skontrolujem typy a najdem spravne/nespravne typy $1 a $3
                  - ak je to int + int, spcitam cisla
                  - ak je to int + real, generuje sa konverze
                  - ak je to string + string tak contact
                  $$.ic = $1.ic;
                  - spravit pripadnu konverziu real na int a podobne
                  $$.ic->append_clear_block($3.ic)
                  - pripadne zase konverzia vysledku, v int / int
                  $$.ic->append_instruction(ta spravna aritmeticka instrukcia)   
                    - napriklad ADDI, ADDR, SUBI, SUBR,...
                  $$.typ =   ( !! type pointer a ten si stale pamatat !! )
                   - nad typ_pointerom je funckia logical_real()
                   - to sluzi na porovnanie recordov (typicky) 
                      - cely medzikod vznika lepenim blokov 
            }  
          } 
       ;

nasobeni: xxx

faktor: volani fuknce
      | ( vyraz )
      | promenna { $$.ic=icblock_create 
                   $$.ic_>append(LDLIT)
                   $$.typ->ctx->tab... (nepostrehol som) 
                  }
      ;      

! pozor, dobre rozlisit plus/ minus

================================================================================  
- ked nam vznikne celkovy medzikod, treba ho priradit procedure/funckii
- to sa deje za pomoci funkcii na symbolickou tabulkou
set_subprogram_code(idx, ict)
set_main_code(idx, ict)

KONVENCIE NA VOLANIE KODU
 a := f(v1, v2, v3)
 
 
 find_symbol();
 - zistime ci to je funkcia, alebo nie
 - vracia symbol pointer
 - prelezieme vsetky parametre, ktore tam su sme tam zadali v minulenej ulohe
 - zlepime kody pre v1 + v2 + v3
 - na zaver instrukcia CALL, v zmysle new CALL(f->code())
    - call vytvori frame pointer na vrchol
    - v nom je schovana navratova adresa
    - dve polozky: IP, predchadzajuci FP
    - od fp vidim v minusovych indexoch vstupne parametre
    - v kladnych vidim lokalne parametre
 - uplne nakoniec vymazat v1, v2, v3
 - na zaciatku v pripade funkcie nastavit typ navratovej hodnoty   
   +------------------
   |  V1
   |  V2
   |  V3
   |  FP
   |  lokalna premenna
   |  lokalna premenn
   +----------
   
   instrukce:
   
   1.INTx
   2.V1
   3.V2
   4.V3
   5. CALL
   
    
 ako najst premennu ?
 ====================
 cez find_symbol rovno vieme, ci je premenna globalna alebo lokalna
 acces_global_variable
 na nej je funkcia address(), ktora vrati adresu
 
 struktury
 ==========
 vieme zistit ci typ je record_type
 na nej su dve funkcie
 find() -> vrati field_entry
   type()
   offset() -> voci zaciatku struktury (prva ma nulu)
 vyuzitie -> a.b
             zistime ze a je record
             najdeme b, zistime typ
 priradenie zaznamu je kopirovanie zaznamov, tam pouzijeme iteratorove
 funkcie begin a end
 
 debug
 ======
 existuje nejaka funkcia na medzikod, ktory vrati instrukcie v citatelnej podobe
 
 
 funkcie:
 my_function_name -> to vrati meno funkce. To sa hodi vtedy, aby sme zistili,
 ci nevolame priradenie funkcie v tele
 
 my_function_address -> to vrati miesto v nazosbniku, kde mame vratit hodnotu          
  
Odpovědět

Zpět na „SWI098 Principy překladačů“