Errata. Seznam chyb v textu bakalářské práce. Překladač s optimalizací výsledného kódu, 2013, Petr Krajník. Stav objevených chyb z 9

Errata Seznam chyb v textu bakalářské práce Překladač s optimalizací výsledného kódu, 2013, Petr Krajník Stav objevených chyb z 9. ledna 2013 Zde jsou uvedeny všechny dosud objevených chyb v textu bakalářské práce. Většina z nich byla způsobena „namotáním“ některých částí z předchozího zápisu bakalářské práce. Nyní následuje výčet chyb s popisem. 1. Chybějící citace (v textu jen [? ]) jsou: (a) Strana 28. Správně Sethi-Ullman (ne Levi-Sethi) algoritmus. AHO, Alfred V, Monica S. LAM, Ravi SETHI a Jeffrey D. ULLMAN. Compiler: Prinzipien, Techniken und Werkzeuge. 2., aktualisierte Aufl. München: Pearson Studium, 2008, 1253 s. ISBN 978-3-8273-7097-6. (b) Strana 23. Domovská strana gen. flex. Flex: The Fast Lexical Analyzer [online]. c2008 [cit. 2013-01-01]. Dostupné z: http://flex.sourceforge.net/. (c) Na staně 45. v příloze s gramatikou. NEŠVERA, Šimon. PROGRAMOVACÍ JAZYKY: Cvičení. Dotisk prvního vydání. Praha: Nakladatelství ČVUT, prosinec 2005, 114 s. ISBN 80-01-02522-5. 2. Příloha s gramatikou byla převzata z prvního zápisu. Uvedená gramatika obsahuje o něco více operátorů, než je implementováno. Jelikož jsem byl zahlcen různými operátory, tak jsem redukoval jejich počet. Zde je výčet pravidel, které by v gramatice být neměly. (a) (b) (c) (d)

Operátor čárka by měl být vynechán (pravidlo 42–44). Logické operátory (pravidlo 48–53). Některé prefixové operátory (pravidla 76–78). Některé postfixové operátory (pravidla 81–82).

Jinak gramatika v příloze plně odpovídá realitě. 3. V uživatelské manuálu, přiloženém jako příloha k práci, se přeložený překladač nazývá kcc. Jelikož jsem zapomněl výstupní soubor přejmenovat, tak se jmenuje Compiler. Toto je nutné při čtení příkladů v manuálu zohlednit. 4. Přepínače uživatelském manuálu neodpovídají realitě. Pro zjištění správných přepínačů stačí Compiler -h. Navíce již nejsou implementovány pomocí GNU getopt. Význam přepínačů je stejný, ale jejich zápis je jiný. 5. Adresář s uživatelským manuálem je prázdný. Měl vněm být umístěn stejný manuál, jako je přiložen k textu práce.

1

Errata Seznam chyb v projektu bakalářské práce Překladač s optimalizací výsledného kódu, 2013, Petr Krajník Stav objevených chyb z 9. ledna 2013 Zde jsou všechny dosud objevené chyby v překladači. 1. Chybné varování kódu 9 (Použití neinicializované proměnné). Při prvním přiřazení do proměnné je vydáno toto varování. Máme tedy k každé proměnné jedno varování. Způsobeno je to tím, že levá strana přiřazení je vyhodnocena (a vydáno varování), pak teprve se definuje daná proměnná. 2. Při nepoužití nějakého parametru funkce, může dojít k rozhození argumentů. Nepoužitým parametrům nepřiřadí adresa a přiřadí se dalšímu parametru nebo proměnné. Když jsem testoval, tak jsem vždy všechny zavedené parametry použil a neodhalil tento nedostatek. 3. U funkcí s více parametry dochází k obrácení pořadí těchto parametrů. Nečekal jsem totiž, že JVM sama obrátí pořadí parametrů a zadávám je v opačném pořadí. 4. Nejsou implementovány globální proměnné. Při jejich použití je „hozena“ výjimka. 5. Přepínač -c nemá žádný efekt. Existence funkce main se nekontroluje. Chovaní je tedy stejné jako při „zapnutém“ přepínači -c.

2

ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE

Fakulta elektrotechnická Katedra počítačů

BAKALÁŘSKÁ PRÁCE Překladač s optimalizací výsledného kódu Petr Krajník

[email protected], [email protected]

Vedoucí práce: Ing. Ivan Šimeček, Ph.D

Praha zima 2012/2013

Informace o bakalářské práci Titul práce Rok tovrby Počet stránek

Překladač s optimalizací výsledného kódu Zimní semestr akademického roku 2012/2013 xvi + 56

Škola

České vysoké učení technické v Praze Fakulta elektrotechnická Technická 2 166 27 Praha 6

Autor Studijní program Studijní obor

Petr Krajník Elektrotechnika a informatika (bakalářský), strukturovaný Výpočetní technika

Vedoucí práce Oponent

Ing. Ivan Šimeček, Ph.D Mgr. Michal Píše

Sazba textu byla provedena pomocí typografického systému LATEX 2ε . Pro sazbu poděkování bylo použito standardní PostScriptové písmo Zapf Chancery. Všechny ostatní písma použité v této práci jsou z projektu Latin Modern. Písma projektu Latin Modern jsou volně dostupné na .

c 2012 Petr Krajník Copyright

Prohlášení Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon). V Praze dne 4. ledna 2013

Podˇekování Chtˇel bych podˇekovat rodiˇcu˚ m za veškerou podporu pˇri tvorbˇe práce. Dále bych chtˇel také za vše podˇekovat vedoucímu práce. Zejména za trpˇelivost. Podˇekovat bych chtˇel také všem, kteˇrí mˇe podpoˇrili pˇri tvorbˇe této práce.

Abstrakt CZ Překladač s optimalizací výsledného kódu Tato práce se zabývá konstrukcí a implementací kompilačního překladače s optimalizací výstupního kódu. Konkrétně je implementován překladač z zjednodušeného jazyka C do jazyka symbolických instrukcí Java Virtual Machine, který můžeme pak dále zpracovat. Čtenář bude proveden konstrukcí tohoto překladače od návrhu architektury a definice vstupního jazyka, přes přední část, až po zadní část překladače. Popsány veškeré použité metody popř. jejich implementace, které byly při tvorbě použity. Probírána a implementována je také optimalizační část překladače. Těžiště je na systémově nezávislých optimalizacích pro zvýšení rychlosti výsledného kódu. Nejdříve jsou probírány různé metody optimalizací na rychlost, z nichž se zaměříme zejména na optimalizace abstraktního syntaktického stromu, interprocedurální optimalizace a optimalizace přímým vkládáním kódu. Z těchto tří skupin jsou implementovány jejich nejvýznamnější zástupci. Jedná se o spojování konstant, odstranění mrtvého kódu a přímé vkládání funkcí. Výsledkem je překladač s optimalizátorem, který prochází testováním, jehož výsledky jsou k závěru práce zhodnoceny. Klíčová slova: překladač, optimalizace, abstraktní syntaktický strom, JVM, generování kódu, syntaktická analýza, Jasmin, Flex

Abstract EN Optimizing compiler This work describes construction and implementation of a compiler with optimization of the resulting output code. Concretely compiler is implemented as a translator of a simplified C language into Java Virtual Machine assembly language. The reader is guided thru construction of this compiler from architecture design and input language definition, through back-end, to the back-end. Every method resp. her implementation used while creation is described. Also discussed and implemented is the optimization part of the compiler. The focus is on system independent optimization methods for increasing speed of the resulting code. First are discussed different optimization methods for speed, from which we focus on optimization of abstract syntax tree, interprocedural optimization and optimization by code inlining. From these three types the main representative methods are implemented. Implemented methods are constant merging, dead code elimination and function inlining. The result is an optimizing compiler, which will be tested, and the results are evaluated at the end of this work. Key Words: compiler, optimization, abstract syntax tree, JVM, code generation, parsing, Jasmin, Flex ix

x

Obsah Obsah

xi

Seznam obrázků

xv

1 Úvod 1.1 Typy překladačů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Shrnutí úvodu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2 3

2 Teoretické základy 2.1 Grafy . . . . . . . . . . . . . . . . . . . . 2.1.1 Průchod grafu do hloubky . . . . 2.1.2 Stomy . . . . . . . . . . . . . . . 2.2 Formální jazyky . . . . . . . . . . . . . . 2.3 Gramatiky . . . . . . . . . . . . . . . . . 2.3.1 Regulární gramatiky . . . . . . . 2.3.2 Překladové gramatiky . . . . . . 2.3.3 Atributované gramatiky . . . . . Atributy speciálních symbolů . . 2.4 Končené automaty . . . . . . . . . . . . 2.4.1 Regulární výrazy a gramatiky . . 2.5 Zásobníkové automaty . . . . . . . . . . 2.6 Syntaktická analýza . . . . . . . . . . . . 2.6.1 LL(1) syntaktický analyzátor . . Rozkladová tabulka a její návrh . Implementace LL(1) analyzátoru 2.7 Definice programovacího jazyka . . . . .

5 5 5 5 6 6 6 6 6 7 7 7 7 7 8 9 9 9

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . .

3 Řešený problém, cíle, struktura práce 11 3.1 Stanovení cílů . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Struktura práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4 Analýza existujících implementací 4.1 NestedVM . . . . . . . . . . . . . 4.2 LLVM . . . . . . . . . . . . . . . 4.3 C2J . . . . . . . . . . . . . . . . 4.4 Java GCC Backend . . . . . . . . 4.5 Jiná řešení . . . . . . . . . . . . . 4.6 Shrnutí a zhodnocení . . . . . . . 5 Architektura překladače

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

13 13 13 14 14 14 15 17 xi

5.1

5.2

5.3

Části překladače . . . . . . . . . . . . . . 5.1.1 Preprocessing . . . . . . . . . . . . 5.1.2 Přední čast překladače . . . . . . . 5.1.3 Zadní část překladače . . . . . . . . 5.1.4 Postprocessing . . . . . . . . . . . Architektura implementovaného překladače 5.2.1 Řízení překladu . . . . . . . . . . . 5.2.2 Tabulka symbolů . . . . . . . . . . 5.2.3 Průběh překladu . . . . . . . . . . Chybové výstupy a logování . . . . . . . . 5.3.1 Systémové chyby . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

6 Přední část překladače 6.1 Preprocessing . . . . . . . . . . . . . . . . . . . . 6.2 Lexikální analýza . . . . . . . . . . . . . . . . . . 6.2.1 Generátory lexikálních analyzátorů . . . . 6.3 Vnitřní forma . . . . . . . . . . . . . . . . . . . . 6.3.1 Abstraktní syntaktický strom . . . . . . . 6.3.2 Průchod AST . . . . . . . . . . . . . . . . 6.4 Syntaktická analýza . . . . . . . . . . . . . . . . . 6.4.1 Návrh gramatiky . . . . . . . . . . . . . . 6.4.2 Optimalizace gramatiky pro LL(1) analýzu 6.4.3 Zpracování chyb . . . . . . . . . . . . . . . 6.5 Sémantická analýza . . . . . . . . . . . . . . . . . 7 Zadní část překladače 7.1 Optimalizace . . . . . . . . 7.2 Přidělování registrů . . . . . 7.3 Přidělování adres . . . . . . 7.4 Generování výstupního kódu

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

18 18 18 19 19 20 20 21 21 22 22

. . . . . . . . . . .

23 23 23 23 24 24 24 25 25 25 25 25

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

27 27 27 28 28

8 Optimalizace 8.1 Klasifikace optimalizací . . . . . . . . . . . . . . . . 8.1.1 Globální a lokální optimalizace . . . . . . . 8.1.2 Cíle optimalizací . . . . . . . . . . . . . . . 8.1.3 Fáze vykonání optimalizací . . . . . . . . . . 8.1.4 Systémově závislé a nezávislé . . . . . . . . 8.1.5 Grafy toku řízení programu . . . . . . . . . 8.2 Tradiční optimalizační metody . . . . . . . . . . . . 8.3 Optimalizace na abstraktním syntaktickém stromu . 8.3.1 Spojování konstant . . . . . . . . . . . . . . 8.3.2 Přesun invariantu z cyklu . . . . . . . . . . 8.3.3 Odstranění mrtvého kódu . . . . . . . . . . 8.3.4 Hledání společných podstromů . . . . . . . . 8.3.5 Optimalizace matematickými zákony . . . . 8.4 Interprocedurální optimalizace . . . . . . . . . . . . Využití a konstrukce grafu volání . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

31 31 31 32 32 32 32 32 32 33 33 33 34 34 34 34

xii

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

8.5 8.6

8.4.1 Optimalizace použití konstant 8.4.2 Odstranění nevolaných funcí . Optimalizace přímým vkládáním . . . Úvod a rozdělení . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

35 35 35 35

9 Testování

37

Literatura

41

A Použité zkratky 43 A.1 Seznam zkratek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 B Bezkontextová gramatika překladače 45 B.1 Bezkontextová LL(1) gramatika . . . . . . . . . . . . . . . . . . . . . . 45 C Uživatelský manuál překladače C.1 Co všechno pořebujeme . . . . . . . C.2 Instalace a deinstalace . . . . . . . C.3 Přepínače . . . . . . . . . . . . . . C.4 Vstupní soubory . . . . . . . . . . . C.5 Výstupní soubory . . . . . . . . . . C.6 Kompilace . . . . . . . . . . . . . . C.7 Chybové a diagnostické zprávy . . . C.8 Příklady použití . . . . . . . . . . . C.8.1 Použití kódu jako knihovny

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

49 49 49 49 50 50 50 50 51 51

D Obsah přiloženého CD D.1 Volba jména CD . . . D.2 Struktura CD . . . . . D.2.1 Adresář Text . Formáty textu . D.2.2 Adresář Projekt D.3 Další informace . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

53 53 53 54 55 55 56

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

xiii

xiv

Seznam obrázků 5.1 5.2

Obecná architektura překladače. . . . . . . . . . . . . . . . . . . . . . . 17 Architektura implementovaného překladače . . . . . . . . . . . . . . . . 20

6.1 6.2

Diagram dědičnosti příkazů. . . . . . . . . . . . . . . . . . . . . . . . . 24 Diagram dědičnosti výrazů. . . . . . . . . . . . . . . . . . . . . . . . . 24

7.1

Schéma zadní části překladače.

. . . . . . . . . . . . . . . . . . . . . . 28

xv

xvi

Kapitola Úvod

1

Spustitelný program pro určitý počítač se skládá ze zakódovaných instrukcí vykonatelných daným procesorem počítače. Instrukce jsou uloženy, ve většině případů, ve formátu s kterým umí pracovat operační systém. Používaný formát skoro vždy obsahuje mnoho dalších informací, které umožňují efektivní zavedení a spuštění programu operačním systémem. Existuje jen málo formátů, které obsahují jen zakódované instrukce (podle architektury počítače případně také rezervu pro datovou paměť). Příkladem jednoduchého formátu je starší spustitelný formát COM, který obsahuje jen binárně zakódovaný strojový kód. Nicméně pokud chceme psát programy, tak musíme znát veškeré detaily daného systému, pro který program píšeme. Při psaní programů můžeme postupovat několika způsoby. Programy lze psát přímo ve strojovém kódu používaného procesoru (většinou pomocí hexa editoru), pokud jsou programy a formáty spustitelných souborů dosti jednoduché. Zdrojový kód je kódem strojovým. Mimo to, že víme jak vypadá výsledný strojový kód, má tato metoda snad všechny nevýhody, s kterými se jako programátor můžeme setkat. Mezi nevýhody patří špatná čitelnost, veliká náchylnost k zavedení chyb programátorem, špatně se provádějí změny a psaní i jednoduchých programů se tím stává velice náročné. Navíc je potřeba absolutní znalost systému, procesoru, jeho instrukční sady a dalších věcí, bez kterých nebudeme schopni vůbec nějaký program napsat. Výsledný kód bude ještě k tomu vázán na určitou architekturu a nebude přenositelný. Nevýhod je samozřejmě ještě víc. Další, lepší, metodou je použití jazyka symbolických instrukcí pro zápis programu. Zakódování instrukcí a vytvoření spustitelného souboru převezme, k tomu účelu vytvořený, překladač nazývaný assembler. Assemblery mimo překlad můžou ještě před generováním výstupu jemně doladit program pro získání lepšího výsledku nebo nám dát k dispozici důležité diagnostické informace. Nejsou nijak složité a mají poměrné nízké paměťové nároky. Díky tomuto faktu byly realizovatelné pro automatizaci překladu již v počátcích existence počítačů. Odstraněn byl tím problém čitelnosti a nutnosti znát výstupní formáty spustitelných souborů, protože o to se postará assembler. K tomu se musí dodat, že čitelnost stále není nijak úchvatná a nadále zůstává požadována znalost procesoru a jeho instrukční sady. Jelikož existuje hodně procesorů s různými instrukčními sadami a architekturami, tak náš kód bude použitelný jen na určité platformě nebo na nějaké s ní kompatibilní (např. x86). Faktem je, že jedině tímto způsobem jsme schopni využít maximálně prostředků daného počítače. Neztrácíme kontrolu nad tím, co bude počítač dělat. Z tohoto důvodu je psaní programů v assembleru jasnou volbou, pokud požadujeme rychlý kód do detailu odladěný. Většina překladačů překládá do jazyka symbolických 1

Kapitola 1. Úvod instrukcí. Díky tomu bude vždy potřeba existence assemblerů, protože pro nás zaručují „spojení“ s procesorem cílového počítače. Pokud chceme psát přenositelný a čitelný kód, tak je potřeba pro zápis zdrojových kódů použít nějaký vyšší programovací jazyk. Tyto jazyky zavádějí obecné konstrukce (cykly, podprogramy, atd.), na jejichž základě lze pak vygenerovat kód pro určitou platformu. Vyšší programovací jazyky nejsou žádnou novinkou. Již v počátcích počítačů se psaly složitější programy v jazycích vyšších. Zde je nutné dodat, že někdejší vyšší programovací jazyky neměly mnoho společného s těmi co používáme dnes. Zdroje v těchto jazycích byly pak přeloženy do jazyka symbolických instrukcí nebo přímo do strojového kódu. Kódy byly tenkrát překládány ručně. Výsledkem snahy tento proces automatizovat, vznikla disciplína konstrukce překladačů jako podmnožina teoretické informatiky, zabývající tvorbou překladačů a algoritmů s nimi spojenými. Hlavní problémem prvních překladačů (padesátá léta 20. stol.) byl nedostatek paměti, způsobený vyššími paměťovými nároky při zpracováním vyšších programovacích jazyků. Překladače z vyšších jazyků do jazyka symbolických instrukcí nazýváme kompilátory. S nárůstem výkonnosti počítačů a jejich paměti došlo k umožnění vývoje překladačů, ale z důvodů narůstající složitosti vyšších programovacích jazyků přišly jiné problémy s jejich zpracováním. Veliký zájem o překladače přinesl poměrně rychlý nárůst metod a algoritmů, které se i dnes stále při tvorbě překladače používají. V dnešní době tím existuje velké množství léta ověřených algoritmů, které nám umožňují systematicky implementovat překladače. Asi největším problémem u vyšších programovací jazyků je, že schvalují programátorovi zavádění neefektivních operací. To nemusí být dáno neschopností programátora, ale i jazykem samotným, který se vzhledem ke své univerzálnosti musí vyhýbat konkrétnostem cílového jazyka překladače. Výsledkem je neefektivní kód. Odezvou na tento problém byl vznik automatických optimalizátorů. Veliký rozvoj proběhl v sedmdesátých letech 20. století, protože za tuto dobu narostla paměť a výpočetní výkon tak, že umožnil jejich implementaci a vývoj. Optimalizátor je součást překladače snažící se vytvořit co nejkvalitnější kód podle programátorových kritérií. Mezi nejčastější kritéria patří optimalizace na rychlost, nebo na paměťovou efektivitu. Samozřejmě mohou existrovat další nebo jejich kombinace. Všechny historické údaje pochází z [1].

1.1

Typy překladačů

Za dobu vývoje překladačů vznikly jejich různé druhy, které bych zde chtěl stručně popsat. Překladače se dají rozdělit na dvě velké skupiny, podle toho, co je výsledkem jejich provedení. Při následujícím rozdělení jsem se držel terminologie použité v [2]. kompilační překladač – Jedná se o překladače jejichž výsledkem je výstupní kód. Kompilační překladač tedy přijímá zdrojový kód ve zdrojovém jazyce a vytváří výstupní kód v jazyce výstupním, jako výsledek překladu. Vygenerovaný kód jsme pak, po případných úpravách, schopni spustit. Tím dochází k oddělení doby překladu a doby běhu programu. Program spustíme vícekrát než ho kompilujeme. Na tom zakládají optimalizace, protože vícenásobným spouštěním se kvalita výstupního kódu projeví více, než případný delší překlad. 2

Podkapitola 1.2. Shrnutí úvodu interpretační překladač – Zcela se liší od překladačů kompilačních, protože negenerují výstupní kód. Namísto toho přijatý zdrojový kód ve zdrojovém jazyce přeloží tak, že je vykonán, jako kdyby byl spuštěn výstupní kód kompilačního překladače. Překladač interpretuje zdrojový kód. Protože dochází k spouštění programu, tak musíme mimo vstupního kódu připravit také vstupní data. Výstupem je pak výstup vytvořený spuštěním programu. U tohoto překladače se počet spuštění rovná počtu překladů. Tím se optimalizacemi nevyplatí zabývat a předpokládáme, že vstupní kód je již co nejvíce optimální. Mimo tohoto rozdělení můžeme překladače rozdělit podle způsobu komunikace s uživatelem. Překladače nazýváme konverzačními, pokud má uživatel provádějící překlad možnost zasahovat do chodu překladače – konverzovat s ním. Druhým druhem jsou klasické, které nám neumožňují jakýkoli zásah do překladu. Dále existují ještě speciální druhy překladačů jako např. cross-compiler, který překládá pro jinou architekturu než na které běží, nebo různé překladače, které se sami kompilují. Samozřejmě existují i další, ale toto byly ty nejvýznamnější zástupci. Jak vidíme, tak je poměrně veliké množství různých druhů překladačů. V této práci se pojmem překladač myslí klasický kompilační překladač dle definic výše. Ostatními se v této práci nezabývám, protože zde nejsou relevantní.

1.2

Shrnutí úvodu

Pokud chceme realizovat složitější, čitelné a přenositelné programy, tak je musíme napsat nějakém z vyšších programovacích jazyků. Tato souvislost nese s sebou nutnost tvorby kvalitních a efektivně běžících překladačů s optimalizací výstupního kódu. Hlavním cílem práce je ukázat návrhem překladače s optimalizací výstupního kódu a metod použitých při jeho tvorbě. Výsledkem je implementace překladače vytvořeného dle popisu v této práci. Znalost fungování překladače navíc každému programátorovi ve vyšším programovacím jazyce, který je tím vázán na překladač, umožní mnohem lépe řešit případné problémy a chyby při překladu. Z tohoto důvodu by měl každý programátor ve vyšším programovacím jazyce rozumět konstrukci a fungování překladače (nebo alespoň znát základní principy).

3

4

Kapitola Teoretické základy

2

V této kapitole proberu různé definice a zavedení pojmů, které budu požívat dále v textu. Určitě bych tuto kapitolu nebral jako referenci pojmů teoretické informatiky, protože se zde snažím spíš popsat důležité pojmy, které používám v této práci. Pojmy nejsou tedy úplně popsány, ale jen v rámci toho, jak je potřebujeme. Při popisu teorie grafů je použil zejména literaturu [3]. Pro popis všech záležitostí okolo překladačů jsem používal hlavně [2].

2.1

Grafy

Graf definujeme jako trojici (U, H, ̺), kde U je množinou uzlů, H je množinou hran. Zobrazení incidence ̺ nám přiřazuje každé hraně h ∈ H neuspořádanou dvojici [u, v], kde u, v ∈ U. Znamená to, že z u do v vede hrana a obráceně. Definicí incidence jako neuspořádané dvojice jsme získali neorientovaný graf. Orientovaný graf získáme přidáním orientace hranám. To zařídíme změnou zobrazení incidence. U orientovaného grafu změníme definici ̺ na ̺ : h → (u, v). Tím, že jsme přiřadili hraně uspořádanou dvojici, jsme stanovili pořadí kde první je uzel ze kterého hrana vychází a druhý je ten do kterého hrana vede. V tomto případě vede orientovaná hrana z uzlu u do v. Tím jsme získali definici orientovaného grafu.

2.1.1

Průchod grafu do hloubky

Při průchodu do hloubky procházíme uzly grafu dokud můžeme. Potom se vracíme k již komplentě neprojetých uzlů kde provádíme totéž. K uložení informace kam se máme vrátit potřebujeme zásobní.

2.1.2

Stomy

Jedná se speciální formu grafu, ve kterém je |U| − 1 počtem hran. Graf je dále acyklický. Strom obsahuje kořen, do kterého nevstupují žádné hrany a listy, z kterých žádné hrany nevystupují. Můžeme definovat následující průchody jejich struktury. Předpokládejme že máme binární strom s uzlem u, levý a pravý podstrom. Na tom založime popis metod průchodu. Průchod preorder – Nejdříve projdeme uzel u, levý podstrom a pak pravý podstrom. Průchod postorder – Průchod začínáme levým podstromem, pravým podstrom a závěrem navštívíme uzel u. 5

Kapitola 2. Teoretické základy Průchod inorder – Nejdříve projdeme levý podstrom, pak uzel u a závěrem pravý podstrom.

2.2

Formální jazyky

Než definujeme formální jazyky, tak musíme definovat co to je abeceda. Abeceda je nepráznou množinou symbolů. Rětězec nad abecedou je zřetězení posloupnosti sybolů abecedy. Prázdný řetěz označujeme symbolem ε. Formální jazyk je definován jako podmnožina všech řetězů vytvořených na dané abecedě (tedy T ∗ ).

2.3

Gramatiky

Gramatika definována jako uspořádaná čtveřice G = (N, T, P, S), kde N jsou neterminání symboly, T jsou symboly terminální, P jsou pravidla gramatiky a S je počáteční symbol gramatiky. Musí dále platit, že N ∩ T = ∅ a S ∈ N. Pravidla se skládají z levé a pravé strany. Tyto jsou složeny zřetězením symbolů N a T , které budeme označovat řeckými písmeny. Pravidla zapisujeme ve formě α → β, jež tvoří uspořádanou dvojici (α, β) ∈ P . Bezkontextové gramatiky jsou takové gramatiky, které mají pravou stranu pravidla P tvořenou jedním neterminálem. Přímou derivací na gramatice myslíme nahrazení neterminálu pravé strany pravidla pravou stranou s nahrazovaným neterminálem na levé straně. Provádím náhradu náhradu X v α → γXδ, pak ho nahradíme nějakou pravou stranou X → σ na α → γσδ. Zřetězení symbolů γ a δ zde tvoří okolí neterminálu. Konečně ješté zbývá definovat, jaký jazyk nám gramatika generuje. Jazyk generovaný gramatikou je reprezentován množinou L(G) = {x : x ∈ T ∗ ∧ S ⇒∗ x}.

2.3.1

Regulární gramatiky

Regulární gramatiky jsou speciálním případem bezkontextových gramatik. Všechny pravidla gramatiky musí mít tvar A → a, A → aB, kde A, B ∈ N a a ∈ T . Výhodou regulárních gramatik je, že se u nich dá velice jednoduše implementovat syntaktická analýza. Provádíme ji deterministickým automatem, který umíme dobře implementovat. Pravidla A → a nám naznačují přechod ze stavu A do koncového stavu (přijetí automatem), pokud je na vstupu symbol a. Pravidlo A → aB provede přechod automatu ze stavu A do stavu B při přečtení symbolu a na vstupu.

2.3.2

Překladové gramatiky

Překladovou gramatiku získáme přidáním výstupních symbolů do definice obecné gramatiky. Tyto symboly jsou pak umístěny v pravých stranách pravidel a tvoří tím výstup překladače v daném místě. Vytvářejí tím překlad. Takto lze přovádět jednoduché překlady, které jsou syntaxí řízené, generující přímo výstupní kód překladače nebo jiný meziprodukt, který bude dále zpracováván.

2.3.3

Atributované gramatiky

Atributové gramatiky získáme, když terminálům a neterminálům přiřádíme atributy – tedy parametry pro uložení informací. Hlavním významem atributů v gramatice, je zaručení přesunu informací po derivačním stromě. Syntetizované atributy nám zaručují 6

Podkapitola 2.4. Končené automaty přesun informací nahoru. Druhým typem atributů jsou dědičné, které nám umožňují přesun informací směrem dolů po derivačním stromu. Atributy speciálních symbolů Lexikální symboly mají buďto syntetizované atributy nebo žádné. Jelikož se jendá o terminály, tak nemá význam dávat dědičné atributy, protože nic není niž v derivačním stromu než terminály. Příkladem můžou být číslicové literály, které obsahují syntetizovaný atribut s hodnotou vypočítanou při lexikální analýze. Dále můžeme zavést tzv. sémantické neterminály. Tyto neterminály nederivují žádnou pravou stranu, ale provádějí sémantickou akci. Provádí nějakou činnost v libovolném místě pravé strany pravidla. Parametry pro provedení získává jako dědičné atributy. Tím se velice podpobá volání procedury vyššího programovacího jazyka.

2.4

Končené automaty

Konečný automat je definován pěticí (Q, T, δ, q0 , F ), kde Q je množina stavů, T je vstupní abeceda, q0 je počáteční stav a F je množina stavů koncových. Dále platí F ⊆ Q a q0 ∈ Q. Přechodová funkce δ nám přiřazuje každé dvojici (q, t) všechny podmnožiny Q, kde q ∈ Q a t ∈ T . Takto je definovaný nedeterministický konečný automat. Konfiguraci konečného automatu definujeme uspořádanou dvojici (q, t). Konečný automat nazýváme deterministickým, když přechodová funkce přiřazuje dvojici (q, t) jeden nebo žádný stav qx ∈ Q. Takto definovaný konečný automat jsme již schopni implementovat, protože každý přechod automatu je jednoznačný. Navíc se dá každý nedeterministický konečný automat převést na ekvivalentní deterministický [3, str. 178]. Může ale dojít k výraznému zvýšení počtu stavů. Deterministický konečný automat můžeme implementovat pomocí tabulky přechodů, nebo

2.4.1

Regulární výrazy a gramatiky

Regulární výrazy jsou speciálním úsporným jazykem pro zápis předpisů pro syntaxi jazyku bez použití regulárních gramatik. Tyto výrazy můžeme převést na regulární gramatiku. Jelikož víme, že ke každé regulární gramatice existuje deterministický konečný automat a opačně (viz [2, str. 50–53]), tak jsme je schopni efektivně implementovat.

2.5

Zásobníkové automaty

Zásobníkové automaty jsou klasické automaty rozšířené o nekonečný zásobní. Navíc jsou přidány zásobníkové symboly. Nyní záleží přijetí automatem ještě na stavu zásobníku. Abychom jej mohli implementovat, tak musí být deterministický. Příkladem jsou syntaktické analyzátory.

2.6

Syntaktická analýza

Syntaktická analýza nám dává jako výsledek informaci, jestli předložený zdrojový text spadá do množiny všech řetězů, které se dají pomocí gramatiky vytvořit. Testování se provádí na základě sestavení derivačního stromu. Každé pravidlo gramatiky nám

7

Kapitola 2. Teoretické základy popisuje, jak má vypadat uzel a varianty jeho možných potomků (pravé strany pravidel). Pokud se nám povede sestrojit z těchto, gramatikou definovaných, uzlů derivační strom, tak je vstupní text syntakticky správný. V případě, že se nepovedlo derivační strom sestavit, pak analyzovaný vstupní text syntakticky správný není. Vyřešení sestavení derivačního stromu, je úkolem algoritmů syntaktické analýzy. Algoritmy syntaktické analýzy můžeme rozdělit do dvou skupin podle toho, jakým směrem vytváří derivační strom. 1. Top-Down algoritmy sestavují derivační strom od kořene k listům. 2. Bottom-Up algoritmy sestavují derivační strom od spodu k kořeni. Nejvýznamější Bottom-Up algoritmy jsou LR(k), kde k udává počet symbolů, o které nahlíží dopředu, aby se mohl lépe rozhodnout. Tyto analyzátory jsou založené na operacích shift a reduce. Pomocí operací shift se snažíme sestavit na pravou stranu pravidla. Pokud se nám povelo tuto pravou stranu sestavit, tak můžeme rozpoznaou stranu redukovat na levou stranu pravidla. Takto se postupně dopracujeme k tomu, že dostaneme jako výsledek redukce kořen derivačního stromu a zjistili jsme, že syntaxe je správná. LR znamená že čteme vstup zleva (L) a že derivujeme nejpravější derivaci (R). LR analyzátory umí např. rychleji objevit syntaktické chyby a umí pokrýt velký počet různých gramatik, ale mají tu velkou nevýhodu, že již při nevině vypadajících gramatikách je jejich návrh poměrně náročný. Proto se s nimy většinou setkáváme ve spojení s generátory syntaktických analyzátorů. V této práci se dále s nimy nebudu zabývat, protože u implementovaného překladaće je syntaktický analyzátor realizován LL(1), který je nejznámějším zástupcem Top-Down algoritmů syntaktické analýzy. LR analyzátory jsou natlik významné, že jsem se zde o nich chtěl alspoň zmínit.

2.6.1

LL(1) syntaktický analyzátor

LL(1) syntaktický analyzátor je realizován jako zásobníkový automat. Stav je jenom jeden, který je také stavem koncovým. Při přechodech se modifikuje jen obsah zásobníku, jehož obsah rozhoduje o přijetí vstupního řetězu automatem. Zásobníkovou abecedu tvoří terminály a neterminály. Počátečním zásobníkovým symbolem je levá strana, tedy neterminál, počátečního pravidla gramatiky. Náhledový symbol (angl. lookahead) nám reprezentuje první nezpracovaný symbol vstupu. Vstup je zpracováván zleva doprava (první L) a vždy se derivuje nejlevější derivace (druhé L). Náhledový symbol je jeden. Odtud název LL(1). Analýza probíhá tak, že se analyzátor rozhoduje na základě vrcholu zásobníku. Pokud tam je neterminál, tak provedeme expanzi neterminálu, tedy nahradíme symbol neterminálu na vrcholu jeho pravou sranou, kterou vybereme na základě symbolu náhledu. Jinak musí být na zásobníku terminál, který je porovnán s symbolem náhledu. Tuto operaci nazýváme srovnání (angl. match). Po úspěšném srovnání symbol odstraníme z vrcholu. Překlad končí prázdným zásobníkem nebo syntaktickou chybou. Prakticky je funkce analyzátoru založena na průchodu derivačního stromu do hloubky. Pokud se nám povede projít strom, tak půjde i sestavit a syntaxe analyzovaného vstupu, definovaná gramatikou, tím bude správná. Procházení vstupního textu je zařizeno směrem čtení vstupního řetězu. Vždy se provádí nejlevější derivace, protože pokud dojde k expanzi, tak se expanduje neterminál na vrcholu zásobníku, 8

Podkapitola 2.7. Definice programovacího jazyka K syntaktické chybě může dojít při srovnání s odlišným symbolem než je na vrcholu, nebo pokud při expanzi nelze vybrat pravou stranu pro doplnění. Syntaktický analyzátor nemůže dále pokračovat. Pak záleží na tom, jestli je implementováno zotavení z syntaktických chyb. Analyzátor se může pokusit chybu opravit, nebo jistou část vstupu přeskočit a zkusit pokračovat dál v analýze. Rozkladová tabulka a její návrh LL(1) analyzátory pokrývají podmnožinu bezkontextových gramatik. Z toho důvodu musíme vždy rozhodnout, jestli z dané gramatiky půjde tento typ analyzátoru zkonstruovat. Oproti LR analyzátorů je tato podmnožina gramatik, ze kterých se dá realizovat LL(1) analyzátor, opravdu malá. Aby byl LL(1) analyzátor z dané gramatiky realizovatelný, tak musí být splněny následující vlastnosti. 1. Všechny pravé strany jednoho pravidla musí mít různé množiny first. 2. Pokud pravidlo může skončit derivací prázného řetězce, pak je nutné, aby platilo 3. Pravidla gramatiky nesmí obsahovat pravou rekurzi. První dvě pravidla slouží pro výběr správné pravé strany pro expanzi, na základě náhledového symbolu. Třetí pravidlo by způsobilo zacyklení analyzátoru, protože by se stále snažil expandovat neterminál, který by znovu expandoval na sám sebe. Implementace LL(1) analyzátoru Jelikož se jedná o implementaci zásobníkového automatu, tak musíme rozhodnout, jak zásobník implementujeme. Můžeme použít zásobník volání programu nebo explicitní zásobník, realizovaný dle vlastních požadavků. Podle implementace zásobníku získáváme dvě hlavní metody implementace LL(1) analyzátoru. 1. Rekurzivní sestup. Používá se implementace programového zásobníku volání. Neterminály jsou reprezentovány podprogramy a v jejich těle je zakódován právě jeden řádek rozkladové tabulky. 2. Tabulková implementace. Uživaný zásobník je explicitní. Rozkladová tabulka je většinou realizována pomocí polí. U obou implementací si navíc musíme pamatovat náhledový symbol.

2.7

Definice programovacího jazyka

Pro definici jazyka potřebujeme nejdříve vědět, jak má daný jazyk vypadat. Musíme tedy popsat jeho syntaxi. Jak již víme, tak nejlepší je syntaxi popsat pomocí bezkontextových gramatik, protože pro ty máme již efektivní algoritmy pro provedení syntaktické analýzy. Musíme tedy navrhnout bezkontextovou gramatiku, pokud možno hned upravenou pro používaný algoritmus syntaktické analýzy. Následkem použití bezkontextových gramatik je, že ztrácíme kontrolu kontexových podmínek, které nejsou tímto druhem gramatik zachtitelné. Pro přidání kontextové kontroly zavádíme tzv. statickou sémantiku. Statická sématnika nám popisuje kontextové podmínky, které musí být splněny pro správnost vstupního jazyka. Kontrola 9

Kapitola 2. Teoretické základy se většinou provádí při syntaktické analýze. Příkladem může být např. preinkrement operátor ++ v jazyce C. Ve staticke sémantice se musí zaručit, že za operátorem musí být identifikátor proměnné. Nyní již zbývá jen popsat dynamickou sémantiku. Dynamická sémantika ná popisuje, jaký je význam jednotlivých konstruktů, které lze vytvořit na základě gramatiky jazyka. Slouží proto, aby jsme věděli, co bude daný výraz dělat. Někdy také bývá uvolněna obecnější gramatika, která popisuje nadmnožinu definovaného jazyka. Detaily ztracené tímto zobecněním, jsou pak dolpněna do seznamu pravidel statické sémantiky. Tím jsme zachovali správnost definice jazyka, která by jinak byla narušena. Můžeme tedy přesunou některé detaily do vyhodnocení sémantiky, ze které se syntaktický analyzátor lépe zotavuje, než ze syntaktických chyb. Podle této sekce byl navrhnut jazyk implementovaného překladače. Gramatiku, statickou sémantiku a dynamickou sémantiku najdete v příloze ??. Navíc tam najdete definici tokenů lexikálního analyzátoru.

10

Kapitola Řešený problém, cíle, struktura práce

3

Práce řeší návrh a implementaci překladače s optimalizátorem, používajícího v zadání vypíchnuté optimalizační metody. To, jaký bude vstupní jazyk a další detaily jsou na autorovi resp. na tom, jak se s vedoucím práce domluvíme. Jako vstupní jazyk jsem zvolil zjednodušený jazyk C, který je velice rozšířen. Navíc patří spolu s C++ k mým oblíbeným programovacím jazykům. Zjednodušení bylo nutné, protože implementace kompletního překladače jazyka C v plné formě by nebylo stihnutelné. Hlavní složitost je způsobená velikou rozmanitostí datových typů, převodů mezi sebou a jejich zavádění (deklarace, definice). Existoje veliké množství jazyků, jejichž základ tvoří syntaxe jazyka C. Příklady jsou např. Java, C#, atd. I když jsou tyto jazyky poměrně rozdílné, tak je zachována základní syntaxe a filozofie jazyka C. Důsledek toho je, že každý kdo zná nějaký z těchto jazyků, bude rozumět, nebo bude mít alespoň tušení, co bude program dělat. Tím, že jazyky založené na jazyce C jsou velice rozšířené, bude také mnoho lidí rozumět vstupnímu jazyku.

3.1

Stanovení cílů

Proto, abychom věděli jaké jsou hlavní cíle. Splnění těchto cílů, je zhodnoceno v závěru. Následující cíle shrnují požadavky a cíle, které vyplývají z zadání práce nebo z mých požadavků. Stěžejními cíly je: C1. Implementovat překladač z zjednodušeného jazyka C do jazyka symbolických instrukcí Java Virtual Machine. C2. Implementovat optimalizaci spojováním konstant. C3. Implementovat optimlizaci odstraněním mrtvého kódu. C4. Implementovat optimalizaci přímým vkládáním funkcí na základě interprocedurální analýzy. C5. Provést testy překladače a implementovaných optimalizací. C6. Porovnat vliv optimalizací na výslednou rychlost programu. C7. Výše uvedené cíle se snažit splnit co nejkvalitněji (v rámci možností). Nyní by chtělo specifikovat další požadavky, které by měly být splněny při realizaci výše vytyčených cílů. Požadavky se rozdělují na funkční, tedy ty kterou souvisí funkcionalitou projektu a nefunční, které specifikují ostatní požadavky na projekt. Toto 11

Kapitola 3. Řešený problém, cíle, struktura práce rozdělení jsem zvolil, protože se běžně používá v softwarovém inženýrství. V seznamu je typ poznamenán v závorce za popisem požadavku. Požadavky jsou: P1. Zkompilovaný program by měl být spustitelný a použitelný stejným způsobem, jako kdyby byl přeložen překladačem javac . (funkční) P2. Uživatel může rozhodnout, jaké optimalizace chce provést. (funkční) P3. Zkompilovaný kód by měl bý použitelný jako knihovna. (nefunkční) P4. Kód překladače by měl být napsán co nejelegantněji a nejefektivněji. (nefunkční) U posledního požadavku PP4.. bude sice těžké dokázat jeho splnění, protože existuje vždy více řešení a ne vždy je zcela jasné jaká bude výsledně lepší. Navíc každé řešení je jistým způsobem kompromisem. Z toho důvodu by chtělo tento požadavek brát spíše jako ideál, kterému se budeme snažit co nejvíce přiblížit. Jak vidíme ze seznamu požadavků, tak obsahuje jen jeden funční požadavek. Funční požadavky totiž souvisejí s případy užití (angl. Use Case), kterè jsou v případě tohoto projektu velice jednoduché. Máme jen jednoho aktéra (uživale), který může provádět jen překlad resp. překlad částečně ovlivnit (zapnutí optimalizací, atd.). Z toho důvodu nemá cenu vytvářet digram případu užití, jelikož je tak jednoduchý a jasný.

3.2

Struktura práce

Práce by se dala rozdělit na několik hlavních částí. Číslování v seznamu neodpovídá číslování kapitol nebo jiných objektů práce. 1. Úvodní část Práce začíná kapitolou Úvod, ve které popisujeme opodstatnění tvorby překladačů a proč je dobré znát jejich konstrukci. Řeší se potřeba optimalizátorů, rozdělení typů překladačů a také stručné popisy historického pozadí. Poté následuje kapitola Teoretické základy, kde budou zavedeny všechny pojmy používané v práci. 2. Analytická část Třetí kapitolou je tato, a popisuje řešený problém (rozhodnutí) tak, že čtenář by měl vědět co se bude dělat. Dále jsou zde specifikovány cíle, jejichž splnění je cílem práce. Následuje popis rozdělení práce. Čtvrtá kapitola popisuje srovnání již existujících implementací, jako inspiraci nebo výchozí bod pro vlastní řešení. 3. Implementační část Popis implementace je probírán v kapitolách Architektura překladaće, Pŕední část a zadní část. Popsáno je, jak byla vyřešena implementace navržená v předchozích částech práce. 4. Testováni Celé testování a jeho metodika je popsána v kapitole Test. 5. Závěr 6. Přílohy Struktura práce odpovídá doporučené struktuře implementační bakalářské práce uvedené na informačních stránkach katedry počítačů. 12

Kapitola Analýza existujících implementací

4

V této kapitole bych chtěl probrat existující projekty a metody pro řešení překladu z nějakého zdrojového jazyka do bytekódu Java Virtual Machine. Některé probírané postupy jsou platné nejen pro JVM, ale i pro další výstupní jazyky a formáty. Jelikož doprovodný program je překladač jazyka C, tak se zaměřím zejména na realizace překladačů jazyka C. Těžištěm je seznámit čtenáře s existujícími projekty, které řeší zhruba stejný problém jako tato práce. Veškeré informace jsem získal z Wikipedie [4] nebo z domovských stránek příslušných projektů. Projekty budou popsány jen velice stručně s vypíchnutím jejich výhod a nevýhod. Důvodem tohoto pojetí je, že s projekty jako LLVM by se dala napsat celá další práce nebo dokonce rozsáhlejší kniha.

4.1

NestedVM

NestedVM [5] je nástroj, který umožňuje konverzi zkompilovaného kódu pro MIPS přeložit do bytekódu pro JVM. Nejdříve se provede kompilace zdrojových kódů pomocí GCC do MIPS binárky. Tato binárka je následně přeložena do bytekódu Java Virtual Machine. NestedVM je opensource software šířený pod Apache 2.0 licencí. Výhodou je, že můžeme překládat zdrojové kódy všech jazyků, které jsou podporovány překladačem pro překlad do binárky MIPS. Další výhodou je, že můžeme využívat všech možností daného překladače. NestedVM je pracuje s překladačem GCC 3.3.6. Nevýhoda je v tom, že není podpora novějších verzí GCC.

4.2

LLVM

LLVM [6] je celá infrastruktura pro implementaci překladačů. Převzaty jsou GCC frontendy a je k dispozici široký výběr doplňků, které můžeme využít pro vývoj vlastních překladačů. Celý systém LLVM je založen na jazyce virtuálního počítače LLVM IR (LLVM Internal Representation). Tento jazyk je velice dobře navrhnutý a optimalizovatelný. Je velice podobný n-adresovému kódu. Jazyk LLVM IR je přeložitelný do jiných jazyků jako např. Jasmin. LLVM IR je buďto spustitelný interpretem LLVM, nebo přeložitelný do nativního kódu počítače, na kterém je překládáno. Toto je umožněno, protože interpret LLVM při spuštění programu provede JIT kompilaci. Tedy přeloží LLVM IR do nativního kódu počítače na němž je spuštěn. 13

Kapitola 4. Analýza existujících implementací LLVM je překladačem a interpretem. Navíc ještě umožňuje jednoduché použití jeho součástí ve vlastních překladačích. Pokud tedy potřebujeme vytvořit nějaký překladač, tak můžeme jen napsat přední část generující jako vnitřní formu jazyk LLVM IR. Zbytek bychom přenechali zadní části, která je velice kvalitní. Testy na [6] ukázaly, že optimalizátor je tak kvalitní, že v testech silně poráží implementaci překladače GCC při stejných optimalizacích. Výhodou je široká nabídka různých kvalitních součástí, které můžeme použít při vlastním vývoji překladače. Projekt a jeho součásti jsou velice dobře dokumentovány. Nevýhodou může být pro začátečníka proniknutí masou nástrojů, modulů a možností.

4.3

C2J

C2J [7] je projekt, který realizuje překlad z jazyka C do jazyka Java. Projekt je založen na překladači GCC. Překladačem je nejdříve je generován javovský kód, pak je teprve z něho vygenerová bytekód pro JVM. V podstatě se provádí klasický překlad mezi dvěma jazyky, následovaný kompilací výsledného kódu. Výsledný bytekód je uložen do *.class souboru. Překladač plně podporuje ANSI C knihovnu, ANSI C a K&R C. Tato dobrá podpora je asi největší výhodou tohoto projektu.

4.4

Java GCC Backend

Java GCC Backend [8] je projekt implementující zadní část překladače GCC pro překlad do jazyka symbolických instrukcí Jasmin. Assembler jasmin vygeneruje výsledný spustitelný program pro JVM. Projekt je nejstarším pokusem o překlad jazyka C do Java bytekódu. Jde tedy jen o rozšíření překladače GCC. Výhodou je, že se práce s takovým překladačem vůbec neliší od standardní práce s GCC. Využitím předních částí GCC, rozumí takto vytvořený překladač všem jazyků, kterým rozumí GCC. Můžeme používat všechny možnosti kompilátoru GCC, i když některé možnosti nebude možno používat, protože nedávají pro danou situaci smysl. Navíc se dosahuje podle [8] docela dobrých výsledků s přeloženým kódem.

4.5

Jiná řešení

Pokud chceme překládat z nějakého nestandardního jazyka, nebo jeho podmnožiny, tak jsme nuceni si vytvořit specializovanou přední část překladače. Pokud chceme ještě nějaké speciality v zadní části, tak si musíme ji napsat také sami. Většinou necháme zadní část překladače generovat zdrojový kód v jazyce symbolických adres pro architekturu, pro kterou překládáme. Máme k dispozici hned několik assemblerů, které se nabízí pro sestavení výsledného spustitelného souboru. O tento typ překladače se jedná i doprovodného projektu této práce. Překládá se z podmnožiny jazyka C do java assembleru Jasmin. Assembler jasmin nám pak přeloží do java bytekódu.

14

Podkapitola 4.6. Shrnutí a zhodnocení

4.6

Shrnutí a zhodnocení

Pokud potřebujeme překládat z nějakého standardního jazyka v jeho plném rozsahu, tak se vyplatí použít nějaký z výše uvedených projektů. Nejspíš bych si v takovém případě vybral projekt LLVM, do kterého se dobře zasahuje a má dobrou dokumentaci. Když chceme implementovat nějaký nestadardní jazyk tak musíme si překladač, nebo jeho část napsat sami. Použít se dá také některých nástrojů z výše uvedených projektů.

15

16

Kapitola Architektura překladače

5

Každý překladač se většinou skládá ze čtyrech základních částí. Tyto části příjímají určitý vstup v jisté formě, formátovaný dle pevně daných pravidel, na jehož základě daná část provádí svou činnost. Výsledkem chodu dané části je výstup, který byl vytvořen operacemi na základě vstupních dat této části. Výstup je pak buďto dále zpracován následující částí, nebo pokud se jedná o poslední část, již výsledným překladem. Obecná architektura překladače je znázorněna na obrázku 5.1.

Obrázek 5.1: Obecná architektura překladače. Šipky nám ukazjí směr toku dat mezi jednotlivými částmi. Pokud dojde k vynechání části, tak je chování takové, že to co dostává na vstup jen přeposílá na výstup pro zpracování dalšími. Jakou formou tok informací probíhá záleží na tom, jakým způsobem jsou realizovány jednotlivé části. Formou můžou být soubory, pipy, fronty nebo jiné datové struktury, pomocí kterých se dá výstup předat tak, aby bylo možné tyto data co nejefektivněji zpracovat v další části. Detialy k realizaci jednotlivých částí bude v následující sekci 5.1. Asi nejproblematičtější je přesun informací z části preprocessingu do přední časti překladače, protože může být zatížen poměrně velkým počtem chyb – jak syntaktických, tak sémantických. Přední část se musí s těmito možnými nesrovnalostmi vstupu vyrovnat a dát programátorovi co nejpřesnější popis, pokud možno všech, chyb. Navíc po provedení části preprocessingu se znemožní přesné mapování symbolů vstupu přední části a symboly zdrojového souboru. Důvodem jsou změny zdrojového kódu preprocessorem, který jej může změnit k nepoznání. Ten samý problém se nastává u varování, které jsou stejného charakteru. 17

Kapitola 5. Architektura překladače Tyto problémy u ostatních toků dat nenastávají, protože se předpokládá, že budou obsahově koretní. Je to důsledek řetezcového propojení jednotlivých částí architektury. Pokud dojde k zjištění nějaké chyby vstupu přední části, tak se nebude výstup posílat dalším částem řetězu zpracování. Chyba znemožní sestavení dat pro další část a neumožní tím běh všech následujících částí. Překlad pak končí s chybou. Samozřejmě, že ne všechny části jsou součástí každého překladače, ale převážná většina překladačů obsahuje alespoň ty části, kterou jsou ve schématu orámové plnou tlustou čarou. Zejména je tím myšlena část první a poslední, jejichž provedení může být volitelné – proto jsou orámovány šrafovaně. Také je nutné říci, že u složitějších překladačů se tomuto rozdělení prostě nevyhneme. Znázorněné rozdělení potvrzuje většina dnešních překladačů, které obsahují v jisté podobě všechny tyto části.

5.1

Části překladače

Rozdělení překladače do několika částí má mnoho výhod. Části jsou na pracují na sobě relativně nezávisle a umožnují tím dekompozici problému překladu na několik dílčích částí. Tím se při vývoji můžeme soustředit na danou část, což vede k zlepšení kvality a čitelnosti zdrojového kódu překladače. Dále se tím také zlepší rozšiřitelnost, protože stačí je rozšiřovat nebo nahrazovat je jednu dílčí část. I přes toto rozdělení mohou být části Co se týče implementace jednotlivých částí, tak může být velice různorodá. Někdy bývají všechny části schované v jednom programu jako jeho moduly, jindy jsou části paralelně běžící procesy, které jsou synchonizovány vstupem předchozí části.

5.1.1

Preprocessing

Preprocessing, nebo-li volně přeloženo předpřípravná, je částí, ve které se provádí transformace na zdrojovém kódu pro překladač. Transformace mohou být provedeny různými separátními programy resp. skripty nebo mohou být přímo zabudovány do překladače. Důležité je, že výsledkem této části je připravený vstup, který je zpracovatelný přední částí překladače. Tím bezkonflikně můžeme rozšířit libovolný jazyk, bez zásahu do jeho překladače. Velikou výhodou tohoto přístupu je, že takto rozšířené jazyky jsou kompatibilní se všemi překladači pro daný jazyk. Typickým příkladem překladače používající tuto fázi je překladač jazyka C resp. ++ C . Preprocessor jazyka C vkládá soubory, spravuje a expanduje makra, řídí podmíněný překlad, atd. Dalším příkladem je framework Qt, který před vlastním překladem provede speciální překompilátor – Meta Object Compiler. Ten zaručí převod specifik používaných v Qtdo standardního jazyka C++, který je pak již přeložitelný programátorovým oblíbeným překladačem. Pokud provádíme tuto fázi ručně, tak si musíme dát pozor, abychom nezavlekli další chyby do zdrojového kódu. Při chybách v zdrojovém kódu nám v závislosti na závažnosti změn v předpřípravě může dojít k ztrátě lokalizace chyb. Tyto chyby je pak velice těžké vystopovat.

5.1.2

Přední čast překladače

Přední čast, nebo anglicky frontend, zpracovává zdrojový text a generuje vnitřní formu IR pro zadní čast překladače. Vnitřní formou může být abstraktní syntaktický strom, n-adresový kód nebo jiný vnitřní jazyk, který pak bude dobře optimalizovatelný a bude se z něj dobře generovat výstupní kód. 18

Podkapitola 5.1. Části překladače V přední časti překladače se provádí nejen samotné vygenerování vnitřní formy, ale kontroluje správnost (syntaxe, sémantika) k překladu předloženého kódu. Spravují se deklarace a definice proměnných, funcí a další důležité věci. Přední část také spravuje chyby a řeší případné zotavení z nich pro umožnění dalšího běhu překladače. Snaží se také varovat uživatele na případné problémy, které při běhu byly zjištěny. Pokud proběhne bez chyb přední část, tak nám dává k dispozici správnou vnitřní formu odpovídající zdrojovému kódu. Jednotlivé proměnné, funkce, adt. jsou spravovány v datové struktuře, která se nazývá tabulka symbolů. Většinou se jedná o tabulku jejímž klíče je řetězec s jménem daného symbolu, pomocí kterého je schopná velice rychle vyhledat záznam odpovídajícího symbolu. Nejčastěji se pro tento účel používají hashovací tabulky. Na rozdíl od zadní části, je většinou přední část stejná pro všechny druhy cílových počítačů. Z toho vyplývá jedna veliká výhoda, že pro daný vstupní jazyk stačí jednou napsat přední část, která se již ve vývoji překladače nemění. Pokud chceme, aby překladač rozuměl více jazykům, tak stačí napsat pro každý z nich přední část, která generuje stejnou vnitřní formu jako ostatní, aby byla zpracovatelná zadní částí.

5.1.3

Zadní část překladače

Zadní část, anglicky bakcend, přijímá vnitřní formu IR vygenerovanou přední částí a generuje kód pro zvolenou architekturu a typ cílového počítače. Před tím, než se generuje výstup na základě vnitřní formy, tak se musí provést optimalizace. Optimalizátor je většinou součástí zadní části. Optimalizace nám provedou transformace na vnitřní formě tak, aby z ní šel vygenerovat co nejoptimálnější výstup. Nejdříve se provedou optimalizace nezávislé na cílovém počítači, které můžeme provés vždy – platformě nezávislé. Potom přijde na specifické optimalizace pro daný počítač a potom případně program optimalizujeme dle specifik operačního systému, pro který je program generován. Pak se teprve začne generovat výstup. Zadní čast může obsahovat větší počet generátorů výstupu, abychom mohli případně rozšířit překladač o další cílové počítače. Na základě uživatelova rozhodnutí se zvolí příslušný generátor výstupu. Velikou výhodou je, že můžeme takto rozšířit překladač v případě potřeby. Stačí napsat generátor výstupu a platformě specifický optimalizátor. Pokud navíc genrujeme výstup v jazyce symbolických instrukcí, což většina složitějších překladačů dělá, tak nám odpadne řešení specifik generovaní strojového kódu pro daný počítač a řešení formátů spustitelných programů. To za nás vyřeší následné spuštěný assembler.

5.1.4

Postprocessing

Postprocessing je poslední částí řetezu překladače. Tato část je užitečná, pokud ná překladač negeneruje přímo výstupní kód, ale je nutné ho ještě dodatečně zpracovat, abychom získali spustitelný program. Zadní části kompilátorů často generují program v jazyce symbolických adres pro zvolenou architekturu cílového počítače. Spoléhá se totiž na to, že výstup bude dále zpracován assemblerem popř. dalšími nástroji pro vytvoření spustitelného programu. Typickým příkladem je překladač GCC. Výstup zadní časti tohoto překladače je GNU Assembler, který je zpracová assemblerem gas jehož výsledkem je objektový soubor. Objektový soubor obsahuje výstup assembleru a čeká na další

19

Kapitola 5. Architektura překladače zpracování. Tyto soubory budou spojeny pomocí linkeru link , který je spojí dohoromady, vyřesí všechny závislosti a vygeneruje spustitelný program. Operace jsou prováděny pomocí příslušných programů nebo přes GCC. Všechny popsané operace jsou součástí postprocessingu.

5.2

Architektura implementovaného překladače

V předchozích sekcích jsme si popsali obecnou architekturu a nyní dojde na konkrétní. Vynechal jsem preprocessing tak, že přední čast přijímá zdrojový kód ze standardního vstupu, nebo je čten ze souboru jehož cesta je zadána jako argument příkazové řádky. Na obrázku 5.2 je znázorněno schéma architektury tohoto překladače.

Obrázek 5.2: Architektura implementovaného překladače s vyznačením vstupních výstupních souborů. Přední a zadní části jsou věnované zvláštní kapitoly, takže je na tomto místě proberu je nebudu probírat.

5.2.1

Řízení překladu

Veškerá činnost překladače, až na zpracování argumentů příkazové řádky, je řízena speciálním kódem. Po zpracování argumentů příkazové řáky je řízení této části předáno a do konce běhu programu rozhoduje, co se bude dělat. Veškerá komunikace s uživatelem probíhá přes řadič. Řadič nám zaručí, jak a kam budou poslány výpisy o chybách, varování a dalších informacích o průběhu překladu. Pokud např. dojde k syntaktické chybě, tak se pošle řadiči informace 20

Podkapitola 5.2. Architektura implementovaného překladače o chybě, ten ji vypíše a zachová se podle závažnosti chyby. V nejhorším případě to znamená ukončení překladu. V řadiči sídlí také tabulka symbolů, protože je používána v přední i zadní části překladače. Po provedení přední části, je tabulka symbolů naplněna globálně definovanými nebo deklarovanými symboly. Zadní část ji potřebuje, aby věděla jaké funkce a globální proměnné jsou přítomny. Další detaily o tabulce symbolů jsou v následující sekci ??. Řadič překladu je relaizován třídou TransDriver. Nutným požadavkem bylo, aby instance této třídy byla dostupná ze všech míst v překladači kde je k ní potřeba přístupu. Jedním možným řešením by bylo předávat ostatním třídám referenci nebo ukazatel na danou instaci řadiče. Toto řešení je pracné a neefektivní, stejně jako použití globálního objektu, který sice vychází trochu lépe, ale pořád to není to pravé. Na základě toho, že řadič bude jen jeden, tak jsem se rozhodl jej implementovat návrhovým vzorem singleton nebo-li jedináček. Pomocí statické metody getInstance máme přístup k této instanci v libovolném místě programu. Dále používám líné inicializace tak, že se řadič inicializuje až v momentě, když je potřebován. Tím jsou splněny všechny požadavky.

5.2.2

Tabulka symbolů

Tabulka symbolů slouží pro správu deklarací a definic symbolů v průběhu překladu. Umožňuje přístup k sybolům, které jsou v daném okamžiku definovány nebo alespoň deklarovány. Největší počet změn a přístupů je při provádění přední části překladače. Tabulku symbolů jsem rozdělil na dvě části. První je tabulka funckcí, ve které se spravují veškeré záležitosti okolo funkcí. Každé jméno v tabulce má právě jeden záznam. Není tedy možné přetěžování funkcí, které by tuto vlastnost vyžadovalo. Rozdělením získáváme heterogení tabulky, které se lépe implementují a navíc můžou mít proměnné stejné názvy jako funkce. O tom, jestli se jedná o funkci nebo proměnnou se rozhodne na základě syntaxe. To také určí, ve které tabulce se bude hledat. Tabulky jsou implementovány pomocí standardních hashovacích tabulek z TR1. TR1 je nutné, abychom nebyli závislí na nejnovější normě jazyka C++.

5.2.3

Průběh překladu

V této sekci bych chtěl jen stručně naznačit průběh překladu s touto architekturou. To pomůže lépe pochopit, jak jednotlivé části do sebe zapadají. Přečteme zdrojový kód ze souboru nebo ze standardního vstupu. Přední část přijímá připravený vstup a spouští syntaktickou a sémantickou analýzu. Přitom generuje vnitřní formu pro další část. Pokud pokud nebyla nelezena nějaká chyba při zpracování, tak můžeme poslat vnitřní formu zadní části překladače. Při nalezení chyby s překladem nelze pokračovat a končíme. Předpokládejme, že přední část překladače proběhla bez chyby. Nejdříve zadní čast optimalizuje vnitřní formu tak, aby s ní bylo možné vytvořit co nejlepší výstupní kód. Pak dojde na samotné generování kódu. Pokud je posprocessingová část vynechána, pak jsme hotovi. Pokud ne, tak ještě zpracujeme výsledný kód.

21

Kapitola 5. Architektura překladače

5.3

Chybové výstupy a logování

Jak již bylo řečeno, tak veškeré výstupy překladače má na starosti řadič. Pokud na nějakém místě překladu dojde k chybě (varování), která není systémová, tak stačí zavolat členskou metodu řadiče error (warning). Řadič zaručí výpis daných chyb. Aby hned uživatel věděl, jestli došlo k nějakým chybám nebo varováním, tak jsou tyto vypisovány do konzole, ze které byl překladač spuštěn. Chyby jsou vypsány na standardní chybový výstup a varování na standardní výstup. Po skončení se v konzoli vypíše ještě výsledek překladu s celkovým počtem chyb a varování. To je vše čím překladač obtěžuje uživatele při běhu. V ideálním případě, žádné chyby, žádné varování, vypíše jen že překlad proběhl úspěšně. Aby byl záznam o tom, jak byl program přeložen, tak jsem se rozhodl ke každému překladu generovat logovací soubor, do kterého se budou poznamenávat všechno o průběhu překladu. Mimo chybové a varovné zprávy se zaznamenávají nastavení, datum a čas spuštění a ukončení překladu, doba překladu, verze překladače, atd. Dobré je to, že k nejaktuálnějšímu překladu máme vždy „report“ o tom, jak byl přeložen. Případně můžeme daný soubor zálohovat. Existence tohoto rozsáhlého výpisu umožnila tak úsporný výpis do konzole, protože bez logovacího souboru bychom museli vše zapisovat do konzole. Při překompilování je tento soubor přepsán novým.

5.3.1

Systémové chyby

Při běhu překladače se může stát, že budeme chtít něco, co nám operačním systém, na kterém překladač běží, nebude schopen splnit. Při překladu se tvoří datové struktury dynamickou alokací, kde je možnost, že žádaný objem paměti nedostaneme. Nebo při čtení souborů může dojít k různým chybám. V takovém případě s vypíše chybové hlášení do konzole a překladač okamžitě končí svou činnost. Toto jsou chyby, které nijak nejsme schopni ovlivnit.

22

Kapitola Přední část překladače

6

Jak jsme si již řekli v předchozích kapitolách, tak se přední část provádí syntaktickou a sémantickou analýzu. Implementace této části překladače bude popsána v této kapitole.

6.1

Preprocessing

V této implementaci překladače je preprocessing volitelný. Pokud dojde k předzpracování nějakým programem, tak dojde k tomu, že ztratíme lokační údaje o chybách. Přesto má své místo a opodstatnění. Většinou ho ale nepoužívám.

6.2

Lexikální analýza

Lexikální analýza nám enormně usnadňuje implementaci syntaktického analyzátoru. Nemusíme totiž realizovat rozpoznání lexikálních elementů, tokenů, při běhu syntaktické analýzy, která bývá poměrně složitá. Mimo to, můžeme provést další operace jako vyčíslení číslicových literálů atd. Lexikální elementy jsou specifikovány regulární gramatikou resp. reg. výrazem. Můžeme je tedy implementovat pomocí deterministického konečné automatu, popsaného v teoretické části. Problém je v tom, že metody implementace složitých automatů jsou poměrně nepřehledné. U složitějších jazyků dostáváme minimalizovaný automat se stovky stavů. Implementovat ho ručně je prostě neefektivní. Použijeme nějaký generátor.

6.2.1

Generátory lexikálních analyzátorů

Generátory lexikálních analyzátorů jsou velice rozšířeny a oblíbeny. Dělí se na tabulkově řízené a bez tabulky. Rozdělení určuje implementaci automatu a tím i dynamické parametry lexeru. Velikou výhodou je jednoduchost, která nám zaručí poměrně jednoduše implementovat libovolně složitý lexer. Co se týče výkonnosti, tak jsou na tom beztabulkové generátory trochu lépe. Nejlepším příkladem je generátor Quex, který generuje velice kvalitní kód. Bohužel jsem s ním měl velice špatné zkušenosti avzdal jsem jeho použití, protože s ním bylo více práce než bych uspořil. Rozhodnutí pak padlo na tabulkově řízený generátor flex [? ]. S ním fungovalo všech hned a bez problémů.

23

Kapitola 6. Přední část překladače

6.3

Vnitřní forma

Vnitřní forma je datovou strukturou vyjadřující transformovanou formu vstupního kódu. Slouží hlavně pro zjednodušení zpracování a předávání informací mezi částmi. Můžeme je rozdělit na implicitní a explicitní. Implicitní je např. derivační strom, který nikde v paměti není, ale je používán syntaktickým analyzátorem. Explicitní je např. abstraktní syntaktický strom.

6.3.1

Abstraktní syntaktický strom

Jako explicitní vnitřní forma překladače byl zvolen abstraktní syntaktický strom (dále jen AST). Jedná se dynamicky alokovanou datovou spojovou hierarchickou strukturu, ve ve které jsou jednotlivé elementy programu zaznamenány uzly. Máme základní dva druhy uzlů. První je výrazový, který odpovídá výrazům daného jazyka. Druhým je příkazový, který realizuje jednotlivé příkazy jazyka. Diagramy dědičnosti jsou na následujících obrázcích.

Obrázek 6.1: Diagram dědičnosti příkazů.

Obrázek 6.2: Diagram dědičnosti výrazů.

6.3.2

Průchod AST

Aby se dal efektivně realizovat průchod této struktury, tak jsem je realizoval návrhovým vzorem Visitor. Každému uzlu je přidána metoda virtual void prijmi( Visitor& );. Visitor řeší průchod jednotlivými uzly. Díky polymorfismu při předávání 24

Podkapitola 6.4. Syntaktická analýza reference získáme možnost předat jakéhokoli potomka třídy Visitor a realizovat různé průchody. Tímto způsobem je navržen sémantický analyzátor nebo generátor výstupního kódu.

6.4

Syntaktická analýza

Syntaktický analyzátor je realizován pomocí třídy Parser, která provádí syntaktickou analýzu. Produktem této analýzy je AST. Ten je dále analyzován sémantickým analyzátorem. Syntaktický analyzátor je realizován jako LL(1) analyzátor.

6.4.1

Návrh gramatiky

Při návrhu gramatiky jsem vycházel z toho, jak je definovaná podle ANSI normy. Sémantiku výrazů, jsem také zachoval stejnou. Jediné co jsem udělal, bylo ořezání rozsáhlé syntaxe na jednodušší. Tuto gramatiku jem následně převedl na LL(1) gramatiku, abych ji mohl implementovat rekurzivním sestupem.

6.4.2

Optimalizace gramatiky pro LL(1) analýzu

Při generování rekurzivního sestupu získáme, příliš mnoho rekurzivních volání. Neoptimalita je způsobena tím, že pro zápis opakování v gramatice se používá rekurze. Mezi hlavní optimalizace patří: 1. Odstranění koncové rekurze cyklem. Uspoří nám volání. 2. Substituce jednoduchých neterminálů. Uspoří další volání. Výsledkem je pak optimální rekurzivní sestup s nutným minimem volání.

6.4.3

Zpracování chyb

Při zpracování chyb rozlišujeme, podle závažnosti, na dva typy. První jsou méně závažné, které vyústí je v výpis. Druhé jsou závažné, ze kterých se analyzátor jen těžko zotavuje. Zotavení jako takové není implementováno, ale analyzátor se vždy snaží pokračovat v analýze. Pokud pokračovat nejde, tak končí překlad.

6.5

Sémantická analýza

Jak již naznačeno, tak je sémantický analyzátor realizován jako potomek třídy Visitor. Při této analýze se kontroluje sémantika uzlů, která nebyla ještě zkontrolována při syntaktické analýze. Třída se jmenuje SemAnalyzer. Hlavním úkolem této analýzy je zkontrolovat typovou korektnost programu, která by příliš komplikovala analýzu syntaktickou.

25

26

Kapitola Zadní část překladače

7

Hlavním úkolem zadní části překladače je přijmout výstupní vnitřní formu přední části, tuto zoptimalizovat a konečně vygenerovat kód výstupního jazyka. Důležitost této části spočívá v tom, že směrodatně určuje kvalitu výstupního kódu. Čím kvalitnější bude zadní část, tím kvalitnější bude výstup překladače. Při generování výsledného kódu se také musí vyřešit přidělování registrů, výběr instrukcí a adres symbolů programu, umístěných v paměti cílového počítače. Adresy můžeme přidělovat buďto absolutní (méně běžné) nebo relativní. Jedná se o řešení klasického problému nejlepšího rozdělení omezených zdrojů. Podle toho, jak chytře přidělíme prostředky, tak dobře bude schopen zkompilovaný program pracovat. Řešení těchto problémů popisují následující sekce.

7.1

Optimalizace

Optimalizace jsou poměrně rozsáhle probírány v následující kapitole ??. Přesto bych chtěl zde naznačit jejich souvislosti s zadní částí překladače. Optimalizace provádějí transformaci zdrojového programu, uloženého ve vnitřní formě, na sémanticky ekvivalentní program. Transofrmace provádíme tak, aby z upravené vnitřní formy šel vygenerovat co nejlepší výstupní kód. Podle použitelnosti optimalizací je můžeme rozdělit na dvě skipiny. Systémově nezávislé optimalizace, které se dají provést pro libovolný počítač a můžeme je provádět vždy. Což je veliká výhoda. Proto se v této práci hlavné zabývám touto skupinou. Druhou skupinou jsou systémově závislé optimalizace, které pro dosažení optimality využívají specifických vlastností cílového systému. Optimalizace provádíme pochopitelně před generováním kódu. Nejprve provedem systémově nazávisle optimalizace, pak předáme vnitřní formu systémově závislému optimalizátoru a konečně se generuje výstupní kód. Přičemž také generátor výstupního kódu přispívá k optimalitě např. výběrem instrukcí. I když je zde zařazen optimalizátor do zadní části, tak optimalizovat můžeme v průběhu celého překladu. Schéma zadní části, je naznačeno na obrázku 7.1.

7.2

Přidělování registrů

Přidělování registrů je založeno na volání virtuální metody size_t getRegUsage( void );, která nám vrátí počet registrů JVM nutných pro vykonání daného výrazu res. vykonání příkazu. Tato hodnota nám učí velikost aritmetického zásobníku pro danou funkci. Každý uzel AST obsahuje tuto metodu. K vypočtené hodnotě je přičtena malinká rezerva. Algoritmus je založen na tom, že pro každý uzel jsme schopni určit registrovou náročnost jeho provedení. Algoritmus použitý pro tento účel je podobný Levi-Sethiho 27

Kapitola 7. Zadní část překladače

Obrázek 7.1: Schéma zadní části překladače.

algoritmu [? ], který se používá pro generování výrazů s minimen použitých registrů. Výrazy jsou jasné z daného algoritmu. Jelikož se příkazy provádějí separátně, tak je nutné najít maximum registrů z daných příkazů. Což není nijak složité.

7.3

Přidělování adres

Globální proměnné jsou realizovány jako statické členy hlavní třídy. Tím není co řešit. Řešit musíme přidělení čísel (od 0) lokálním proměnným. První jsou parametry funkce pak ostatní proměnné bloků. Používá se linearizované blokové struktury. Pomocí značek jsou rozlišeny začátky bloků, konce bloků a proměnné jimž se bude přidělovat adresa. Algoritmus je opět velice jednoduchý. Jedná se o průchod stromu bloků do hloubky. Při narazení na začátek bloku se uloží původní adresa dané blokové úrovně. Pak se přidělí adresy proměnným. Po ukončení se obnoví původní adresa ze zásobníku. Toto se provede pro všechny bloky. Při přidělování adres je přidána adresa jen těm proměnným, které jsou použity. Tím prakticky optimalizujeme použití proměnných. Využití paměti je optimální.

7.4

Generování výstupního kódu

Generátor výstupního kódu nám pomocí virtuálních metod třídy Visitor generuje výstupní kód v jazyce jasmin . Navíc má na starosti správu návěští, které potřebujeme generovat pro příkazy skoků. Spravuje také operace nad výstupním souborem. Příkazy printf a puts jsou prováděny pomocí javovských metod println resp. print. Při generování je formátovací řetěz rozlámán na vypsatelné úseky a tyto jsou 28

Podkapitola 7.4. Generování výstupního kódu následně „vypsány“ generováním příslušných metod. Tyto metody jous relizovány přímým vložením kódu, takže se uspoří volání. Hranice mezi optimalizacemi a generováním kódu nejsou ve skutečnosti tak striktní, jako bylo výše popisováno. Při generování kódu se musí také optimalizovat. Nejvýznamnější je asi správný výběr instrukcí a zamezení generování zbytečných instrukcí.

29

30

Kapitola Optimalizace

8

Když mluvíme o optimalizacích, tak máme na mysli optimalizační proces, který má za úkol vyřešit určitý problém co nejlepším možným způsobem — řešení je pak optimální. To samé platí u počítačových programů, které jsou v tomto příkladě řešeným problémem a cílem je najít co nejlepší sémanticky ekvivalentní řešení k původnímu programu pro určitý počítač. Velice zajímavá je otázka, jestli vůbec nějaké optimální řešení existuje. Na tuto otázku nelze jednoznačně odpovědět. Už jen z toho důvodu, když si představíme kolik různých možných řešení existuje. A co ty, které si třeba představit neumíme? Hlavně při vývoji software se musíme spokojit s kompromisy, způsobené různými omezujícími podmínkami, které brání v vytvoření nejlepšího řešení. Mimo to, neexistuje jedno optimální řešení pro všechny naše nároky na optimální software. Proto se musíme rozhodnout, co je naším cílem optimality a dopracovat se k tomuto cíli na úkor méně kritických parametrů software. Příkladem je optimalizace na maximální rychlost programu, které je často docíleno na úkor paměťové efektivity. Optimalizátor překladače se snaží najít nejlepší řešení překladu pro určitou počítačovou architekturu. Může se jen pokusit „vytáhnout“ na dané architektuře maximum z programu, který mu programátor předložil. Důsledkem je, že volba algoritmů použitých v programu má mnohem větší váhu, než optimalizace. Při neefektivně zvoleném nebo vymyšleném algoritmu nepomůže i sebelepší optimálzor, protože je schopen jen optimalizovat danou implementaci daného algoritmu.

8.1

Klasifikace optimalizací

Optimalizace jde kategorizovat podle mnoha kritérií. • • • • •

Globální a lokální. Podle cíle (optimalizace na rychlost, paměť). Podle fáze, kdy mají být vykonány. Systémově závislé a nezávislé. Další.

8.1.1

Globální a lokální optimalizace

Globální optimalizace pohlížejí na celý program jako na jeden celek. Tento celek se snaží co nejlépe sladit dohromady. Cítíme, že to vůbec nebude jednoduché, a že globální optimalizace mohou být poměrně složité a neefektivní. Opakem jsou lokální optimalizace, které jsou vázány jen na nějaký malý úsek kódu, který se snaží optimalizovat. Úsekem může být blok instrukcí, blok grafu toku řízení programu, tělo podrogramu, nebo úplně jiný. Každopádně je tento úsek znatelně menší 31

Kapitola 8. Optimalizace než celý program a dovoluje ta mnohem rychlejší a efektivnější optimalizování. Typickým přikladem lokálních optimalizací jsou optimalizace na základním bloku.

8.1.2

Cíle optimalizací

Pokud provádíme optimalizaci, tak sledujeme nějaký optimální cíl, kterého chceme dosáhnout, nebo se mu alespoň přiblížit. Tento cíl nám zásadně ovlivňuje celý proces optimalizace, protože nikdy nedojde k tomu, že bychom vyhověli všem. Pokud optimalizujeme na rychlost, tak se může stát, že vložením funcí naroste velikost kódu, čímž to je na úkor potřebné paměti, ale program bude rychlejší. Samozřejmě cíly nemusí být jen tyto standardní (rychlost vs. paměť), ale i jakýkoli jiný požadavek na optimalitu programu.

8.1.3

Fáze vykonání optimalizací

Fází se myslí fáze překladu. Pokud to vezmeme obecně, tak se nemusí optimalizovat jen v zadní části překladače, ale v jakýkoli moment překladu. Vždy se snažíme rozdělit optimalizace v průběhu překladu tak, aby jsem získali co nejdokonalejší výsledek. Některé optimalizace se mohou provádět ve více fázích.

8.1.4

Systémově závislé a nezávislé

Systémově nezávislé optimalizace jsou takové, které jsme schopni provést pro jakýkoli systém. Tím tvoří základní repertoár optimalizátorů překladačů. Systémově závislé optimalizace jsou takové, které jsou možné nebo efektivní jen pro danou architekturu, do jehož kódu které se překládá. Tím jsou tyto optimalizace velice specifické. V této práci se budu hlavně zabývat strojově nezávislými optimalizacemi.

8.1.5

Grafy toku řízení programu

Grafy toku řízení jsou skvělým nástrojem pro analýzu programů lineárním zápise. Pricip spočívá v rozdělení vnitřní formy na bloky, které jsou mezi sebou provázány hranami, zastupující podmíněné a nepodmíněné skoky. Prakticky tím získáme z lineárního zápisu zpátky strukturu řídících struktur jako jsou např. smyčky, podmínky, atd. Na tomto základě jsme je schopni rozpoznat a optimalizovat. Výhodou je, že se nám optimalizace redukují na optimalizace na grafech, které jsou velice dobře známy. Mimo to umožnují analyzovat a optimalizovat tok programu. Na jeho základě jde rozhodovat o přidělování registrů, mnoho dalších věcí. To všechno je k tomu dělat efektivně.

8.2

Tradiční optimalizační metody

Tradiční optimalizační metody využívají grafu toku řízení programu jako je popsáno v [9]. Nicméně se tyto metody dají adaptovat na vnitřní formu nebo jiné struktury překladače.

8.3

Optimalizace na abstraktním syntaktickém stromu

Abstraktní syntaktický strom (dále jen AST = Asbstract Syntax Tree) je velice často používanou vnitřní formou předních částí překladačů. Jedná se o hierarchickou stromovou strukturu založenou na syntaktickém stromě, ve kterém jsou vynechány všechny přebytečné detaily jazyka. Výhodou je jeho obecnost a jednoduchost. Nevýhodou může 32

Podkapitola 8.3. Optimalizace na abstraktním syntaktickém stromu být složitost operací nad ní právě z toho důvodu, že je struktura hierarchická. Z tohoto důvodu se většinou používá jako první vnitřní forma uvnitř překladače. Dále je přeložena do jiných forem, s kterými se pak lépe provádějí některé operace. I když se AST moc pro optimalizace nehodí, z důvodu stromového charakteru, tak se přesto na některé optimalizace použít dá. Výsledkem je ušetření optimalizačních průchodů v dalších částech překladače, protože některé vybrané optimalizace je jednodušší a efektivnější provést na AST. Následkem těchto poměrně jednoduchých optimalizací je extrémní zjednodušení programu a tím i jeho zrychlení. Účinnost je bohužel závislá na daném kódu. Dá se říci, že výsledek je vždy lepší než kdybychom optimalizace nepoužívali.

8.3.1

Spojování konstant

Spojování konstant je optimalizační metoda založená na myšlence, že pokud se výrazy v jazyce budou skládat z konstant, což je většinou pravda, tak lze takový výraz celý vyhodnotit nebo alespoň zjednodušit již v době překladu. U takto na minimum zjednodušených příkazů se dá lépe rozhodnout o tom, jak by se daly dále optimalizovat. Tato optimalizace by měla být provedena co nejdříve a možné je i její zopakování v průběhu optimalizací. Tuto optimalizaci lze provádět na libovolném typu vnitřní formy. V literatuře se často ukazuje na n-adresovém kódu nebo jiných lineárních vnitřních formách. Nevýhodou je, že se na těchto formách musí optimalizace provádět globálně a celý proces je poměrně komplikovaný. Pokud použijeme AST, tak získáme hned několik výhod. Abstraktní syntaktický strom výrazu odpovídá syntaktickému stromu výrazu. Stačí tedy provést výpočet postorder průchodem. Další výhodou je to, že se optimalizace provádějí lokálně. Optimalizujeme např. jen řídící podmínku cyklu, což celý proces výrazně zjednoduší. Nutnou podmínkou pro úspěšné provedení je, aby příkaz neobsahoval žádné proměnné nebo volání funkcí. Proměnné by nešly vyhodnotit v době překladu. O funcích platí to stejné, ještě k tomu by mohli mít nějaký vedlejší efekt. Také výpočet při kompilaci nemusí být vždy jednoduchý.

8.3.2

Přesun invariantu z cyklu

Metoda pro přesunutí příkazů a výrazů z cyklu, které se nemění v průběhu iterace cyklu. V tom je právě to nejtěžší této metody. Musíme zjistit, jaké příkazy jsou opravdu invariantní. Pokud chybně vybereme příkaz, který invariantní není, tak dojde k změně sémantiky programu. Pokud tuto optimalizaci provádíme na AST, tak můžeme provádět jen přesuny celých příkazů z cyklu. To je poměrně nevýhoda oproti variantě této optimalizace realizované pomocí grafů toku řízení programu. Zde je řešení optimalizace na AST méně efektivní.

8.3.3

Odstranění mrtvého kódu

Když provedeme spojení konstant, a případně další zjednodušení, tak budeme moci některé příkazy úplně odstranit. Puku bude řídící podmínka smyčky 0, tak víme, že tento mrtvý kód můžeme celý odstranit, protože nikdy nedojde k jeho vykonání. Na AST se provádí odstranění jen na této vysoké úrovni, protože jinak to není možné. 33

Kapitola 8. Optimalizace

8.3.4

Hledání společných podstromů

V poslední době se začal vyvíjet výzkum zpracování stromů. Nová věda se nazývá Arbologie. Této skupině se úspěšně podařilo implementovat algoritmus hledání všech sémanticky stejných podstromů pomocí zásobníkových automatů s lineární složitostí. Tedy jsme schopni efektivně najít a případně spojit společné výrazy. Tím ušetříme nejen dobu výpočtu (výraz je vyhodnocen jen jednou), ale i místo v paměti, protože každý podstrom bude obsažen pouze jednou. Právě díky těmto novým výzkumům, získáváme nové poznatky o stromech, které umožňují lépe zpracovat AST.

8.3.5

Optimalizace matematickými zákony

Název je možná trochu zavádějící. Myšleno je použití zákonů typu asociativního, komutativního a dalších. Pomocí těchto zákonů upravíme výrazy, tak aby dala efektivně použít nějaká jiná optimalizace. Pro AST je tento postup složitý, protože musíme pracovat se stromy.

8.4

Interprocedurální optimalizace

Inteprocedurální optimalizace (dále v textu jen zkráceně IPO) je souborem optimalizačních metod pro poředkladače. Tyto optimalizace se liší od ostatních tím, že se analyzuje celý program a závislosti mezi elemetny programu (funkce, cykly, atd.) namísto lokálních analýz samotných elementů. Síla těchto optimalizací spočívá v sběru informací na překládaném programu. Tomuto sběru se říká interprocedurální analýza. Při optimalizacích se snažíme redukovat výpočty, optimalizovat volání funkcí, a inlinování funkcí. Inlinování, tedy vkládání, funkcí se bude probírat v následující kapitole. Mimo toto se k interprocedurálním optimalizacím řadí také klasické metody jako odstranění mrtvého kódu. Optimalizováno je také zpracvání konstant. Využití a konstrukce grafu volání Pro Inteprocedurální analýzu se používá grafu volání. Příklad grafu volání je na OBRAZEKu. Definice: Graf volání je obecným orientovaný grafem. Každá funkce/procedura je reprezentována uzlem grafu. Vtah volání je zaznamenán orientovanou hranou s orientací od volajícího S k volanému D. Tedy hrana je orientována S D. Po sestavení grafu jsme schopni pomocí klasických grafových algoritmů určit metriky pro kompilovaný program program. Jsme schopni např. analýzou cyklů grafu volání najít rekurzi, přímou i nepřímou. Přímá rekurze je reprezentována smyčkou. Nepřímou rekurzi rozpoznáme nalezením cyklu. Tato informace je důležitá, protože nám říká, jestli budeme moci tuto funckci inlinovat. Dále jsme velice jednoduše schopni určit počet volání každé funkce a použít tuto informaci pro další optimalizace. Pokud bude čítač volání nulový, tak může být odstraněna protože není používána. Pokud je funkce volána jen jednou a je nerekurzivní, pak můžeme s klidem funci vložit a ušet tím volání.

34

Podkapitola 8.5. Optimalizace přímým vkládáním

8.4.1

Optimalizace použití konstant

V této metodě se hlavně využívá propagace konstant a zamezení aliasingu. Pokud voláme funci a předáváme konstantu, tak dojde k tomu, že se bude parametr muset předat a bude se vždy muset nahrávat z adresy parametru. Ve skutečnosti by se dala ušetřit pamět a předání parametru. Každý výskyt proměnné by se pak mohl nahradit jednoduchým nahráním konstanty. Po těchto optimalizacích je dobré provést, popř. znovu, klasické optimalizace. Zejména spojování konstant, které nám může umožnit další optimalizace.

8.4.2

Odstranění nevolaných funcí

Nejdříve provedeme analýzu grafu volání a zjistíme pocet volání dané funkce nebo procedury. V grafu se jedná o uzly, do kterých nevstupuje žádná hrana. Pokud je čítač volání nulový, tak můžeme tuto mrtvou funkci nebo proceduru odstranit, protože nám je zábírá kódová paměť. Výjímku tvoří funkce main, která nejde odstranit. Odstranění nevolaných funcí by se mělo při překladu povést co nejdříve, protože pak nemusíme se vůbec zabývat vnitřní analýzou dané funkce nebo procedury. Výsledkem bude zrychlení překladu.

8.5

Optimalizace přímým vkládáním

V této kapitolu se dubou probírat metody a strategie pro přímé vkládání úseků kódu. Zejména se budeme zaměřovat na vkládání funkcí tak, aby se uspořil čas zdpotřebovaný volání dané funkce. Probrány budou strategie, jak rozhodnout, co budeme s blokem kódu dělat.

8.6

Úvod a rozdělení

Pokud chceme psát přehledný kód, tak musíme dekomponovat řešený problém na podproblémy. Tyto podproblémy budou řešeny procedurami nebo funkcemi. Pro volání funkce se nejprve musí předat všechny parametry a návratová adresa místa, ze kterého jsme funkci volali. Potom následuje nastavení programového čítače na první instrukci funkce. Dále se musí alokovat rámec funkce na zásobníku, na kterém budou uloženy lokální proměnné. Pak se teprve začne vykonávat kód, který jsme napsali do těla funcke. Na konci se musí zase uklidit rámec funkce a nastavit programový čítač na adresu, ze které byla funkce volána. Navíc se ještě musí vybrat vstupní parametry. Základní myšlenkou přímeho vkládání kódu je, že pokud vložíme tělo funkce přímo na místo volání, tak všechny výše uvedené operace uspoříme. Cena za rychlost získanou touto operací je duplicitní kód. Pokud je daná funkce dlouhá a je volána mnohokrát, tak dojde k extrémnímu nárůstu výstupního kódu. Pokud je ale funkce volána jen jednou nebo je jednoduchá, pak vložením získáme a optimalizace má požadovaný efekt. Vkládání koódu se délí na dva typy. Prvním je vkládání kódu při překladu. Překladač při překladu jednotky se snaží vkládat kód na základě jemu známých dat. Tento typ velice mnoho nevýhod. Mezi hlavní patří nutnost definice funkce šířit na všechny místa volání, protože překladač

35

Kapitola 8. Optimalizace musí vědět co má vkládat – pokud to tedy uzná za vhodné. Následkem je směšování deklarací a definice, které by pro čitelnost měly být odděleny. Další nevýhodou malá účinost optimalizace vykonané v této fázi. Udává se, že se dosahuje maximálně 2 % zrychlení výsledného kódu. Druhým typem je vkládání při linkování. V této fázi máme k dispozici maximum dat pro analýzu. Při rozhodování o vložení se bere v úvahu celý program. To má za následek mnohem lepší výsledky. Udává se až 10 % zrychlení výsledného kódu.

36

Kapitola Testování

9

Každá třída byla jako celek důkladně testována. Ověřeny byly také její případné vedlejší účinky. Jednotkové testování bylo provedeno ručně, což sice ztěžuje opakovatelnost testování, ale jen tak lze zaručit, že vše funguje co nejlépe. Dále byly provedeny integrační testování. Nelze říci jestli jsem integroval zhora dolu nebo naopak, protože jsem vždy volil tu metodu, která byla pro daný příklad nejjednodušší. Závěrem byl testován překladač a jeho funkce. Na konec byly provedeny testy optimalizací, které byly velice skromné, z důvodu úrovně jejich implementace. Co se týče jejich kvality, tak zajisté uspoří jistý čas, ale pro dokonalost by potřebovaly více času pro implementaci.

37

38

Závěr Podařilo se mi úspěšně implementovat funkční překladač podle vymezených cílů. Překladač bezchybně funguje a generuje funční kód pro JVM. V průběhu přípravy na tuto práci jsem nastudoval různé optimalizační metody. V programu jsem implementoval metody spojování konstant, odstranění mrtvého kódu a přímé vkládání kódu funkcí. U vkládání funkcí se musí poznamenat, že na rozdíl od ostatních metod funguje s omezením. Omezením je, že funkce nesmí mít žádné parametry aby byla vložena. Musím zde přiznat, že implementace optimalizací je poměrně chabá. Při tvorbě jsem se soustředil na překladač a pak jsem nestíhal implementovat ještě optimalizace. Ty nejsou moc povedené nebo nejsou stihnuté (vkládání funkcí). Z důvodu složitosti celého projektu a nedostatku čásu jsou některé části trochu nedokonalé a muselo dojít k kompromisům jako je zjednodušení vkládání funkcí. Program je tak napsán, že kvalitní přidělení paměti umožňuje, ale tato možnost nebyla využita a držel jsem se jednoduchosti. Další věcí k zlepšení by bylo zavedení zotavení ze syntaktických chyb. Zatím je tato situace řešena tak, že pokud by došlo k porušení koezistence programu, tak se radši překlad ukončí. Při pokračování by nejspíše došlo k velkému množství zavlečených chyb. Nejlepší by bylo implementovat tzv. Hartmanovo schéma zotavení, což ale není vůbec jednoduché při složitých gramatikách. Všechny výše uvedené nedostatky by mohly být v budoucnosti náměty na další bakalářské práce. Jinak by se daly přidávat postupně další systémová volání, které by rozšířily použití daného překladače. Překladač by se určitě dal použít pro výukové účely.

39

40

Literatura [1] History of compiler construction. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2012-12-16]. Dostupné z: [2] MELICHAR, Bořivoj, Milan ČEŠKA, Karel JEŽEK a Karel RICHTA. Konstrukce překladačů I. část. 1. vyd. Praha: Vydavatelství ČVUT, 1999, 367 s. ISBN 80-010-2028-2. [3] KOLÁŘ, Josef. TEORETICKÁ INFORMATIKA. Vydání první. Praha: Nakladatelství ČVUT, červen 2009, 204 s. ISBN 978-80-01-04331-8. [4] Java Virtual Machine: C to bytecode compilers. In: Wikipedia: the free encyclopedia [online]. San Francisco (CA): Wikimedia Foundation, 2001- [cit. 2012-06-02]. Dostupné z: [5] NestedVM: Binary translation for Java [online]. Neznámý rok vydání [cit. 2012-05-01]. Dostupné z: [6] The LLVM Compiler Infrastructure Project [online]. Neznámý rok vydání [cit. 2012-05-30]. Dostupné z: [7] C2J translator: Translate C programs to Java programs. NOVOSOFT LLC. Novosoft: Custom software development services [online]. c2000 [cit. 2012-05-04]. Dostupné z: [8] Resourceable and Retargetable Binary Translator: Java Backend for GCC. School of Information Technology and Electrical Engineering: University of Queensland [online]. 1999 [cit. 2012-06-02]. Dostupné z: [9] MELICHAR, Bořivoj, Milan ČEŠKA, Karel JEŽEK a Karel RICHTA. Konstrukce překladačů I. část. 1. vyd. Praha: Vydavatelství ČVUT, 1999, 367 s. ISBN 80-010-2028-2. [10] Jasmin Home Page [online]. c2004 [cit. 2013-01-04]. Dostupné z:

41

42

Příloha Použité zkratky

A

V této kapitole jsou vypsány všechny zkratky, které byly použity v textu. Součástí je stručný popis zkratky, případně detaily k významu v rámci tohoto textu. Při psaní textu jsem se snažil jich používat co nejméně, protože výrazně zhoršují čitelnost textu. Někdy se zkratkám prostě nevyhneme, např. u jmen formátů, a pak jsme odkázáni na tento seznam.

A.1

Seznam zkratek

Seznam zkratek je seřazen vzestupně podle abecedy. AST . . . . . . . . . . . . . . . . . . Abstract Syntax Tree. Abstraktní syntaktický strom je vnitřní formou přední části překladače. V mém překladači je to jediná vnitřní forma. DVI . . . . . . . . . . . . . . . . . . Device Independend. Jedná se o standardní výstupní formát programu TEXa LATEX. Všechny ostatní formáty jsou pak generovány právě z tohoto formátu. EPS . . . . . . . . . . . . . . . . . . Encapsulated PostScript. Grafický formát s plnou podporou jazyka PostScript. V této práci jsou všechny obrázky v tomto formátu, protože kresby ponechávají v vektorové podobě. Do formátu lze přidat i rastrovou kresbu. IR . . . . . . . . . . . . . . . . . . . . Internal Representation. Jedná se o obecné označení vnitřní formy překladače. V tomto textu se tím hlavně myslí vnitřní forma přenášená z přední do zadní části překladače. PDF. . . . . . . . . . . . . . . . . .Portable Document Format. Vysoce přenosný formát pro dokumenty. Není závislý na prostředí ve kterém je zobrazen a měl by nezávisle na prostředí vypadat vždy stejně. PS. . . . . . . . . . . . . . . . . . . .PostScript.

43

44

Příloha Bezkontextová gramatika překladače

B

Toto je výpis bezkontextové gramatiky, která je implementována v doprovodném projektu překladače. Co se týče notace, tak odpovídá původnímu zápisu podle Backus-Naura. Rozdílem je, že neterminály nejsou uzavřeny v "ostrých" závorkách a skládají se jen z jednoho slova (slov může být více, ale nesmí být mezi nimi mezera). Terminály jsou v uvozovkách a mezery jsou povoleny, protože terminál je jasně vymezen uvozovkami. Operátor ::= nám přiřazuje pravou stranu a | nám vytváří další pravou stranu stranu jako alternativu k předchozím pravým stranám pravidla. Prázdný řetězec je ε. Pokud pomocí odstraníme first-follow konfliktu neterminálu Else, tak je gramatika jednoznačná LL(1). Jelikož konflikt first-follow je neodstranitelný, tak jsem si pomohl trikem z [? ]. Problém konfliktu byl v tom, že jsme mohli při vícenásobném vnoření podmínek mít víc alternativ kam přidat část else. Tím došlo k nejednoznačnosti. Problém bude elegantně vyřešen, když řekneme, že se else část bude vždy vázat k nejbližšímu if. Tím je konflikt odstraněn a gramatika je LL(1). V souboru gramatika.xls, na doprovodném CD, je tato kompletní gramatika, atributy a atributová gramatika. Dále jsou obsaženy i změny, které byly provedeny, aby bylo možné generovat optimální rekurzivní sestup. Pro další informace bych odkázal tam.

B.1 (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) (14)

Bezkontextová LL(1) gramatika Program FuncVar RoFuncVar FuncBody VarDecl ParamList RoParam

::= | ::= ::= | ::= | ::= | ::= | ::= |

FuncVar Program ε Type ’ident’ RoFuncVar ’(’ ParamList FuncBody VarDecl Blok ’;’ ’,’ ’ident’ VarDecl ’;’ Type RoParam ’)’ ’ident’ RoParamList ’)’ 45

Příloha B. Bezkontextová gramatika překladače (15) (16) (17) (18) (19) (20) (21) (22) (23) (24) (25) (26) (27) (28) (29) (30) (31) (32) (33) (34) (35) (36) (37) (38) (39) (40) (41) (42) (43) (44) (45) (46) (47) (48) (49) (50) (51) (52) (53) (54) (55) (56) (57) (58) (59) (60) 46

RoParamList Type TypeSpec TypeName Blok DeclList LocVarDecl RoLocVarDecl StmtList Stmt

Else Expr RoExpr Assign RoAssign LogOr RoLogOr LogAnd RoLogAnd Equal RoEqual

Relat

::= | ::= ::= | ::= | ::= ::= | ::= ::= | ::= | ::= | | | | | | | | | ::= | ::= ::= | ::= ::= | ::= ::= | ::= ::= | ::= ::= | | ::= | |

’,’ Type ’ident’ RoParamList ’)’ TypeSpec TypeName ’const’ ε ’int’ ’void’ ’{’ DeclList StmtList ’}’ LocVarDecl DeclList ε Type ’ident’ RoLocVarDecl ’,’ ’ident’ RoLocVarDecl ε Stmt StmtList ε Blok ’if’ ’(’ Expr ’)’ Stmt Else ’while’ ’(’ Expr ’)’ Stmt ’do’ Stmt ’while’ ’(’ Expr ’)’ ’for’ ’(’ OptExpr ’;’ OptExpr ’;’ OptExpr ’;’ ’)’ Stmt ’break’ ’;’ ’continue’ ’;’ ’return’ OptExpr ’;’ Expr ’;’ ’;’ ’else’ Stmt ε Assign RoExpr ’,’ Assign RoExpr ε LogOr RoAssign ’=’ Assign ε LogAnd RoLogOr ’||’ LogAnd RoLogOr ε Equal RoLogAnd ’&&’ Equal RoLogAnd ε Relat RoEqual ’==’ Realat RoEqual ’!=’ Relat RoEqual ε ’>’ Aditive RoRelat ’<’ Aditive RoRelat ’>=’ Aditive RoRelat

Podkapitola B.1. Bezkontextová LL(1) gramatika (61) (62) (63) (64) (65) (66) (67) (68) (69) (70) (71) (72) (73) (74) (75) (76) (77) (78) (79) (80) (81) (82) (83) (84) (85) (86) (87) (88) (89) (90) (91) (92) (93)

Aditive RoAditive

Multi RoMulti

Faktor Prefix

Postfix

Primary

SysCall RoPrintf OptExpr

| | ::= ::= | | ::= ::= | | | | ::= ::= | | | | | ::= | | | ::= | | | ::= | ::= | ::= |

’<=’ Aditive RoRelat ε Multi RoAditive ’+’ Multi RoAditive ’-’ Multi RoAditive ε Faktor RoMulti ’*’ Faktor RoMulti ’*’ Faktor RoMulti ’/’ Faktor RoMulti ’%’ Faktor RoMulti ε Prefix Primary Postfix ’+’ Prefix ’-’ Prefix ’!’ Prefix ’++’ Prefix ’–’ Prefix ε ’(’ Expr ’)’ ’++’ ’–’ ε ’ident’ ’cislo’ ’(’ Expr ’)’ SysCall ’printf’ ’(’ ’string’ RoPrintf ’puts’ ’(’ ’string’ ’)’ ’,’ LogAnd RoPrintf ’)’ Expr ε

47

48

Příloha Uživatelský manuál překladače

C

V tomto manuálu budou uloženy všechny informace týkající se správného použití a pochopení chování doprovodného překladače kcc – krajníkova C compilátoru.

C.1

Co všechno pořebujeme

Pro provedení překladu pořebujeme spustitelnou binárku překladače, assembler Jasmin a Java Runtime Enviroment. S touto konfigurací jsme schopni kompilovat a spouštět přeložené programy. Pokud chceme provádět další operace s přeloženým souborem *.class, tak pořebujeme mít nainstalovyný JDK (Java Developer Kit). Tato sbírka nástrojů nám pomůže při další práci s zkompilovanými kódy.

C.2

Instalace a deinstalace

Instalace je velice jednoduchá. Stačí zkopírovat spustitelný soubor s programem na místo, kde ho chceme používat. Pokud chceme, aby se náš program choval jako příkaz, tak musíme přidat do systémové proměnné PATH cestu k spustitelnému souboru. Pro všechny následující kapitoly a hlavné příklady budeme předpokládat, že cesta k překladači byla přidána do proměnné PATH. Pro deinstalaci programu stačí smazat spustitelný soubor. Případně je nutné odstranit z PATH již neexistující cestu k našemu programu.

C.3

Přepínače

Pomocí přepínačů můžeme v určité míře měni chování celého programu nebo jeho částí. Překladče jsou zpracovávány pocí GNU getopt. Seznam je seřazen podle abecedy. -a -c -d -h -i -m -p

Zapnutí výpisu abstraktního stromu do souboru *.ast. Standadně se soubor negeneruje. Provede se jen kompilace. Tedy se netestuje výskyt funkce main. Používáme hlavně pokud kompilujeme pro knihovnu. Optimalizace vypuštění mrtvého kódu (Dead Code elimination). Výpis pomoci. Zapnutí optimalizace vkládání funkcí (inline). Zapnutí optimalizace spojování konstant. Parametr jeho argument určuje jméno Java balíku. Standardně se nepoužívá a je prázdný. 49

Příloha C. Uživatelský manuál překladače -s

-t -v

C.4

Parametr za přepínačem udává, jak se bude jmenovat Javovská třída. Současně se jedná o jméno výstupníh souboru. Standardně ’Main’. Šířka tabelátoru. Argumentem musí být celé nenulové číslo. Standardně 4 znaky. Výpis verze překladače.

Vstupní soubory

Jediným vstupním souborem je zdrojový kód v jazyce C, splňující syntaxi udávanou v příloze B. Cesta k souboru je zadána jako poslední argument příkazové řádky. Důležité je, aby soubor existoval a my měli alespoň přístupová práva pro čtení. Pokud nějaká z těchto podmínek je nesplněná, tak samozřejmé dojde k výpisu adekvátní chybové zprávy a program končí. Pokud cesta k souboru není zadána, pak se bude zdrojový kód číst ze standardního vstupu stdin. Umožňuje to zpracování pomocí pipe ve spojení s jinými nástroji. Můžeme tedy realizovat např. filtry pomocí awk, sed a dalších. Navíc můžeme vytěžit z té výhody, že procesy běží paralelně a jsou synchronizovány pomocí pipe.

C.5

Výstupní soubory

Všechny výstupní soubory jsou generovány překladačem. Jedná se soubory *.log s detailními informacemi o průběhu překladu a *.j s přeloženým kódem v jazyku symbolických adres pro Javu. Dodatečně lze pomocí přeínače -a aktivovat generování výpisu vnitřní formy ve formě abstraktního syntaktického stromu.

C.6

Kompilace

Pro kompilaci stačí zadat příkaz ve formátu (znak $ je začátek příkazové řádky a nepatří k příkazu jako takovému): $ kcc [přepínače] [zdrojový soubor] Přepínače se zapisují podle POSIXové normy. Tedy jak jsme zvyklí z jiných programů. Jak přepínače, tak zdrojový soubor je možno vynechat. Zdrojový text se bude číst ze standardního vstupu. Pokud je zadána cesta k zdrojovému souboru, tak za ním nesmí následovat žádný další argument.

C.7

Chybové a diagnostické zprávy

V průběhu překladu může dojít k různým druhům chyb. Asi nejhorší jsou chyby selháním systém, kterým se nedá vyhnout a nedá se proti nim většinou ani nic dělat. Takové chyby se snaží překladač ošetřit, vypsat chybovou zprávu s informacemi o chybě a končí korektně svou funkci. Další kategorií jsou chyby a diagnostické zprávy překladače. Tyto zprávy nám jen říkají, že někde v zdrojových je chyba nebo nějaký nesmyslný úsek kódu, na který se nás překladač snaží upozornit. Chyby a varování mají vždy následující jednotný zápis. Chyba[KÓD] SOUBOR: ŘÁDKY: SLOUPCE: ZPRÁVA Varování[KÓD] SOUBOR: ŘÁDKY: SLOUPCE: ZPRÁVA 50

Podkapitola C.8. Příklady použití Sloupce mohou být případně vynechány. Pokud máme např. víceřádkový konstrukt, tak těžko určíme rozsah sloupců. Překladač se vždy snaží držet co největší přesnost a místo rozsahu sloupců určí počáteční sloupec na prvním z řádků konstruktu.

C.8

Příklady použití

Pro standarní překlad stačí povést následující příkaz. $ kcc < file.c

nebo

$ kcc file.c

Pokud chceme, tak můžeme přidat některé přepínače a ovlivnit tím výsledek překladu. Následující příklad ukáže použití některých z nich. $ kcc -adim -s Trida < file.c

nebo

$ kcc -adim -s Trida file.c

Nyní umíme přeložit zdrojový soubor jazyka C do Jasmin. Dalším krokem je přeložení vygenerovaného Jasmin assembleru do Java bytekódu. To provedeme následujícím příkazem (přepokládá se existence jasmin.jar v pracovním adresáři). $ java -jar ./jasmin.jar ClassName.j Nyní jsme schopni program spustit pomocí: $ java ClassName.class.

C.8.1

Použití kódu jako knihovny

Pro vytvoření kódu, který by se dal použít jako knihovna musíme kód zkompilovat stejným způsobem jako v přechozí sekci. Pokud nechceme mít v třídě metodu main, tak přidáme přepínač -c. Po assemblování Jasminem dostáváme Java bytekód. Zde si musíme dát pozor na zradu, protože abychom mohli přeložený program jako knihovnu používat, tak musíme ho umísti do Java balíku, který nebude kolidovat s balíky programu, ve kterém chceme knihovnu používat. K tomu slouží přepínač -d. Nyní stačí zabalit zkompilovaný kód do JAR archívu, který je pak použitelný jako plnohodnotná knihovna jazyka Java. Pro použití pak stačí vložit knihovnu do projektu a import balíku knihovny do zdrojového Java souboru, ve kterém jej chceme používat. Pak můžeme používat funkce knihovny. Jak to udělat v NetBeans je naznačeno na: http://stackoverflow.com/questions/1983513/java-how-do-i-use-a-class-file

51

52

Příloha Obsah přiloženého CD

D

V této příloze bude probírán obsah CD. CD obsahuje všechny dokumenty, které vznikly jako výsledek této práce. Následující části této přílohy popíšou ty nejdůležitější adresáře a soubory.

D.1

Volba jména CD

Pro pojmenování CD jsem zvolil kód, pomocí kterého se dobře pozná, že se jedná o tuto bakalářskou práci, kdo je autorem, v jakém semestru se obhajovala a v jakém roce. Jméno bylo sestaveno podle následujícího schematu. Jednotlivé údaje jsou ohraničeny ostrými závorkami. Jelikož jsme, z důvodů kompatibility, omezeni počtem znaků ve jméně, tak je za za znakem : uvedena délka ve znacích. Doporučuje se, aby jméno CD nebylo delší než 16 znaků, což je u tohoto pojmenování vždy splněno. Schéma pojemanování je následující. hUName : 8i hT ypP race : 2i hSemestr : 1i hRok : 4i Kde UName je uživatelské jméno autora do kosu, které ho unikátně identifikuje. Typ práce nám určuje o jaký typ práce se jedná (v mém případě se jedná o bakalářskou práci, takže BP). Semestr a rok určují v jakém roce a semestru byla práce obhajována. Semestr na bývá hodnoty Z(zimní) nebo L(letní). Z toho vyplývá název CD — krajnpetBPZ2013 jehož délka je 15 znaků.

D.2

Struktura CD

V kořenovém adresáři CD se vyskytují dva adresáře a jeden textový soubor. Nálsedující text kapitoly se zabývá významem a obsahem těchto „kořenových“ adresářů. Bakprace-Text Obsahuje text této bakalářské práce. Obsaženy jsou také všechny zdrojové soubory textu pro typografický systém LATEX, které jsem pro vysázení použil. Včetně obrázků a sestavovacího skriptu pro make. Bakprace-Projekt Adresář obsahující program překladače a všechny soubory, které vznikly v souvislosti s ním. Hlavními je projekt pro Code::Blocks s vším k implementaci překladače, soubory návrhu gramatiky, uživatelská a implementační dokumentace. notes.txt Je textový soubor s textem obsahově totožným s tímto textem. Popisuje, jak je členěn obsah CD a jak se v něm má čtenář orientovat. 53

Příloha D. Obsah přiloženého CD

D.2.1

Adresář Text

Adresář, jak již bylo zmíněno, obsahuje všechny soubory, které byl potřebné pro vytvoření textu této práce. Na následujícím stromu adresářové struktury tohoto adresáře je popis všech klíčových souborů a adresářů. Adresáře jsou vyznačeny kurzívou, soubory jsou zapsány standardním písmem a výplňky jsou v špičatých závorkách. Pomocí výplňků se okazuji na skupinu adresářů nebo souborů, ale nejsou tak důležité, abych je na tomto místě detailně probíral. Jestli se jedná o skupinu adresářů nebo souborů rozhoduje řez písma uvnitř špičatých závorek. Text Build bakprace.pdf . . . . . . . . . . . . . . . . . Výstupní soubory s textem práce rovnou ve třech formátech, aby nikomu ňějaký nechyběl. bakprace.dvi bakprace.ps hostatníi . . . . . . . . . . . . . . . . . . . . . Všechny ostatní soubory, které byly vygenerovány při sestavování textu. Obrazky . . . . . . . . . . . . . . . . . . . . . . . . Adresář obsahující všechny obrázky, které byly vytvořeny pro účely tohoto textu. Obsaženy jsou zdrojové soubory obrázků pro OpenOffice.org Draw a jejich exportované formy, ve formátu EPS, pro použití v textu. Zdroje . . . . . . . . . . . . . . . . . . . . . . . . . . Všechny dokumenty, které jsem používal při tvorbě tohoto textu. Jedná se hlavně o dokumentace balíčků LATEXu, texty o typografii a cokoli co se týká sazby v systému LATEX. zprace.sty . . . . . . . . . . . . . . . . . . . . . . . Balíček pro systém LATEX s makry usnadňující sazbu závěrečných prací. Navíc se v něm nastavuje většina parametrů sazby. Tvůrcem je autor tohoto textu. gramat.sty . . . . . . . . . . . . . . . . . . . . . . Balíček pro systém LATEX umožňující sazbu gramatik. Tvůrcem je autor tohoto textu. bakrapce.tex . . . . . . . . . . . . . . . . . . . . Hlavní soubor pro sazbu práce typografickým systémem LATEX. Jednotlivé kapitoly jsou v samostatných souborech, které jsou do tohoto vkládány. Makefile . . . . . . . . . . . . . . . . . . . . . . . . Hlavní sestavovací skript pro vytvoření textu. Pro řízení sestavení se používá program make, pro který je tento skript napsán.

54

Podkapitola D.2. Struktura CD hkapitoly.texi . . . . . . . . . . . . . . . . . . . Pro každou kapitolu je vytvořen soubor, který se vkládá do hlavního souboru bakprace.tex. Soubory jsou pojmenovány dle jména kapitoly. Formáty textu Při sestavování textu je použit babelyzovaný LATEX spolu s dvips. Je to z toho důvodu, že jsem chtěl mít co nejkvalitnější zdroj textu pro následný tisk na PostScriptové tiskárně. Jako výsledek tohoto postupu máme jako výstup soubory DVI a PS. Navíc mi použití PS umožnilo dosáhnou maximální technické kvality ilustrací v tomto textu. Bohužel většina lidí nemá nainstalován prohlížeč DVI ani PS. Nejvíce je rozšířen formát PDF, jehož prohlížeč je již snad na každém počítači nainstalován popř. je volně dostupný. Programem ps2pdf, za pomoci PS interpreta GhostScript, se vygeneruje soubor PDF, který navíc obsahuje hyperlinky a metadata pro PDF, protože nedochází v řetězu konverzí k ztrátě těchto vložených informací. Tím získáváme text ve formátu PDF v takové kvalitě, jako kdybychom ho generovali přímo.

D.2.2

Adresář Projekt

Jak již napovídá jméno tohoto adresáře, tak se v něm budou vyskytovat všechny soubory a adresáře, které byly vytvořeny pro pro účely implementace doprovázející text práce. Při zápisu adresářového stromu jsem použil stejný zápis jako v přechozí kapitole. Projekt Compiler . . . . . . . . . . . . . . . . . . . . . . . Program jednoduchého překladače jazyka C s optimalizátorem realizovaný jako projekt v Code::Blocks a jazyce C++. bin html doxyfil . . . . . . . . . . . . . . . . . . . . . . Konfigurační soubor pro sestavení implementační dokumentace programem doxygen. lexer.flex . . . . . . . . . . . . . . . . . . . . Zdrojový soubor pro sestavení lexikálního analyzátoru překladače pomocí programu flex. hzdrojei . . . . . . . . . . . . . . . . . . . . . Všechny zdrojové soubory překladače. Gramatika . . . . . . . . . . . . . . . . . . . . . . Všechny soubory týkající se návrhu a dokumentace zdrojové gramatiky pro překladač. UserMan . . . . . . . . . . . . . . . . . . . . . . . Uživatelský manuál překladače. Tento je totožný s tím, který je jako příloha B.

55

Příloha D. Obsah přiloženého CD

D.3

Další informace

Při průchodu adresářovou strukturou narazíme na soubory info.txt. Tyto soubory obsahují informace k danému adresáři a jeho obsahu. Soubory jsou umístěny ve všech klíčových místech adresářového stromu CD, nebo na místech, ve kterých by mohlo dojít k nejasnostem. V adresářových stromech jsem tyto soubory záměrně vynechal, protože tyto stromy obsahují veškeré důležité adresáře a v každém by byl jeden z těchto souborů. Důsledkem by bylo zbytečné znepřehlednění.

56