A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Improved normal form for grammars with one-sided contexts
Tekijät: Alexander Okhotin
Toimittaja: Helmut Jurgensen, Rogério Reis
Kustannuspaikka: London, Ontario, Canada
Julkaisuvuosi: 2013
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Descriptional Complexity of Formal Systems
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 8031
Aloitussivu: 205
Lopetussivu: 216
Sivujen määrä: 12
ISBN: 978-3-642-39309-9
eISBN: 978-3-642-39310-5
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-39310-5_20
Tiivistelmä
Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin (``An extension of context-free grammars with one-sided context specifications'', submitted), further extending the author's (``Conjunctive grammars'', J.~of Automata, Languages and Combinatorics, 2001) earlier work on propositional connectives in grammars. These grammars allow two types of context specifications: for a substring $w$ of a string $uwv$, a \emph{left context} operator $\lhd D$ states that $u$ is of the form described by $D$, while the \emph{extended left context} operator $\trianglelefteqslant E$ states that $uw$ is described by $E$. This paper establishes a normal form for these grammars, in which extended left contexts are never used, while left contexts may be applied only for individual symbols, so that all rules are of the form $A \to B_1 C_1 \& \ldots \& B_n C_n$ or $A \to a \& \lhd D$. This eliminates circular dependencies in the grammar and allows simplifying the known cubic-time parsing algorithm. Some further improvements to the algorithm accelerate it from time $O(n^3)$ to time $O(\frac{n^3}{\log n})$.
Formal grammars equipped with operators for specifying the form of the context of a substring were recently studied by Barash and Okhotin (``An extension of context-free grammars with one-sided context specifications'', submitted), further extending the author's (``Conjunctive grammars'', J.~of Automata, Languages and Combinatorics, 2001) earlier work on propositional connectives in grammars. These grammars allow two types of context specifications: for a substring $w$ of a string $uwv$, a \emph{left context} operator $\lhd D$ states that $u$ is of the form described by $D$, while the \emph{extended left context} operator $\trianglelefteqslant E$ states that $uw$ is described by $E$. This paper establishes a normal form for these grammars, in which extended left contexts are never used, while left contexts may be applied only for individual symbols, so that all rules are of the form $A \to B_1 C_1 \& \ldots \& B_n C_n$ or $A \to a \& \lhd D$. This eliminates circular dependencies in the grammar and allows simplifying the known cubic-time parsing algorithm. Some further improvements to the algorithm accelerate it from time $O(n^3)$ to time $O(\frac{n^3}{\log n})$.
Turun yliopiston Tutkimustietojärjestelmän portaali