This site contains the artifacts and supporting materials for our paper Incremental Packrat Parsing presented at SLE'17:
Packrat parsing is a popular technique for implementing top-down, unlimited-lookahead parsers that operate in guaranteed linear time. In this paper, we describe a method for turning a standard packrat parser into an incremental parser through a simple modification to its memoization strategy. By "incremental", we mean that the parser can perform syntax analysis without completely reparsing the input after each edit operation. This makes packrat parsing suitable for interactive use in code editors and IDEs — even with large inputs. Our experiments show that with our technique, an incremental packrat parser for JavaScript can outperform even a hand-optimized, non-incremental parser.
- Try the online visualization as mentioned in Section 3
- Source code for the ES5 parsers described in Section 4:
- src/standard.js: the classes for a standard (non-incremental) packrat parser
- src/incremental.js: additional classes for implementing an incremental parser as described in the paper
- src/es5.js: ES5 grammar, which can be instantiated into either a standard or incremental parser
- Git repository with complete artifacts, including benchmark scripts, etc.
- Ohm is our open-source packrat parsing framework, which supports incremental parsing as described in the paper