Parsing Backends

Backend Comparison

How Each Backend Works

Memo Table:
┌─────────┬────────┬─────────────────┐
│ Position│ Rule   │ Cached Result   │
├─────────┼────────┼─────────────────┤
│    0    │ expr   │ Success, len=5  │
│    0    │ term   │ Success, len=2  │
│    2    │ expr   │ Success, len=3  │
│   ...   │  ...   │      ...        │
└─────────┴────────┴─────────────────┘

For input length n with r rules:
Table size = O(n × r)
                

Bytecode for pattern (a*)*:
┌────────┬───────────────────────┐
│ Addr   │ Instruction           │
├────────┼───────────────────────┤
│   0    │ Choice L3 (outer *)   │
│   1    │   Choice L2 (inner *) │
│   2    │     Char 'a'          │
│   3    │     PartialCommit L1  │
│   4    │   L2: Commit          │
│   5    │   PartialCommit L0    │
│   6    │ L3: End               │
└────────┴───────────────────────┘

For input "aaa": tries many paths!
                

When to Use Each Backend

Problematic Grammar Patterns

The following patterns can cause exponential time complexity (O(2^n)) in the Bytecode backend. They are safe with Packrat due to memoization. If your grammar contains any of these patterns, use Packrat.

// CRITICAL - Exponential O(2^n):
(a*)*           // Outer * tries many ways to divide input
(a+)+           // Similar issue with + quantifier
((a|b)*)*       // Nested choice makes it worse
([0-9]*)*       // Same issue with character classes

// MODERATE - Polynomial O(n^k):
(a*b*)*         // k=2 repetitions, polynomial slowdown
(a|b*c*)*       // Mixed, still problematic

// SAFE - Linear O(n):
a*              // Single repetition - no nesting
(a)*            // Same as above - just grouping
(a b)*          // Fixed sequence inside - O(n)
(a+ b+)*        // Multiple but bounded sequences
                

The outer * can try:
  (aaa)           - one group
  (aa)(a)         - two groups
  (a)(aa)         - two groups, different split
  (a)(a)(a)       - three groups
  (aaa)()         - with empty group
  (aa)(a)()       - etc.
Total: O(2^n) possibilities for input of length n
                

// PROBLEMATIC - Many backtrack points:
("a" | "aa" | "aaa" | "aaaa")+    // All start with 'a'
("if" | "iff" | "iffy")+          // Prefix overlap

// BETTER - Distinct first characters:
("a" | "b" | "c")+                // No overlap
("ab" | "cd" | "ef")+             // Distinct prefixes

// BEST - Use negative lookahead:
("aaa" | "aa" | "a")+             // Order longest first
// Or with lookahead:
("a" ~"aa" | "aa" ~"aaa" | "aaa" | "a")+
                

// INVALID - Direct left recursion (infinite loop):
expr = expr "+" term | term

// PROBLEMATIC - Indirect left recursion:
A = B | 'a'
B = A | 'b'    // A → B → A cycle

// CORRECT - Right recursion or iteration:
expr = term ("+" term)*
// or
expr = term ("+" expr)?
                

// PROBLEMATIC - Depth > 10:
(((((((((a | b) | c) | d) | e) | f) | g) | h) | i) | j)

// BETTER - Flatten alternatives:
(a | b | c | d | e | f | g | h | i | j)

// Or use character class:
[a-j]
                

// EXPENSIVE - Lookahead with repetition:
&(.*) "end"     // Scans to end, then backtracks
!"end" .*         // Negative lookahead on every position

// BETTER - Bounded or specific:
&[a-z]+ "end"   // Bounded lookahead
!"end" [a-z]+    // Specific negation
                

Analyzing Your Grammar

Parsanol's grammar analysis is deliberately simple: it checks for nested repetitions, the only pattern that causes exponential time complexity in the Bytecode backend.

Rust API

Why Only Nested Repetitions?

Nested repetitions like (a*)* cause O(2^n) time in the Bytecode backend because the parser must try all possible ways to divide the input. Packrat's memoization solves this by caching each (position, rule) result, guaranteeing O(n) time.

Other patterns don't matter for backend selection:

When to Override Auto-Selection

The auto-selection only considers time complexity. You may want to manually select based on:

GrammarAnalysis Fields

// This is the entire logic:
pub fn recommended_backend(&self) -> Backend {
    if self.has_nested_repetition {
        Backend::Packrat  // Prevents O(2^n)
    } else {
        Backend::Bytecode // Lower memory, faster for simple patterns
    }
}
            

Usage Examples

Automatic Selection (Recommended)

Explicit Backend Selection

Pre-compiled Parser (Best for Repeated Parsing)

Ruby Bindings

Bytecode Optimization Passes

The Bytecode backend applies 11 optimization passes automatically during compilation. These reduce instruction count and improve runtime performance.

Known Behavioral Differences

Both backends produce identical results for the vast majority of patterns. However, there is one edge case where behavior differs:

Pattern: ("a" | "aa") "b"
Input:   "aab"
              

1. Try "a" at pos 0 → Success
2. Try "b" at pos 1 → Fail (input is 'a')
3. Backtrack, try "aa" at pos 0 → Success
4. Try "b" at pos 2 → Success
5. Result: MATCH

Memoization allows re-evaluating
the alternative at pos 0.
                

1. Try "a" at pos 0 → Success
2. Try "b" at pos 1 → Fail (input is 'a')
3. No backtrack point → FAIL

Standard PEG semantics: once
"a" succeeds, "aa" is not tried.
                

Performance Benchmarks

Running Benchmarks

Verify performance claims by running benchmarks on your own machine:

# Run bytecode vs packrat benchmarks
cargo bench --bench bytecode

# Output includes:
# - Packrat vs Bytecode comparison for each grammar
# - Compilation overhead measurement
# - Large input handling comparison
# - Memory usage comparison
            

Expected Results