456-0316/01 – Konstrukce překladačů (KPR)

Garantující katedraKatedra informatikyKredity6
Garant předmětudoc. RNDr. Petr Šaloun, Ph.D.Garant verze předmětudoc. RNDr. Petr Šaloun, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
Ročník3Semestrzimní
Jazyk výukyčeština
Rok zavedení2003/2004Rok zrušení2006/2007
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 2+2

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

Praktické zvládnutí implementace překladače i doplnění teoretických znalostí z překladačů.

Vyučovací metody

Anotace

Kurs se zaměřuje na teoretické prohloubení základů překladu diskutovaných v bakalářském kursu PJP. Teoretické znalosti studentů rozšiřuje o pokročilá a doplňující témata, která svou náročností bakalářský kurs PJP překračují. Součástí cvičení je zadání a řešení samostatné práce na téma konstrukce překladače podmnožiny zadaného jazyka s využitím dostupných prostředků pro automatizaci návrhu.

Povinná literatura:

Sylaby přednášek Melichar, Češka, Ježek, Richta: Konstrukce překladačů. Vydavatelství ČVUT, Praha, 1999, ISBN 80-01-02028-2 Češka, Beneš, Hruška: Překladače. Skriptum VUT Brno, 1993. Melichar: Překladače. Skriptum ČVUT Praha, 1989.

Doporučená literatura:

Wilhelm, Maurer: Compiler design. Addison-Wesley, 1995. ISBN 0-201-42290-5 Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Compilers : Principles, Techniques, and Tools. ISBN: 0201100886 Sylaby přednášek. Eletronické výukové materiály: HTML, JavaScript, Java applety, a Macromedia Flash simulace.

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

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 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.

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

Kombinovaná 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.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán

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

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