Překladače jsou základním vybavením každého počítače, jakožto nástroje pro překlad z jednoho (programovacího) jazyka do druhého. Bez jejich existence by programování bylo prakticky nerealizovatelné, protože by programátoři museli psát ve strojovém kódu, což je v dnešní době již zcela nepředstavitelné.

Programovací jazyky

Z důvodu snadnější realizace programů a algoritmů vznikla celá řada programovacích jazyků, které jsou buď vázány na konkrétní typ procesoru – strojově orientované jazyky (assemblery), nebo jazyky nezávislé na konkrétní typ procesoru – vyšší programovací jazyky (též někdy problémově orientované jazyky), příkladem může být C++ nebo Java.

Kompilované a interpretované jazyky

Z hlediska implementace jednotlivých programovacích jazyků rozeznáváme jazyky kompilované a interpretované. Kompilované programy jsou kompilátorem a sestavovacím programem převedeny do strojového kódu a strojový kód je přímo vykonáván procesorem. Naproti tomu interpretované programy jsou převedeny do tzv. vnitřní formy, v níž jsou pomocí speciálního programu (interpretu) vykonávány.

Do skupiny kompilovaných jazyků patří C/C++, do interpretovaných PHP. Existuje ještě třetí cesta - JIT (Just In Time) kompilace, ve které jsou intenzivně využívané části programů kompilovány až na cílové platformě. Touto cestou se vydaly programovací jazyky C# a Java.

Nelze říct, který přístup je nejlepší, protože všechny mají své výhody. Kompilovaný program je z podstaty věci rychlejší, interpretovaný je přenositelný a více flexibilní (interpretované jazyky se často používají ke skriptování v příkazové řádce). JIT kompilované programy jsou výrazně rychlejší než interpretované (ale pořád pomalejší než ty čistě kompilované), jsou přenositelné, ale jejich nasazení vyžaduje komplexní běhové prostředí, které se stará o kompilaci za běhu programu (např. .NET Framework a Mono pro C#, Java Runtime Environment pro Javu).

Konstrukce frontendu překladače

Co se týká samotné konstrukce překladače, tak ten se skládá z dvou hlavních částí – frontendu a backendu. Frontend obsahuje lexikální, syntaktický a sémantický analyzátor. Backend obsahuje optimalizátor a generátor výstupní formy.

Lexikální analyzátor

Lexikální analyzátor je obvykle stavový automat, jenž převádí znaky vstupního programu na lexikální elementy (například trojici znaků 1, 2, 9 na celé číslo 129), s nimiž dále pracuje překladač. Lexikální analyzátor se nijak nestará o to, zda-li mají dané kontrukce smysl.

Příklad

Syntaktický analyzátor

Syntaktický analyzátor kontroluje smysl programu, respektive syntax jeho konstrukcí, z hlediska předem definovaných pravidel (gramatiky). V programovacích jazycích se velmi často využívá LL1 gramatika, která je zpracovávaná pomocí rekurzivního sestupu.

LL1 gramatika

LL1 gramatika je postavena tak, aby se v žádném okamžiku nedostala do situace, ve které by mohlo jít zpracování vstupu více cestami (tj. zpracování je deterministické). Zásobníkový automat gramatiky je vždy schopen rozhodnout na základě svého stavu a prvního nezpracovaného znaku, do kterého dalšího stavu má přejít.

Rekurzivní sestup

Rekurzivní sestup je způsob, jakým dochází ke zpracování vstupu. Gramatika definuje množinu přepisovacích pravidel, která se skládá z terminálních a neterminálních symbolů. Terminální symbol je znak vstupu, který není nijak přepisován. Neterminální symbol je znak, který slouží k rozvinutí (a kontrole) pravidel gramatiky.

Na počátku zpracování obsahuje zásobník automatu jeden neterminální znak, říkejme mu . Aby mohl automat zkontrolovat validitu vstupu, tak tento znak musí být schopen rozvinout na celý řetězec vstupu (tzn. na všechny odpovídající terminální symboly). V každém kroku se proto automat podívá na vrchol zásobníku, je-li tam neterminální symbol, tak jej správným způsobem rozvine (buď pomocí LL1 gramatiky nebo jiného orákula). Je-li na vrcholu zásobníku terminální symbol, který rozvinout nejde, tak se podívá na vstup. Pokud je na vstupu stejný symbol, tak oba symboly srovná (odstraní), v opačném případě havaruje. V okamžiku, kdy již na vstupu není žádný znak a zásobník je prázdný, je ověřena syntaktická správnost vstupu.

Příklad

Mějme gramatiku, která zpracovává jednoduchý aritmetický výraz, který se skládá z operací sčítání a násobení (s obvyklými prioritami), čísel a závorek. Terminálními symboly pro nás proto jsou znaky číslo, +, *, (, ).

Níže uvedená gramatika kontroluje správnost libovolného výrazu. Pro přehlednost není LL1), proto při přechodech musíme dát na svoji intuici.

První pravidlo definuje, že můžeme sčítat dva výrazy, pravá rekurze (znak je znovu použit jako pravý operátor sčítání v tomto pravidle) značí, že můžeme vyhodnotit výrazy typu , které se budou vyhodnocovat při návratu z rekurze z pravé strany (pravá asociativita výrazu). Obdobně třetí pravidlo definuje operaci násobení. Pravidlo dva říká, že místo operace sčítání můžeme zapsat i výraz s vyšší prioritou (uzávorkovaný výraz, násobení, samotné číslo), analogicky funguje čtvrté pravidlo pro operaci násobení. Páté pravidlo umožňuje terminaci přepisování, šesté pak uzávorkování výrazů.

Čím je pravidlo v rámci stromu rekurze hlouběji, tím dříve dojde k jeho zpracování (výraz se zpracovává při rekurzivním návratu). Tímto způsobem jsou zajištěny priority jednotlivých operací.

#Krok	Vstup	Zásobník	Poznámka
0	(5 + 6) * 7		Inicializace
1	(5 + 6) * 7		Pravidlo 2
2	(5 + 6) * 7		Pravidlo 3
3	(5 + 6) * 7		Pravidlo 6
4	5 + 6) * 7		Srovnání
5	5 + 6) * 7		Pravidlo 1
6	5 + 6) * 7		Pravidlo 4
7	5 + 6) * 7		Pravidlo 5
8	+ 6) * 7		Srovnání
9	6) * 7		Srovnání
10	6) * 7		Pravidlo 2
11	6) * 7		Pravidlo 4
12	6) * 7		Pravidlo 5
13	) * 7		Srovnání
14	* 7		Srovnání
15	7		Srovnání
16	7		Pravidlo 4
17	7		Pravidlo 5
18			Srovnání, přijato

Zpracování výrazu (5 + 6) * 7

Sémantická analýza

Nyní, když je již zřejmé, že je program napsán pomocí platných konstrukcí, nastoupí sémantická analýza, která bývá realizována pomocí atributovaných překladových gramatik a statických pravidel. V praxi obvykle tato fáze probíhá současně se syntaktickou analýzou.

Atributované překlady přidávají každému elementu libovolný atribut (hodnotu), která slouží sémantickým účelům. Příkladem může být překlad konstrukce dynamicky typovaného jazyka na staticky typovaný:

Při návratu z rekurzivního sestupu atributovaná gramatiky na základě sémantických pravidel vrátí při zpracovávání čísla 0.5 nadřazenému volání (operátoru +), že výraz vyžaduje pro své uložení desetinné číslo. Volání odpovídající operátoru plus složí toto volání s druhou větví (celého čísla 5) a vyhodnotí, že celý výraz vrací desetinné číslo a tuto informaci opět vrátí o úroveň výš, kde volání u operátoru rovnosti přiřadí typ proměnné a.

Vnitřní forma

Když již má překladač všechny potřebné informace o korektnosti a struktuře, může vygenerovat vnitřní formu, která je výstupem frontendu (děje se tak obvykle při rekurzivním návratu, po provedení sémantické analýzy).

Program ve vnitřní formě iž není problém přeložit do libovolného jiného jazyka, případně jej zoptimalizovat nebo interpretovat. O tuto činnost se stará backend překladače.

Abstraktní syntaktický strom

Jednou z repezentací vnitřní formy je abstraktní syntaktický strom, což je strom, jehož vnitřními uzly jsou operátory a listy jsou operandy. Abstraktního syntaktického stromu se využívá primárně pro překlad a optimalizaci kódu. Jako příklad si můžeme představit strom, který reprezentuje booleovský výraz. V tomto stromu může překladač velmi pohodlně optimalizovat – např. pokud je jedna větev disjunkce vždy pravdivá, tak není třeba vyhodnocovat druhou větev.

Zásobníkový automat

Druhým přístupem je tzv. zásobníkový automat, kdy je program přeložen do posloupnosti příkazů pracujících nad zásobníkem jako paměťovým médiem – v podstatě se jedná o postfixovou notaci.

Zásobníkový jazyk je vhodný zejména pro interpretaci (takto je implementován jazyk Java).