git.highenergymagic.org

README.md raw

Neotoma

A flexible, cached parser combinator framework for Rust with built-in memoization and backtracking capabilities.

Features

  • Parser Combinators: Compose complex parsers from simple building blocks
  • Built-in Caching: Automatic memoization prevents redundant parsing work
  • Backtracking Support: Efficient backtracking with automatic position management
  • UTF-8 Aware: Dual-level design supporting both byte-level and character-level parsing
  • Generic Input Sources: Works with any Read + Seek implementation
  • Thread Safe: Uses parking_lot for efficient synchronization primitives
  • Grammar Support: Self-parsing grammar system for complex syntax definitions

Quick Start

Add Neotoma to your Cargo.toml:

[dependencies]
neotoma = "0.1"

Basic Example

use neotoma::prelude::*;
use neotoma::{seq, oneof};
use std::io::Cursor;

// Parse "hello world" with optional whitespace
let parser = seq![
    Literal::from_str("hello"),
    Optional::new(Utf8Class::whitespace()),
    Literal::from_str("world")
];

let input = Cursor::new(b"hello world");
let mut source = Source::new(input);

match parse(parser, &mut source) {
    Ok(result) => println!("Parsed: {:?}", result),
    Err(e) => println!("Parse error: {:?}", e),
}

Character Classes

use neotoma::prelude::*;

// Parse one or more digits
let numbers = Utf8Class::with_min("0123456789", 1);

// Parse alphabetic characters
let letters = Utf8Class::alpha();

// Parse alphanumeric with bounds
let identifier = Utf8Class::alphanumeric().with_bounds(1, 20);

Composition with Macros

use neotoma::{seq, oneof};
use neotoma::prelude::*;

// Sequential composition
let sequence = seq![
    Literal::from_str("if"),
    Utf8Class::whitespace(),
    Literal::from_str("true")
];

// Alternative composition  
let choice = oneof![
    Literal::from_str("true"),
    Literal::from_str("false"),
    Utf8Class::digits()
];

Repetition and Lists

use neotoma::prelude::*;

// Zero or more digits
let numbers = Repeat::new(Utf8Class::digits());

// Comma-separated list
let csv = Repeat::new(Utf8Class::alpha())
    .with_joint(Literal::from_str(","));

// Bounded repetition
let bounded = Repeat::new(Utf8Class::alpha())
    .with_bounds(2, 5);

Grammar System

Neotoma includes a self-parsing grammar system that allows you to define complex parsers using a declarative syntax. The GrammarParser can parse grammar definitions and produce executable parsers.

Basic Usage

use neotoma::grammar::GrammarParser;
use neotoma::prelude::*;
use std::io::Cursor;

let grammar_text = r#"
    @start expression
    expression = (number "+" number)
    number = digits
"#;

let grammar_parser = GrammarParser::new();
let mut input = Cursor::new(grammar_text.as_bytes());
let mut source = Source::new(&mut input);

let grammar = parse(grammar_parser, &mut source).unwrap();

// Use the grammar to parse expressions
let mut expr_input = Cursor::new(b"42+24");
let mut expr_source = Source::new(&mut expr_input);
let result = parse(grammar, &mut expr_source).unwrap();

Grammar Syntax

Terminals and Literals

  • "text" - matches literal string (use \" for escaped quotes)
  • eof - matches end of file (ensures complete input consumption)

Character Classes

  • digits - matches one or more decimal digits (0-9)
  • alpha - matches one or more alphabetic characters (ASCII)
  • alphanumeric - matches one or more alphanumeric characters (ASCII)
  • whitespace - matches one or more whitespace characters (ASCII)
  • hexdigits - matches one or more hexadecimal digits (0-9, a-f, A-F)
  • udigits, ualpha, ualphanumeric, uwhitespace - UTF-8 equivalents
  • [abc] - matches any character in the set (custom UTF-8 character class)
  • [^abc] - matches any character NOT in the set (negated UTF-8 character class)

Composition

  • (A B C) - matches A followed by B followed by C (sequence)
  • (| A B C) - matches either A or B or C (alternatives)

Repetition

  • (* A) - matches zero or more instances of A
  • (+ A) - matches one or more instances of A
  • (? A) - matches zero or one instances of A
  • (* A / B) - matches zero or more A’s separated by B
  • (+ A / B) - matches one or more A’s separated by B

Rules and References

  • name = rule - defines a named parsing rule
  • name - references a named rule (enables recursion)
  • @start name - sets the starting rule (defaults to last rule if not specified)

Complex Grammar Example

let arithmetic_grammar = r#"
    @start complete_expression
    
    complete_expression = (expression eof)
    expression = additive_expr
    
    additive_expr = (| addition subtraction multiplicative_expr)
    addition = (multiplicative_expr (? whitespace) "+" (? whitespace) additive_expr)
    subtraction = (multiplicative_expr (? whitespace) "-" (? whitespace) additive_expr)
    
    multiplicative_expr = (| multiplication division primary_expr)
    multiplication = (primary_expr (? whitespace) "*" (? whitespace) multiplicative_expr)
    division = (primary_expr (? whitespace) "/" (? whitespace) multiplicative_expr)
    
    primary_expr = (| number variable parenthesized_expr)
    number = digits
    variable = alpha
    parenthesized_expr = ("(" (? whitespace) expression (? whitespace) ")")
"#;

This grammar handles:

  • Proper operator precedence (multiplication/division before addition/subtraction)
  • Recursive expressions with parentheses
  • Variables and numbers
  • Optional whitespace handling
  • Left-associative operations

Architecture

Neotoma uses a Template Method Pattern for its core Parser trait:

  • read(): Implement your parsing logic here
  • parse(): Public API that automatically handles caching and backtracking
  • id(): Override for parameterized parsers to avoid cache conflicts

Key Design Principles

  • Composability: Orthogonal combinators work together seamlessly
  • Performance: Memoization prevents redundant parsing
  • Type Safety: Generic composition prevents common mistakes
  • Memory Efficiency: Smart pointer integration and optimized data structures

Documentation

Examples

The tests/ directory contains comprehensive examples:

  • Arithmetic Parser: Mathematical expression parsing
  • Lisp Expressions: Recursive data structure parsing
  • Grammar Definitions: Self-parsing grammar systems

Python Bindings

Python bindings are available in the neotoma-py/ directory. See the Python README for details.

License

Licensed under either of:

  • Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
  • MIT License (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contributing

Contributions are welcome! Please feel free to submit a patch.