Fast Incremental PEG Parsing
summary
Presents an incremental PEG parser implementation called GPeg with a syntax-highlighting library Flare and a prototype editor, claiming typical reparses are logarithmic in input size instead of linear. Key techniques are interval tree memo tables to evict overlaps, lazy shifts to avoid eager updates, and tree memoization for repeated tokens. Experimental runs show sub-5ms reparses on files from tens to hundreds of megabytes and competitive behavior versus existing incremental parsers like tree-sitter.
AI-written summary · about
chapters (16)
- 0:00Overview
- 0:46Parsing Expression Grammars (PEG)
- 2:05Parsing Expression Grammars (cont.)
- 2:42Incremental Parsing
- 4:56Full Parse Example
- 6:02Handling an Edit
- 6:13Reparse Example
- 7:33Incremental Packrat Parsing Summary
- 8:05Interval Tree
- 8:41Lazy Shifts
- 10:12Problem #3: Linear Memoization
- 11:02Tree Memoization
- 12:09Space Optimizations
- 12:41Evaluation: Asymptotic Validation
- 13:17Evaluation: Example Text Editor
- 13:52Conclusion
related talks
23mA Verified Packrat Parser Interpreter for Parsing Expression Grammars
42mFrom Linear to Incremental
15mA Semantic Framework for PEGs
44mParsing Text with a Virtual Machine
19mIncremental Parsing with emacs-tree-sitter- Questions
14mA Derivative-based Parser Generator for Visibly Pushdown Grammars
25mIncremental Parsing with emacs-tree-sitter
19mAn Incremental Algorithm for Algebraic Program Analysis