456-0316/01 – Konstrukce překladačů (KPR)
| Garantující katedra | Katedra informatiky | Kredity | 6 |
| Garant předmětu | doc. RNDr. Petr Šaloun, Ph.D. | Garant verze předmětu | doc. RNDr. Petr Šaloun, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
| Ročník | 3 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2003/2004 | Rok zrušení | 2006/2007 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
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:
Doporučená literatura:
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
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.