Inside Ohm's PEG-to-Wasm Compiler
核心摘要
Ohm解析器v18版本将PEG语法编译为WebAssembly，实现50倍以上的性能提升和90%的内存减少。本文深入解析其编译器架构和优化技术。
关键亮点
- PExpr树编译 vs AST解释：v18不再解释执行PExpr抽象语法树，而是将其编译为Wasm字节码
- Bump Allocator：使用bump allocator在Wasm线性内存中分配CST节点，显著降低内存开销
- Terminal节点优化：使用32位标签值 (matchLength << 1) | 1，无需为每个终端字符分配独立节点
- Chunked Bindings：使用128元素固定大小的链表块，避免动态数组扩容开销
- 规则编译为函数：每个PEG规则编译为独立的Wasm函数，规则应用即为函数调用
- 区域分配：CST节点具有相同生命周期，适合区域内存管理
技术细节
- Runtime支持代码使用AssemblyScript编写
- codegen部分使用TypeScript实现
- Non-terminal节点布局：matchLength(4字节) + typeAndDetails(4字节) + childCount + failureOffset + children数组
- child references使用32位偏移而非完整指针
- Recognizer（仅接受/拒绝）开发仅用8天，纯PEG特性；Ohm特有特性（参数化规则、左递归）更具挑战性