Překladač
Z Wikipedie, otevřené encyklopedie
Překladač (též kompilátor, anglicky compiler z to compile – sestavit, zpracovat) je všeobecně stroj, respektive program, provádějící překlad z nějakého vstupního jazyka do jazyka výstupního. Nejčastěji bývá tento pojem používán v programování, kde označuje nástroje překládající algoritmus zapsaný ve vyšším programovacím jazyce do jazyka strojového, nebo spíše do strojového kódu. (O překladačích mezi přirozenými jazyky viz strojový překlad.)
Obsah |
[editovat] Historie
Prvním programem, který by bylo možno označit jako kompilátor, byl A-0 System, který v roce 1952 vytvořila Grace Hopperová pro počítač UNIVAC I. První kompletní překladač byl vyvinut v roce 1957 ve společnosti IBM a byl pro jazyk Fortran.[1] V roce 1960 měl jazyk COBOL první překladač pro více architektur,[2] což zvýšilo jeho přenositelnost. Tyto překladače byly vytvořeny v assembleru. Jazyky, které umožňují napsat překladač, který přeloží sám sebe, se označují jako self-hosting („samonosné“) a prvním takovým se stal LISP, jehož překladač byl vytvořen v roce 1962 na MIT. Ovšem použití jazyků vyšší úrovně pro psaní překladačů se stalo běžné až po roce 1970, kdy byly překladače C a Pascalu vytvořeny v těchto jazycích.
[editovat] Struktura překladače
Překladač lze navrhnout mnoha způsoby, nejčastěji bývá rozdělen na dvě části. První je závislá na vstupním jazyce (tzv. front-end) a druhá závisí na cílové architektuře (tzv. back-end). Mezi těmito částmi program existuje ve formě tzv. mezikódu (bytekódu).
[editovat] Lexikální analyzátor
Lexikální analyzátor je první jednotka překladače, která má za úkol relativně jednoduchým způsobem získat ze vstupního zdrojového textu tzv. lexému (některý základní prvek příslušného jazyka, např. klíčové slovo „if“) a tu pak zasílá syntaktickému analyzátoru.
Všechny možné lexémy jsou ve vstupním jazyce popsány pomocí regulárních výrazů. V kompilátoru se pro jejich rozpoznávání používá konečný automat. Kromě samotné lexémy se do syntaktického analyzátoru posílají další související údaje, např. jakého druhu je daná lexéma (operátor, klíčové slovo, identifikátor, …), u identifikátorů odkaz do tabulky identifikátorů (pro urychlení překladu, překladač poté nemusí pracovat s textem, ale pouze s číselným označením) apod. Celý soubor údajů předávaný z lexikálního do syntaktického analyzátoru se označuje anglickým termínem token (známka, odznak).
[editovat] Syntaktický analyzátor
Syntaktický analyzátor (v angličtině označovaný jako parser, z to parse – rozebrat, oddělovat, udělat větný rozbor) se dá považovat za mozek překladače, protože provádí samotnou analýzu vstupního jazyka. Úkolem syntaktického analyzátoru je rozpoznat, zda je program zapsán správným způsobem, např. zda na úvodní „begin“ bude navazovat někde koncové „end“, ale také určuje, v jakém pořadí se budou provádět jednotlivé části příkazů, např. u „x + y*z“ rozpozná a určí, že nejdříve se bude násobit a pak až sčítat, nebo u vnořených příkazů zajistí, že nejdříve se vyhodnotí parametr funkce a teprve pak se daná funkce zavolá.
Úloha syntaktického analyzátoru je o něco složitější než úloha lexikálního analyzátoru, neboť na rozdíl od regulárního jazyka lexém musí syntaktický analyzátor rozpoznávat složitější bezkontextový jazyk (typicky LL(1) či LR(1)). Syntaktický analyzátor k tomu musí vyhodnocovat vstup v delším záběru.
Výsledkem práce syntaktického analyzátoru je tzv. syntaktický strom (anglicky „parse tree“), který popisuje strukturu vstupního programu.
Jedním z nejjednodušších způsobů konstrukce syntaktického analyzátoru je tzv. metoda rekurzivního sestupu. V této metodě se pomocí rekurzivních volání konstruuje syntaktický strom, přičemž struktura implementace překladače odráží strukturu příslušné gramatiky. Pokud je v gramatice na daném místě neterminální symbol, v překladači mu odpovídá (rekurzivní) volání funkce reprezentující příslušný neterminál. Tato rekurzivní volání končí u terminálních symbolů (lexémů jazyka), které jsou přečteny a uloženy do syntaktického stromu.
[editovat] Sémantický analyzátor
Sémantický analyzátor zpracovává syntaktický strom a provádí analýzu významu jednotlivých operací. Na rozdíl od syntaktického analyzátoru, který provádí kontrolu správnosti struktury programu čili zápis programového kódu, sémantický analyzátor provádí kontrolu správnosti operací. V tomto mechanismu se odehrává veškerá typová kontrola a různé konverze. Prací sémantického analyzátoru je např. analýza typů výrazů na levé a pravé straně přiřazovacího příkazu, přičemž musí zabránit např. přiřazení hodnoty s plovoucí řádovou čárkou do proměnné s pevnou řádovou čárkou.
Vstupem sémantického analyzátoru je syntaktický strom, který vygeneroval syntaktický analyzátor, výstupem je opět syntaktický strom, ale s doplněnými dodatečnými informacemi a s provedenými konverzemi.
[editovat] Překladač do mezikódu
V této fázi se ze syntaktického stromu generuje kód, tzn. strukturovaný syntaktický strom se transformuje do lineární posloupnosti instrukcí. Obvykle se však negeneruje přímo kód cílového jazyka, ale kód v nějakém pomocném jazyce, tzv. mezikód. Cílem tohoto kroku je ulehčit následující operace, které by v cílovém jazyce mohly být komplikované. Tohoto přístupu se s výhodou používá pro tvorbu optimalizátorů efektivity kódu. Existují však i překladače bez fáze překladu do mezikódu, překládající přímo do cílového jazyka.
Jednou z možností návrhu mezikódu je tzv. tříadresný kód. Instrukce tříadresného kódu mají jednotnou strukturu, pracují nad adresami dvou vstupních operandů a jednoho výsledkového operandu, např. Id1 = Id2 * 5. Nejtypičtější formou mezikódu však je kód nějakého zásobníkového počítače.
Překladem do mezikódu končí část závislá na zdrojovém programovacím jazyku (front-end), zbytek překladače (back-end) může být dokonce shodný pro překladače různých jazyků (tak je navržen např. překladač GCC).
Jako mezikód se používá i jazyk symbolických adres, někdy též nepřesně nazývaný Assembler (ovšem s omezením na cílovou architekturu).
[editovat] Optimalizátor
Optimalizátor mezikód různě transformuje, přičemž cílem je urychlení výsledného kódu. Ve vygenerovaném kódu se mohou např. vyskytovat cyklická přiřazení typu:
Id1 = 5 + Id2 Id3 = Id1
takovýto kód optimalizátor přepíše na:
Id3 = 5 + Id2
Také se může vyskytovat tzv. mrtvý kód, tedy kód, který se nikdy nevykoná, například:
while (false)
{
...
}
takový kód optimalizátor zcela zahodí. Na výstupu optimalizátoru je stále mezikód.
[editovat] Generátor kódu
V poslední fázi se z mezikódu generuje výstupní kód, program v cílovém jazyce. Cílovým jazykem nejčastěji bývá přímo strojový kód.
[editovat] Nejznámější překladače
- GCC (GNU Compiler Collection)
- Intel C++ Compiler (ICC)
- Microsoft Visual Studio (přesněji v něm obsažené překladače C++, C#, Visual Basic atd.)
- Glasgow Haskell Compiler (GHC)
- Turbo Pascal, následně Delphi
- Borland C++, následně C++Builder
- FreePascal
- Watcom C/C++
[editovat] Reference
- ↑ David Muxworthy: Fortran’s Fiftieth Birthday, British Computer Society Fortran Specialist Group
- ↑ The World’s First COBOL Compilers – Free public lecture, 12. 7. 1997 (anglicky)
[editovat] Související články
[editovat] Externí odkazy
- Formální jazyky a překladače – materiály z cvičení Katedry informatiky a výpočetní techniky Fakulty aplikovaných věd Západočeské univerzity v Plzni
- Seriál na ABCLinuxu - Jazyky a překladače
Tento článek je zčásti nebo zcela založen na překladu článku Compiler na německé Wikipedii.
