A4 Refereed article in a conference publication
Improved normal form for grammars with one-sided contexts
Authors: Alexander Okhotin
Editors: Helmut Jurgensen, Rogério Reis
Publishing place: London, Ontario, Canada
Publication year: 2013
Journal: Lecture Notes in Computer Science
Book title : Descriptional Complexity of Formal Systems
Series title: Lecture Notes in Computer Science
Volume: 8031
First page : 205
Last page: 216
Number of pages: 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(external)
Abstract
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})$.
UTU Research Portal