We present a novel approach to context-free grammar parsing that is based on generating a sequence of grammars called derivative grammars from a given context-free grammar and input string. The generation of the derivative grammars is described by a few simple inference rules. We present an O(n 2 ) space and O(n 3 ) time recognition algorithm, which can be extended to generate parse trees in O(n 3 ) time and O(n 2 log n) space. Derivative grammars can be viewed as a symbolic approach to implementing the notion of derivative languages, which was introduced by Brzozowski. Might and others have explored an operational approach to implementing derivative languages in which the context-free grammar is encoded as a collection of recursive algebraic data types in a functional language like Haskell. Functional language implementation features like knot-tying and lazy evaluation are exploited to ensure that parsing is done correctly and efficiently in spite of complications like left-recursion. In contrast, our symbolic approach using inference rules can be implemented easily in any programming language and we obtain better space bounds for parsing. Reifying derivative languages by encoding them symbolically as grammars also enables formal connections to be made for the first time between the derivatives approach and classical parsing methods like the Earley and LL/LR parsers. In particular, we show that the sets of Earley items maintained by the Earley parser implicitly encode derivative grammars and we give a procedure for producing derivative grammars from these sets. Conversely, we show that our derivative grammar recognizer can be transformed into the Earley recognizer by optimizing some of its bookkeeping. These results suggest that derivative grammars may provide a new foundation for context-free grammar recognition and parsing. Given a grammar Γ and string w = t 1 t 2 . . . t n , we construct a sequence of derivative grammars Γ t 1 , Γ t 1 t 2 , . . ., Γ t 1 ...t n that generate languages D t 1 (L), D t 1 t 2 (L), . . . , D t 1 ...t n (L). The string w is in L if and only if ϵ can be derived from the start symbol S w in Γ w = Γ t 1 t 2 ...t n . This approach, which reifies derivative languages by representing them symbolically using grammars rather than encoding them as algebraic data types within a program, is advantageous because it does not require language features like knot-tying and lazy evaluation, and can be easily implemented in any language. A baseline implementation of this approach, called the pruned derivative grammar (PrDA) algorithm, permits recognition in O(n 3 ) time and O(n 2 ) space, the same complexity as Earley, CYK and PWD. (2) (Section 4) We show that this recognizer can be extended to a parser that requires O(n 3 ) time and O(n 2 log n) space, improving previous results on PWD [Adams et al. 2016 ]. (3) (Section 5) While PWD has been studied for several years, its connection to classical parsing algorithms like Earley or LL/LR has remained a mystery. Recently Thiemann has introduced an interesting notion called partial derivatives to construct nondeterministic pushdown automata (NPDA) from µ-regular expressions [Thiemann 2017]. However there is no direct way to obtain a parsing algorithm starting from an NPDA (one can convert the NPDA back to a CFG and use Earley or CYK but in that case, the NPDA is not needed), so the connection between PWD and classical parsing algorithms has remained unclear. In this paper, we establish direct and formal connections between derivative grammars and classical parsing algorithms such as the Earley algorithm. In particular, we show that the sets of Earley items maintained by the Earley recognizer implicitly encode derivative grammars and give a procedure for producing derivative grammars from Earley sets. Conversely, we show that the PrDA recognizer can be transformed into the Earley recognizer in three steps, each of which is provably correct. This establishes a formal relationship between the Earley recognizer and the derivatives approach for the first time. These results do not imply that the Earley recognizer is the same as the PrDA recognizer; rather, they suggest that derivative grammars may provide a new foundation for CFG recognition algorithms in the sense that algorithms such as Earley, LL/LR and PWD can be obtained as optimized implementations of the baseline derivative grammar approach introduced in this paper.
Henriksen et al. REF show a parsing technique based on derivatives for context-free grammars.
Derivative grammars: a symbolic approach to parsing with derivatives
PACMPL
Computer Science