|
| |
|
|
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.
|
|
|
Regulated Parsing
Wolf, Dominik ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This work deals with advanced models of context-free grammars and explores the possibilities of adaptation and usefulness for deterministic parsing of non-context-free sructures by deep parsing method. It introduces adapted model of context-free grammar named LL programmed grammar and adapted deep pushdown automaton that makes deterministic parsing of non-context-free structures possible.
|
|
|
Parsing Based on State Grammars
Novotný, Miroslav ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis's main focus is parsing, based on state grammars. The goal is to create a program, that will be able to load the grammar from input file. Based on a loaded grammar, the program will create an LL table and parse an input file using this table. The next goal is to study properties of parsing, based on state grammars, while using a created program as a stand point. Part of the testing will also be grammar structures which are not context-free.
|
|
|
Parsing Based on Regulated Grammars
Vaníček, Luboš ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
This thesis deals with regulated grammars. It describes their behavior and it compares them using different examples of context-sensitive languages. The thesis focuses mostly on programmed grammars. It modifies the methods of parsing and it uses them for programmed grammars. This thesis applies the developed method of parsing on context-sensitive languages and examines their power.
|
|
|
Path-Controlled Grammars
Adamec, Ondřej ; Soukup, Ondřej (referee) ; Křivka, Zbyněk (advisor)
This thesis deals with path-controlled grammars, which are grammars that place restrictions on the paths in a derivation tree of a context-free grammar. The goal of this thesis is to create an algorithm for conversion between the path-controlled grammars and the state grammars, which is a di erent type of regulated grammars. Another goal is to study the generative power of path-controlled grammars based on the conversion algorithm. The conversion algorithm is implemented and tested on a number of path-controlled grammars. Also, its complexity is discussed. Finally, a parsing tool for path-controlled grammars is implemented. Complexity of this tool is analyzed as well.
|
guest ::
