|
|
Interactive Generator of Syntax of Heterogeneous Data Structures
Kotraš, Martin ; Janoušek, Vladimír (referee) ; Smrčka, Aleš (advisor)
Today, software systems are often composed of several components that transmit data through various communication channels. Despite the fact that there are a number of standardized data encoding formats, developers still create their own mostly with regard to the specific use of the software they create. One of the essential parts of quality verification or minimization of data transmission errors is the validation of input data. The first step to validation is to formalize a language describing data structures. The most general formalism for these purposes is the grammar of the language in the standard description, e.g. BNF, ABNF, or EBNF. However, creating a language-specific grammar can be a step that is sensitive to error for an inexperienced developer. The aim of this project is a simple application for creating grammar from a sample of data. The work solves the generation of grammar and validation code snippets from the sample string of the language, e.g. the source code of the programming language. The user solves the problem by sequentially marking parts of the uploaded string, naming them, and assigning properties to them. This is aided by tools for splitting rules, merging rule prefixes and/or suffixes, creating lists, and optimizing the resulting rules. As part of the work, a single-page web application was created, which was able to pass relatively well when tested on JSON and XML, and it was possible to create a more general grammar despite the problems with a weak parser. Thanks to this work, even less experienced users can create more general grammars of their strings and use them for validation purposes. In addition, the work provides a basis for further research in this area and is open to further improvement.
|
|
|
Semi-Parallel Deep Pushdown Transducers and Their Applications
Putala, Marek ; Dolejška, Daniel (referee) ; Meduna, Alexandr (advisor)
The goal of this work was to become familiar with deep stack automata and, based on the acquired knowledge, to further design, formally define and implement a partially parallel deep stack transducer. It is an extension of deep stack transducer that is capable of accessing non-terminal symbols simultaneously on the stack in one step. With a suitably chosen configuration in the form of rules, they can process the input string with fewer transitions and therefore have a higher speed compared to deep stack transducer.
|
|
|
Parsing Based on Grammar Systems
Sedmík, Adam ; Klobučníková, Dominika (referee) ; Meduna, Alexandr (advisor)
This thesis is focused on grammar systems and syntax analysis. Thesis introduces cooperating distributed and parallel communicating grammar systems. Based on knowledge of grammar systems, new grammar system is introduced. This grammar system focuses on modularization of syntax analysis. Shown are two methods of syntax analysis, recursive descent parsing and precedence parsing. Grammar systems introduced are demonstrated on syntax analysis of custom programming language.
|
|
|
Interactive Generator of Syntax of Heterogeneous Data Structures
Kotraš, Martin ; Janoušek, Vladimír (referee) ; Smrčka, Aleš (advisor)
Today, software systems are often composed of several components that transmit data through various communication channels. Despite the fact that there are a number of standardized data encoding formats, developers still create their own mostly with regard to the specific use of the software they create. One of the essential parts of quality verification or minimization of data transmission errors is the validation of input data. The first step to validation is to formalize a language describing data structures. The most general formalism for these purposes is the grammar of the language in the standard description, e.g. BNF, ABNF, or EBNF. However, creating a language-specific grammar can be a step that is sensitive to error for an inexperienced developer. The aim of this project is a simple application for creating grammar from a sample of data. The work solves the generation of grammar and validation code snippets from the sample string of the language, e.g. the source code of the programming language. The user solves the problem by sequentially marking parts of the uploaded string, naming them, and assigning properties to them. This is aided by tools for splitting rules, merging rule prefixes and/or suffixes, creating lists, and optimizing the resulting rules. As part of the work, a single-page web application was created, which was able to pass relatively well when tested on JSON and XML, and it was possible to create a more general grammar despite the problems with a weak parser. Thanks to this work, even less experienced users can create more general grammars of their strings and use them for validation purposes. In addition, the work provides a basis for further research in this area and is open to further improvement.
|
|
|
Parallel Parsing
Holko, Maroš ; Regéciová, Dominika (referee) ; Meduna, Alexandr (advisor)
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.
|
|
|
Finite State Grammars and Language Models for Automatic Speech Recognition
Beneš, Karel ; Glembek, Ondřej (referee) ; Hannemann, Mirko (advisor)
Tato práce se zabývá transformací bezkontextových gramatik na váhované konečně stavové převodníky. Je vybrána podmnožina bezkontextových gramatik, kterou lze tranformovat přesně. Je představen test, zda daná gramatika naleží do této podmnožiny, i algoritmus převodu. Dále je popsán vlastní nástroj, který tyto postupy implementuje, včetně způsobu zpracování vstupu a výstupu. S použitím toho nástroje byl vytvořen systém rozpoznání řeči pro kokpit letadla. Jsou představeny výsledky ukazující, že systém založený na takto získaném modelu jazyka podává výrazně lepší výkon, než je dosažen při použití obecného modelu.
|
|
|
Syntactic Analysis Based on Matrix Grammar
Brindza, Dominik ; Horáček, Petr (referee) ; Zámečníková, Eva (advisor)
The subject of this thesis is to develop a method of syntactic analysis based on matrix grammar s. In its theoretical part we provide various analytical aspects for this type of regulated grammar in order to reveal the common background as well as search for similarities with the classical context-free grammars which we will then be able to benefit from in the practical part. Our goal is to extend the well-known predictive method of syntactic analysis to further accept a wider spectrum of formal languages - some of the context-sensitive ones which we are able to generate using our matrix grammars. Besides this main effort we also present some experimental algorithms and suggestions hich could be used in further research of this project.
|
|
|
Parsing Based on Programmed Grammars
Pačes, Jan ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This thesis is researching methods of parsing based on programmed grammars. It modifies known algorithm of table driven non-recursive predictive parser for context-free grammars and applies it on programmed grammars. It studies strength of this method, focusing on some languages which are not context-free.
|
|
|
Transformation of Grammars into Normal Forms
Klapuchová, Mirka ; Koutný, Jiří (referee) ; Zemek, Petr (advisor)
This thesis deals with issues of normal forms from theory of formal languages. Basic terms from this area are listed here, different types of grammars as well and especially normal forms and algorithms that transfer grammars into normal forms. Description of design and implementation of program which is used to transfer input grammar into entered normal form is included.
|
|
|
Parsing Based on Deep Pushdown Automata
Senko, Jozef ; Vrábel, Lukáš (referee) ; Solár, Peter (advisor)
This thesis is concerning with syntax analysis based on deep pushdown automata. In theoretical part are defined themselves deep pushdown automata, all the necessary theoretical concepts and then is discussed the implementation of these deep pushdown automata embedded in the educational program for students.
|
guest ::
