Skip to content
Parsing

PwZ: Parsing with zippers

Parsing with Zippers (Functional Pearl), 2020 by Pierce Darragh and Michael D. Adams

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 be clened up, and also you don’t need to retraverse grammar you can just continue from the place where you left.

Same as PwD:

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.

Papers