Parsing Text with a Virtual Machine
summary
Library compiles PEG grammars to a custom bytecode and runs them on a tiny VM (Java implementation) so parsing becomes a compiler pipeline rather than regex glue. It implements captures, macro-like grammar abstraction, and emits flat integer bytecode; a 99-line Clojure JSON grammar parses within about five times the speed of Jackson. Inspired by LPeg, it uses choice/commit backtracking markers and compiles PEGs to custom bytecode, with more optimizations (tail calls, head-fail, delayed captures) planned.
AI-written summary · about
chapters (18)
- 0:00Start
- 7:06parsing with combinators
- 7:55terminology
- 8:43Parsing Expression Grammar
- 11:38PEG primitives & semantics
- 13:21repetition
- 14:31searching for a pattern
- 14:59and/not "predicates"
- 15:57Implementation
- 17:18machine state
- 18:08instruction types
- 19:54human compiler
- 26:28bytecode optimizations
- 32:43architecture
- 37:17public interface CharMatcher
- 40:11pex rule macros
- 41:15pex future
- 42:58recap
related talks
14mFast Incremental PEG Parsing
23mA Verified Packrat Parser Interpreter for Parsing Expression Grammars
15mA Semantic Framework for PEGs
14mA Derivative-based Parser Generator for Visibly Pushdown Grammars
37mThe Art of Parsing
13mParboiled2: better parsing in Scala
39mInstaparse
38mDemystifying compilers by writing your own