Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Překladače

Definice (Překladač)

Formální definice: překladač je zobrazení pro nějaké dva jazyky , vstupní generovaný gramatikou , výstupní generovaný gramatikou nebo přijímaný automatem . Je to takové zobrazení, kde . Pro zobrazení neexistuje.

Neformálně jde o stroj, který nějaký zdrojový kód (v nějakém zdrojovém jazyce) převádí na cílový kód (v cílovém jazyce) a případně vypisuje chybová hlášení.

Definice neříká nic o třídách jazyků a gramatik, ve kterých překladač operuje. Běžné programovací jazyky jsou plus minus bezkontextové - nebo se na bezkontextové převádějí, aby byly rozpoznatelné něčím prakticky implementovatelným (tedy zásobníkovým automatem, Turingovy stroje jsou poněkud složité).

Příklady

Příklady použití překladačů:

- (překvapivě) překlad programů, psaných v nějakém vyšším programovacím jazyce, do strojového kódu cílové platformy
- syntax-highlighting (většinou lexikálně řízený)
- pretty printer
- statické kontroly programu (hledání chyb bez spouštění programů)
- interpretery (např. skriptovacích jazyků, run-time moduly pro interpretované jazyky jako je Java)
- databázové stroje, dotazovací jazyky

Překlad programu

Program (pro jednoduchost jediný modul) se

1. ze zdrojového kódu v nějakém programovacím jazyce preprocesorem (což je taky překladač, upravující zdrojový kód na textové úrovni) převede na textový soubor (připravený pro další překlad),
2. překladačem se převede dál do assemblerového kódu (jde o kód v jiném jazyce, mnohem bližším cílové architektuře - jde o textový popis instrukcí procesoru),
3. assemblerem se převádí na object-file - modul, ve kterém už jazyk odpovídá strojovému kódu cílové CPU,
4. nakonec linker, resp. loader připojí další informace a vytvoří finální spustitelný kód.

Fáze překladu překladačem

Tradičně se překladače dělí na dvě fáze - front-end a back-end. První z nich je zaměřená hlavně na analýzu zdrojového kódu po lexikální a syntaktické stránce a její převod do nějakého mezikódu, tj. přípravu pro back-end. Úkolem back-endu je pak z předpřipravené formy vygenerovat finální kód v cílovém jazyce.

První fáze se dále dělí na tyto části:

1. lexikální analýza - převádí vstupní text do binární formy, na sled identifikátorů a konstant; hodnoty objektů ukládá do spec. tabulek
2. syntaktická analýza - abstraktní část, nezajímá se o hodnoty a význam elementů jazyka, úkolem je rozpoznat, zda vstupní slovo (vstup) patří do jazyka; v dnešních překladačích staví tzv. syntaktický strom kódu
3. sémantická analýza - zkoumá sémantiku (význam, smysl) elementů jazyka (např. u sčítání proměnných kontrola typů, používání definovaných proměnných atd.)
4. generování mezikódu - úzce svázané se sémantickou analýzou, načítá hodnoty lexikálních elementů z tabulek a vytváří binární formu kódu, v ideálním případě nezávislou na vstupním ani výstupním jazyce
5. optimalizace nad mezikódem - díky překladu do nějakého abstraktního mezikódu lze nad ním potom provádět různé obecné (teoreticky dokázané) optimalizace, aby byl výsledný kód ekvivalentní s původním, ale rychlejší při provádění cílovým strojem

Backend má na starosti hlavně

1. generování kódu - vytváří už kód pro konkrétní cílový stroj / architekturu / CPU.
2. optimalizace nízkoúrovňového kódu - optimalizace, zaměřené na vlastnosti konkrétních CPU a cílový jazyk (tj. takové, které nad obecným mezikódem s vysokou abstrakcí provést nejde)

Všechny fáze překladače (většinou, když se pominou třeba staší verze GCC a podobně) sdílejí jednotné tabulky symbolů - hodnot lexikálních elementů a jiných věcí a obsluhu chyb. Překladač musí rozpoznat všechny chyby, ale bez velké časové režie, navíc nesmí mít falešné poplachy. Taky by neměl vyrábět chyby sám ;-).

V dřívějších překladačích se vstupní kód procházel několikrát, protože nebylo technicky možné ho udržet celý v paměti. Dnes je potřeba většinou jen jeden přechod, ale někdy je nutných víc (např. dopředné skoky v assembleru - nevím ještě jak daleko skáču).

Poznámka (Syntax-driven compilation)

Nejdůležitější částí dnešních překladačů bývá syntaktická analýza; provádí se často najednou se sémantickou analýzou a generováním mezikódu - vše mívá na starosti jediný zásobníkový automat. Navíc si často sám vyvolává lexikální analýzu, ta je jím tedy řízená, takže se taková technika označuje syntaxí řízený překlad.

Automatické generování (částí) překladače

Protože dnešní programovací jazyky jsou relativně složité (gramatiky které je generují mají řádově stovky přepisovacích pravidel), konstrukce automatů přijímajících takové jazyky ručně je příliš náročná. Proto existují nástroje, které generují některé části překladače - generátor lexikálních analyzátorů - scannerů - (popíšu lexikální elementy a struktury a co s nimi dělá a vypadne mi analyzátor jako kód v jazyce C) je např. Flex, pro výrobu parserů (syntaktických analyzátorů) z popisu gramatiky slouží např. Bison, Coco/R nebo ANTLR. Některé známé překladače mají ale i tak ručně generované parsery (GCC).

Existují i generátory generátorů kódu (ale jejich méně, protože to je dost složité) - pro popis výstupního CPU dostanu z instrukčního mezikódu kód přímo pro něj. Instrukční mezikód může být pro více architektur úplně stejný. Příkladem tohoto je Mono JIT Compiler.

Mezikód

(Vysokoúrovňový) mezikód je vlastně jakési rozhraní pro přechod (rozdělení i spolupráci) mezi front-endem a back-endem. Jde o binární reprezentaci zdrojového kódu, má být nezávislý na vstupním i výstupním jazyce. Pokud tomu tak je, je možné např. kombinovat různé back-endy a front-endy, jako tomu je u GCC (více back-endů pro 1 front-end) nebo .NET (více front-endů). Většinou ale je mezikód o něco posunutý buď více k závislosti na back-endu nebo na front-endu.

Mezikód je možné reprezentovat několika způsoby - např. syntaktickým stromem (vhodné v paměti), postfixovým zápisem (linearizace stromu) nebo tříadresovým kódem (lineární, sekvence příkazů ).

Graf toku řízení

Graf toku řízení je graf, vytvářený překladači (větš. pro 1 funkci) za účelem optimalizací a také generování výsledného kódu. Uzly - základní bloky - jsou nepřerušované výpočty (bez instrukcí skoků a bez cílů skoků uvnitř bloků), z nichž první instrukce bývá cílem skoku nebo vstupním bodem funkce. Hrany pak reprezentují skoky - pro podmíněné skoky a case příkazy pak z uzlů vede více hran.