Working with trees & tokens

parse hands you a Tree: a rule node with a data name and a list of children. Its leaves are Tokens — a type (the terminal name), a value (the matched text), and six code-point positions. A child can also be a null/None hole (an omitted optional under maybe_placeholders), which is why walking code checks what a child is before reading it. That is the whole data model, and it is the same in every target.

(If you know Lark, this is its Tree/Token shape exactly — hyperlark implements it natively.)

Same capability, idiomatic spelling

Every target exposes the same operations; only the spelling changes. Python and TypeScript give you plain objects; Rust and C give you a borrowed cursor over a retained arena (no eager copy-out).

Capability	Python	TypeScript	Rust	C
Parse result	Tree (returned)	Tree (returned)	ParseResult → .root()	LarkParseResult → lark_root
Rule name	tree.data	tree.data	cursor.data()	lark_node_data
Children	tree.children	tree.children	cursor.children()	lark_node_child / _child_count
Tree vs token vs hole	isinstance(x, Tree)	isTree(x) / isToken(x)	cursor.kind() → NodeKind	lark_node_kind
Token type / value	tok.type / tok.value	tok.type / tok.value	cursor.token() → &Token	lark_node_token_type / _token_value (_token_value_copy for a C string)
Positions	tok.start_pos …	tok.start_pos …	tok.line() / tok.column() …	lark_node_token_positions
Pretty-print	tree.pretty()	pretty(tree)	result.pretty()	lark_result_pretty
Find by rule	tree.find_data(n)	findData(tree, n)	result.find_data(n)	lark_cursor_find_data
Find by token	tree.find_token(t)	findToken(tree, t)	result.find_token(t)	lark_cursor_find_token
Ordered walks	iter_subtrees() …	handle.subtrees() …	recurse children()	lark_cursor_new_*

A running grammar

A tiny assignment list — un-inlined so the tree shape is explicit. Call it GRAMMAR below:

start: assign+
assign: NAME "=" NUMBER
NAME: /[a-z]+/
NUMBER: /[0-9]+/
%ignore " "

Parsing x = 1 y = 22 gives two assign subtrees, each holding a NAME and a NUMBER token (the "=" literal is anonymous and filtered out):

start
  assign
    x
    1
  assign
    y
    22

Reading a tree

Reach the first NUMBER and read its value and position.

Python

Tokens compare by value (num == "1") and support the usual string operations, and also carry .type and the positions — but by default (fast_tokens=True) they are not str subclasses; pass fast_tokens=False for lark-identical str-subclass tokens.

import hyperlark as lark

parser = lark.Lark(GRAMMAR, parser="lalr")
tree = parser.parse("x = 1  y = 22")

tree.data                 # "start"
len(tree.children)        # 2  — two `assign` subtrees
first = tree.children[0]           # a Tree
name, num = first.children         # two Tokens
num.type                  # "NUMBER"
num.value                 # "1"  (and num == "1")
num.line, num.column      # (1, 5)  — 1-based, code points

TypeScript

A child is a Tree, a Token, or null; the isTree / isToken guards narrow it (and satisfy TypeScript).

import { Lark, isTree, isToken } from "hyperlark";

const parser = new Lark(GRAMMAR, { parser: "lalr" });
const tree = parser.parse("x = 1  y = 22");   // { data, children }

tree.data;                    // "start"
tree.children.length;         // 2
const first = tree.children[0];
if (isTree(first)) {
  const [name, num] = first.children;
  if (isToken(num)) {
    num.type;                 // "NUMBER"
    num.value;                // "1"
    num.line, num.column;     // 1, 5
  }
}

Rust

root() returns a Cursor; kind() classifies a node, and children() yields child cursors. cursor.token() borrows the &Token at a leaf.

use hyperlark::{Lark, NodeKind};

let parser = Lark::new(GRAMMAR)?;               // LALR under all defaults
let result = parser.parse("x = 1  y = 22")?;    // ParseResult

let root = result.root();                        // Cursor at the root
assert_eq!(root.data(), Some("start"));
let first = root.children().remove(0);           // the first `assign`
for child in first.children() {
    if let NodeKind::Token(tok) = child.kind() {
        // tok: &Token — value derefs to &str; line()/column() are u32
        println!("{} @ {}:{}", tok.value, tok.line(), tok.column());
    }
}

C

The by-value lark_root / lark_child forms chain safely (a miss returns the NULL node). Name/value come back as (ptr, len) slices — not NUL-terminated — that borrow the result.

That last point has a consequence worth knowing before you hit it: you cannot hand a token value straight to strtod, strtol or sscanf. Either read the slice in place with a range-based parser (C++17 std::from_chars, fast_float) and copy nothing, or use lark_node_token_value_copy to copy it into your own buffer NUL-terminated. A value that does not fit is rejected, never truncated — so check the status.

LarkParseResult *res = NULL;
lark_parse(p, "x = 1  y = 22", 13, NULL, &res);

LarkNode root = lark_root(res);            /* LARK_NODE_TREE */
const char *name; size_t nlen;
lark_node_data(root, &name, &nlen);        /* "start" */

LarkNode first = lark_child(root, 0);      /* first `assign` */
LarkNode num   = lark_child(first, 1);     /* child 0 is NAME, 1 is NUMBER */
if (lark_node_kind(num) == LARK_NODE_TOKEN) {
    const char *t, *v; size_t tl, vl;
    lark_node_token_type(num, &t, &tl);    /* "NUMBER" */
    lark_node_token_value(num, &v, &vl);   /* "1" — (ptr,len), no NUL */
    LarkTokenPositions pos;
    lark_node_token_positions(num, &pos);  /* pos.line, pos.column, … */

    char buf[32]; double d = 0;            /* want a C string? copy it out */
    if (lark_node_token_value_copy(num, buf, sizeof buf, NULL) == LARK_OK)
        d = strtod(buf, NULL);             /* 1.0 — needs <stdlib.h> */
}
lark_result_free(res);                     /* frees every cursor/slice above */

Pretty-printing

The same indented rendering as Lark’s Tree.pretty — handy for debugging.

Python

print(tree.pretty())

TypeScript

import { pretty } from "hyperlark";
console.log(pretty(tree));

Rust

println!("{}", result.pretty());

C

/* Owned by the result, cached, never freed by you: */
printf("%s", lark_result_pretty(res));

Queries: find by rule or token

find_data(name) yields every subtree with that rule name, and find_token(type) every token of that terminal type — both bottom-up, innermost match first (Lark’s iter_subtrees order), which matters when a rule nests inside itself. They save you a hand-written recursion when you only want some of the tree.

Python

for a in tree.find_data("assign"):        # each `assign` subtree
    print(a.children[0], "=", a.children[1])
total = sum(int(t) for t in tree.find_token("NUMBER"))   # 23

On a large tree, Lark(GRAMMAR, fast_scan=True) runs these queries natively over the parse arena — only matched nodes cross into Python. Results are identical; it is purely an opt-in speedup.

TypeScript

The queries are free functions from the toolkit (they take the tree first).

import { findData, findToken } from "hyperlark";

for (const a of findData(tree, "assign")) { /* a: Tree */ }
let total = 0;
for (const t of findToken(tree, "NUMBER")) total += Number(t.value);  // 23

Rust

find_data yields Cursors (innermost matches first); find_token yields &Tokens directly.

for a in result.find_data("assign") {          // a: Cursor
    let kids = a.children();
    // kids[0] is NAME, kids[1] is NUMBER
}
let total: i64 = result
    .find_token("NUMBER")
    .filter_map(|t| t.value.parse::<i64>().ok())
    .sum();                                     // 23

C

A query is a cursor: construct it, pull hits with lark_cursor_next, free it before the result.

LarkTreeCursor *cur = NULL;
lark_cursor_find_data(res, lark_root(res), "assign", 6, &cur);
LarkNode hit;
while (lark_cursor_next(cur, &hit)) {
    /* hit is an `assign` node */
}
lark_cursor_free(cur);

Walking in a chosen order

For a full traversal, four orders are available (the vocabulary is shared; each target names them its own way):

Order	Visits	Lark name
subtrees	every subtree, leaves-first (snapshot)	iter_subtrees
topdown	every subtree, root-first (live; prunable)	iter_subtrees_topdown
postorder	depth-first, children before parent	Visitor_Recursive order
leaves	non-tree leaves only (tokens / holes)	scan_values

Python

The Tree walk methods are the orders directly; tokens fall out via scan_values (or just index children).

for sub in tree.iter_subtrees():          # leaves-first
    print(sub.data)
for sub in tree.iter_subtrees_topdown():  # root-first
    print(sub.data)

TypeScript

For a large tree, parseHandle keeps the nodes WASM-side and hands you cursors — no eager copy-out. Cursors are iterable and self-free at the end of the loop; each yields a numeric position you resolve with the handle.

using handle = parser.parseHandle("x = 1  y = 22");

for (const pos of handle.subtrees())          // leaves-first
  console.log(handle.data(pos));              // rule name, or undefined for a leaf
for (const pos of handle.leaves())            // tokens / holes
  console.log(handle.token(pos)?.value);
// handle.topdown() / handle.postorder() / handle.findData("assign") too

The eager toolkit forms — iterSubtrees(tree), iterSubtreesTopdown(tree), scanValues(tree, pred) — walk a materialized tree instead.

Rust

Recurse the Cursor for a full walk; use find_data / find_token for the filtered bottom-up passes. Both are iterative internally, so tree depth is never stack-bounded.

fn walk(c: &hyperlark::Cursor) {
    match c.kind() {
        hyperlark::NodeKind::Tree { data } => {
            println!("{data}");
            for child in c.children() {
                walk(&child);
            }
        }
        hyperlark::NodeKind::Token(tok) => println!("  {}", tok.value),
        _ => {}                              // None hole / foreign
    }
}
walk(&result.root());

C

One constructor per order; drive it with lark_cursor_next. topdown can prune with lark_cursor_skip_children.

LarkTreeCursor *cur = NULL;
lark_cursor_new_subtrees(res, lark_root(res), &cur);   /* leaves-first */
LarkNode n;
while (lark_cursor_next(cur, &n)) {
    if (lark_node_kind(n) == LARK_NODE_TREE) { /* … */ }
}
lark_cursor_free(cur);
/* also: _new_topdown / _new_postorder / _new_leaves */

Positions & propagate_positions

Every token carries its six code-point positions everywhere, no flag needed: start_pos / end_pos (offsets), line / end_line, and column / end_column (both 1-based). Offsets and columns count Unicode code points, not bytes.

Turning on propagate_positions additionally attaches a per-node Meta — the span covering a subtree’s tokens — so you can ask where a whole rule sits, not just its leaves.

Python

parser = lark.Lark(GRAMMAR, parser="lalr", propagate_positions=True)
tree = parser.parse("x = 1  y = 22")
m = tree.children[0].meta          # Meta of the first `assign`
m.line, m.column, m.end_line, m.end_column, m.start_pos, m.end_pos

TypeScript

const parser = new Lark(GRAMMAR, { parser: "lalr", propagate_positions: true });
const tree = parser.parse("x = 1  y = 22");
const m = tree.children[0].meta;   // Meta | undefined; m.empty guards absence

Rust

use hyperlark::{Lark, LarkOptions};

let parser = Lark::from_lark_source(GRAMMAR, LarkOptions {
    propagate_positions: true,
    ..Default::default()
})?;
let result = parser.parse("x = 1  y = 22")?;
if let Some(meta) = result.root().children()[0].meta() {
    // meta: &Meta — Meta::Positioned { line, column, .. } or Meta::Empty
}

C

The C v1 surface reads positions at the token level; set propagate_positions to populate the per-node spans internally.

lark_from_source(GRAMMAR, strlen(GRAMMAR), LARK_OPT_PROPAGATE_POSITIONS, &p);
/* then per token: lark_node_token_positions(node, &pos); */

Your own tree class

tree_class= is a Python option: give it a Tree subclass and every node of the result is an instance of it — at the root and all the way down.

class MyTree(lark.Tree):
    def names(self):
        return [str(t) for t in self.find_token("NAME")]

tree = lark.Lark(GRAMMAR, parser="lalr", tree_class=MyTree).parse("x = 1  y = 22")
type(tree) is MyTree        # True
tree.names()

The nodes are your class, so everything you put on it behaves normally: __getattr__, copy(), __deepcopy__, pickling, and helpers of your own that rebuild through type(self).

A parse with your own tree class is built eagerly

By default a parse returns a lazy view — children materialise on first access, and fast_scan=True can run the queries above natively over the parse arena. With a tree_class= of your own, the tree is built eagerly instead: your constructor has to run for every node, so every node has to exist.

Two consequences, for parses that pass a tree_class= of their own and no others:

• fast_scan has no effect. The native cursors read the parse arena, and an eagerly built tree does not hold one — the queries fall back to their Python implementations. Same results, no speedup.
• Build cost — the whole tree, up front. It costs most when you read least and evens out once you visit every node; reading even one child already pays for that node’s whole child list. What moves it is how much your grammar builds, not how big the input is — both paths scale with input alike. (bindings/python/bench/bench_tree_class.py measures it on your own machine.)

If you only want to attach a few helpers and you care about the lazy path, a plain function over the default tree costs nothing.

The Rust, WASM and C surfaces have no equivalent — they return their own tree types, and tree_class is a Python-object idea.

Once you can read a tree, the next step is usually turning it into a value — see Transformers. For the full per-target picture, the feature matrix is the honest map.