An LLP (q, k) Parser Generator
summary
An implementation called Alpac generator produces LLP(q,k) parsers meant for data parallelism and is used to build a JSON parser; the work resolves minor theoretical gaps from prior LLP papers. Benchmarks show the GPU build achieves roughly 0.5 GB/s throughput on an 800 versus highly optimized single‑core parsers at ~2–3 GB/s; lexing dominates cost and the current parallel tokenization tables blow up to ~1k×1k for modest grammar additions. Plans include CUDA and ISPC back ends and collapsing multi‑symbol transitions.
AI-written summary · about
chapters (10)
- 0:00LLP (q,k) generator intro
- 1:49Why build LLP for GPUs
- 2:54Lexical analysis basics
- 5:50Optimizing transition function
- 7:18LLP parsing with look-back
- 11:52State transitions in grammar
- 13:00Parallel bracket matching
- 14:23Benchmarking Alpac
- 16:34Future CUDA and ISPC plans
- 18:39Q&A
related talks
14mPerformance Interfaces for Hardware Accelerators
21mgoSLP - Globally Optimized Superword Level Parallelism Framework
30mA reference GLL implementation
37mThe Art of Parsing
42mFrom Linear to Incremental
15mPluS: Highly Efficient and Expandable ML Compiler with Pluggable Graph Schedules
57mHigh-Performance Logic Programming on Servers, Clusters, and GPUs
32mTLA + specification of PCR parallel programming pattern