What is Parsanol?
A high-performance PEG parser library for Rust with Ruby bindings, inspired by Parslet.
In a Nutshell
Parsanol is a parser combinator library that lets you build complex parsers by combining small, simple parsing functions. It separates parsing into two stages: parsing (syntax recognition) and transformation (semantic interpretation).
PEG Parsing
Parsing Expression Grammar with packrat memoization for deterministic, efficient parsing.
Two-Stage Model
Separate parsing from transformation for debuggability and flexibility.
Cross-Language
Rust core with Ruby bindings. Parse once, use from any language via FFI.
Arena Allocation
Zero-copy AST with arena allocation for minimal memory overhead.
Why Use Parsanol?
Traditional parser generators like Yacc/Bison require learning a separate DSL and generate code that's hard to debug. Parser combinators like Parsanol let you write parsers in your host language with full IDE support, type checking, and debugging tools.
✓ Choose Parsanol When:
- • You need modular, composable parsers
- • You want to debug parse trees easily
- • You're building domain-specific languages
- • You need cross-language parsing (Rust + Ruby)
- • You value readable, maintainable code
✗ Consider Alternatives When:
- • You need left-recursive grammars (PEG limitation)
- • Parsing binary formats (use nom instead)
- • You need LR(k) with k > 1 lookahead
Comparison with Other Rust Parsers
| Feature | Parsanol | nom | lalrpop | pest |
|---|---|---|---|---|
| Approach | PEG Combinator | Combinator | LR Parser Gen | PEG Parser Gen |
| Grammar in Code | Yes | Yes | No (DSL) | No (DSL) |
| Two-Stage Model | Yes | No | No | Partial |
| Ruby Bindings | Yes | No | No | No |
| Debug Trees | Excellent | Good | Good | Good |
| Binary Data | Limited | Excellent | Good | Good |
Performance
Parsanol achieves high performance through several key optimizations:
Packrat Memoization
Caches parse results to avoid re-parsing the same input. Transforms O(n³) worst-case into O(n) for most grammars. Uses dense bit-packed cache for memory efficiency.
Arena Allocation
All AST nodes allocated in a single arena. Zero individual allocations means no memory fragmentation. Entire AST freed in one operation.
SIMD Optimization
Uses memchr crate for SIMD-accelerated substring search. Scanning for delimiters is 10-50x faster than naive byte-by-byte comparison.
SmallVec Optimization
Small collections stored on stack, only heap-allocated when they grow. Eliminates allocation overhead for typical parse trees.
Performance Characteristics
What is a Parser Combinator?
A parser combinator is a design pattern where small, simple parsing functions (called atoms) are combined using higher-order functions (called combinators) to build complex parsers.
The Key Insight
Instead of writing one massive parser, you build small, reusable pieces and compose them. This makes parsers modular, testable, and easy to reason about.
Atoms: The Building Blocks
Atoms match the smallest units of input:
str("hello")- Match a literal stringre("[0-9]+")- Match a regex patternany()- Match any single character
Combinators: The Glue
Combinators join atoms together:
.then()- Sequence: match A followed by B.or()- Alternative: match A or B.repeat()- Repetition: match multiple times.maybe()- Optional: match zero or one time