Original title:
Paralelní syntaktická analýza
Translated title:
Parallel Parsing
Authors:
Holko, Maroš ; Regéciová, Dominika (referee) ; Meduna, Alexandr (advisor) Document type: Bachelor's theses
Year:
2019
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
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.
The goal of this bachelor thesis is to create and implement a parallel version of a Cocke-Younger-Kasami algorithm, which is used for syntactic analysis. This algorithm works with context-free grammars, so a big part of this work is dedicated to context-free grammars and their transformation to the Chomsky normal form. Output of this thesis is console application in C++ which use threads for parallel processing. There is also an extension for finding all rule successions for given input string designed and implemented. In the end there is a discussion about program's advantages and disadvantages.
Keywords:
C++; Chomsky normal form; CNF; Cocke-Younger-Kasami; compiler; context-free grammar; parallel CYK algorithm; rule succession; syntax analysis; bezkontextová gramatika; C++; Chomského normálna forma; CNF; Cocke-Younger-Kasami; paralelný CYK algoritmus; prekladač; rozbor pravidiel; syntaktická analýza
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/180580