Implementing incremental and parallel parsing

Abstract

Using recent improvements to Valiant’s algorithm for parsing contextfree languages, we present an implementation of a generator of parsers that works incrementally, that can be parallelized and generated from a grammar specification. Using a tree structure makes for both easy use of incrementality and parallelization. The resulting code is reasonably fast and handles correct input in a satisfactory way, and would be suitable for use in a text editor setting, where small changes are frequent but only should lead to minimal work.