22 - Struktura překladače a charakteristika fází překladu

• překladač je program, jehož:
  1. vstup je text představující zdrojový kód v zdrojovém jazyce - zdrojový program
  2. výstup je cílový program, který je funkčně ekvivalentní se zdrojovým programem
• před samotným překladem je třeba určit, zda je zdrojový program korektně zapsaný v daném zdrojovém jazyce (je podmnožinou daného jazyka)
  1. pokud ANO, provede překlad
  2. pokud NE, ukončí se a případně vypíše chyby
• fáze překladu se dělí se několik dílčích částí
  1. lexikální analyzátor - zdrojový program > řetězec tokenů
  2. syntaktický analyzátor - řetězec tokenů > derivační strom
  3. sémantický analyzátor - derivační strom > abstraktní syntaktický strom
  4. generátor vnitřního kódu - abstraktní syntaktický strom > vnitřní kód
  5. optimalizátor - vnitřní kód > optimalizovaný vnitřní kód
  6. generátor cílového kódu > optimalizovaný vnitřní kód > cílový program
  • jednotlivé části mohou být vzájemně provázány

• scanner
• část překladače, která načítá vstup a určuje jednotlivé lexémy (posloupnost znaků v daném jazyce)
• odstraňuje prázdná místa a komentáře
• může komunikovat s tabulkou symbolů
• lexémy jsou reprezentovány tokeny, který v sobě nese:
  1. typ lexému (číslo/řetězec/identifikátor/…) - zpravidla integer
  2. atribut - daný lexém (hodnota) - zpravidla union
• lexikální analyzátor se dá provést deterministickým konečným automatem nebo pomocí regulérních výrazy
  1. konečný automat - přijímá regulární jazyk
  2. regulární výraz - popisuje/značí regulární jazyk
  • příklady na převod RV na KA

• v praxi se používá LEX (existují i jiné nástroje) - generuje konečný automat na základě zadaných regulárních výrazech

• parser
• část překladače, která přijímá řetězec tokenů a vytváří derivační strom (ověřuje správnou posloupnost za sebou jdoucích tokenů)
• je postaven na gramatických pravidlech

• syntaktická analýza je rozdělena na metody:
  • shora dolů - LL gramatiky
    • pojmy:
      1. množina First
      2. množina Empty
      3. množina Follow
  • zdola nahoru
    1. precedenční SA - nejslabší, ale snadno se implementuje
    2. LR syntaktický analyzátor

• část překladače, která kontroluje sémantické aspekty programu ⇒ přijímá derivační strom a vytváří z něho abstraktní syntaktický strom
  1. kontrola typů (implicitní přetypování)
  2. kontrola deklarací
• v praxi se často používá syntaxí řízený překlad - překladač kontroluje sémantiku už při vytváření derivačního stromu (při kontrole syntaxe)

• část překladače která konvertuje abstraktní syntaktický strom do vnitřního kódu – trojadresná instrukce
• výhody:
  1. jednotnost
  2. snadno se převede do cílového kódu na rozdíl od přímého překladu, který je „neprůhledný“
  3. snadno se dá zoptimalizovat

• část překladače, která se snaží optimalizovat vnitřní kód
• program rozdělíme do základních bloků (sekvence příkazů, kterou vždy musím vykonat v daném pořadí) - jak?
  • hned první příkaz je vedoucí (úvodní příkaz bloku)
  • každý příkaz, který je návěští je vedoucí
  • každý příkaz za goto je vedoucí
  • ⇒ na konec spočítáme počet vedoucích a máme počet bloků
  • ⇒ můžeme si nakreslit graf bloků (něco jako konečný automat) ⇒ pokud zjistíme, že nějaký blok je nedostupný (mrtvý kód) ⇒ můžeme ho odstranit = > globální optimalizace
• lokální optimalizace - v rámci bloku

// --- zabalení konstanty --- //
a = 1;
b = 2;
c = a + b; //c = 3;
 
// --- šíření konstanty --- //
a = 2;
b = a;
c = b; // c = 2;
 
// --- kopírování proměnné --- //
// stejné jako šíření konstanty, akorát šířím proměnnou
 
// --- výrazové invarianty v cyklu --- //
for(i = 0; i < 100; i++)
{
  sum = p*q/r + i // p*q/r (výrazový invariant) se nemění s krokem, ale generovali bychom to 100x
}
 
// --- eliminace mrtvého kódu --- //
a = a; // toto je také mrtvý kód => sice se provede, ale nemá žádný význam
 
// --- rozbalení cyklu --- //
// zrušíme podmínku cyklu, ale nagenerujeme např 10x za sebou příkaz foru - třeba určit, kolikrát provádíme cyklus
// urychlí to cyklus, ale zabere víc paměti

• optimalizace rychlosti x optimalizace paměti
• generování:
  1. slepé: nezajímám se o to, co je za mnou a přede mnou a generuju instrukci z trojadresného kódu
  2. kontextové: redukuje … kouká, co bylo přede mnou, co bude následovat … pamatuje si proměnné, které ještě budou potřeba

; ...
store r1, c
load r1, c  ; zbytečně loadujeme do c => slepé generování toto nezoptimalizuje => nekoukáme na kontext
mul r1, d
; ...

• část překladače, která převádí zoptimalizovaný kód do výsledného kódu programu, což je např. strojový kód nebo assembler