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...
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:306013 |
| Date | January 2012 |
| Creators | Procházka, Martin |
| Contributors | Plátek, Martin, Pardubská, Dana, Průša, Daniel |
| Source Sets | Czech ETDs |
| Language | Czech |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0021 seconds