456-0316/01 – Compiler Construction (KPR)

Gurantor departmentDepartment of Computer ScienceCredits6
Subject guarantordoc. RNDr. Petr Šaloun, Ph.D.Subject version guarantordoc. RNDr. Petr Šaloun, Ph.D.
Study levelundergraduate or graduateRequirementChoice-compulsory
Year3Semesterwinter
Study languageCzech
Year of introduction2003/2004Year of cancellation2006/2007
Intended for the facultiesFEIIntended for study typesFollow-up Master
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2
Combined Credit and Examination 2+2

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

Další požadavky na studenta

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

Combined form (validity from: 1960/1961 Summer semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (145) 51
        Examination Examination 100  0
        Exercises evaluation Credit 45  0
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2006/2007 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2006/2007 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan
2006/2007 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2006/2007 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner