Incremental PEG Parsing

Abstract

Code analysis software in a text editor or IDE must repeatedly parse source code whenever an edit occurs. In many cases, a user's edit will affect only the parse of nearby characters, meaning a full-document reparse is unnecessary and inefficient. Incremental parsing algorithms support quick reparsing after common-case edits by remembering parse state and only parsing the parts of the document that have changed.

This thesis builds on previous work in incremental parsing for parsing expression grammars (PEGs). We develop new methods for incremental parsing that enable reparsing in logarithmic time in the common case for a wide variety of grammar types. These methods are implemented in a practical library called GPeg that supports efficient dynamic incremental parsers and a language-agnostic parser format via a parsing machine. Finally, we use this library to study the performance and usability of our parsing methods for the cases of pattern matching, full grammar parsing, and syntax highlighting.