|
|
Parsing Based on Automata with Deep Pushdowns
Pločicová, Dominika ; Dvořák, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
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.
|
|
|
Hluboké zásobníkové automaty konečného indexu
Poncová, Vendula ; Horáček, Petr (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce představuje několik modifikací hlubokých zásobníkových automatů s ohledem na redukci počtu stavů nebo nevstupních symbolů. Je ukázáno, že síla hlubokých zásobníkových automatů konečného indexu není ovlivněna omezením nevstupních symbolů na jeden, tudíž tyto automaty charakterizují nekonečnou hierarchii jazykových rodin vycházejících z programových gramatik konečného indexu. Na základě principu tohoto automatu je stanovena normální forma hlubokých zásobníkových automatů. Nakonec zavádím zobecněný hluboký zásobníkový automat, který expanduje nejvrchnější možný nevstupní symbol na zásobníku. Tento automat spolu s jeho zredukovanými formami je ekvivalentní se stavovými gramatikami.
|
|
|
Částečně paralelní hluboké zásobníkové automaty
Ševčík, Miroslav ; Zámečníková, Eva (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce zavádí částečně paralelní hluboké zásobníkové automaty jako rozšíření sekvenčních hlubokých zásobníkových automatů. Toto rozšíření spočívá v tom, že oproti sekvenční verzi je automat schopen provést expanzi n nejvýše položených nonterminálních symbolů na zásobníků současně. Tyto automaty jsou schopné rozpoznat třídu jazyků generovanou n-omezenými stavovými gramatikami stejně jako sekvenční hluboké zásobníkové automaty. Výhoda částečně paralelních hlubokých zásobníkových automatů je ale ve vyšší rychlosti. Dále je v této práci popsána implementace aplikace, která simuluje činnost těchto automatů.
|
|
|
Syntaktická analýza založená na stavových gramatikách
Paulík, Miroslav ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce popisuje vlastnosti stavových gramatik a n-limitovaných stavových gramatik s důrazem na nedeterminismus v analýze takových gramatik. Zejména se zaměřuje na problémy způsobené povolením vymazávacích pravidel a možných výskytů rekurze. Na základě analýzy těchto problémů nabízí možná řešení, která jsou posléze uplatněna při návrhu prakticky zaměřené metody paralelní syntaktické analýzy. Tato metoda je výrazně rychlejší, než sekvenční analýza s návratem.
|
|
|
Syntaktická analýza založená na stavových gramatikách
Svatý, Lukáš ; Vrábel, Lukáš (oponent) ; Solár, Peter (vedoucí práce)
V této bakalářské práci je zaveden syntaxí řízený překlad za pomocí stavových gramatik. Teoretická část práce je zaměřená na zavedení teoretických modelů potřebných pro pochopení syntaktické analýzy za pomocí stavových gramatik. Mezi nejdůležitejší z teoretických formálních modelů v této práci patří hluboký zásobníkový převodník a překladová gramatika vytvořená ze stavové gramatiky, které lze využít k syntaktické analýze. Praktická část práce sa zaměřuje hlavně na syntaktickou analýzu zdola nahoru pomocí stavových gramatik a její implementaci.
|
|
|
Syntaktická analýza založená na modifikovaných zásobníkových automatech
Pluháček, David ; Lukáš, Roman (oponent) ; Meduna, Alexandr (vedoucí práce)
Práce prezentuje nové modely formálních jazyk, m-omezenou stavovou gramatiku a hluboký zásobníkový automat. Uvádí jejich základní definice, vzájemnou ekvivalenci, a charakteristiku jazyků, jež popisují. Následně je představena metoda syntaktické analýzy, založená na těchto nástrojích. Ta vychází z obdobné metody používané u bezkontextových jazyk, tzv. analýzy řízené LL tabulkou. V závěru práce je popsán postup implementace syntaktického analyzátoru, založeného na této metodě.
|
|
|
Kanonické derivace programovaných gramatik
Zemek, Petr ; Masopust, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
V této práci jsou studovány kanonické derivace (se zaměřením na nejlevější derivace) v programovaných gramatikách a rozsah levého omezení. Je ukázáno, že zavedením n-limitovaných derivací v programovaných gramatikách tak, jako byly zavedeny pro stavové gramatiky, dostaneme nekonečnou hierarchii jazykových tříd vyplývající z n-limitovaných programovaných gramatik, takže rozsah levého omezení ovlivňuje generativní sílu n-limitovaných programovaných gramatik. Tento výsledek má význam pro syntaktickou analýzu založenou na programovaných gramatikách.
|
|
|
Částečně paralelní hluboké zásobníkové převodníky a jejich aplikace
Putala, Marek ; Dolejška, Daniel (oponent) ; Meduna, Alexandr (vedoucí práce)
Cílem této práce bylo seznámit se s hlubokými zásobníkovými automaty a na základě získaných znalostí dále navrhnout, formálně definovat a implementovat částečně paralelní hluboký zásobníkový převodník. Jedná se o rozšíření hlubokých zásobníkových převodníků, které je na zásobníku schopné v jednom kroku přistupovat k non-terminálním symbolům současně. S vhodně zvolenou konfigurací ve formě pravidel mohou zpracovat vstupní řetězec s menším množstvím přechodů, a tím pádem mají oproti hlubokým zásobníkovým převodníkům vyšší rychlost.
|
|
|
Parsing Based on Automata with Deep Pushdowns
Pločicová, Dominika ; Dvořák, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
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.
|
|
|
Kanonické derivace programovaných gramatik
Zemek, Petr ; Masopust, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
V této práci jsou studovány kanonické derivace (se zaměřením na nejlevější derivace) v programovaných gramatikách a rozsah levého omezení. Je ukázáno, že zavedením n-limitovaných derivací v programovaných gramatikách tak, jako byly zavedeny pro stavové gramatiky, dostaneme nekonečnou hierarchii jazykových tříd vyplývající z n-limitovaných programovaných gramatik, takže rozsah levého omezení ovlivňuje generativní sílu n-limitovaných programovaných gramatik. Tento výsledek má význam pro syntaktickou analýzu založenou na programovaných gramatikách.
|
host ::
RSS.