Write a Blog >>
Sun 20 - Fri 25 October 2019 Athens, Greece

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, and 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 derivative languages and classical parsing methods. In particular, we show that the sets of Earley items maintained by the Earley recognizer 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 book-keeping. These results suggest that derivative grammars may provide a new foundation for context-free grammar recognition and parsing.

This program is tentative and subject to change.

Fri 25 Oct

11:00 - 12:30: OOPSLA - [THIS SESSION MAY MOVE TO THURSDAY] DSLs and Parsing at Olympia 2
Chair(s): Eric Van WykUniversity of Minnesota, USA
splash-2019-oopsla11:00 - 11:22
splash-2019-oopsla11:22 - 11:45
Tetsuro YamazakiGraduate School of Information Science and Technology, The University of Tokyo, Tomoki NakamaruGraduate School of Information Science and Technology, The University of Tokyo, Kazuhiro IchikawaGraduate School of Information Science and Technology, The University of Tokyo, Shigeru ChibaGraduate School of Information Science and Technology, The University of Tokyo
splash-2019-oopsla11:45 - 12:07
Ian HenriksenThe University of Texas at Austin, Gianfranco BilardiUniversity of Padova, Italy, Keshav PingaliThe University of Texas at Austin