Original title: Sekvenční a paralelní gramatiky: vlastnosti a aplikace
Translated title: Sequential and Parallel Grammars: Properties and Applications
Authors: Klobučníková, Dominika ; Martiško, Jakub (referee) ; Meduna, Alexandr (advisor)
Document type: Master’s theses
Year: 2019
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Táto práca sa zaoberá problematikou sekvenčných a paralelných gramatík. Obe skupiny zastrešujú veľké množstvo gramatických tried, väčšina ktorých však nemá veľké uplatnenie kvôli komplikáciám spojeným s ich spracovaním. Práca skúma niektoré takéto gramatiky, ako napríklad gramatiky s rozptýleným kontextom, multigeneratívne gramatické systémy a interaktívne L-systémy s dôrazom na ich normálne formy. Práca následne predstavuje niekoľko algoritmov využívajúcich vlastnosti týchto gramatík, ako aj ich normálnych foriem. Tieto algoritmy sú založené na algoritme Cocke-Younger-Kasami pre bezkontextové gramatiky a dokážu spracovať ľubovoľnú gramatiku v príslušnej normálnej forme. Posledná časť práce predstavuje program implementujúci navrhnuté algoritmy. This thesis deals with the topic of sequential and parallel grammars. Both of these groups cover a large number of grammar families, most of which, however, are not widely used because of the difficulties related to their processing. The thesis examines some of these grammar types, such as scattered-context grammars, multigenerative systems, and interactive L-systems, with focus on their normal forms. Subsequently, it introduces a set of algorithms utilising properties of the discussed grammar types as well as their normal forms. These algorithms are based on the Cocke-Younger-Kasami algorithm for context-free grammars, and are capable of parsing any grammar in the corresponding normal form. Finally, a program implementing the proposed algorithms is presented.
Keywords: 2-limited; Chomsky; CKY; Cocke-Kasami-Younger; Cocke-Younger-Kasami; context-sensitive grammar; CYK; Kuroda; L-system; multigenerative grammar system; normal form; Penttonen; scattered context grammar; syntax analysis; 2-obmedzená (2-limited); Chomsky; CKY; Cocke-Kasami-Younger; Cocke-Younger-Kasami; CYK; gramatika s rozptýleným kontextom; kontextová gramatika; Kuroda; L-systém; multigeneratívny gramatický systém; normálna forma; Penttonen; syntatická 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/180329

Permalink: http://www.nusl.cz/ntk/nusl-403110


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses