|
|
Demonstration of Tree Controlled Grammars Properties
Kunštátský, Martin ; Čermák, Martin (referee) ; Koutný, Jiří (advisor)
Tree controlled grammars are grammars regulated by restriction placed on its derivation trees. It is simple and natural extension of context-free grammars. There are several types of derivation tree control, two principles are mentioned in this work: horizontal and vertical control. Application demonstrating tree controlled grammars properties, implemented in Python programming language, is also part of this work.
|
|
|
Parsing Based on Multigeneration
Kleiner, Miloš ; Čermák, Martin (referee) ; Meduna, Alexandr (advisor)
Multygeneratic system is based on cooperation action of infinity count of context-free grammars. All this context free-grammars parallel and synchronous derivate individual sentential form. During generation came in each specific derivation step to checking of correction of each generated sentential forms. This checking can be made by different ways. Solution is then so-called multistring (vector of strings), so by the help of this is defined generated language.
|
|
|
On Erasing Rules in Regulated Grammars
Zemek, Petr ; Koutný, Jiří (referee) ; Meduna, Alexandr (advisor)
This work discusses the effect of erasing rules to the generative power of regulated grammars, which is a big open problem in the theory of regulated rewriting. It studies the possibility of removal of erasing rules from regulated grammars by aggregation of current, up-to-date results concerning this elimination and by presentation of a new condition, called k-limited erasing, under which all erasing rules can be always removed from regularly controlled context-free grammars without affecting their generative power. This result partially solves the abovementioned problem. Moreover, a new algorithm for elimination of erasing rules from context-free grammars is presented. This algorithm does not require any predetermination of so called epsilon-nonterminals (in contrast to the standard algorithm used in textbooks). In the conclusion, a significance of these results concerning syntactical analysis is discussed.
|
|
|
Syntax-Direxted Translation Based on Deep Pushdown Automata
Solár, Peter ; Lukáš, Roman (referee) ; Meduna, Alexandr (advisor)
This thesis introduces syntax-directed translation based on deep pushdown automata. Necessary theoretical models are introduced in the theoretical part. The most important model, introduced in this thesis, is a deep pushdown transducer. The transducer should be used in syntax analysis, significant part of translation. Practical part consists of an implementation of simple-language interpret based on these models.
|
|
|
Conversions between CF Grammars and Pushdown Automata
Makovský, Benjamin ; Goldefus, Filip (referee) ; Masopust, Tomáš (advisor)
This work suggests and solves the implementation of the transformation of context-free grammars and the conversions between context-free grammars and pushdown automata. It makes acquainted with the models used in modern theory of formal languages. In the work are indicated all algorithms necessary for transformations and mutual conversions between context-free grammars and pushdown automata. Proposed is an object representing the grammar and the automaton in the programme. Described is the assigning of definitions of grammar and of the automaton, the solution of drawing the automaton on the screen and the creation of graphical user interface of the application. The resulting programme is developed as Jawa applet which is available on public internet pages www.convertcfg.php5.cz.
|
|
|
Graphdrawer and Mathemathic Equation Evaluator of Expressions
Skalický, Ivo ; Rychnovský, Lukáš (referee) ; Lukáš, Roman (advisor)
This work deals with utilization of precedence syntax analysis for conversion of mathematical expression into dynamic object model in order of evaluate and go on processing expressions. Objective was to create a program, which connects function of scientific calculator and graph drawer. Program can evaluate mathematical expressions in scope of real numbers, calculate fractional expressions, numerically integrate and analytically derive in accordance with a given parameter. Besides it provides function for depiction of any given curve explicitly, implicitly or parametricly into 2D graph. Graphic output can be exported in selectable resolution into several basic raster and vector formats. On account of portability Java was chosen as a language of implementation.
|
|
|
Lexical Analyzer for Multiprocesor Computers
Otáhal, Jiří ; Goldefus, Filip (referee) ; Čermák, Martin (advisor)
Aim of this thesis is to invent method, which should accelerate speed of the analysis of source texts with multiprocessor computers. For this purpose application runs multiple process in Unix system. Each undergoing process analyzes exact partition in source file and then closes itself. Outcome of this process are internal structures, which presents exact partition. Inter-code is sequentially built from the structures which are subsequently interpreted. This kind of parallel analysis achieves acceleration of speed on the contrary of typical sequential analysis.
|
|
|
Parsing Based on Multigeneration
Kyjovská, Linda ; Přikryl, Zdeněk (referee) ; Lukáš, Roman (advisor)
This work deals with syntax analysis problems based on multi-generation. The basic idea is to create computer program, which transforms one input string to n -1 output strings. An Input of this program is some plain text file created by user, which contains n grammar rules. Just one grammar from the input file is marked as an input grammar and others n -1 grammars are output grammars. This program creates list of used input grammar rules for an input string and uses corresponding output grammar rules for the creation of n -1 output strings. The program is written in C++ and Bison
|
|
|
A New Approach to LL and LR Parsing
Martiček, Štefan ; Burgetová, Ivana (referee) ; Meduna, Alexandr (advisor)
Cílem této práce je vytvořit nový efektivní způsob syntaktické analýzy propojením LL a LR přístupů. Pro demonstrační účely je zhotoven nový programovací jazyk podle vzoru programovacího jazyka PHP. Tento jazyk je rozdělen na části, kde pro každou část je použita ta nejvhodnejší ze zmíněných metod. Jednotlivé metody jsou zde podrobněji popsané v kontextu dvou typů přístupů. Jedním z nich je syntaktická analýza shora dolů a tím druhým opačná verze, syntaktická analýza zdola nahoru. Pro každou separovanou část je vytvořen samostatný syntaktický analyzátor. Táto práce poskytuje kompletní teoretický základ k sestrojení všech zde použitých syntaktických analyzátorů a rozkladových tabulek. Nakonec jsou sestrojené analyzátory společne propojeny, což je úspěšné zakončení praktické demonstrace naší metody. V závěru jsou diskutovány dosažené výsledky práce jako efektivnejší druh syntaktické analýzy, modularita přístupu a podobně. Je zde také diskutovaná použitelnost navržené metody za účelem zefektivnení vývoje a rychlosti překladu. Jako poslední jsou uvedeny náměty pro další výzkum v této oblasti.
|
|
|
Deep Syntax-Directed Translation
Senko, Jozef ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
This thesis is a continuation of my bachelor thesis, which is dedicated to syntax analysis based on deep pushdown automata. In theorical part of this thesis is defined everything fundamental for this work, for example deep syntax-directed translation, pushdown automata, deep pushdown automata, finite transducer and deep pushdown transducer. The second part of this thesis is dedicated to the educational program for students of IFJ. In this part is defined strucure of this program and its parts. All part of program are analyzed from a theoretical and practical point of view.
|
guest ::
