Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:prekladac

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

pitel:isz:prekladac [03. 07. 2012, 13.53:46] (aktuální)
Řádek 1: Řádek 1:
 +====== 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
  
/var/www/wiki/data/pages/pitel/isz/prekladac.txt · Poslední úprava: 03. 07. 2012, 13.53:46 (upraveno mimo DokuWiki)