velikost textu

Redukční automaty a syntaktické chyby

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Redukční automaty a syntaktické chyby
Název v angličtině:
Reducing Automata and Syntactic Errors
Typ:
Disertační práce
Autor:
RNDr. Martin Procházka, Ph.D.
Školitel:
Martin Plátek, CSc.
Oponenti:
doc. RNDr. Dana Pardubská, CSc.
RNDr. Daniel Průša, Ph.D.
Id práce:
42659
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra teoretické informatiky a matematické logiky (32-KTIML)
Program studia:
Informatika (P1801)
Obor studia:
Matematická lingvistika (4I3)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
17. 9. 2012
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Čeština
Klíčová slova:
redukční automaty, robustní redukční analýza, lokalizace syntaktických chyb
Klíčová slova v angličtině:
reducing automata, robust analysis by reduction, localization of syntactic errors
Abstrakt:
Tato práce se zabývá redukčními automaty, jejich normalizacemi a využitím pro (robustní) redukční analýzu a lokalizaci syntaktických chyb pro jazyky ze třídy DCFL. Redukční automat navazuje na restartovací automat, od kterého se odlišuje explicitním určením redukovaných symbolů (to umožňuje přesné určení místa chyby) a přesunem výhledového okna do stavu řídící jednotky (ten ho přibližuje zařízením studovaným klasickou teorií automatů a formálních jazyků). Pro redukční automat pak lze snadněji než pro automat restartovací přebírat pojmy a postupy klasické teorie, jako je např. prefixová korektnost nebo minimalizace množiny stavů. Pro libovolný neprázdný jazyk ze třídy DCFL zadaný monotónním redukčním automatem, navíc ještě prefixově korektním a stavově minimálním, navrhujeme metodu robustní redukční analýzy, která zaručuje lokalizaci formálně definovaných typů skutečných (nezavlečených) chyb, bezchybných podslov a míst redukčních konfliktů (podslov s nejednoznačnou syntaktickou strukturou redukovatelných v různých slovech různými způsoby). Navrhovanou metodu implementujeme novým typem zařízení (postprefixovým robustním analyzátorem) a stručně ukazujeme, jak jí implementovat deterministickým zásobníkovým převodníkem pracujícím v lineárním čase vzhledem k délce slova.
Abstract v angličtině:
This thesis deals with reducing automata, their normalization, and their application for a (robust) reduction analysis and localization of syntactic errors for deterministic context-free languages (DCFL). A reducing automaton is similar to a restarting automaton with two subtle differences: an explicit marking of reduced symbols (which makes it possible to determine a position of an error accurately), and moving a lookahead window inside a control unit (which brings reducing automata closer to devices of classical automata and formal language theory). In case of reducing automata, it is easier to adopt and reuse notions and approaches developed within classical theory, e.g., prefix correctness or automata minimization. For any nonempty deterministic context-free language specified by a monotone reducing automaton, both prefix correct and minimal, we propose a method of robust analysis by reduction which ensures localization of formally defined types of (real) errors, correct subwords, and subwords causing reduction conflicts (i.e., subwords with ambiguous syntactic structure that can be reduced in different words in different ways). We implement the proposed method by a new type of device (called postprefix robust analyzer) and we briefly show how to implement this method by a deterministic pushdown transducer working in linear time with respect to the length of the analyzed word.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Martin Procházka, Ph.D. 831 kB
Stáhnout Příloha k práci RNDr. Martin Procházka, Ph.D. 343 kB
Stáhnout Abstrakt v českém jazyce RNDr. Martin Procházka, Ph.D. 42 kB
Stáhnout Abstrakt anglicky RNDr. Martin Procházka, Ph.D. 42 kB
Stáhnout Posudek vedoucího Martin Plátek, CSc. 77 kB
Stáhnout Posudek oponenta doc. RNDr. Dana Pardubská, CSc. 278 kB
Stáhnout Posudek oponenta RNDr. Daniel Průša, Ph.D. 94 kB
Stáhnout Záznam o průběhu obhajoby doc. Ing. Zdeněk Žabokrtský, Ph.D. 66 kB