Bachelor's Thesis

Parsing Based on Several Grammars

Final Thesis 2.14 MB Appendix 1.33 MB

Author of thesis: Daniel Ulvr

Acad. year: 2025/2026

Supervisor: prof. RNDr. Alexandr Meduna, CSc.

Reviewer: Ing. Martin Havel

Abstract:

This thesis deals with the application of CD grammar systems in the field of syntax analysis. Within the thesis, a new type of CD grammar system controlled by a communication table is introduced. The thesis also presents an algorithm for constructing this communication table for deterministic parsing. Subsequently, a specific grammar system of the introduced type is designed, and a parser is implemented for it, combining three parsing methods: LL parsing, operator-precedence parsing, and SLR parsing. The implemented parser allows the selection of the parsing method used for individual components of the grammar system independently of one another. This is made possible by the control via the communication table and by the modularity of the system's components. The applicability of the introduced type of CD grammar system in syntax analysis is thus demonstrated in practice.

Keywords:

grammar systems, CD grammar systems, communication table, syntax analysis, LL parsing, recursive descent, operator-precedence parsing, SLR parsing, parser

Date of defence

19.06.2026

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

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

Topics for thesis defence

  1. Jaké výhody a nevýhody má vámi navrhnutá syntaktická analýza oproti zavedeným?
  2. Srovnejte vyjadřovací sílu vašeho CD systému rozšířeného o tabulku se standardně definovanými CD systémy.
  3. Algoritmus jsme vymyslel nebo převzal? Jsou v něm nějaké další podmínky?

Language of thesis

Czech

Faculty

Fakulta informačních technologií

Department

Department of Information Systems

Study programme

Information Technology (BIT)

Composition of Committee

prof. RNDr. Alexandr Meduna, CSc. (předseda)
prof. Ing. Martin Čadík, Ph.D. (místopředseda)
Ing. Jaroslav Rozman, Ph.D. (člen)
Ing. Zbyněk Křivka, Ph.D. (člen)
Ing. Lukáš Kekely, Ph.D. (člen)

Supervisor’s report
prof. RNDr. Alexandr Meduna, CSc.

Sumarizujme:


Nad rámec zadání student implementoval navíc lexikální analýzu a generování AST pro následnou vizualizaci. V rámci syntaktické analýzy byl implementován i SLR analyzátor, to však považuji za součást zadání, stejně jako výpis informací o analýze do konzole při běhu analýzy a možnost výběru typu použité analýzy pro každou komponentu GS. S prací se mu podařilo dostat na konferenci Excel@FIT. Práce byla dokončena v předstihu.


Na bázi těchto pozitivních aspektů si dovoluji inspirovat komisi ke zvážení vhodné ceny předložené BP, např cenu děkana.

Evaluation criteria Verbal classification
Informace k zadání

Tato práce byla vypracována dle uvedeného tématu a postupu. Byla velmi náročná, neboť vyžadovala studium cizojazyčné literatury a zavést zcela nové koncepty a dokázat rigorózně nové výsledky. Práce překročila zadání signifikantně.
Práce s literaturou

Při získávání a využívání studijních materiálů k řešení práce byl student velmi aktivní.
Aktivita během řešení, konzultace, komunikace

Student se mnou komunikoval pravidelně osobně i elektronicky. V některých týdnech jsme komunikovali až čtyřikrát. Pracoval extrémně intenzivně.
Aktivita při dokončování

Práce byla dokončena v obrovském předstihu a její obsah byl konzultován naprosto detailně.
Publikační činnost, ocenění

Ano. Excel@FIT 2026.
Points proposed by supervisor: 98

Grade proposed by supervisor: A

Reviewer’s report
Ing. Martin Havel

Zavedený formální model i jeho aplikace v překladačích jsou velmi nadprůměrné a zajímavé. Kvůli nižší prezentační úrovni technické zprávy navrhuji hodnocení velmi dobře (B).

Evaluation criteria Verbal classification Points
Náročnost zadání

Evaluation level: obtížnější zadání

Obtížnost zadání spočívala v nutnosti pochopení pokročilých modelů formálních jazyků, které jsou běžně probírány až v rámci doktorského studia, a jejich využití v překladačích.
Prezentační úroveň technické zprávy

Celkově je logická struktura práce v pořádku. Přínos sekce 2.3 je pro práci nulový. Definice jsou v pořádku, ovšem v textu návazném na definice se vyskytuje několik chyb a nepřesností. Jako příklad chyby uvádím tvrzení ze strany 11, že konečný automat má vždy několik koncových stavů, a příklad nepřesnosti ze strany 13, tvrzení, že zásobníkový automat má 2 hlavy. Práce obsahuje několik překlepů na kritických místech. Například na straně 9 autor nazývá pravě lineární gramatiky pravé lineární. 

 67
Formální úprava technické zprávy

Práce po typografické stránce obsahuje na několika místech přetečení (například na straně 52). Po jazykové stránce je práce v pořádku a počet gramatických chyb je v normě.

 85
Realizační výstup

Implementace realizačního výstupu má dobrou kvalitu a kód je řádně komentovaný. Realizační výstup obsahuje značné rozšíření oproti zadání.

 95
Využitelnost výsledků

Práce nabízí alternativní překladač s možností návaznosti dalšího výzkumu pro jiné gramatické systémy.
Rozsah splnění požadavků zadání

Evaluation level: zadání splněno

Zadání splněno ve všech bodech.
Rozsah technické zprávy

Evaluation level: je v obvyklém rozmezí

Rozsah práce je na horní hranici obvyklého rozmezí.
Práce s literaturou

Práce obsahuje 19 zdrojů. Zdroje jsou vhodně zvolené a většinou adekvátně použité.

 80
Topics for thesis defence:
  1. Jaké výhody a nevýhody má vámi navrhnutá syntaktická analýza oproti zavedeným?
  2. Srovnejte vyjadřovací sílu vašeho CD systému rozšířeného o tabulku se standardně definovanými CD systémy.
Points proposed by reviewer: 80

Grade proposed by reviewer: B

Responsibility: Mgr. et Mgr. Hana Odstrčilová