Crate sipha_pratt 

Pratt parser for operator precedence parsing.

This crate provides support for Pratt expression parsing, which handles operator precedence and associativity elegantly. It’s particularly useful for parsing mathematical expressions and other operator-heavy constructs.

Algorithm Overview

Pratt Parsing Algorithm

Pratt parsing (Top-Down Operator Precedence Parsing) uses “binding powers” (precedence) to determine operator grouping:

1. Parse Expression: Start with minimum precedence
2. Parse Left Operand: Recursively parse with current precedence
3. Check Operator: Look ahead for operator token
4. Compare Precedence: If operator precedence > current, parse right operand
5. Handle Associativity:
   • Left-associative: right precedence = operator precedence
   • Right-associative: right precedence = operator precedence - 1
   • Non-associative: error on chaining
6. Build AST: Create binary/unary node with parsed operands

Time Complexity: O(n) where n is number of tokens Space Complexity: O(d) where d is expression depth (recursion stack)

Precedence Levels

Higher precedence values bind more tightly:

• Multiplication/Division: Precedence(20)
• Addition/Subtraction: Precedence(10)
• Assignment: Precedence(5)

Associativity

• Left: a + b + c → (a + b) + c
• Right: a = b = c → a = (b = c)
• None: a < b < c → Error (cannot chain)

Rule Types

• Prefix: -x, !x (operators before operand)
• Binary: x + y (operators between operands)
• Postfix: x++, x! (operators after operand)
• Ternary: cond ? true : false (three-part operators)
• Atom: Leaf nodes (literals, identifiers, parenthesized expressions)

Modules

prelude

Prelude module containing commonly used types.

Structs

AtomRule

Pratt rule describing an atom (leaf node).

BinaryRule

Pratt rule describing a binary operator.

PostfixRule

Pratt rule describing a postfix operator.

Precedence

Operator precedence wrapper.

PrefixRule

Pratt rule describing a prefix operator.

TernaryRule

Pratt rule describing a ternary operator.

Enums

Associativity

Associativity for binary operators.

PrattRuleKind

Pratt rule kinds supported by the parser.