Write a Blog >>
PLDI 2020
Mon 15 - Fri 19 June 2020

We present a novel parsing algorithm for all context-free languages. The algorithm features a clean mathematical formulation: parsing is expressed as a series of standard operations on \emph{regular} languages and relations. Parsing complexity w.r.t. input length matches the state of the art: it is worst-case cubic, quadratic for unambiguous grammars, and linear for LR-regular grammars. What distinguishes our approach is that parsing can be implemented using only immutable, acyclic data structures. We also propose a parsing optimization technique called context-free memoization. It allows handling an overwhelming majority of input symbols using a simple stack and a lookup table, similarly to the operation of a deterministic LR(1) parser. This allows our proof-of-concept implementation to outperform the best current implementations of common generalized parsing algorithms (Earley, GLR, and GLL). Tested on a large Java source corpus, parsing is 3–5 times faster, while recognition—35 times faster.

Fri 19 Jun
Times are displayed in time zone: (GMT-07:00) Pacific Time (US & Canada) change

06:20 - 07:40: PLDI Research Papers - Parsing, Debugging, and Code Search at PLDI Research Papers live stream
Chair(s): Dan BarowyWilliams College

YouTube lightning session video

pldi-2020-papers06:20 - 06:40
Grzegorz HermanJagiellonian University, Poland
pldi-2020-papers06:40 - 07:00
Romain EdelmannEPFL, Switzerland, Jad HamzaEPFL, Switzerland, Viktor KunčakEPFL, Switzerland
pldi-2020-papers07:00 - 07:20
Yuanbo LiGeorgia Institute of Technology, USA, Shuo DingGeorgia Institute of Technology, USA, Qirun ZhangGeorgia Institute of Technology, USA, Davide ItalianoApple, USA
pldi-2020-papers07:20 - 07:40
Varot PremtoonMassachusetts Institute of Technology, USA, James KoppelMassachusetts Institute of Technology, USA, Armando Solar-LezamaMassachusetts Institute of Technology, USA