|
Regulated Grammar Systems
Tomko, Martin ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
Práce poskytuje přehled základů teorie formálních jazyků, regulovaných gramatik a analýzy LL(1) jazyků. Je zde navržen a analyzován algoritmus pro analýzu programovaných gramatik, inspirován LL(1) analyzátorem. Třída jazyků přijímaná tímto algoritmem je striktní nadtřídou LL(1) jazyků, obsahující některé jazyky, které nejsou bezkontextové. Tato třída se však jeví být neporovnatelná s třídou bezkontextových jazyků.
|
|
Advanced Parser Generators
Havranek, Daniel ; Kövári, Adam (referee) ; Křivka, Zbyněk (advisor)
This bachelor thesis deals with parser generation by tools that use advanced parsing techniques. These techniques are compared from both theoretical and practical point of view. The GNU Bison tool, which uses the LALR(1) method and Generalized LR method, and the ANTLR tool, which uses the more modern ALL(*) method, are examined in detail. To compare the effectiveness of these tools, a parser for a fictional programming language is implemented using them to demonstrate the strengths and weaknesses of each approach. As the results, GNU Bison is much more powerful, but the ANTLR outweighs it in terms of implementation friendliness and functionality. The results of this thesis can help deciding which approach or tool to choose when implementing a parser.
|
|
Robust Parsing of Noisy Content
Daiber, Joachim ; Zeman, Daniel (advisor) ; Mareček, David (referee)
While parsing performance on in-domain text has developed steadily in recent years, out-of-domain text and grammatically noisy text remain an obstacle and often lead to significant decreases in parsing accuracy. In this thesis, we focus on the parsing of noisy content, such as user-generated content in services like Twitter. We investigate the question whether a preprocessing step based on machine translation techniques and unsupervised models for text-normalization can improve parsing performance on noisy data. Existing data sets are evaluated and a new data set for dependency parsing of grammatically noisy Twitter data is introduced. We show that text-normalization together with a combination of domain-specific and generic part-of-speech taggers can lead to a significant improvement in parsing accuracy. Powered by TCPDF (www.tcpdf.org)
|
|
Parsing for ET0L Systems
Kožár, Tomáš ; Klobučníková, Dominika (referee) ; Meduna, Alexandr (advisor)
This thesis focuses on deciding the membership of strings in languages generated by ET0L systems. It is achieved by designing two algorithms. The first one is a modification of the existing algorithm Cocke-Younger-Kasami for syntax analysis of context-free grammars in Chomsky normal form. This modification takes into account different properties of ET0L systems compared to context-free grammars. Specifically, the parallel application of production rules and multiple tables of these production rules. Also, used normal form is different from Chomsky normal form since CNF is unfit for ET0L systems. The second designed algorithm works in a top-down manner and gradually generates all valid strings. The resulting algorithms are tested, demonstrated, and fully functional. The contributions of this thesis are two new algorithms for syntax analysis of ET0L systems.
|
|
Parsing Based on Automata with Deep Pushdowns
Pločicová, Dominika ; Dvořák, Tomáš (referee) ; Meduna, Alexandr (advisor)
Language is a basic means of communication. Formal languages provide the basis for human-computer communication. The aim of this work is to contribute to this area and analyze the possibility of processing the context-sensitive elements of formal languages. The work includes the theoretical description of state grammar and deep pushdown automaton, which is a model of a parser for languages including context-sensitive elements. It describes an algorithm that can convert the state grammar to the said deep pushdown automaton. The work further describes parsing, its methods and the use of the created automaton in performing the syntax analysis. For a better understanding, the work also includes examples of the creation and operation of the automaton. Finally, the work describes the implementation of a program that performs theoretically described activities. The functionality of the program was verified on examples, whose inputs and outputs are also part of the text of the work.
|
|
Syntaktická analýza textů se střídáním kódů
Ravishankar, Vinit ; Zeman, Daniel (advisor) ; Mareček, David (referee)
(English) Vinit Ravishankar July 2018 The aim of this thesis is twofold; first, we attempt to dependency parse existing code-switched corpora, solely by training on monolingual dependency treebanks. In an attempt to do so, we design a dependency parser and ex- periment with a variety of methods to improve upon the baseline established by raw training on monolingual treebanks: these methods range from treebank modification to network modification. On this task, we obtain state-of-the- art results for most evaluation criteria on the task for our evaluation language pairs: Hindi/English and Komi/Russian. We beat our own baselines by a sig- nificant margin, whilst simultaneously beating most scores on similar tasks in the literature. The second part of the thesis involves introducing the relatively understudied task of predicting code-switching points in a monolingual utter- ance; we provide several architectures that attempt to do so, and provide one of them as our baseline, in the hopes that it should continue as a state-of-the-art in future tasks. 1
|
|
Regulated Grammar Systems
Tomko, Martin ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
Práce poskytuje přehled základů teorie formálních jazyků, regulovaných gramatik a analýzy LL(1) jazyků. Je zde navržen a analyzován algoritmus pro analýzu programovaných gramatik, inspirován LL(1) analyzátorem. Třída jazyků přijímaná tímto algoritmem je striktní nadtřídou LL(1) jazyků, obsahující některé jazyky, které nejsou bezkontextové. Tato třída se však jeví být neporovnatelná s třídou bezkontextových jazyků.
|
|
Parsing Based on Deep Pushdown Automata Systems
Šoustar, Jakub ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis investigates deep pushdown automata and introduces their modification called controlled deep pushdown automata. Distributed deep pushdown automata systems and parallel communicating deep pushdown automata systems are described. Their accepting power and properties are investigated and several variants are introduced. This thesis proves that the accepting power of one such variant of parallel communicating deep pushdown automata systems is equal to the accepting power of Turing machines. A method for syntactical analysis based on the previously introduced automata systems is described.
|
|
Advanced Error Recovery during Bottom-Up Parsing
Regéciová, Dominika ; Kolář, Dušan (referee) ; Meduna, Alexandr (advisor)
This bachelor thesis deals with advanced methods for error recovery during bottom-up parsing. It describes and compares methods with the modified grammar FUN. It creates a web-based interface, Project Alan, where chosen methods are implemented for the simulation of error recovery process. The author also added her own method and she compared it with others.
|
|
Robust Parsing of Noisy Content
Daiber, Joachim ; Zeman, Daniel (advisor) ; Mareček, David (referee)
While parsing performance on in-domain text has developed steadily in recent years, out-of-domain text and grammatically noisy text remain an obstacle and often lead to significant decreases in parsing accuracy. In this thesis, we focus on the parsing of noisy content, such as user-generated content in services like Twitter. We investigate the question whether a preprocessing step based on machine translation techniques and unsupervised models for text-normalization can improve parsing performance on noisy data. Existing data sets are evaluated and a new data set for dependency parsing of grammatically noisy Twitter data is introduced. We show that text-normalization together with a combination of domain-specific and generic part-of-speech taggers can lead to a significant improvement in parsing accuracy. Powered by TCPDF (www.tcpdf.org)
|