Treestand

Treestand is a complete re-implementation of the Tree-sitter parser generator in Nim. It takes grammar.js, or grammar rules defined in Nim and optionally scanner.c as input and generates high-performance Nim parsers automatically.

Treestand leverages Nim's powerful metaprogramming capabilities to make parser generation seamless and efficient: - Compile-time macros (importGrammar, buildGrammar) that generate parsers directly in your code - Zero runtime overhead - all grammar processing happens at compile-time - Type-safe DSL for defining grammars in pure Nim with full IDE support

Purpose

The goal of Treestand is to provide a native Nim implementation of the Tree-sitter ecosystem, matching its rigorous standards for conflict detection and parsing performance, while eliminating the need for a C runtime during the generation phase (though scanner.c files are still supported).

Features

• Direct Execution: Executes grammar.js using Bun or Node.js via an integrated DSL.
• Full Compatibility: Closely follows Tree-sitter's internal algorithms (NFA, DFA, LR(1) table construction).
• Nim-Native: Generates pure Nim code for the parser and runtime.
• External Scanners: Native support for both scanner.nim (pure Nim) and scanner.c (C/C++) external scanners:
• Auto-detection: Automatically finds scanner.nim or scanner.c in the grammar directory when external tokens are defined
• Priority order: scanner.nim → scanner.c → scanner.cc → src/scanner.c → src/scanner.cc
• Nim scanners: Imported directly as Nim modules (zero FFI overhead)
• C scanners: Compiled using {.compile.} and {.importc.} pragmas
• Excellent Conflict Detection: Accurate reporting of Shift/Reduce and Reduce/Reduce conflicts.

Installation

nimble install treestand

Or install from source

nimble install https://github.com/YesDrX/nim-treestand

CLI Usage

Treestand provides a unified CLI for generating and testing parsers.

Generate a Parser

treestand --cmd generate --grammarPath grammar.js --outputDir ./generated

Options: - --grammarPath: Path to the grammar.js file. - --outputDir: Output directory for the generated parser.nim (default: .). - --dslPath: (Optional) Explicit path to dsl.js. - --parserName: (Optional) Custom name for the generated parser.

Test a Grammar

treestand --cmd test --fixtureDir ./tests/fixtures/my_grammar

This will generate the parser, compile it with a test runner, and verify it against corpus.txt.

Library APIs

Treestand is also available as a library. The main entry point is treestand.nim.

import treestand

when isMainModule:
  generateParser(
    grammarPath = "/path/to/tree-sitter-mylang/grammar.js",
    outputDir = "/path/to/output"
  )

Using tsGrammar Macro (Recommended)

The easiest way to define grammars is using the tsGrammar macro with a concise, PEG/EBNF-like syntax:

import treestand

tsGrammar "my_lang":
  # Rule Assignment
  program     <- +stmt

  # Sequence (*) and Choice (|)
  stmt        <- assign * semi

  # Repetition
  # +rule  -> One or more
  # *rule  -> Zero or more
  # ?rule  -> Optional
  assign      <- (variable: identifier) * eq * (value: expr) # Named fields by (fld : rule) format
  expr        <- identifier | number | external_token # external_token is a token handled by an external scanner (C function), but not implemented in tsGrammar yet

  # Lexical Tokens
  # Use token() wrapper for lexical rules
  # String literals and regex patterns are auto-wrapped with str() or patt()
  identifier  <- re"\w+"
  number      <- re"\d+"
  eq          <- "="
  semi        <- ";"

  # Configuration·
  extras      = re"\s+"

when isMainModule:
  echo parseMyLang("a = 1; b=a;")

Benefits: - Clean Syntax: Readable PEG/EBNF-like notation - Named Fields: Easy AST node field access with (name: rule) - Operator Sugar: * for sequence, | for choice, +/*/? for repetition - Set Syntax: {"a", "b"} for keyword choices - Embedded Actions: Execute Nim code during parsing (see below) - No JavaScript: Pure Nim, zero dependencies - Compile-time: All generation happens at compile-time

Embedded Actions

Attach Nim code blocks to rules to execute actions during parsing:

type Env = object
  vars: Table[string, int]

tsGrammar "calc", userdata: Env:
  prog   <- +assign
  assign <- ident * eq * number * semi:
    # Access matched node via `node`
    let varName = node.child("ident").text
    let value = parseInt(node.child("number").text)
    userdata.vars[varName] = value

  ident  <- token(re"[a-zA-Z_]\w*")
  number <- token(re"\d+")
  eq     <- token("=")
  semi   <- token(";")

# Usage
var env = Env()
if matchCalc("x = 10; y = 20;", env):
  echo env.vars  # {"x": 10, "y": 20}

Actions can build custom AST structures, populate symbol tables, perform semantic validation, and more. See examples/09_ast_actions for a complete example.

See docs/using_dsl.md for the complete macro reference.

Using importGrammar Macro

For existing Tree-sitter grammars, use importGrammar to generate parsers from grammar.js files:

import treestand
import std/os

# Import grammar at compile-time - generates parser directly in your module
importGrammar(currentSourcePath.parentDir / "grammar.js")

when isMainModule:
  # Use the auto-generated parser
  let tree = parseJson("""{"key": "value", "number": 42}""")
  echo tree

Benefits: - No intermediate parser.nim files - All parser generation happens at compile-time - Zero runtime overhead - Self-contained modules

See docs/import_grammar.md for detailed documentation.

Using buildGrammar Macro

For the ultimate in simplicity, use buildGrammar to define grammars in pure Nim without any JavaScript dependencies:

import treestand
import std/options

# Define grammar using pure Nim DSL
proc createMathGrammar(): InputGrammar =
  InputGrammar(
    name: "math",
    variables: @[
      Variable(name: "program", kind: vtNamed, rule: rep(sym("expression"))),
      Variable(name: "expression", kind: vtNamed, 
               rule: choice(sym("number"), sym("binary_op"))),
      Variable(name: "binary_op", kind: vtNamed,
               rule: prec_left(1, seq(sym("expression"), sym("op"), sym("expression")))),
      Variable(name: "number", kind: vtNamed, rule: token(patt("\d+"))),
      Variable(name: "op", kind: vtNamed, rule: token(patt("[+\\-*/]")))
    ],
    extraSymbols: @[token(patt("\\s+"))]
  )

# Build parser from pure Nim grammar
buildGrammar(createMathGrammar)

when isMainModule:
  let tree = parseMath("1 + 2 * 3")
  echo tree

Benefits: - No JavaScript: Zero JavaScript dependencies - Type-safe DSL: Full Nim type checking and IDE support - Single file: Grammar and code in one place - Compile-time: All generation at compile-time

See docs/build_grammar.md for detailed documentation.

Project Structure

• src/treestand.nim - Main entry point (CLI & Library Exports)
• src/treestand/cli/ - CLI implementation
• generate.nim - Parser generation command
• test.nim - Grammar testing command
• src/treestand/ - Core library modules
• pragmas.nim - Compile-time macros (importGrammar, buildGrammar)
• grammar.nim - Grammar types and structures (InputGrammar, Variable, Rule)
• dsl.nim - Pure Nim DSL for grammar definitions
• parse_grammar.nim - JSON grammar parser (for grammar.js)
• prepare_grammar.nim - Grammar preparation (flattening, inlining, optimization)
• build_tables.nim - NFA/DFA/LR(1) table construction
• codegen.nim - Nim code generation for parsers
• js_exec.nim - JavaScript execution engine (for grammar.js)
• query.nim - Tree-sitter compatible query engine
• parser_types.nim - Parser runtime types
• parser_runtime.nim - Parser runtime implementation
• dsl.js - JavaScript DSL used during grammar.js execution
• docs/ - Documentation
• getting_started.md - Installation and first parser
• import_grammar.md - importGrammar macro guide
• build_grammar.md - buildGrammar macro guide
• using_dsl.md - Nim DSL reference
• query.md - Query engine documentation
• advanced_usage.md - Conflict resolution and debugging
• examples/ - Example projects
• 05_importGrammar/ - Using importGrammar with grammar.js
• 06_buildGrammar/ - Using buildGrammar with pure Nim

License

MIT