|
|
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.
|
|
|
A LaTex Interpreter Based on a Combination of Several Parsing Methods
Lebeda, Petr ; Techet, Jiří (referee) ; Meduna, Alexandr (advisor)
The diploma thesis discusses the potential of interpretation of typographical language LATEX and describes the structure of this language, its functions and their syntax. Also it analyses possibilities of LaTeX interpretation into HTML (HyperText Markup Language), in order to create typographically accurate publications, which could be viewed by common web browser. The solution concept and outlines of possible problems follows.
|
|
|
Regulated Syntax-Directed Translation
Dvořák, Tomáš ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis deals with formal and syntax directed translation. This thesis contains theoretical part, which defines regular, context free, context sensitive and recursively enumerable languages a grammar. There are given examples of grammars which are able to generate languages that are not context free. Covered by this thesis are matrix grammars, random context grammars and programed grammars. Researched are also finite, pushdown, deep and regular automata, transducers and their part within format syntax directed translation. This project also defines regular transducers based as regulated automata. Thesis defines regulated methods of syntax analysis based on predictive parsers. These methods cover analysis of studied regulated grammars. The final part of this thesis describes new language capable of effective description of these grammars and compiler producing parser code for these grammars written in this new language and their graphical analyzer.
|
|
|
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.
|
|
|
Sequential and Parallel Grammars: Properties and Applications
Klobučníková, Dominika ; Martiško, Jakub (referee) ; Meduna, Alexandr (advisor)
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.
|
|
|
New Versions of Pushdown Automata
Genčúrová, Ľubica ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis investigates multi pushdown automata and introduces their new modifications based on deep pushdown. The first modification is Input driven multi deep pushdown automata, which has several deep pushdown lists and the current input symbol determines whether the automaton performs a push operation, a pop operation, an expansion operation or does not touch the stack. The second introduced modification is Regulated pushdown automata by deep pushdown. In addition to ordinary pushdowns, this version contains deep pushdown, which is used to generate the control language. This thesis proves, that the acceptance power of the described variants is equal to the accepting power of Turing machines. This thesis also contains view on program realisation of theoretical models, which were described in the theoretical part and introduces a library for the syntax analysis, which is based on it.
|
|
|
General Grammars: Normal Forms with Applications
Klobučníková, Dominika ; Krčmář, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis deals with the topic of unrestricted grammars, normal forms, and their applications. It focuses on context-sensitive grammars as their special cases. Based on the analysis of the set, an algorithm was designed using the principles of the Cocke-Younger-Kasami algorithm to make a decision of whether an input string is a sentence of a context-sensitivegrammar. The final application, which implements this algorithm, works with context-sensitive grammars in the Penttonen normal form.
|
|
|
Translation Grammars: Properties and Applications
Vít, Radek ; Krčmář, Radim (referee) ; Meduna, Alexandr (advisor)
The goal of this thesis is to discuss translation grammars and their use in syntax-driven translation. It provides an example of the use of translation grammars in predictive top-down translation and provides formal devices for language accepting and translation output generation. It examines the descriptional complexity of tranlation grammars as language generating devices. An implementation of a translation framework using these devices is described and a simple compiler is designed and implemented using this framework. This compiler translates a new language REON designed in this paper to Python 3.
|
|
|
Grammar Systems and Syntax-Directed Translation Based on Them
Handlíř, Jaroslav ; Martiško, Jakub (referee) ; Meduna, Alexandr (advisor)
The thesis examines the theory of formal languages in the field of context-free grammars. It focuses mainly on the possibilities and models of collaborating grammars to solve a common problem. In this context, it presents grammatical systems that have been designed as a formal means for describing distributed and parallel processing. After introducing to the problematics, the thesis focuses on the practical use of these mechanisms in the translation controlled syntax, and therefore the second part of the thesis deals with the implementation of a dynamic syntactic analyzer that uses more grammars during the analysis. With respect to the greatest user friendliness and the possible didactic use, the application is implemented using modern web technologies HTML5, JavaScript, AngularJS, CSS3, LESS and more.
|
|
|
A General Generator of Syntax Directed Translation
Marcin, Juraj ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
This thesis is dedicated to the design and creation of generic generator that performs syntax directed translation according to user requirements. The translation is processing in the time of analysis of the source program. Parser is based on bottom-up parsing. The result of the translation is the creation of syntax tree. From this syntax tree are created instructions in the form of three - address code. These instructions represent final program and they are essential in rendering of syntax tree.
|
guest ::
