Detail předmětu

Vybraná témata z analýzy a překladu jazyků

FIT-APDAk. rok: 2023/2024

Předmět diskutuje vybraná pokročilá témata z analýzy a překladu jazyků. Soustřeďuje se především na nejmodernější výsledku z této oblasti, přičemž si všímá i témat již známých, ale často opomíjených pro svou náročnost. Detailně je prezentována jak teorie spojená s tématem, tak i praktická programová realizace.  Získání a porozumění prezentovaných poznatků je ověřeno zpracováním vlastní tvůrčí tématické práce studenta.

Okruhy otázek k SDZ

  1. LL(k) jazyky a jejich způsoby syntaktické analýzy.
  2. Syntaktická analýza LR a LALR jazyků, tvorba rozkladové tabulky.
  3. Sémanticky a kontextově závislá lexikální analýza.
  4. Atributované gramatiky a jejich využití při analýze formálních jazyků.
  5. Gramatiky s rozptýleným kontextem a jejich varianty a vzájemný vztah, vlastnosti.
  6. Vztah gramatik s rozptýleným kontextem a jejich variant k Chomského hierarchii formálních jazyků.
  7. Řízené zásobníkové automaty, deterministické varianty, vztah k TS.
  8. LL gramatiky s rozptýleným kontextem jako vstup pro analýzu formálních jazyků, konstrukce řízeného zás. automatu.
  9. Praktická implementace analyzátoru založeného na gramatikách s rozptýleným kontextem - varianty, optimalizace, omezení.
  10. Role priorit a atributů u zpracování formálních jazyků s využitím LL gramatik s rozptýleným kontextem.

Jazyk výuky

čeština

Garant předmětu

doc. Dr. Ing. Dušan Kolář

Zajišťuje ústav

Ústav informačních systémů (UIFS)

Vstupní znalosti

formální jazyky a automaty, základy překladačů, teorie grafů, vyčíslitelnost a složitost

Pravidla hodnocení a ukončení předmětu

Několik referátů na vybrané téma, řešení projektu (konstrukce specifikovaného překladače či analyzátoru danými technikami).

Učební cíle

Rozšířit a prohloubit teoretické znalosti z oblasti analýzy a překladu jazyků do oblastí méně známých, nebo zcela opomíjených, nezřídka však založených na výsledcích základního výzkumu prováděného na FIT a poskytujících nové možnosti, a jejich provázání s praktickou realizací programového vybavení pro dané účely.

Teoretické i praktické znalosti a dovednosti z konstrukce překladačů a analýzy jazyků založené na pokročilých a nových technologiích.

Doporučená literatura

Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, Second Edition, Addison Wesley, Pearson, 2007, ISBN 0-321-48681-1.
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling, Volume I: Parsing, Prentice-Hall, Inc., 1972, ISBN 0-13-914556-7.
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation,and Compiling, Volume II: Compiling, Prentice-Hall, Inc., 1972,ISBN 0-13-914564-8.
Kolář Dušan, Meduna Alexander: Regulated Automata: From Theory towards Applications, In: Proceeding of 8th International Conference on Information Systems Implementation and Modelling ISIM'05, Ostrava, CZ, MARQ, 2005, s. 33-48, ISBN 80-86840-09-3.
Přednášky

Zařazení předmětu ve studijních plánech

  • Program DIT doktorský 0 ročník, zimní semestr, povinně volitelný
  • Program DIT doktorský 0 ročník, zimní semestr, povinně volitelný
  • Program DIT-EN doktorský 0 ročník, zimní semestr, povinně volitelný
  • Program DIT-EN doktorský 0 ročník, zimní semestr, povinně volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

  • Program VTI-DR-4 doktorský

    obor DVI4 , 0 ročník, zimní semestr, volitelný

Typ (způsob) výuky

 

Přednáška

39 hod., nepovinná

Vyučující / Lektor

doc. Dr. Ing. Dušan Kolář

Osnova

  1. Úvod - rekapitulace, LL(1) jazyky a jejich analýza.
  2. LL(k) jazyky.
  3. Způsoby zpracování LL(k) jazyků.
  4. SLR jazyky.
  5. LR a LALR jazyky - I.
  6. LR a LALR jazyky - II.
  7. Sémanticky závislá lexikální analýza.
  8. Atributy, jejich role a zpracování.
  9. Gramatiky s rozptýleným kontextem a jejich LL varianta.
  10. Řízené zásobníkové automaty.
  11. Kontextové jazyky a jejich zpracování.
  12. LL gramatiky s rozptýleným kontextem a jejich analýza řízenými zásobníkovými automaty.
  13. Vybrané kapitoly z optimalizací.

Konzultace v kombinovaném studiu

26 hod., nepovinná

Vyučující / Lektor

doc. Dr. Ing. Dušan Kolář

Projekt

13 hod., povinná

Vyučující / Lektor

doc. Dr. Ing. Dušan Kolář

Osnova

  1. Tématicky orientovaná práce z oblasti analýzy jazyků spjatá s tématem disertační práce studenta.
  2. Programové vybavení z oblasti překladačů založené na pokročilé technologii, která je prezentována v přednáškách.