456-0316/01 – Compiler Construction (KPR)
| Gurantor department | Department of Computer Science | Credits | 6 |
| Subject guarantor | doc. RNDr. Petr Šaloun, Ph.D. | Subject version guarantor | doc. RNDr. Petr Šaloun, Ph.D. |
| Study level | undergraduate or graduate | Requirement | Choice-compulsory |
| Year | 3 | Semester | winter |
| | Study language | Czech |
| Year of introduction | 2003/2004 | Year of cancellation | 2006/2007 |
| Intended for the faculties | FEI | Intended for study types | Follow-up Master |
Subject aims expressed by acquired skills and competences
Teaching methods
Summary
Advanced topics from compiler design and implemetation are covered, including compiler generators, attribute grammars, code optimization techniques etc.
Students build a small language subset compiler as a laboratory project.
Compulsory literature:
Recommended literature:
Way of continuous check of knowledge in the course of semester
E-learning
Other requirements
Prerequisities
Subject has no prerequisities.
Co-requisities
Subject has no co-requisities.
Subject syllabus:
Přednášky:
Úvod
Zopakování obsahu předmětu PJP.
Lexikální analýza.
Čtení zdrojového textu, sestavování lexikálních symbolů, screening. Popis lexikálních symbolů pomocí konečného automatu, regulární gramatiky a regulárního výrazu. Meze použití regulárních jazyků. Důvod pro oddělení lexikální a syntaktické analýzy.
Syntaktická analýza
Analýza shora dolů; metoda rekurzivního sestupu a z ní vyplývající omezení,
pojem LL(1) gramatiky, množiny First a Follow a metoda jejich výpočtu.
Analýza zdola nahoru - tvar rozkladové tabulky, činnost analyzátoru, možné konflikty a jejich řešení.
Metody zotavení po chybě. Metoda zdola nahoru a její možnosti,
srovnání s metodou shora dolů. Tvorba rozkladové tabulky Algoritmy vytváření rozkladových tabulek LR(0), SLR(1), LALR(1) a LR(1). Konstrukce LR analyzátoru, výpočet rozkladových tabulek.
Nástroje pro vytváření lexikálních a syntaktických analyzátorů
Programy lex a yacc - zápis gramatiky, rozšíření o sémantické akce, komunikace s lexikálním analyzátorem, zotavení. Definice priority a asociativity operátorů, řešení konfliktů. Program javacc - definice lexikálních symbolů,
zápis gramatiky, sémantické akce, řešení konfliktů.
Atributovaný překlad
Pojem dědičného a syntetizovaného atributu, atributová gramatika, překladová schémata. Atributy při překladu shora dolů, zavedení do metody rekurzivního sestupu, realizace v javacc. Atributy při překladu zdola nahoru, problémy s
dědičnými atributy, realizace v programu yacc.
Typová kontrola.
Datové typy, jednoduché a strukturované typy, vztah k matematickým pojmům (kart. součin, posloupnost, mocnina, sjednocení, ...). Slabá a silná typová kontrola, typové konverze. Tabulka symbolů.
Datové struktury pro jednoduchou tabulku symbolů - pole, seznam, strom, TRP.
Pojem rozsahu platnosti, viditelnost. Blokově strukturovaná tabulka symbolů - operace, datové struktury a algoritmy. Překlady složitějších jazykových konstrukcí.
Víceprůchodové překlady. Překlady výrazů s proměnnými typu pole, překlady booleovských výrazů a složitějších řídicích příkazů.
Zpracování chyb.
Teoretická východiska. Zotavení po chybě v lexikální a syntaktické analýze, implementace zotavení.
Paralelní syntaktická analýza a překlad.
Využití informací o sousedních symbolech, meziprocesová komunikace, binární
redukční strom.
Vnitřní reprezentace programu
Abstraktní syntaktický strom, DAG, tříadresový kód. Objektový model programovacího jazyka, výrazy, příkazy. Struktura programu v době běhu.
Optimalizace programu.
Optimalizace lokální a globální. Strojově nezávislá optimalizace - optimalizace cyklů, algebraické úpravy, analýza toku dat a toku řízení.
Generování cílového programu.
Generování cílového programu pro reálné a virtuální procesory - význam přenositelnosti cílového programu, příklady virtuálních procesorů (P-kód, Java, Perl, Smalltalk, ...). Využití stromových automatů, generování podle vzorů.
Laboratoře:
Náplní cvičení jsou konzultace a řešení semestrálního projektu podle zvoleného zadání. Témata s problematikou překladačů budou vypisována na začátku semestru.
Projekty:
Ucelený projekt konstrukce překladače podmnožiny moderního programovacího jazyka. Překladač může být vyvíjen s podporou generátorů překladačů a dalších podpůrných nástrojů.
Počítačové laboratoře:
Náplní cvičení jsou konzultace a řešení semestrálního projektu podle zvoleného zadání. Témata s problematikou překladačů budou vypisována na začátku semestru.
Conditions for subject completion
Occurrence in study plans
Occurrence in special blocks
Assessment of instruction
Předmět neobsahuje žádné hodnocení.