456-0063/01 – Introduction to Compilers (UDP)

Gurantor departmentDepartment of Computer ScienceCredits8
Subject guarantorIng. Marek Běhálek, Ph.D.Subject version guarantorIng. Marek Běhálek, Ph.D.
Study levelundergraduate or graduateRequirementCompulsory
Year4Semesterwinter
Study languageCzech
Year of introduction1992/1993Year of cancellation2010/2011
Intended for the facultiesFEIIntended for study typesMaster
Instruction secured by
LoginNameTuitorTeacher giving lectures
BEH01 Ing. Marek Běhálek, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+2

Subject aims expressed by acquired skills and competences

The course aims students to understand basic principles of compilers, their structure, design, and implementation. Students will be able to effectively make a compiler of a simple programming language.

Teaching methods

Summary

The course covers all pricipal parts of typical compilers and interpreters with special emphasis to design and implementation issues. Students experiment with a simple expression interpreter and learn to write recursive-descent parsers.

Compulsory literature:

Recommended literature:

Way of continuous check of knowledge in the course of semester

Průběžná kontrola studia: Půlsemestrální písemná práce. Podmínky udělení zápočtu: Podmínkou udělení zápočtu je získání alespoň 21 bodů v rámci cvičení (test+projekt).

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: Historie, funkce a struktura překladače, interpretační a kompilační překladač, fáze překladu, testování a údržba překladače. Lexikální analýza: Funkce lexikálního analyzátoru, reprezentace symbolů, slova a jazyky, regulární jazyky, konečný automat, regulární výrazy, implementace lexikálního analyzátoru, konstruktor lex. Syntaktická analýza: Účel a metody syntaktické analýzy. Jazyky, gramatiky a automaty. LL(1) gramatiky, výpočet množin FIRST a FOLLOW. Implementace syntaktického analyzátoru: Zásobníkový automat pro LL(1) jazyky. Analýza rekurzivním sestupem. Syntaktická analýza zdola nahoru: Zásobníkový automat pro LR(1) jazyky. Generátor yacc. Syntaxí řízený překlad: Překladová gramatika, atributová překladová gramatika. Implementace atributového překladu při analýze shora dolů. Atributy v generátoru yacc. Tabulka symbolů: Funkce tabulky symbolů. Model programovacího jazyka. Organizace tabulky symbolů. Blokově strukturovaná tabulka symbolů. Implementace. Struktura programu v době běhu: Systém řízení běhu programu. Podprogramy - aktivace, statická a dynamická struktura, aktivační záznam. Organizace paměti, přidělování paměti pro aktivační záznamy, přístupové ukazatele. Předávání parametrů do podprogramu. Vnitřní reprezentace: Formáty vnitřní reprezentace - graf, zásobníkový kód, tříadresový kód. Implementace tříadresového kódu. Překlad výrazů. Adresování prvků polí. Překlad booleovských výrazů. Optimalizace programu I: Druhy optimalizací. Reprezentace programů pro optimalizaci. Organizace optimalizujícího překladače. Graf toku řízení, základní blok, DAG. Základní optimalizace - algebraické optimalizace, odstranění mrtvého kódu, optimalizace cyklů. Lokální optimalizace cílového programu. Optimalizace programu II: Analýza toku dat, rovnice toku dat. Živé proměnné, dosahující definice, ud-řetězce, dostupné výrazy. Generování cílového programu: Vlastnosti cílového procesoru, algoritmus generátoru, generování ze čtveřic, přidělování registrů, formální metody a atributovaný překlad. Další vybrané problémy návrhu překladačů Cvičení: Reprezentace regulárních jazyků - gramatiky, automaty, regulární výrazy. Převody mezi reprezentacemi. Reprezentace bezkontextových jazyků - gramatiky, syntaktické diagramy, automaty. Návrh gramatiky pro základní jazykové konstrukce. Výpočty množin First, Follow a Select, test na LL(1). Vytvoření rozkladové tabulky pro LL(1) gramatiku. Činnost syntaktického analyzátoru LR(1). Návrh atributových gramatik - příklady. Návrh atributových překladových gramatik pro generování zásobníkového kódu. Optimalizační algoritmy, konstrukce DAG, topologické řazení. Algoritmy pro globální optimalizaci. Řešení konkrétních problémů spojených s projektem.

Conditions for subject completion

Full-time 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
2008/2009 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2007/2008 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2007/2008 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2007/2008 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2007/2008 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2007/2008 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2006/2007 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2006/2007 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2006/2007 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2006/2007 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2006/2007 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2006/2007 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2006/2007 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2005/2006 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2005/2006 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2005/2006 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2005/2006 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2005/2006 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2005/2006 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2005/2006 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2004/2005 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2004/2005 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2004/2005 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2004/2005 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2004/2005 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2004/2005 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2004/2005 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2003/2004 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2003/2004 (B2612) Electrical Engineering and Computer Science (1801R001) Computer Science P Czech Ostrava 4 Compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2002/2003 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2601T004) Measurement and Control Engineering P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2612T018) Electronics and Communication Technology P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (10) Elektrické stroje a přístroje P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (2642T004) Electrical Machines, Apparatus and Drives (20) Elektrické pohony a výkonová elektronika P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (3907T001) Electrical Power Engineering P Czech Ostrava Choice-compulsory study plan
2001/2002 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan
2000/2001 (M2612) Electrical Engineering and Computer Science (3902T023) Computer Science P Czech Ostrava 4 Compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner