Derivative grammars: a symbolic approach to parsing with derivatives
Abstract
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Oct 10, 2019
- Source ID
- 10.1145/3360553
Entities
People
- Gianfranco Bilardi
- Ian Henriksen
- Keshav Pingali
Organizations
- Defense Advanced Research Projects Agency
- National Science Foundation
- University of Padua
- University of Texas at Austin