From Linear to Incremental
summary
Describes turning a linear parser into an incremental one that hits best-case logarithmic time by mapping characters to composable partial functions, caching composed nodes in a balanced 2-3 tree (leaf = chunked token functions), and using a watermark/transportation technique plus scoped mutable instrumentation to adapt cached outputs. Benchmarks show a 5k-char file full parse ~200 ms, composition update ~1 ms, and a single-char edit reparse ~6 ms instead of redoing the whole file.
AI-written summary · about
chapters (19)
- 0:00Start
- 2:27Consequences
- 2:55Incremental parsing
- 5:11What's a parser?
- 6:26What I'm interested into
- 6:44reduce considered slightly harmful
- 11:10Actual computation
- 12:39With memoized nodes
- 13:54Refining memoization
- 14:42What's the function?
- 15:57a LR step
- 16:40What's in a stack?
- 17:11LR step conclusion
- 17:58Stack transplantation
- 23:32Dependencies
- 24:10Inside the step fn
- 25:33The buffer
- 27:32Composition tree
- 39:56What's next?
related talks
14mFast Incremental PEG Parsing
19mIncremental Parsing with emacs-tree-sitter- Questions
19mAn Incremental Algorithm for Algebraic Program Analysis
25mIncremental Parsing with emacs-tree-sitter
25mNano-parsing: A Data-parallel Architecture for Perverse Parsing Environments
54mKEYNOTE: A journey through incremental computation
01h 27mBoost.Parser (Part 1 of 2) - A Parser Combinator Library for C++
01h 01mExpressive Compile Time Parsers