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