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í.

¹⁾

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.

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.

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

Bottom-up parsing

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

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

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

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í.

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.

• 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