How it works

Hyperlark accepts a grammar and text, and produces a structured tree that represents that text. Python, Rust, TypeScript and C run the same Rust engine, so the same grammar, parser and options give the same tree on every target. Not every target exposes every feature; the feature matrix lists the gaps.

The pipeline

1. Write a grammar. Terminals define the alphabet of your language, and rules its structure. See the grammar reference.

2. Construct a parser with LALR or Earley. This compiles the grammar in memory: the expensive step, so build the parser once. Loading the grammar shows the call in each language.

3. Parse. You get a tree, or a parse error saying where it stopped and which terminals it expected.

4. Use the result. Walk the tree, or write a transformer (in Rust and C, a fold function) to evaluate the tree into a structure you are comfortable with. With LALR it can run during the parse, so one call both parses and computes the value.

For example, this grammar:

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

parses x = 1 y = 2 into this tree, printed with pretty:

start
  assign
    x
    1
  assign
    y
    2

NAME and NUMBER are terminals and assign a rule: each assign match is a branch with its matches as children. The unnamed literal "=" is filtered out as punctuation; Shaping the tree has the rules.

LALR and Earley

Hyperlark has two parsing algorithms. LALR(1) is fast, needs little memory, and can parse most programming languages. Earley is slower, but accepts any context-free grammar, even ambiguous ones.

We recommend LALR. Earley is the default in Python, Rust and TypeScript, so select LALR with parser="lalr", Lark::lalr or { parser: "lalr" }. C has LALR only, for now. These features also need LALR: computing a value during the parse, the interactive parser, error recovery with on_error, and saving a compiled grammar.

Use Earley when your language is ambiguous, or when LALR fails on a grammar you cannot rewrite. Due to having only a lookahead of one token, LALR is limited in its ability to choose between rules when they both match the input. Where it cannot choose, the grammar has a conflict:

• Reduce/reduce (two rules could both complete here): constructing the parser fails with an error naming the rules, unless a rule priority decides it. The highest priority rule wins (.N after its name, as for terminals).
• Shift/reduce (the parser could complete a rule here, or read the next token first): resolved as shift, without error. The parser reads the next token, so an ambiguous grammar parses one way without warning, and a grammar that needs more than one token of lookahead can reject valid input.

When more than one parse is valid, the ambiguity option decides what Earley returns. resolve, the default, chooses the best derivation for you, and rule priorities (.N) prioritize or demote rules. explicit (Ambiguity::Explicit in Rust) returns all derivations wrapped in _ambig nodes, at a cost in space and performance (ambiguity example).

Lexers

The lexer splits the input into tokens, one per terminal match. By default LALR uses the contextual lexer, which uses the parser’s lookahead prediction to narrow its choice of terminals, resolving common terminal collisions. Earley uses the dynamic lexer, which has no fixed tokenization: it tries every combination of terminals, matching each exactly once. The lexers guide covers overriding the choice, indentation and custom lexers.

Runtime compilation

There is no code-generation step: a program can build or choose a grammar while it runs. Some parsers are faster than Hyperlark; the benchmarks give the ratios.

With LALR you can save the compiled grammar and load it later instead of compiling again; Saving a compiled grammar has the calls on each target. Rust’s to_canonical_json and Python’s to_json write JSON that every target loads, so for TypeScript or C, save from Rust or Python. In Python, cache= caches the compiled parser on disk and reuses it on the next identical construction.

Lark compatibility

Lark’s grammar documentation applies to Hyperlark; the grammar reference notes the few differences.

Tests check that Hyperlark produces the same tokens and trees as Lark 1.3.1 over a corpus of grammars and inputs, and Lark’s own test suite runs against the Python binding (how compatibility is checked). Python API differences are on the divergences page.