|
|
Parsing Based on Deep Pushdown Automata
Senko, Jozef ; Vrábel, Lukáš (referee) ; Solár, Peter (advisor)
This thesis is concerning with syntax analysis based on deep pushdown automata. In theoretical part are defined themselves deep pushdown automata, all the necessary theoretical concepts and then is discussed the implementation of these deep pushdown automata embedded in the educational program for students.
|
|
|
Pushdown Systems and Parsing Based on Them
Křesťan, Zdeněk ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
This thesis focuses on the use of deep pushdown automaton in parsing . This method overcomes the power of traditional context - free grammars . The predictive parsing algorithm, driven by LL table, is modified by the use of deep pushdown automaton . The modifications extended LL tables by adding depth , in order for tables to collaborate with the deep pushdown automaton .
|
|
|
Parsing Based on State Grammars
Svatý, Lukáš ; Vrábel, Lukáš (referee) ; Solár, Peter (advisor)
Syntax-directed translation based on state grammars is introduced in this bachelor's thesis. Theoretical section of this thesis is focused on the introduction of theoretical models that are necessary for understanding syntax analysis based on state grammars. The most important theoretical formal models in this thesis include deep pushdown transducer and translation grammar based on state grammar, which can be used in syntax analysis. Practical section of this thesis is focused on bottom-up syntax analysis using state grammar and its implementation.
|
|
|
Modified Deep Pushdown Automata
Škvařilová, Radka ; Horáček, Petr (referee) ; Meduna, Alexandr (advisor)
This thesis introduce two new modifications of deep pushdown automata - stateless deep pushdown automata and parallel deep pushdown automata. In theoretical part of this thesis is formal definition and research into power of these modification. Practical part consists of an implementation of simple automata program.
|
|
|
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.
|
|
|
Parallel Deep Pushdown Automata
Solár, Peter ; Křivka, Zbyněk (referee) ; Meduna, Alexandr (advisor)
This thesis introduces parallel deep pushdown automata as the parallel version of the deep pushdown automata. They are based on the rules, where the automaton can expand n topmost non-terminals in only one derivation step if there are enough non-terminals on the pushdown. The main advantage rests in a fact, that parallel automaton can makde a decission faster.
|
|
|
Alternative Versions of Deep Pushdown Automata and Their Applications
Klembara, Radovan ; Kocman, Radim (referee) ; Meduna, Alexandr (advisor)
The goal of this thesis is to design new versions of deep pushdown automata, their analysis and aplication in informatics. In this thesis I present two new versions of automata. The idea behind modificatons is to add parallel processing of expansive transitions. The first version differs from second one by variable number of expansive transitions in each parallel step. For each new version I have created algorithms, which can be used to convert these versions to basic deep pushdown automata. Furhtermore I have created algorithms for converting basic deep pushdown automata back to these new versions. Proposed alternative versions of deep pushdown automata are faster than their basic version thanks to the paralelism. Through their analysis I have found out that their strength is same as strength of basic deep pushdown automata. For easier conversion between automata I have programmed console application, which implements proposed conversion algorithms. Solution of this thesis allows designing parallel version of deep pushdown automaton instead of basic deep pushdown automaton, that can result in faster and more efective design. Created automaton then can be easily converted via algorithm to basic version.
|
|
|
New Parallel and Regulated Automata and Grammars
Kučera, Jiří ; Průša, Daniel (referee) ; Sawa, Zdeněk (referee) ; Meduna, Alexandr (advisor)
Tato práce zkoumá a zavádí čtyři nové jazykové modely se zaměřením na regulované a paralelní verze automatů a gramatik. První z modelů, stavově synchronizované systémy automatů , zavádí systémy složené z konečného počtu zásobníkových automatů jejichž činnost je řízena slovy z řídícího jazyka nad množinou stavů. Druhý model, neomezené hluboké zásobníkové automaty , je variantou hlubokých zásobníkových automatů z nichž bylo sejmuto omezení kladené na hloubku expanze na zásobníku. Třetí model, skákající čisté gramatiky , zavádí skákající gramatiky bez neterminálních symbolů. Poslední model, k#$-přepisující systémy , rozšiřuje #-přepisující systémy o přídavnou zásobníkovou paměť. Text této práce je členěn do tří částí. První část uvádí motivaci k zavedení studovaných jazykových modelů a zasazuje je do kontextu souvisejících oblastí teorie formálních jazyků. Je zde také uveden přehled o celkové organizaci práce, základních pojmů teorie formálních jazyků a současných poznatků souvisejících s předmětem výzkumu. Druhá část tvoří jádro této práce. Jsou v ní formálně definovány všechny nově zavedené jazykové modely a studována jejich vyjadřovací síla. Poslední část uzavírá tuto práci souhrnem získaných teoretických výsledků společně se souvisejícími otevřenými problémy a nastiňuje cesty dalšího výzkumu spolu s výhledy na možná využití.
|
|
|
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.
|
|
|
Deep Pushdown Automata and Their Restricted Versions
Charvát, Lucie ; Kučera, Jiří (referee) ; Meduna, Alexandr (advisor)
Pro přirozené číslo n, n-expandovatelné hluboké zasobníkové automaty vždy obsahují maximálně n výskytů nevstupních symbolů v jejich zásobníku v průběhu jakékoli kompilace. Jako hlavní výsledek, tato práce demonstruje, že tyto automaty mají stejnou vyjadřovací sílu jako automaty s #, nacházející pouze na dně zásobníku, a jediným dalším nevstupním symbolem. Z tohoto závěru vyplývá nekonečná hierarchie jazyků přijímaných těmito automaty.
|
guest ::
