Parsing with Zippers (Functional Pearl)
summary
Generalizes Huet’s zipper to handle CFG features like alternation, sharing, and cycles, suspends traversal state so derivatives resume instead of retraversing, and pushes memo entries into each expression to drop the global table. Implementation is concise: a 31-line OCaml derivative plus a ~100-line full parser. On the Python 3.4.3 corpus it runs 15,600× faster than original PwD and 3.43× faster than the optimized PwD, while producing full parse trees and avoiding exponential zipper blowup.
AI-written summary · about
chapters (7)
- 0:00Intro
- 0:51Parsing with Derivatives (PWD)
- 5:10Parsing with Zippers (PwZ)
- 6:01Generalizing the Zipper
- 11:45Eliminating Memoization Tables
- 12:40Evaluation
- 13:55Conclusion
related talks
30mEfficient Embedding of Strategic Attribute Grammars via Memoization
14mA Derivative-based Parser Generator for Visibly Pushdown Grammars
23mA Verified Packrat Parser Interpreter for Parsing Expression Grammars
40mType-safe Nanopasses: How to write a safe and modern compiler front-end
14mFast Incremental PEG Parsing
19mCode Size Reduction Deep Dive: Zc Extensions and Dictionary Compression Custom Instruction
14mOne Down, 699 to Go: or, synthesising compositional desugarings
25mGenerating a corpus of Hazel programs from ill-typed OCaml programs