A reference GLL implementation
summary
A reference GLL implementation provides a deliberately unoptimized, easy-to-read interpreted parser plus a low-level alternative that hand-manages memory. It implements the six GLL sets, explicit grammar nodes, and contingent-pop handling, and the GitHub code reproduces the experiments. The handcrafted hash pool version reduces heap use by about 4–5× and runs ~3–4× faster than a naïve Java API version; on a ~120KB input the unoptimized interpreter runs in ~1.35s versus 7–18s for other grammars/implementations.
AI-written summary · about
chapters (18)
- 0:00GLL parsing introduction
- 1:43Generalized parsing history
- 4:31Limitations of deterministic parsing
- 6:39Parsing tools performance
- 9:11Motivation for GLL reference
- 10:59Reference implementation goals
- 13:25Simplest GLL algorithm
- 15:32Grammar data structures
- 18:24Core GLL algorithm six sets
- 20:51Handling parentheses sub-rules
- 21:33Contingent pops in GLL
- 21:54Memory management for GLL
- 22:58GLL variants and extensions
- 23:42GLL performance benchmarks
- 25:10Resources and GitHub
- 26:35Q&A: Hash pooling indentation
- 27:41Q&A: GLL implementation mistakes
- 29:07Q&A: EBNF correctness future
related talks
21mGOOL: A Generic Object-Oriented Lanugage
31mSimplifying and Optimizing Life on the Edge with Graal
37mThe Art of Parsing
14mFast Incremental PEG Parsing
38mGraal
29mHow does Lrama make the Ruby parser grammar G.O.A.T.?
39mIs Go A Good Language to Build Compilers?
37mGraalVM for Polyglots: Harder, Better, Faster, Stronger?