456-0063/01 – Úvod do překladačů (UDP)

Garantující katedraKatedra informatikyKredity8
Garant předmětuIng. Marek Běhálek, Ph.D.Garant verze předmětuIng. Marek Běhálek, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník4Semestrzimní
Jazyk výukyčeština
Rok zavedení1992/1993Rok zrušení2010/2011
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
BEH01 Ing. Marek Běhálek, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Předmět si klade za cíl pochopení základních principů činnosti překladače, jeho struktury, metod návrhu a implementace. Po absolvování předmětu dokážou studenti navrhnout a implementovat interpret jednoduchého programovacího jazyka. Po absolvování předmětu bude student schopen popsat strukturu a principy činnosti jednotlivých modulů překladače a dokáže implementovat analyzátor jednoduchého programovacího jazyka přímo nebo s použitím podpůrných nástrojů.

Vyučovací metody

Anotace

Cílem předmětu je získání základní představy o konstrukci všech základních částí kompilačních i interpretačních překladačů.

Povinná literatura:

Aho, A. V., Sethi, R., Ullman, J. D.: Compilers. Principles, Techniques, and Tools. Addison-Wesley, 1987. Češka, M., Beneš. M., Hruška, T.: Překladače. Skriptum FEI VUT Brno, 1993.

Doporučená literatura:

Forma způsobu ověření studijních výsledků a další požadavky na studenta

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

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

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.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 1960/1961 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2008/2009 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (B2612) Elektrotechnika a informatika (1801R001) Informatika P čeština Ostrava 4 povinný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán
2000/2001 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 4 povinný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku