Making Grammar fun Again

I wanted to build a Monkeytype like speedtyping platform for developers. The problem was that we needed a way to generate the code snippets which should be structurally correct and resemble the correct language very very fast.

A database of real snippets doesn’t scale, and random tokens aren’t code. So I built Resrap, a tool that takes a grammar and generates infinite, structurally valid code from it, a parser in reverse. This talk is the story of chasing that problem into EBNF, discovering its limitations in code generation, and inventing new operators (infinite generation, weighted probabilities, seeded determinism) to make it actually work.

• Introduction to BNF/EBNF and where their basic operators fall short

• How a reverse parser works: walking a grammar as a graph instead of validating against one

• Using PRNG and seeding to make generation deterministic and reproducible

• Freezing graphs: using immutable data structures to get lock-free concurrent reads