zgram

JIT-compiled PEG parser generator for Python.

Compiles grammars to SIMD-accelerated native code via LLVM JIT, callable from Python with zero-copy text access and a rich Pythonic API.

Built with PyOZ

Performance

zgram compiles PEG grammars into SIMD-accelerated native code via LLVM JIT at runtime. No subprocess, no disk cache, no .so files -- grammars compile in-process in milliseconds.

On a JSON parsing benchmark (from Python, including call overhead):

Small JSON (43 bytes):    0.1us  -  6x faster than json.loads
Medium JSON (1.2KB):      1.0us  -  4x faster than json.loads
Large JSON (15KB):       16.1us  -  5x faster than json.loads

Compared to other Python parser generators:

Against the fastest parsing libraries in C++ and Rust (Spirit X3, lexy, PEGTL, rust-peg, pest), zgram is the fastest in 15 of 16 benchmark comparisons across a JSON and an expression grammar, whether they build a parse tree or only validate: Spirit X3 building the same flat node array takes 1.3-1.7x longer on typical input, rust-peg with tree actions 3-10x, and for validation only (matches()) compile-time C++ takes 1.2-2.7x longer. The exception is a deeply nested expression tree, where Spirit X3 is 9% faster. See BENCHMARK.md. String-heavy input is where zgram's SIMD code shines: a 75 KB JSON document of long strings parses in 10us (7.5 GB/s).

json.loads does more work (parses + builds Python dicts/lists). zgram returns a zero-copy parse tree.

A small language

examples/tiny is a complete language in about 300 lines: functions, if/while/break/return, variables and expressions. The grammar builds the AST directly (labels, @left folding, -> Class actions), a tree-walking interpreter runs it, and syntax and runtime errors come out as the same kind of diagnostic:

program.tiny:1:13: error: expected expression [syntax]
    1 | let x = 1 + ;
      |             ^
program.tiny:2:7: error: undefined name 'y' [undefined-name]
    2 | print(y);
      |       ^

SQL-to-MongoDB Converter

The included sql2mongo example demonstrates zgram as a real-time query translator. It walks the tree through to_tuple(), so zgram's share of each conversion (parse plus tree export) is about 1-1.5us; the rest is the Python walk and formatting the MongoDB query with json.dumps:

Query                    Parse (us)   Convert (us)   Overhead      Ops/sec
---------------------- ------------ -------------- ---------- ------------
Simple SELECT *               0.1us          7.1us      7.0us     140,434
WHERE filter                  0.3us         12.5us     12.2us      80,184
AND + comparisons             0.3us         15.4us     15.2us      64,739
BETWEEN range                 0.1us         10.9us     10.7us      91,836
IN list                       0.2us         12.4us     12.3us      80,329
LIKE pattern                  0.2us         10.6us     10.4us      94,768
IS NOT NULL                   0.2us          9.9us      9.8us     100,631
ORDER + LIMIT                 0.3us         15.3us     15.0us      65,262
DISTINCT                      0.1us          1.2us      1.1us     854,145
COUNT aggregate               0.3us         12.7us     12.4us      78,905
Nested boolean                0.4us         22.3us     21.9us      44,795
Pagination                    0.2us         12.8us     12.7us      77,836

Installation

pip install zgram-py

The package is named zgram-py on PyPI (zgram is taken); the module is zgram:

import zgram

Prebuilt wheels cover CPython 3.10+ on x86_64 Linux (glibc 2.17+) and x86_64 Windows. ARM (aarch64 Linux, Windows on ARM, Apple Silicon) isn't supported yet: the bundled LLVM only includes the x86 code generator.

From source

Requires Zig 0.16. pip install . builds through the PyOZ build backend.

pip install .

Quick Start

import zgram

# Define a grammar using PEG syntax
parser = zgram.compile("""
    value   = object | array | string | number | 'true' | 'false' | 'null'
    object  = '{' (pair (',' pair)*)? '}'
    pair    = string ':' value
    array   = '[' (value (',' value)*)? ']'
    string  = '"' (escape | plain)* '"'
    @silent escape = '\\\\' ["\\\\/bfnrt]
    @silent plain  = [^"\\\\]+
    number  = '-'? ('0' | [1-9] [0-9]*) ('.' [0-9]+)?
""")

# Parse input - returns the root Node
tree = parser.parse('{"name": "Alice", "scores": [100, 200]}')

# Navigate the tree
print(tree.rule())    # 'value'
print(tree.text())    # '{"name": "Alice", "scores": [100, 200]}'
print(len(tree))      # number of direct children

Grammar Syntax

zgram uses PEG (Parsing Expression Grammar) syntax:

rule_name = expression

The first rule is the start rule. A grammar can have up to 4096 rules.

@silent Annotation

Rules annotated with @silent match input but produce no node in the parse tree. Use this for whitespace, delimiters, and other structural rules you don't need in the tree:

value  = ws (number | string) ws
number = [0-9]+
string = '"' chars '"'
@silent chars = [^"]*
@silent ws    = [ \t\n\r]*

@memo Annotation

PEG parsers backtrack: when an alternative fails, the next one re-parses the same input. Usually that's cheap, but a rule tried several times at the same position on every level of nesting makes parsing exponential:

expr = term '+' expr / term '-' expr / term
@memo term = '(' expr ')' / 'x'

@memo caches each rule result per input position (packrat parsing), so the rule runs at most once per position. On 14 levels of parentheses the grammar above parses in 0.014 ms with @memo and 56 ms without, and each two extra levels multiply the unmemoized time by 10. Results and error messages are identical either way. Memoization costs a table lookup per call, so add it to the rules that are re-tried, not everywhere. Annotations combine in any order: @silent @memo ws = ....

Predicates (!e, &e) are composable: !!e, !&e, &!e all work as expected.

Labels

label:rule on a rule reference names that child. The label is stored in the child's node:

if_stmt = 'if' ws cond:expr ws then:block (ws 'else' ws else_:block)?

node.get("cond")      # the child labelled cond, or None
node.get_all("body")   # all children with that label (labels inside * or +)
child.field()         # 'cond', or None for an unlabelled node
parser.fields()       # every label of the grammar

Only rule references can be labelled. A label on a @silent rule applies to every node that rule produces. A grammar can use up to 255 distinct labels. Labels cost one extra write per labelled child; a grammar without labels compiles to the same code as before.

Folding chains: @left, @right, @postfix

PEG has no left recursion, so 1 + 2 - 3 is written product (addop product)* and parses to a flat node sum[1, +, 2, -, 3], with a sum wrapper around every lone operand. The fold annotations make the parser produce the nested tree instead:

@left sum     = left:product (ws op:addop ws right:product)*
@left product = left:atom (ws op:mulop ws right:atom)*

@postfix is for suffix chains where each suffix is its own kind of node: the suffix node adopts everything to its left as its first child, under the head's label.

@postfix post = target:primary (call | index | member)*
call   = '(' args:arglist? ')'
index  = '[' index:expr ']'
member = '.' name:ident

a.b(c)[d] becomes index(target=call(target=member(target=a, name=b), args=c), index=d).

A folded rule must have the form head (group)* (the group may also use ? or +) and can't be @silent. If the head isn't exactly one node, or a @postfix repetition isn't, the rule's own node is used as the wrapper. Folding happens during the parse, in place. Compared with the flat grammar, a folded one takes the same time or less where no operator matches, about 1.3x on input made only of single operators (a + b), and about 1.6x on input made only of longer chains.

Building an AST: -> name and parse_ast()

-> name after a rule says what its node becomes. parser.parse_ast(text) parses, then converts the tree bottom-up in one native pass:

from dataclasses import dataclass

@dataclass
class BinOp:
    left: object
    op: str
    right: object

@dataclass
class Number:
    text: str

parser = zgram.compile("""
    @left sum = left:number (op:addop right:number)*   -> BinOp
    number    = [0-9]+                                 -> Number
    addop     = [+\-]                                  -> str
""", ast={"BinOp": BinOp, "Number": Number})

parser.parse_ast("1+2-3")
# BinOp(left=BinOp(left=Number(text='1'), op='+', right=Number(text='2')), op='-', right=Number(text='3'))

For -> Name, labelled children become keyword arguments: a label inside */+ (or used twice) is always a list, any other label is the value or None when absent. Unlabelled children are not passed. A rule without labels passes its children's values positionally, or its matched text if it can't have children (Number(text='1') above).

ast is a dict or any object with the names as attributes (a module); parser.bind(ast) sets it after compiling. Objects built by -> Name get two attributes, unless they can't take attributes (or parse_ast(text, spans=False)): __zspan__ = (start, end), their byte offsets, and __znode__, the index of their node in the tree.

parse_ast(text) is parse(text).to_ast(). Use the two-step form to keep the tree as well: node.to_ast() converts any subtree, and __znode__ then identifies each object's node in node.tree.

A JSON grammar with -> dict, -> list, -> float and -> unquote converts the 16 KB benchmark document in about 1.5x the time of json.loads (85 us against 55 us).

API Reference

Module Functions

zgram.compile(grammar: str, ast=None) -> GrammarParser

Compile a PEG grammar string into a native parser via LLVM JIT. ast supplies the classes named by -> Name actions (see Building an AST). Compilation happens in-process -- no subprocess, no disk I/O -- and releases the GIL. The 16 most recently compiled grammars are cached, so compiling the same grammar again returns in microseconds.

await zgram.compile_async(grammar: str, ast=None) -> GrammarParser

Compile on a worker thread without blocking the event loop (a cold compile takes ~100 ms of LLVM work). ast is bound when the compile finishes, as in compile(); a missing class raises ValueError from the await. grammar is positional-only here.

zgram.clear_cache() -> None

Drop the compiled-grammar cache. Existing parsers keep working.

zgram.dump_ir(grammar: str) -> str

Return the LLVM IR text for a grammar (useful for debugging/optimization).

zgram.version() -> str

Return the zgram version string.

GrammarParser

parser = zgram.compile("start = [a-z]+")
tree = parser.parse("hello")

• parse(input: str | bytes, start: str | None = None) -> Node -- Parse the whole input and return the root node. Raises ParseError on failure. start picks the start rule (default: the first rule). bytes input must be UTF-8 if you call text().
• match(input: str | bytes, start: str | None = None) -> Node | None -- Match the start rule at the beginning of the input without requiring it to consume everything (like re.match). The root node's end() is where the match stopped. Returns None if it doesn't match.
• matches(input: str | bytes, start: str | None = None) -> bool -- Does the whole input match? Runs a separate validation-only parser that builds no tree (about 2x faster than parse()). On False, error explains the rejection. The validator is compiled on the first call (0.1-1 s depending on grammar size) and cached with the grammar.
• parse_ast(input: str | bytes, start: str | None = None, spans: bool = True) -> object -- Parse the whole input and convert the tree to values as the rules' -> name actions say. Raises ParseError on failure.
• parse_tree(input: str | bytes, start: str | None = None) -> Tree -- Parse the whole input and return the Tree (see Tree).
• bind(ast) -> None -- Supply (or replace) the classes named by -> Name actions.
• rules() -> list[str] -- The grammar's rule names, in definition order.
• fields() -> list[str] -- The grammar's labels, in order of first use.
• actions() -> list[str | None] -- Each rule's -> name action, by rule id (None for a rule without one).
• error -> ParseErrorInfo | None -- Property with error details from the last failed parse()/match().

parser = zgram.compile(json_grammar)
parser.parse("42", start="number")      # parse with another start rule
m = parser.match('{"a": 1} trailing')   # prefix match
print(m.end())                           # 9

Node

A node in the parse tree. Supports the full Python sequence and iterator protocols.

Each parse() call produces its own tree, which keeps the input string and the parser alive. Nodes stay valid after the parser variable goes out of scope and after later parse() calls on the same parser:

node = zgram.compile("root = [a-z]+").parse("hello")
print(node.text())  # "hello" -- the node keeps its tree, input and parser alive

first = parser.parse("[1, 2]")
second = parser.parse("[3]")
print(first.text())  # still "[1, 2]"

Methods

node.rule()        # Grammar rule name that matched: 'string'
node.text()        # Matched text (zero-copy): '"hello"'
node.start()       # Byte offset of match start: 0
node.end()         # Byte offset of match end: 7
node.child_count() # Number of direct children: 2
node.child(i)      # Get child by index, or None
node.children()    # All children as a list[Node]
node.find("name")  # This node and its descendants matching a rule -> list[Node]
node.parent()      # The node this one is a child of, or None for the root
node.tree          # The Tree this node belongs to (property)
node.index         # Index of this node in the tree's node array (property)
node.field()       # Label this node was matched under ('cond'), or None
node.get("cond")   # First child with that label, or None
node.get_all("arg") # All children with that label -> list[Node]
node.to_tuple()    # Whole subtree as nested tuples, built natively (see below)
node.to_ast()      # Subtree converted by the rules' -> actions (see parse_ast)

start() and end() are byte offsets into the UTF-8 encoded input. They equal string indices only for ASCII input; for other text, use text() or slice input.encode().

rule() returns the same interned string object for every node of a rule, so node.rule() is other.rule() holds and comparisons are cheap.

Protocols

len(node)           # Same as child_count()
node[0]             # Indexing with negative index support
node[-1]            # Last child

for child in node:  # Iteration over direct children (O(1) per step;
    print(child)    # nested loops over the same node are independent)

str(node)           # Matched text
repr(node)          # "Node('rule', 0..7, 2 children)"
bool(node)          # Always True (a Node means the parse succeeded)
node1 == node2      # Equality by position and parse identity

Bulk export: to_tuple()

Creating a Python object per node is the main cost of walking a tree from Python. to_tuple() builds the whole subtree in one native pass as nested (rule, text, children) tuples -- or (rule, start, end, text, children) with spans=True:

tree = parser.parse("[1, true]")
tree.to_tuple()
# ('value', '[1, true]', (('array', '[1, true]', (('value', '1', (('number', '1', ()),)), ('value', 'true', ()))),))

On the 15 KB benchmark JSON, converting the tree with to_tuple() takes 145 us, against 929 us for the equivalent walk through the Node API.

Tree Search

# Find all nodes matching a rule name, in document order
strings = tree.find("string")
for s in strings:
    print(s.text())

# Nested iteration
for child in tree:
    for grandchild in child:
        print(grandchild.rule(), grandchild.text())

Tree

parser.parse_tree(text) (or node.tree) gives the whole result of a parse, for code that reads the node array itself:

tree = parser.parse_tree("ab=12")
tree.root      # the root Node
tree.node(i)   # the Node at index i of the node array (the inverse of node.index)
len(tree)      # number of nodes
tree.nodes     # bytes: a copy of the node array, 16 bytes per node, in pre-order
tree.input     # bytes: the parsed text as UTF-8 (node offsets index into it)
tree.rules     # rule names by rule id
tree.fields    # label names by field id - 1
tree.capsule   # PyCapsule "zgram.tree.v1" for native code

Each node is four little-endian uint32: text_start, text_end, subtree_size (number of descendants, which follow the node directly) and meta = child count (bits 0-11, 4095 meaning "4095 or more") | rule id (bits 12-23) | field id (bits 24-31, 0 = unlabelled).

The capsule points to this C struct (TreeView in src/parse_abi.zig), which reads the nodes and input in place, without copying. The capsule keeps the tree alive. zgram.TREE_ABI (currently 1) is the struct's abi field; native code should check it before reading anything else.

typedef struct { const char *ptr; size_t len; } zgram_str;   /* not NUL-terminated */
typedef struct { uint32_t text_start, text_end, subtree_size, meta; } zgram_node;
typedef struct {
    uint32_t abi;               /* zgram.TREE_ABI */
    uint32_t node_count;
    const zgram_node *nodes;    /* node 0 is the root */
    const char *input;
    size_t input_len;
    uint32_t rule_count;
    uint32_t field_count;
    const zgram_str *rule_names;
    const zgram_str *field_names;
} zgram_tree_v1;

Diagnostic

zgram.Diagnostic is one error, warning or note about a source text. zgram reports syntax errors with it, and it is meant to be shared by everything built on top (semantic checks, runtime errors, editor tooling), so a language's errors look the same whichever stage finds them.

d = zgram.Diagnostic("error", "break-outside-loop", "'break' outside loop", (30, 35))
print(d.render(source, "program.z"))
# program.z:4:5: error: 'break' outside loop [break-outside-loop]
#     4 |     break;
#       |     ^^^^^

Diagnostic(severity, code, message, span, line=0, column=0, notes=()): severity is "error", "warning" or "note"; span is (start, end) in bytes of the UTF-8 source; line and column are 1-based (0 = let render() work them out from the source); notes are further Diagnostics rendered after it ("previous definition is here"). The same names are read-only properties, and diagnostics compare equal by value.

ParseError

Raised when parsing fails. The error points to the furthest position the parser reached, and says what was expected there:

What is expected is worked out as follows:

• Literals and character classes that failed at the furthest position are listed (expected ',' or ')'). Character classes are left out when a literal or a rule is expected too.
• A rule name replaces them when a rule that makes a node failed right where it started: let a = ; expects expr, not everything an expression can begin with. The outermost such rule is named, so errors read the way the grammar names its rules.
• Display names say it better than rule names: with expr "expression" = ... and addop "operator" = ... the messages are expected expression and expected operator or ';'. Rules sharing a display name are listed once.
• Never reported: failures inside predicates, inside @silent rules that can match nothing (whitespace, comments), and what could have made a matched token longer (another digit after 1).
• unexpected input after match: the start rule matched part of the input and nothing failed beyond it.

The generated parser only tracks which rule failed furthest; the detail comes from re-running a failed parse in an interpreter (src/diagnose.zig). Successful parses pay nothing; a failing parse takes about 40x a successful one (0.8 ms for 16 KB). On very deep nesting or pathological backtracking the interpreter gives up and the rule-level error (expected <rule>) is reported.

zgram.ParseError is a ValueError subclass whose message includes the location:

try:
    tree = parser.parse('{"name": }')
except zgram.ParseError as e:
    print(e)  # "line 1, col 9: expected value"

The exception also carries the details as attributes:

except zgram.ParseError as e:
    print(e.message)  # "expected value"
    print(e.line)     # 1
    print(e.column)   # 9 (1-based, in bytes)
    print(e.offset)   # 8 (byte offset)
    print(e.diagnostic.render(source))   # the same error as a Diagnostic

The same details stay available from the parser.error property (a ParseErrorInfo) after a failed parse:

err = parser.error
print(err.message(), err.line(), err.column(), err.offset())

Architecture

Grammar string
     |
     v
[Grammar Parser]   -- PEG syntax -> IR (grammar_parser.zig)
     |                 Left-recursion detection, @silent annotation
     v
[LLVM Codegen]     -- IR -> LLVM IR in memory (jit_codegen.zig)
     |                 SIMD char scanning, inline node allocation,
     |                 high-water mark error tracking
     v
[LLVM JIT]         -- LLVM IR -> native code via ORC LLJIT (jit_compiler.zig)
     |                 O3 optimization, vectorization, host CPU targeting
     v
[Python API]       -- Call JIT'd function, expose Node/GrammarParser (lib.zig)
                       Zero-copy input and text, per-parse trees, freelist pooling

Key implementation details:

• LLVM JIT compilation: Grammars compile to native x86-64 code in-process via LLVM's ORC LLJIT. No subprocess, no .so files, no disk cache. Each grammar gets its own ResourceTracker for independent cleanup.
• SIMD character scanning: Character class repetitions ([a-z]+, [^"\\]*) test the first 8 bytes one at a time (most runs are a space or a few digits) and continue in an out-of-line 16-byte (SSE2) or 32-byte (AVX2) vector loop only for longer runs. Single ranges, small included sets and small excluded sets are vectorized, including through @silent rules and in loops like JSON's (escape | plain)*: when the other branches can't start with a byte of the class, runs of it are scanned in bulk and the other branches are tried only where a run stops.
• Inline node allocation: Rule functions reserve nodes via an inlined fast path (compare + increment) with a slow path fallback to zgram_ensure_capacity. Node filling is also inlined -- no function call overhead per node.
• High-water mark errors: Every rule failure updates max_pos = max(max_pos, pos). On parse failure, the error is reported at the furthest position reached with "expected <rule_name>".
• Flat node tree: 16-byte FlatNode structs in pre-order with subtree sizes; the last word packs the child count (12 bits, saturating: larger nodes are counted by stepping through their children), the rule id (12 bits) and the label's field id (8 bits). Iterating children steps from sibling to sibling in O(1), and find() is a linear scan, because a node's descendants are contiguous.
• Per-parse trees: each parse writes into its own node buffer, which becomes a tree object holding a reference to the input str/bytes. Parsing reads the string's own UTF-8 buffer (no input copy), and text() slices it without copying. Nodes are small (tree reference + index) and reference the tree, so they stay valid across later parses.
• Compile cache: compiled grammars are shared and reference-counted; the 16 most recent stay cached.

Threads and Async

• compile() releases the GIL, and compiles from several threads (or compile_async() tasks) run in parallel.
• parse()/match() release the GIL for inputs of 16 KB or more, so threads can parse in parallel: four threads parsing a 410 KB document take about as long as one.
• A GrammarParser can be shared between threads. Its error property reflects the most recent failed parse from any thread.
• Free-threaded CPython (3.14t) isn't supported yet: the wheels use the stable ABI, which doesn't cover it.

Known Issues

• Each distinct grammar compiled leaves about 130 KB inside LLVM's JIT after its parsers are freed. The compile cache means repeated grammars cost nothing, but compiling many different grammars in a long-running process grows memory slowly.

Project Structure

src/
  lib.zig               # Python module: Node, GrammarParser, compile cache, ParseError
  grammar_parser.zig    # PEG grammar -> IR (with left-recursion detection)
  jit_codegen.zig       # IR -> LLVM IR (SIMD, inline alloc, HWM tracking)
  jit_compiler.zig      # LLVM ORC LLJIT compilation + ResourceTracker
  jit_helpers.zig       # Runtime helpers called by JIT code (node alloc, errors)
  llvm_builder.zig      # Ergonomic wrapper over LLVM C API
  parse_abi.zig         # FlatNode/ParseOutput C ABI structs (16 bytes per node)
  diagnose.zig          # PEG interpreter that re-runs failed parses for precise errors
test/
  conftest.py                  # Shared fixtures (JSON/list grammars)
  test_node_api.py             # Node/GrammarParser Python API tests
  test_features.py             # Compile cache, async, start rules, match, to_tuple, @memo, threads, SIMD loops
  test_differential.py         # Random grammars/inputs checked against peg_reference.py
  peg_reference.py             # Reference PEG interpreter in Python (for differential tests)
  test_grammar_correctness.py  # Grammar pattern correctness
  test_json_parsing.py         # JSON parsing: values, structures, errors
  test_edge_cases.py           # 115 edge case tests (@silent, backtracking, GC, etc.)
  test_hwm.py                  # High-water mark error position tests
  test_labels.py               # label:rule, Node.field/get/get_all
  test_fold.py                 # @left / @right / @postfix chain folding
  test_ast.py                  # -> actions and parse_ast()
  test_tree.py                 # parse_tree(), Tree, the zgram.tree.v1 capsule
  test_diagnostic.py           # Diagnostic, ParseError.diagnostic
  test_error_messages.py       # "expected ';'" errors from the diagnosis pass
  test_example_tiny.py         # The tiny example language
  test_benchmark_json.py       # Multi-parser comparative benchmark
  test_benchmark_sql2mongo.py  # SQL-to-MongoDB latency benchmark
examples/sql2mongo/
  sql2mongo.py          # SQL SELECT -> MongoDB query converter example
examples/tiny/
  tiny.py               # A small language: grammar -> AST -> interpreter, with diagnostics
  fib.tiny              # A program in it
build.zig               # Zig build configuration
pyproject.toml          # Python package configuration

License

MIT