sipha_pratt/lib.rs
1//! Pratt parser for operator precedence parsing.
2//!
3//! This crate provides support for Pratt expression parsing, which handles
4//! operator precedence and associativity elegantly. It's particularly useful
5//! for parsing mathematical expressions and other operator-heavy constructs.
6//!
7//! # Algorithm Overview
8//!
9//! ## Pratt Parsing Algorithm
10//!
11//! Pratt parsing (Top-Down Operator Precedence Parsing) uses "binding powers"
12//! (precedence) to determine operator grouping:
13//!
14//! 1. **Parse Expression**: Start with minimum precedence
15//! 2. **Parse Left Operand**: Recursively parse with current precedence
16//! 3. **Check Operator**: Look ahead for operator token
17//! 4. **Compare Precedence**: If operator precedence > current, parse right operand
18//! 5. **Handle Associativity**:
19//! - Left-associative: right precedence = operator precedence
20//! - Right-associative: right precedence = operator precedence - 1
21//! - Non-associative: error on chaining
22//! 6. **Build AST**: Create binary/unary node with parsed operands
23//!
24//! **Time Complexity**: O(n) where n is number of tokens
25//! **Space Complexity**: O(d) where d is expression depth (recursion stack)
26//!
27//! ## Precedence Levels
28//!
29//! Higher precedence values bind more tightly:
30//!
31//! - Multiplication/Division: Precedence(20)
32//! - Addition/Subtraction: Precedence(10)
33//! - Assignment: Precedence(5)
34//!
35//! ## Associativity
36//!
37//! - **Left**: `a + b + c` → `(a + b) + c`
38//! - **Right**: `a = b = c` → `a = (b = c)`
39//! - **None**: `a < b < c` → Error (cannot chain)
40//!
41//! ## Rule Types
42//!
43//! - **Prefix**: `-x`, `!x` (operators before operand)
44//! - **Binary**: `x + y` (operators between operands)
45//! - **Postfix**: `x++`, `x!` (operators after operand)
46//! - **Ternary**: `cond ? true : false` (three-part operators)
47//! - **Atom**: Leaf nodes (literals, identifiers, parenthesized expressions)
48
49mod associativity;
50mod precedence;
51mod rules;
52
53pub use associativity::Associativity;
54pub use precedence::Precedence;
55pub use rules::{AtomRule, BinaryRule, PostfixRule, PrattRuleKind, PrefixRule, TernaryRule};
56// Note: PrattParser trait is defined in sipha-parse to avoid circular dependencies
57
58/// Prelude module containing commonly used types.
59pub mod prelude {
60 pub use crate::{
61 associativity::Associativity,
62 precedence::Precedence,
63 rules::{BinaryRule, PostfixRule, PrattRuleKind, PrefixRule, TernaryRule},
64 };
65}