Thesis Details

Sekvenční a paralelní gramatiky: vlastnosti a aplikace

Master's Thesis Student: Klobučníková Dominika Academic Year: 2018/2019 Supervisor: Meduna Alexander, prof. RNDr., CSc.
English title
Sequential and Parallel Grammars: Properties and Applications
Language
Czech
Abstract

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

syntax analysis, normal form, Kuroda, Penttonen, Chomsky, 2-limited, context-sensitive grammar, scattered context grammar, multigenerative grammar system, L-system, Cocke-Younger-Kasami, Cocke-Kasami-Younger, CYK, CKY

Department
Department of Information Systems FIT BUT
Degree Programme
Information Technology, Field of Study Information Systems
Files
Status
defended, grade A
Date
18 June 2019
Reviewer
Martiško Jakub, Ing.
Committee
Zendulka Jaroslav, doc. Ing., CSc. (DIFS FIT BUT), předseda
Balík Miroslav, Ing., Ph.D. (FIT CTU), člen
Bartík Vladimír, Ing., Ph.D. (DIFS FIT BUT), člen
Burget Radek, doc. Ing., Ph.D. (DIFS FIT BUT), člen
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT), člen
Orság Filip, Ing., Ph.D. (DITS FIT BUT), člen
Citation
KLOBUČNÍKOVÁ, Dominika. Sekvenční a paralelní gramatiky: vlastnosti a aplikace. Brno, 2019. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2019-06-18. Supervised by Meduna Alexander. Available from: https://www.fit.vut.cz/study/thesis/21128/
BibTeX 
@mastersthesis{FITMT21128,
    author = "Dominika Klobu\v{c}n\'{i}kov\'{a}",
    type = "Master's thesis",
    title = "Sekven\v{c}n\'{i} a paraleln\'{i} gramatiky: vlastnosti a aplikace",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2019,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/21128/"
}

Theses

Back to top