Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:isz:prekladac

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)

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.

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
1)
Některé browsery tu tabulku vykreslují divně
/var/www/wiki/data/pages/pitel/isz/prekladac.txt · Poslední úprava: 03. 07. 2012, 13.53:46 (upraveno mimo DokuWiki)