====== Struktura překladače a charakteristika fází překladu ======
[[wp>Compiler]]

Překladač čtě zdrojový program (napsaný ve zdrojovém jazyce) a překládá ho na cílový program (napsaný v cílovém jazyce -- zpravidla nějaký asembler). Zdrojový a cílový program jsou vzájemně funkčně ekvivalentní.

^  Lexikální anaýza  ^^  Syntaktická analýza  ^^  Sémantická analýza  ^^  Generování vnitřního kódu  ^^  Optimalizátor  ^  Generování cílového kódu  ^^
|  Zdrojový kód  |  Řetězec tokenů  ||  Derivařní strom  ||  Abstraktní syntaktický strom  ||  Vnitřní kód (optimalizovaný)  |||  Cílový program  |
((Některé browsery tu tabulku vykreslují divně))

===== Lexikální analýza =====
[[wp>Lexical analysis]]

Vstup: Zdrojový program

Výstup: Řetězec tokenů

V podstatě jde o to rozsekat tok znaků na jednotlivé tokeny (slova) a přiřadit jim význam (2 je číslo, //x// je proměnná, + je operátor, ...). Často se k tomu používají regulární výrazy.
===== Syntaktická analýza =====
[[wp>Parsing]]

Vstup: Řetězec tokenů

Výstup: Derivační strom

Cílem je zkontrolovat, že jednotlivé tokeny jdou správně za sebou a dávají tak smysl. Výsledkem je tzv. syntaktický (derivační) strom. Pokud takový strom nalezneme, program je správný, jinak ne. Vytváření derivačního stromu je založeno na [[bezkontextove_jazyky|bezkontextových gramatikách a zásobníkových automatech]].

==== Shora dolů ====
[[wp>Top-down parsing]]

Probíhá tak, že se symboly v gramatice postupně rozgenerovávají, takže z počátečního symbolu vznikne posloupnost jiných symbolů podle gramatiky. Používá se častěji.

  * [[wp>LL parser]]
  * [[wp>Recursive descent parser]]

==== Zdola nahoru ====
[[wp>Bottom-up parsing]]

Naopak, z posloupnosti symbolů se snažíme udělat počáteční symbol.

===== Sémantická analýza =====
Vstup: Derivační strom

Výstup: Abstraktní syntaktický strom

Sémantický analyzátor kontroluje sémantické aspekty programu:
  * kontrola typů, při které může provádět implicitní konverze (např. int-to-real)
  * kontrola deklarací proměnných

===== Generování vnitřního kódu =====
Vstup: Abstraktní syntaktický strom

Výstup: Vnitřní kód

Generátor vnitřního kódu vytváří vnitřní reprezentaci programu nazývanou vnitřní kód (většinou tří adresný) z následujících důvodů:
  * jednotnost
  * přímý překlad do cílového programu je složitý a "neprůhledný"
  * vnitřní kód lze snadno optimalizovat

===== Optimalizátor =====
Vstup: Vnitřní kód

Výstup: Optimalizovaný vnitřní kód

Optimalizátor upraví vnitřní kód tak, aby byl efektivnější. Příklady úprav:
  * **Šíření konstanty:** (a = 1; b = 2; c = a+b; ⇒ c = 3) -- Proměnné a, b nejsou již dále v programu použity
  * **Šíření kopírováním:** (b = a; c = b; d = c ⇒ d = a) -- Proměnné b, c nejsou již dále v programu použity
  * **Eliminace mrtvého kódu:** (while false do ... ⇒ odstranit)

Některé překladače optimalizátor nemají. 

===== Generování cílového kódu =====
[[wp>Code generation (compiler)]], [[wp>Three address code]]

Vstup: Optimalizovaný vnitřní kód (popř. neoptimalizovaný)

Výstup: Cílový program

Cílový program je zapsán v cílovém jazyce. V praxi je cílovým jazykem většinou asembler nebo strojový kód.
===== Shrnutí =====
  * překladač: překládá vstupní jazyk na výstupní (obvykle strojový)
  * jednotlivé kroky: viz tabulka nahoře
  * syntaktická analýza: shora dolů: máme první neterminál a snažíme se z něj postupně odvodit větu na vstupu, zdola nahoru: postupně se z věty snažíme dostat ke kořenu
  * zdola nahoru: je potřeba rozšířený zásobníkový automat, používá se třeba na výrazy (bezkontextové, obsahuje priority a závorky)
  * shora dolů: je potřeba běžný zásobníkový automat, používá se na zpracování nevýrazových kusů klasického procedurálního jazyka
  * tříadresový kód: cíl, 2 operandy, operátor
  * optimalizátor: šíření konstanty, eliminace mrtvého kódu, šíření kopírováním