sipha-memo

Memoization support for packrat parsing in sipha.

Overview

sipha-memo provides memoization tables for caching parse results at specific positions, enabling packrat parsing which can handle left-recursive grammars and improve performance for ambiguous grammars.

Features

MemoTable: Cache for parse results keyed by (rule_id, position) pairs
MemoEntry: Cached parse results (success or failure)
Enable/disable memoization at runtime
Efficient lookup and storage

Quick Start

Add sipha-memo to your Cargo.toml:

[dependencies]
sipha-memo = "0.1.1"

Example

use sipha_memo::{MemoTable, MemoEntry};
use sipha_core::traits::{TokenKind, RuleId};
use sipha_tree::RawNodeId;

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
enum Token { A }
impl TokenKind for Token { fn is_trivia(&self) -> bool { false } }

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
enum Rule { Expr }

let mut memo: MemoTable<Token, Rule, RawNodeId> = MemoTable::new();
memo.store_success(Rule::Expr, 0, RawNodeId(0), 5);

if let Some(entry) = memo.get(Rule::Expr, 0) {
    match entry {
        MemoEntry::Success { node, consumed } => {
            println!("Cached: node {:?}, consumed {} tokens", node, consumed);
        }
        _ => {}
    }
}

License