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

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

1) Některé browsery tu tabulku vykreslují divně

Lexikální analýza

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

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 bezkontextových gramatikách a zásobníkových automatech.

Shora dolů

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.

LL parser

Recursive descent parser

Zdola nahoru

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

Code generation (compiler), 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