Parsing with zippers
Parsing with Zippers (Functional Pearl), 2020 by Pierce Darragh and Michael D. Adams
Related:
Idea
They took the same idea as in PwD, but they relaized that main problem is that on each derivation algorithm needs to traverse whole grammar graph again, so instead they can use zipper, to trverse through the grammar and doing derivation same time. This allows to avoid creation of unused nodes that needs to clened up, and also you don’t need to retraverse grammar you can just continue from the place where you left.
Same as PwD:
- grammar as graph
- memoization and cycle detection
- derivation
Differrent from PwD:
- no need for compaction
- N-arry operations (
Seq,Alt) instead of binary
While this algorithm is inspired by PwD, I find it quite different. For me it’s much easier to think of it as graph traversing and building parse tree a long the way. Use playground to experiment with it.