Překladač

Article on other languages:

• Vertalerkonstruksie
• Compilador
• مصرف_(برمجة)
• Compilador
• Компилатор
• Kompajler
• Compilador
• Compiler
• Compiler
• Μεταγλωττιστής
• Compiler
• Tradukilo
• Compilador
• Kompilaator
• همگردان
• Ohjelmointikielen_kääntäjä
• Compilateur
• Compilador
• מהדר
• Jezični_procesor
• Fordítóprogram
• Kompilator
• Þýðandi_(tölvunarfræði)
• Compilatore
• コンパイラ
• კომპილატორი
• 컴파일러
• Kompiliatorius
• Компајлер
• കംപൈലര്‍
• Compiler
• Kompilator
• Kompilator
• Compilador
• Компилятор
• Compiler
• Компилатор
• Kompilator
• நிரல்மொழிமாற்றி
• โปรแกรมแปลโปรแกรม
• Derleyici
• Компілятор
• Trình_biên_dịch
• קאמפיילער
• 編譯器

Příklad struktury překladače podporujícího dva vstupní jazyky i dvě cílové architektury

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.

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 jazyce symbolických adres. 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.

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).

Části překladače

• lexikální analyzátor
• syntaktická analýza
• sémantický analyzátor
• optimalizace kódu
• generování cílového kódu

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).

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.

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.

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).

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.

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.

Průchody překladače

Průchodem překladače se rozumí kompletní načtení celého zdrojového kódu. Průchodem vzniká mezikód pro vnitřní potřebu překladače. Mezikód je vstupem další části nebo dalšího průchodu překladače.

dělení:

• Jednoprůchodové - jsou jednodušší v oblasti překladače a jazyka. Mají nižší režiji, protože nevzniká mezikód.
• Víceprůchodové - je složitější, ale je jednodušší vznik a údržba překladače, jelikož se skládá ze samostatných částí, které spolu nemusí souviset. Požaduje nižší nároky na hardware při překladu, jelikož části překladače jsou samostatné.

Příklad překladače

Následující program implementuje velmi jednoduše jednoprůchodový překladač napsaný v jazyce C. Tento překladač kompiluje výrazy definované v infixsovém zápisu do postfixové notace (reverzní polská notace, zkráceně RNP) a taktéž do assembleru. Překladač provádí strategii rekurentního zanořování výrazů. Každé vyvolání funkce odpovídá při setkání s neterminálním symbolem do gramatiky jazyka.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
#define MODE_POSTFIX 	0
#define MODE_ASSEMBLY 	1
 
char    lookahead;
int     pos;
int	compile_mode;
char    expression[20+1];
 
void error()
{
        printf("Syntax error!\n");
}
 
void match( char t )
{
        if( lookahead == t )
        {
                pos++;
                lookahead = expression[pos];            
        }
        else
                error();
}
 
void digit()
{
        switch( lookahead )
        {
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
			if( compile_mode == MODE_POSTFIX )
				printf("%c", lookahead);
			else
				printf("\tPUSH %c\n", lookahead);			
 
                        match( lookahead );
                        break;
                default:
                        error();
                        break;
        }
}
 
void term()
{
        digit();
        while(1)
        {
                switch( lookahead )
                {
                        case '*':
                                match('*');
                                digit();
 
                                printf( "%s", compile_mode == MODE_POSTFIX ? "*" 
					: "\tPOP B\n\tPOP A\n\tMUL A, B\n\tPUSH A\n");
 
                                break;
                        case '/':
                                match('/');
                                digit();
 
                                printf( "%s", compile_mode == MODE_POSTFIX ? "/" 
					: "\tPOP B\n\tPOP A\n\tDIV A, B\n\tPUSH A\n");
                                break;
                        default:
                                return;
                }
        }
}
 
void expr()
{
        term();
        while(1)
        {
                switch( lookahead )
                {
                        case '+':
                                match('+');
                                term();
 
                                printf( "%s", compile_mode == MODE_POSTFIX ? "+" 
					: "\tPOP B\n\tPOP A\n\tADD A, B\n\tPUSH A\n");
                                break;
                        case '-':
                                match('-');
                                term();
 
                                printf( "%s", compile_mode == MODE_POSTFIX ? "-" 
					: "\tPOP B\n\tPOP A\n\tSUB A, B\n\tPUSH A\n");
                                break;
                        default:
                                return;
                }
        }
}
 
int main ( int argc, char** argv )
{
        printf("Please enter an infix-notated expression with single digits:\n\n\t");
        scanf("%20s", expression);
 
        printf("\nCompiling to postfix-notated expression:\n\n\t");	
	compile_mode = MODE_POSTFIX;
        pos = 0;
        lookahead = *expression;
        expr();
 
        printf("\n\nCompiling to assembly-notated machine code:\n\n");        
        compile_mode = MODE_ASSEMBLY;
        pos = 0;
        lookahead = *expression;
        expr();
 
        return 0;
}

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++

Reference

1. ↑ David Muxworthy: Fortran’s Fiftieth Birthday, British Computer Society Fortran Specialist Group
2. ↑ The World’s First COBOL Compilers – Free public lecture, 12. 7. 1997 (anglicky)

Související články

• Linker

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
• Jazyky a překladače (seriál na ABCLinuxu)

Tento článek je zčásti nebo zcela založen na překladu článku Compiler na německé Wikipedii. Číslo revize nebylo určeno.