|
|
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.
|
|
|
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.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (referee) ; Doc. In.g Petr Sosík, Dr. (referee) ; Meduna, Alexandr (advisor)
Tato disertační práce zavádí jednostranné gramatiky s nahodilým kontextem jako řízené gramatiky založené na bezkontextových gramatikách. V těchto gramatikách je ke každému pravidlu přiřazena množina povolujících symbolů a množina zakazujících symbolů a množina pravidel je rozdělena na množinu levých pravidel s nahodilým kontextem a množinu pravých pravidel s nahodilým kontextem . Levým pravidlem s nahodilým kontextem lze přepsat neterminál pokud se všechny povolující symboly vyskytují vlevo od přepisovaného neterminálu a žádný zakazující symbol tam přítomen není. Pravé pravidlo s nahodilým kontextem lze aplikovat analogicky, ale ona kontrola na přítomnost a nepřítomnost symbolů je provedena doprava od přepisovaného neterminálu. Práce je rozdělena na tři části. První část uvádí motivaci za zavedením jednostranných gramatik s nahodilým kontextem a umisťuje materiál pokrytý v této práci do vědeckého kontextu. Poté dává přehled základů teorie formálních jazyků a některých méně známých oblastí, jejichž znalost je nutná pro pochopení studovaného tématu. Druhá část tvoří jádro práce. Formálně definuje jednostranné gramatiky s nahodilým kontextem a studuje je z mnoha pohledů. Mezi studovaná témata patří generativní síla, vztah k jiným typům gramatik, redukce, normální formy, nejlevější derivace, zobecněné a LL verze těchto gramatiky. Třetí část této práce zakončuje diskusi několika poznámkami. Mezi ně patří poznámky týkající se aplikovatelnosti zavedených gramatik v praxi, bibliografie a otevřených problémů.
|
|
|
Parsing Based on Matrix Grammars
Bednář, Petr ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This thesis is researching parsing based on matrix grammars. Introduces automata controled parsing method. It discusses problems of deterministic parsing of matrix grammars. Thesis is focusing on deterministic parsing of non-deterministic languages. It studies strength of this deterministic method.
|
|
|
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.
|
|
|
Parallel Syntax Analysis
Otáhal, Jiří ; Koutný, Jiří (referee) ; Čermák, Martin (advisor)
This thesis focuses on modern methods of language description. It introduces several controlled grammars, describing in detail the tree controlled grammar. The thesis is based on relatively new technique of syntax analysis using tree controlled grammars. The process of this analysis is described in detail, followed by a design of parallel-processing of this analysis. We managed to succesfully implement this design, speed up the syntax analysis and therefore achieve the main goal of the thesis.
|
|
|
One-Sided Random Context Grammars
Zemek, Petr ; Černá, Ivana (referee) ; Doc. In.g Petr Sosík, Dr. (referee) ; Meduna, Alexandr (advisor)
Tato disertační práce zavádí jednostranné gramatiky s nahodilým kontextem jako řízené gramatiky založené na bezkontextových gramatikách. V těchto gramatikách je ke každému pravidlu přiřazena množina povolujících symbolů a množina zakazujících symbolů a množina pravidel je rozdělena na množinu levých pravidel s nahodilým kontextem a množinu pravých pravidel s nahodilým kontextem . Levým pravidlem s nahodilým kontextem lze přepsat neterminál pokud se všechny povolující symboly vyskytují vlevo od přepisovaného neterminálu a žádný zakazující symbol tam přítomen není. Pravé pravidlo s nahodilým kontextem lze aplikovat analogicky, ale ona kontrola na přítomnost a nepřítomnost symbolů je provedena doprava od přepisovaného neterminálu. Práce je rozdělena na tři části. První část uvádí motivaci za zavedením jednostranných gramatik s nahodilým kontextem a umisťuje materiál pokrytý v této práci do vědeckého kontextu. Poté dává přehled základů teorie formálních jazyků a některých méně známých oblastí, jejichž znalost je nutná pro pochopení studovaného tématu. Druhá část tvoří jádro práce. Formálně definuje jednostranné gramatiky s nahodilým kontextem a studuje je z mnoha pohledů. Mezi studovaná témata patří generativní síla, vztah k jiným typům gramatik, redukce, normální formy, nejlevější derivace, zobecněné a LL verze těchto gramatiky. Třetí část této práce zakončuje diskusi několika poznámkami. Mezi ně patří poznámky týkající se aplikovatelnosti zavedených gramatik v praxi, bibliografie a otevřených problémů.
|
|
|
Parsing Based on Matrix Grammars
Bednář, Petr ; Solár, Peter (referee) ; Meduna, Alexandr (advisor)
This thesis is researching parsing based on matrix grammars. Introduces automata controled parsing method. It discusses problems of deterministic parsing of matrix grammars. Thesis is focusing on deterministic parsing of non-deterministic languages. It studies strength of this deterministic method.
|
|
|
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.
|
guest ::
