Detail práce

Paralelní syntaktická analýza

Bakalářská práce Student: Holko Maroš Akademický rok: 2018/2019 Vedoucí: Meduna Alexander, prof. RNDr., CSc.
Název anglicky
Parallel Parsing
Jazyk práce
český
Abstrakt

Práca sa zaoberá štúdiom niekoľkých metód syntaktickej analýzy, obzvlášť najmä Cocke-Younger-Kasami algoritmu. Ďalej je navrhnutý spôsob paralelizácie tohto algoritmu a jeho implementácia v jazyku C++. Na dosiahnutie paralelizácie boli použité vlákna. S prácou bola vytvorená aj konzolová aplikácia, v ktorej bol implementovaný paralelný CYK algoritmus. Zároveň bolo navrhnuté a implementované rozšírenie, ktoré zisťuje všetky postupnosti použitých pravidiel v prípade, že vstupný reťazec patrí do danej gramatiky. V závere sú diskutované jeho prednosti a nedostatky.

Klíčová slova

syntaktická analýza, prekladač, Cocke-Younger-Kasami, paralelný CYK algoritmus, Chomského normálna forma, CNF, bezkontextová gramatika, rozbor pravidiel, C++

Ústav
Ústav informačních systémů FIT VUT v Brně
Studijní program
Informační technologie
Soubory
Stav
obhájeno, hodnocení C
Obhajoba
11. června 2019
Oponent
Regéciová Dominika, Ing.
Průběh obhajoby

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm "C".

Otázky u obhajoby

1. Stručně zdůvodněte výběr CYK algoritmu a případně uveďte, zda znáte další algoritmus pro syntaktickou analýzu, který by bylo možné paralizovat.
2. Uveďte, jaký je největší možný počet vláken během běhu programu (bez omezení na současný běh). Lze tento počet ještě optimalizovat?

Komise
Kolář Dušan, doc. Dr. Ing. (UIFS FIT VUT), předseda
Bařina David, Ing., Ph.D. (UPGM FIT VUT), člen
Hrubý Martin, Ing., Ph.D. (UITS FIT VUT), člen
Kořenek Jan, doc. Ing., Ph.D. (UPSY FIT VUT), člen
Zendulka Jaroslav, doc. Ing., CSc. (UIFS FIT VUT), člen
Citace
HOLKO, Maroš. Paralelní syntaktická analýza. Brno, 2019. Bakalářská práce. Vysoké učení technické v Brně, Fakulta informačních technologií. 2019-06-11. Vedoucí práce Meduna Alexander. Dostupné z: https://www.fit.vut.cz/study/thesis/21000/
BibTeX 
@bachelorsthesis{FITBT21000,
    author = "Maro\v{s} Holko",
    type = "Bakal\'{a}\v{r}sk\'{a} pr\'{a}ce",
    title = "Paraleln\'{i} syntaktick\'{a} anal\'{y}za",
    school = "Vysok\'{e} u\v{c}en\'{i} technick\'{e} v Brn\v{e}, Fakulta informa\v{c}n\'{i}ch technologi\'{i}",
    year = 2019,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/21000/"
}

Závěrečné práce

Nahoru