Prekladače

All + All -

Prekladače

~ Autor: Juraj Michálek
+ - sémantická analýza
- + - analýza rozsahov
  - je viditeľný aktuálny rozsah
  - sú viditeľné otvoené rozsahy
  - + - uloženie v jednej tabuľke
    - jedna hash tabuľka
    - pri kolízii sa pridáva cez hlavu zoznamu
    - s každým menom je uložená identifikácia rozsahu
    - + - uzatvorenie rozsahu
      - odstrániť všetky premenné, ktoré majú dané číslo rozsahu
    - rýchle
    - náročné na implementáciu
  - + - samostatná tabuľka pre každý rozsah
    - + - vnorená deklarácia
      - pointerom spojené do jednej tabuľky
      - alebo na zásobníku
    - + - implementácia
      - + - scope stack
        ukazatele na prvú položku v danom rozsahu
      - + - zásobník rozsahov
        obsahuje samotné tabuľky s rozsahmi
- + - zmena viditeľnosti
  - + - implicitné deklarácie
    - problém riešený backpatchingom
  - + - riadenie viditeľnosti
    - + - duplikácia rozsahu
      - väčšie nároky na pamäť
      - rovnaké vyhľadávanie
      - + - záznamy
        pre každý záznam sa vytvorí tabuľka symbolov
    - + - bez duplikácie
      - dopĺňajú sa príznaky, spoje
      - nerovnaké vyhľadávanie
      - náročné na implementáciu
      - + - záznamy
        každá premenná má číslo záznamu
        
        číslo závisí na hĺbke zanorenia
  - + - export
    - niektoré mená môžu byť viditeľné v inom rozsahu
    - + - jednorázový
      - pri uzatváraní sa zmažú všetky položky, ktoré majú príznak export
    - + - viacúrovňový
      - to čo sa privezie, sa môže aj dviesť
    - + - duplikácia
      - pri otváraní tabuľky sa pridá príznak export
      - pri uzatváraní sa nájdu všetky položky s príznakom a presunú sa
  - + - import
    - dováža sa len to, čo niekto vyviezol
  - + - with
    - každý rozsah - nová tabuľka
    - + - každý záznam má svoju tabuľku
      - pri skončení záznamu sa tabuľka odstráni
    - + - číslovanie záznamov
      - + - kopírovaním
        skopírujú sa všetky položky, ktoré majú dané číslo nadradeného zoznamu
      - + - bez kopírovania
        vytvorí sa zásobník
        
        prehľadáva sa zásobník od vrcholu
        
        ak nie je v záznamoch hľadá sa ako normálna premenná
  - + - selektívny import
    - importujú sa len vybrané položky
- typová analýza
+ - atribútové gramatiky
- + - definícia
  - ku každému symbolu X
  - I(X) - mn. dedičných atribútov
  - S(X) - mn. syntetyzovaných atribútov
  - I a S sú dizjnunktné
  - + - pre štartovací neterminál S
    - je dané I(S)
    - terminálne symboly majú dané atribútu
+ - organizácia pamäte
- + - rozsah viditeľnosti
  - + - netriedené tabuľky
    - + - nový rozsah - nové id
      - + - bez scope stack
        otváranie rozsahu: zvýši číslo
        
        ku každej premennej sa eviduje číslo rozsahu
        
        uzatvorenie: postup zhora dole, než narazí na menšie číslo rozsahu
        
        informácia o uzavretom rozsahu ide do tabuľky
      - + - scope stack
        čísla rozsahov nie sú v riadkoch
        
        sú uložené na scope stack
        
        obsahuje číslo rozsahu a ukazateľ na poslednú premennú v rozsahu
      - možné zrýchliť triedením
    - + - nový rozsah - nová tabuľka
      - otvor rozsah a vytvor tabuľku
      - uzatvorenie rozsahu - ukazateľ current sa posunie vyššie
      - + - možnosti
        z nižšieho rozsahu ukazateľ do vyššieho
        
        zásobník rozsahov
  - + - hash tabuľky
    - + - otvor rozsah
      - zvýš číslo rozsahu
    - + - uzatvor rozsah
      - aktualizuj okolie
    - uložené v tabuľke
    - + - scope stack
      - prvky jedného rozsahu sú prepojené ukazateľom scope link
    - + - bez scope stack
      - každá položka obsahuje číslo rozsahu
- + - zmenená viditeľnosť
  - kopírovať všetko
  - + - nekopírovať nič
    - nutné prehľadať tabuľky uzatvorených rozsahov
  - kopírovať len to čo je požadované
- + - aktivačný záznam
  - pomocné premenné
  - lokálne dáta
  - + - oblasť úschovy
    - návratová adresa
    - obsahy registrov
  - + - statický spoj
    - referencovanie globálnych premenných
    - + - napr. ukazateľ na staticky nadradený AZ
      - prvý, ktorý sa nachádza v zásobníku
  - + - riadiaci spoj
    - dynamický spoj
    - ukazateľ na aktivujúcu procedúru
  - skutočné parametre
  - vrátená funkčná hodnota
  - display
- + - dátové typy
  - + - základný typ
    - na rôznych architektúrach rôzny
  - + - štrukurovaný typ
    - pole jednodimenzionálne
    - + - dvojdimenzionálne
      - po riadkoch
      - po stĺpcoch
      - vektor ukazateľov
    - + - reťazce
      - pevná dĺžka
      - + - premenná dĺžka
        stanovenie maxma
        
        + - nie je určená maximálna dĺžka
        dĺžka je uložená v deskriptore v aktivačnom zázname
    - + - pole
      - + - dynamické
        zásobník
      - + - silne dynamické
        halda
- + - dátové oblasti
  - + - statické
    - väzby sa behom výpočtu nemenia
    - je možné generovať v absolútnyhc adresách
    - AZ neobsahuje statický a riadiaci spoj
  - + - dynamické
    - + - silne dynamické
      - po utvorení rozsahu sa môžu meniť
    - + - slabo dynamické
      - po utvorení rozsahu sa nemenia
  - + - funkcie
    - prideľ
    - uvolni
  - + - uloženie
    - + - zásobník
      - + - simple stack
        bez dynamických typov
        
        bez dynamických premenných
        
        s vnárarním procedúr
        
        s viditeľnosťou globálnych premenných
        
        + - kód pri vstupu do procedúry
        alokácie pamäte re AZ volanej procedúry
        
        naplnenie AZ zodpovedajúcimi informáciami
        
        úschova registrov
        
        + - kód pri výstupu z procedúry
        obnova registrov
        
        dealokácia pamäte
        
        + - vstupná volajúca postupnosť
        + - volajúca
        vyhodnoť parametre
        
        uloženie návratovej adresy a top_sp
        
        predanie riadenia
        
        + - volaná
        + - úschova registrov
        do save area
        
        inicializácia lokálnych dát
        
        predá sa riadenie samotnému kódu
        
        + - výstupná volajúca postupnosť
        + - volaná
        umiestniť vrátenú fčnú hodnoty a
        
        aktualizovať top_sp
        
        obnova registrov
        
        predanie riadenia volajúcej procedúre
        
        + - volajúca
        skopírovanie vrátenej hodnoty
      - + - simple stack s dynamickými dátovými typmi
        ukladá hodnoty medzi volaniami danej procedúry
        
        premenné dynamického typu sú na halde
        
        + - modifikácia oproti simple stack
        pri inicializácii lokálnych dát zisťuje veľkosť stat. prem. dyn typu
        
        + - pri vstupe
        výpočet top
        
        + - pri výstupe
        staré top uložené v AZ
        
        alebo je vypočítané
      - + - stack s vnorenými procedúrami
        nelokálne dáta
        
        nie sú na úrovni hlavného programu statické
        
        + - globálne a lokálne premenné
        riadené dynamicky
        
        riadené staticky
        
        + - staticky nadradený AZ
        zodpovedá poslednej aktivácií podprogramu
        
        + - statický spoj
        ukazateľ priamo na nadradený AZ
        
        + - display
        vektor ukazateľov
        
        na začiatky nadradených záznamov
        
        + - jeden globálny display
        posledný v poli ukazateľov
        
        aktivačný záznam a displej predchádzajúceho AZ
        
        + - procedúry ako formálne parametre
        + - bez vnárania procedúr
        uvádza sa skutočná adresa procedúry
        
        + - vnáranie procedúr
        adresa procedúry
        
        statický spoj
    - + - halda
      - silne dynamické premenné
      - súvislý úsek pamäte
      - počiatočné pridelenie pamäte
      - uvolnenie a príprava na nové použitie
      - + - fragmentácia
        zaceľovanie pamäte
      - + - prvky pevnej dĺžky
        počiatočné pridelenie pamäte
        
        + - uvolnenie a príprava na znovupoužitie
        + - riadené programátorom
        mark, allocate, dispose
        
        viaznuce referencie
        
        + - garbage collection
        + - mark and sweap
        dva priechody
        
        nemusí byť dosť pamäte na uloženie zásobníku
        
        + - obrátenie ukazateľov
        naviac potrebné dva ukazatele
        
        ukazateľ na predchádzajúci prvok
        
        ukazateľ na aktuálny prvok
        
        prehľadáva sa do hĺbky
        
        pri priechode sa otáčajú pointery
        
        + - stop and copy
        rozdelenie pamňte na dva bloky
        
        + - rozdelenie na viac blokov
        generačné gb
        
        reference counter
      - + - prvky premennej dĺžky
        + - fragmentácia
        čiastočné sceľovanie
        
        úplné sceľovanie
        
        + - organizácia zoznamu voľného priestoru
        zoznam s adresami
        
        + - dvojsmerný zoznam
        zoznam voľných
        
        zoznam obsadených
        
        + - buddy
        pre každú veľkosť n je udržiavaný vlastný zoznam
- + - volania
  - + - volanie referenciou
    - adresou
    - v AZ sa vymedzí pamäť na uloženie pointru
  - + - volanie hodnotou
    - vymedzí sa priestor v AZ potrebný na uloženie hodnoty
  - + - volanie výsledkom
    - uschová sa adresa parametra
    - vymedzí sa lokálne umiestnenie
    - pred ukončením sa skopíruje výsledok na adresu parametra
  - + - volanie hodnotou-výsledkom
    - vymedzí sa miesto pre uloženie hodnoty
    - po skončení sa skopíruje na toto miesto
  - + - volanie menom
    - textová substitúcia
    - musí byť prítomná fcia, ktorá vypočíta adresu
  - + - parameter procedúra
    - na vstup ide adresa procedúry
+ - generovanie medzikódu
- + - formy
  - + - trojadresový
    - <operator, op1, op2>
    - výsledok je odkazovaný z poradia inštrukcie
  - + - štvoradresový
    - Quadruples
    - zavádza fciu quad
    - <operator, op1, op2, vysledok>
    - nevýhoda: temp premenné sú vkladané do tabuľky
  - stromová reprezentácia
- + - dvojpriechodový preklad
  - vygenerujú sa odskoky
  - v druhom priechoda sa priradia adresy
  - nie je to backpatching
- + - vnorovanie procedúr
  - jazyky s blokovou štruktúrou
  - medikód uchováva informáciu o vnáraní rozsahov - scope
  - + - spôsoby
    - čísla rozsahov
    - každý rozsah má samostatnú tabuľku
  - + - funkcie
    - + - entry( table, name, type, offset)
      - uloženie identifikátoru do niektorej tabuľky
    - + - mk_table(previous)
      - vytvorí novú tabuľku
      - previos je pointer na staticky nadradenú tabuľku
    - + - enterproc(table, name, type, offset)
      - pridá odkaz na novú tabuľku pre procedúru
  - + - zásobníky
    - pre každú tabuľku je nutné udržiavať zvlášť offset
      preto potrebujeme dva zásobníky
    - + - tab_ptr
      - obsahuje ukazatele na tabuľky nadradených procedúr
    - + - offset
      - konkrétne offsety
  - + - priradzovanie
    - spracovanie pomocou dočasných premenných
    - + - newtemp
      - vráti offset do aktuálnej tabuľky
      - vytvorí premennú príslušného typu
- + - kompletné vyhodnocovanie
  - využíva numerické hodnoty pre skoky
  - + - S->id = E
    - štart gramatiky
    - {
      p=lookup(id.name);
      if(p!=NULL) {
      gen(ASSIGN, p, E.place);
      } else {
      error();
      }
      }
  - + - E -> E1 + E2
    - sčítanie dvoch výrazov
    - vytvor nové miesto
    - vygeneruj inštrukciu pre sčítanie
    - {
      E.place = newtemp();
      gen(ADD, E.place, E1.place, E2.place);
      }
  - + - E -> -E1
    - zmena zmanienka
    - {
      E.place = newtemp();
      gen(UMINUS, E.place, E1.place);
      }
  - + - E -> (E1)
    - odstránenie zátvoriek
    - {
      E.place = E1.place
      }
  - + - E -> id
    - nájdi hodnotu výrazu
    - {
      p = lookup(id.name)
      if(p != NULL) {
      E.place = p;
      } else {
      error();
      }
      }
  - + - E -> E1 or E2
    - {
      E.place = newtemp();
      gen(E.place = E1.place OR E2.place);
      }
  - + - E -> E1 and E2
    - {
      E.place = newtemp();
      gen(E.place = E1.place AND E2.place);
      }
  - + - E -> not E1
    - {
      E.place = newtemp();
      gen(E.place = not E1.place);
      }
  - + - E -> id1 relop id2
    - {
      E.place = newtemp();
      gen(if id1.place relop id2.place goto next+3)
      gen(E.place = 0);
      gen(goto next+2);
      gen(E.place = 1);
      }
  - + - E -> true
    - {
      E.place = newtemp();
      E.place = 1;
      }
  - + - E -> false
    - {
      E.place = newtemp();
      E.place = 0;
      }
  - + - funkcie
    - + - lookup
      - vracia pointer na tabuľku symbolov
    - + - gen
      - vytvorí trojadresový záznam
    - + - newtemp
      - vytvorí novú dočasnú premennú
- + - lenivé vyhodnocovanie
  - využíva kontrolu toku skoky nie sú explicitne vyjadrené
  - + - S -> if E then S1
    - {
      E.true = newlabel();
      E.false = S.next();
      S1.next = S.next();
      S.code = E.code + "E.true :" + S1.code
      }
  - + - S -> if E then S1 else S2
    - {
      E.true = newlabel();
      E.false = newlabel();
      S1.next = S.next;
      S2.next = S.next;
      S.code = E.code + "E.true :" + S1.code + "goto S.next" + "E.false :" + S2.code
      }
  - + - S -> while E do S1
    - {
      E.true = newlabel();
      E.false = S.next;
      S.begin = newlable();
      S1.next = S.begin;
      S.code = "S.begin" + E.code + "E.true :" + S1.code + "goto S.begin"
      }
  - + - E -> E1 or E2
    - {
      E1.true = E.true;
      E1.flase = newlabel();
      E2.true = E.true;
      E2.false = E.false;
      E.code = E1.code + "E1.false :" + E2.code
      }
  - + - E -> E1 and E2
    - {
      E1.true = newlabel();
      E1.false = E.false;
      E2.true = E.true;
      E2.false = E.flase;
      E.code = E1.code + "E1.true :" + E2.code;
      }
  - + - E -> not E1
    - {
      E1.true = E.false;
      E1.false = E.true;
      E.code = E1.code;
      }
  - + - E -> (E1)
    - {
      E1.true = E.true;
      E1.false = E.false;
      E.code = E1.code;
      }
  - + - E -> id1 relop id2
    - {
      E.code = "if id1.place relop id2.place goto E.true" + "goto E.false"
      }
  - + - E -> true
    - {
      E.code = "goto E.true"
      }
  - + - E -> false
    - {
      E.code = "goto E.false";
      }
- + - backpatching
  - počas generovania kódu je nutné generovať
    odskoky na kód, ktorý ešte nie je vygenerovaný
  - rieši sa použitím symbolických mien
  - pridáva sa true a false list
  - + - jednopriechodnový preklad
    - riešenie backpatchingom
    - udržiavame zoznam oadries odkazujúcich na symbolické návestie
    - keď sa vygeneruje kód, na ktorý sa odkazuje
    - spätne doplníme do všetkých miest uvedených v zozname
  - + - funkcie
    - + - makelist(i)
      - vytvorí nový zoznam obsahujúci index i
      - vráti pointer na tento zoznam
    - + - merge(p,q)
      - spojí zoznamy určené pointermi
      - vráti pointer na výsledný zoznam
    - + - backpatch(p,i)
      - vloží adresu i do všetkých príkazov v zozname p
  - + - vzťahy
    - + - E -> true
      - {
        E.tlist = makelist(next);
        gen("goto -");
        }
    - + - E -> false
      - {
        E.flist = makelist(next);
        gen("goto -");
        }
    - + - E -> id1 relop id2
      - {
        E.tlist = makelist(next);
        E.flist = makelist(next + 1);
        gen("if id1.place relop id2.place goto -");
        gen("goto -");
        }
    - + - E -> E1 or M E2
      - {
        backpatch(E1.flist, M.quad);
        E.tlist = merge(E1.tlist, E2.tlist);
        E.flist = E2.flist
        }
    - + - E -> E1 and M E2
      - {
        backpatch(E1.tlist, M.quad)
        E.flist = merge(E1.flist, E2.flist)
        E.tlist = E2.tlist
        }
    - + - E -> not E1
      - {
        E.tlist = E1.flist;
        E.flist = E1.tlist;
        }
    - + - E -> (E)
      - {
        E.tlist = E1.tlist;
        E.flist = E1.flist;
        }
    - + - M -> epsilon
      - {
        M.quad = next;
        }
    - + - S -> if E then MS1
      - {
        backpatch(E.tlist, M.quad);
        S.nlist = merge(E.flist, S1.nlist);
        }
    - + - S -> if E then M1S1N else M2S2
      - {
        backpatch(E.tlist, M1.quad);
        backpatch(E.flist, M2.quad);
        S.nlist = merge(S1.nlist, S2.nlist, N.nlist);
        }
    - + - S -> while M1E do M2S
      - {
        backpatch(S.nlist, M1.quad);
        backpatch(E.tlist, M2.quad);
        S.nlist = E.flist;
        gen("goto M1.quad");
        }
    - + - N -> epsilon
      - {
        N.nlist = makelist(next);
        gen("goto -");
        }
    - + - S -> begin L end
      - {
        S.nlist = L.nlist;
        }
    - + - S -> A
      - {
        S.nlist = NULL;
        }
    - + - L -> L1; MS1
      - {
        backpatch(L1.nlist, M.quad);
        S.nlist = S1.nlist;
        }
    - + - L -> S
      - {
        L.nlist = S.nlist;
        }
+ - optimalizácia
- + - lokálna
  - eliminácia spoločných podvýrazov
  - odstránenie zbytočných priradení
  - redukcia počtu pomocných premenných
- + - globálna
  - zbytočné výpočty cez všetky cesty
  - trace ekvivalencia
- + - detekcia
  - konštrukcia grafu toku riadenia
  - samotná detekcia
- + - transformácie v blokoch
  - + - eliminácia zbytočných píkazov
    - nedostupné z počiatočného príkazu
    - nepočítajú hodnotu výstupných premenných
  - + - eliminácia nadbytočného výpoču
    - odstraňuje spoločné podvýrazy
  - výmena poradia príkazov
  - premenovanie premenných
- + - minimalizácia Load a Store
  - L = 0
  - nájdi príkaz, kde všetky premenné, ktoré využíva sú už v zozname
  - pridaj ho do zoznamu
  - L je reverse optimálny blok
- + - detekcia trace ekvivalencie
  - + - graf toku riadenia
    - reprezentácia vnútorného tvaru programu
    - orientovaný graf
    - + - vrcholy = postupnosť príkazov
      - označované ako základné bloky
      - prevádzanie bloku môže začať iba prvým príkazom
      - mimo posledného príkazu neobsahuje vetvenie
    - + - hrany = relácie následnosti
      - zobrazujú potenciálny prenos riadenia medzi blokmi
  - + - detekcia živých premenných
    - LIVE problem
      premenná i je živá v uzle u, ak existuje cesta z u do nejakého
      uzlu v, že spočítaná hodnota i v u je vo v použitá
      + - LIVE
      - živá premenná
      + - KILL
      - premenná je v uzle definovaná
      - všetky premenné v bloku U, kde prvá akcia je modifikácia ich hodnoty
      + - NOTKILL
      - doplnok do KILL
      + - GEN
      - premenná je v uzle redefinovaná
      - premenné v bloku U, kde je prvou akciou referencovanie hodnoty premennej
      + - systém vzájomne rekurzívnych rovníc
      - + - LIVEIN(N)
        LIVEOUT(N) prienik (NOTKILL(N) zjednotené GEN(N)
        
        bola živá na výstupe
        
        nebola definovaná v bloku N
        
        mohla byť redefinovaná v bloku N
      - + - LIVEOUT(N)
        zjednotenie cez následníkov N, LIVEIN(m)
      - + - riešením rovníc je pevný bod
        + - algoritmus
        vstup: pre všetky uzly u GEN(U) a NOTKILL(u)
        
        výstup: pre všetky uzly LIVETOP(u)
        
        uzly z N sú očíslované ako postorder
        
        + - inicializácia
        všetkým uzlom nastav LIVETOP na prázdnu množinu
        
        + - pokiaľ dochádza k zmene
        postupne prelez všetky prvky
        NEWLIVETOP=zjednotenie LIVETOP cez vvšetkých predchodcov,
        prienik s NOTKILL uzlu, zjednotené s GEN uzlu
        ak došlo k zmene NEWLIVETOP od LIVETOP, použi LIVEIN
  - + - detekcia dostupných výrazov
    - postorder
    - + - pracovný zoznam
      - AVAIL - problém dostupných výrazov
      - GEN(n) - výrazy, ktorých hodnota je spočítaná
      - KILL(n) - výrazy obsahujúce premennú, ktorých hodnota sa zmenila
      - + - AVAILOUT(n)
        AVAILIN(n) a (NOTKILL(n) zjednotené GEN(n)
        
        výraz živý na vstupe
        
        premenná vo výraze nebola zmenená
        
        výraz mohol byť spočítaný
      - + - AVAILIN(n)
        zjednotenie cez predchodcov n, AVAILOUT(m)
    - + - inicializácia
      - AVAILOUT=GEN
      - AVAILIN=0
- + - programy s cyklami
  - + - transformácia
    - nahradenie výpočtu výsledom už v dobe kompilácie
    - + - rozvinutie cyklov
      - ušetria sa príkazy skoku
    - zlúčenie cyklov
    - + - čistenie cyklov
      - presun invariantných príkazvo pred cyklus
    - + - indukčné premenné
      - eliminácia indukčných premenných
      - redukcia zložitosti operátorov
    - inline procedúry
+ - generovanie cieľového kódu
- + - algritmus
  - 1. čítaj inštrukciu
    ak je to popis operandu ulož na zásobník a opakuj 1.
    2. Vyber tabuľku pre načítaný operátor
    vyber položku podľa druhého operandu na zásobníku
    3. Ak je má niektorý operand popis na zásobníku,
    ulož stradač, s výnimkou výrazou, ktoré vystupujú
    v práve spracovávanom výraze.
    Ulož stradač a označ ho v zásobníku označením pomocnej premennej
    4. Generuj inštrukcie
    5. Zo zásobníku zruš použíté operandy
    a na zásobník pridaj označenie miesta, kde bol
    uložený výsledok
- tabuľky