Working with trees and tokens

Hyperlark builds a tree based on the structure of the grammar: each rule that is matched becomes a branch (node) in the tree, and its children are its matches, in the order of matching. A node has the name of the rule or alias in data and its matches in children. Terminals are always values in the tree, never branches: Tokens, with the terminal name in type (Rust: a numeric type_id) and the text in value.

In the grammar, [item] is an optional item. [item] returns the item if it matched, or a placeholder if it didn’t, so the other children keep their indexes: None in Python, null in TypeScript, NodeKind::None in Rust and LARK_NODE_NULL in C. This is maybe_placeholders, on by default. With it off, [] behaves like ()?: an unmatched item leaves no child. To turn it off: maybe_placeholders=False in Python, maybe_placeholders: false in TypeScript, maybe_placeholders: Some(false) in Rust, LARK_OPT_NO_PLACEHOLDERS in C.

In Rust and C, every node, token and string slice borrows the parse result and is valid only while it lives. Rust checks this at compile time. In C, copy out anything you keep, and free each cursor (lark_cursor_free) before the result (lark_result_free).

API by language

Operation	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_child / lark_node_child_count
Tree vs token vs placeholder	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() → Option<&Token>, then tok.type_id / tok.value	lark_node_token_type / lark_node_token_value
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() …	iterSubtrees(tree) …; handle.subtrees() …	recurse children(), or SubtreesCursor …	lark_cursor_new_*

Example grammar

The samples below call this GRAMMAR:

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

x = 1 y = 22 gives two assign subtrees. The unnamed "=" literal is dropped as punctuation (keep_all_tokens keeps it). pretty prints:

start
  assign
    x
    1
  assign
    y
    22

Reading a tree

Python

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, in code points

A token equals its text and has the str methods, but by default is not a str instance, so "".join(tokens) raises TypeError. Use tok.value there, or build the parser with fast_tokens=False for str-subclass tokens as in Lark (slower).

TypeScript

parse returns Tree | Token | null, as does each child; isTree and isToken narrow it.

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

const parser = new Lark(GRAMMAR, { parser: "lalr" });
const tree = parser.parse("x = 1  y = 22");   // Tree | Token | null
if (!isTree(tree)) throw new Error("expected a tree");

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

A Token stores its type as a numeric type_id; result.table.id_to_token[tok.type_id] is the terminal name.

use hyperlark::{Lark, NodeKind};

let parser = Lark::lalr(GRAMMAR)?;
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

lark_root and lark_child return nodes by value, so calls nest without checks. A bad index, or a child of a non-tree node, gives the null node (LARK_NODE_NULL), also a placeholder’s kind. To tell them apart, check lark_node_child_count first, or use lark_node_child, which returns LARK_INVALID_ARGUMENT for a bad index or a non-tree node and LARK_OK for a placeholder.

Rule names and token values are (ptr, len) slices into the result, with no NUL. lark_node_token_value_copy copies a value into your buffer with a NUL; if it does not fit, nothing is written and the status says so. To size the buffer, call it with NULL, 0, &len first and allocate len + 1 bytes.

/* p: a Lark* from lark_from_source(GRAMMAR, strlen(GRAMMAR), LARK_OPT_NONE, &p) */
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;            /* copy out for a C string */
    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);                     /* every node and slice above is now invalid */

Pretty-printing

pretty returns an indented string representation of the tree; great for debugging. Its size grows with node count times depth, so bound untrusted input before printing it. In Rust and C, an allocation failure aborts the process.

Python

print(tree.pretty())

TypeScript

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

Rust

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

C

/* The string belongs to the result; do not free it. */
printf("%s", lark_result_pretty(res));

Queries

find_data(data) returns all nodes of the tree whose data equals the given value, nested matches first. find_token(type) returns all tokens whose type equals the given terminal name. Python and TypeScript also take a predicate: find_pred(pred) (findPred) returns all nodes for which pred(node) is true, and scan_values(pred) (scanValues) all values for which pred(value) is true.

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

fast_scan=True on Lark (off by default) runs these four queries and both iter_subtrees walks in compiled code, with the same results.

TypeScript

import { findData, findToken } from "@hyperlark/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

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")                       // yields &Token
    .filter_map(|t| t.value.parse::<i64>().ok())
    .sum();                                     // 23

C

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);                 /* before lark_result_free */

Walking in a chosen order

A walk visits every subtree or leaf in one of four orders.

Order	Visits
subtrees	Every subtree, bottom-up, one level at a time, from a sequence fixed before the walk starts, so changing the tree inside the loop does not alter it.
topdown	Every subtree, root first, in the order pretty prints them.
postorder	Each child’s whole subtree, then the parent: the order Transformer uses.
leaves	Tokens and placeholders only, left to right.

A topdown cursor can skip the children of the node it just returned: skip_children in Rust, skipChildren on a TypeScript parse handle cursor, lark_cursor_skip_children in C. Plain iter_subtrees_topdown and iterSubtreesTopdown cannot.

Python

iter_subtrees, iter_subtrees_topdown and scan_values(pred) are the subtrees, topdown and leaves orders. Tree has no postorder iterator; Transformer and Visitor_Recursive visit in that order.

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

TypeScript

iterSubtrees, iterSubtreesTopdown and scanValues(tree, pred) are the subtrees, topdown and leaves orders. A plain tree has no postorder iterator; Transformer and Visitor_Recursive visit in that order, and a parse handle has one.

import { iterSubtrees, iterSubtreesTopdown } from "@hyperlark/hyperlark";

for (const sub of iterSubtrees(tree)) console.log(sub.data);          // bottom-up
for (const sub of iterSubtreesTopdown(tree)) console.log(sub.data);   // root first

Rust

Recurse over Cursor for a full walk. A deeply nested tree can overflow the stack; find_data, find_token and pretty are iterative and have no such limit.

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),
        _ => {}                              // NodeKind::None: a placeholder
    }
}
walk(&result.root());

Without recursion, SubtreesCursor, TopdownCursor, PostorderCursor and LeafCursor yield node numbers: an index into result.tree.arena, or CURSOR_ROOT for the root, which lives outside the arena. node_at and result.cursor_at turn a node number back into a Cursor.

use hyperlark::{node_at, SubtreesCursor, CURSOR_ROOT};
use std::sync::Arc;

for pos in SubtreesCursor::new(Arc::clone(&result.tree), CURSOR_ROOT) {   // bottom-up; pos is a node number
    if let Some(node) = node_at(&result.tree, pos) {
        println!("{:?}", result.cursor_at(node).data());
    }
}

C

LarkTreeCursor *cur = NULL;
lark_cursor_new_subtrees(res, lark_root(res), &cur);   /* bottom-up */
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 */

Large trees in TypeScript

To read a small part of a large parse, parseHandle builds no JavaScript tree: the nodes stay in WebAssembly memory, and the handle names each one by an integer pos. handle.kind(pos), data, token and meta read a node, childCount and childPos(pos, i) step to its children, and toJs(pos) builds the plain tree for one subtree.

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

for (const pos of handle.subtrees())          // bottom-up
  console.log(handle.data(pos));              // the rule name
for (const pos of handle.leaves())            // tokens / placeholders
  console.log(handle.token(pos)?.value);
// handle.topdown() / handle.postorder() / handle.findData("assign") too

The walk iterators free themselves when the loop ends, break included. The handle does not: call handle.free(), or declare it with using (Node 24+, or compiled by TypeScript 5.2+) to free it at the end of the block.

parseHandle throws for a parser with a custom lexer; use parse there.

Positions and propagate_positions

A token records its place in the text: start_pos and end_pos, the indexes where it starts and ends; line and column, from 1; end_line and end_column, the line of its end and the next column after it. Indexes and columns count code points, not bytes or UTF-16 units. So convert an index before slicing with it: in Rust and C for non-ASCII input, in TypeScript for input with characters outside the Basic Multilingual Plane, such as emoji.

A token from the built-in lexer has all six. One from a custom lexer has only the positions you set. One fed by hand to the interactive parser has none in Python, TypeScript and C, and in Rust whatever the Token carries.

propagate_positions (off by default) propagates token positions into the meta attribute of all tree branches: a Meta with the same six fields, spanning the node’s tokens.

Python

meta.empty is True for a node with no positioned tokens under it; its position attributes are then missing (meta.line raises AttributeError).

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

Token positions are typed number | null. They are null on a token fed by hand to the interactive parser and undefined on one from a custom lexer that set none, so test with != null before arithmetic. A node has meta only with propagate_positions on, and meta has position fields only when meta.empty is false.

import { Lark, isTree } from "@hyperlark/hyperlark";

const parser = new Lark(GRAMMAR, { parser: "lalr", propagate_positions: true });
const tree = parser.parse("x = 1  y = 22");
if (isTree(tree) && isTree(tree.children[0])) {
  const m = tree.children[0].meta;   // Meta of the first assign
  if (m && !m.empty) console.log(m.line, m.column, m.end_line, m.end_column, m.start_pos, m.end_pos);
}

Rust

Position fields are SentinelOption<u32>: .get() returns an Option, and line() and column() return 0 for a token without positions. cursor.meta() returns a node’s Meta; its resolved_spans() returns a pair of spans (the first is the node’s own), or None when any position is unknown.

use hyperlark::{Lark, LarkOptions, ParserKind};

let parser = Lark::from_lark_source(GRAMMAR, LarkOptions {
    parser: Some(ParserKind::Lalr),
    propagate_positions: true,
    ..Default::default()
})?;
let result = parser.parse("x = 1  y = 22")?;
if let Some(meta) = result.root().children()[0].meta() {
    // Some when every position is known
    if let Some((span, _container)) = meta.resolved_spans() {
        println!("{}:{} .. {}:{}", span.start.line, span.start.column, span.end.line, span.end.column);
    }
}

C

lark_node_token_positions (see Reading a tree) gives the six token fields, each with a flag saying whether it is set. C has no per-rule span yet: LARK_OPT_PROPAGATE_POSITIONS is accepted and exposes nothing.

Your own tree class (Python)

With tree_class=, Hyperlark will produce trees comprised of instances of this class instead of the default Tree, so your overrides (__getattr__, copy(), __deepcopy__, pickling) apply throughout.

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()

A custom tree class builds the whole tree up front

By default the tree is built lazily, as you read it. A custom tree_class builds every node during the parse. So a parse you read only part of is slower (a full visit is not measurably slower), and fast_scan has no effect: the queries run in Python. tree_class=Tree is the same as leaving the option out. To add helpers and keep the lazy build, write plain functions that take a Tree.

To turn a tree into a value, see Transformers. The feature matrix lists per-target support.