Improved normal form for grammars with one-sided contexts

: Alexander Okhotin

: Helmut Jurgensen, Rogério Reis

: London, Ontario, Canada

: 2013

: Lecture Notes in Computer Science

: Descriptional Complexity of Formal Systems

: Lecture Notes in Computer Science

: 8031

: 205

: 216

: 12

: 978-3-642-39309-9

: 978-3-642-39310-5

: 0302-9743

DOI: https://doi.org/10.1007/978-3-642-39310-5_20

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})$.