A fast PEG (Parsing Expression Grammar) parser and packrat virtual machine for Odin.

📖 Documentation Website • 🚀 Quick Start • 📊 Benchmarks

--- Compiles grammars into bytecode, optimizes them, and executes them with selective memoization — fast enough to parse real-world JavaScript files up to 545 KB.

Key Optimizations:

• Multi-byte literal optimization: ~2.4x faster keyword matching
• SIMD class caching: Per-charset caching eliminates re-scanning
• AOT V2: Functional native code generation for basic grammars
• Zero-allocation: match_prefix() for consecutive char literals

Ships with a full ES2025 JavaScript grammar (~304 rules) validated against 76 production files (~2.5 MB total) from Node.js, Express, Three.js, Lodash, Underscore, Prettier, D3, and more.

Pegasus is designed to be used as a shared collection. Symlink or copy the project into Odin's shared folder:

# From your Odin installation's shared directory
ln -s /path/to/pegasus pegasus

Then import it in your code:

import pegasus "shared:pegasus"

Define a grammar as a string using PEG syntax, then call match():

import pegasus "shared:pegasus"
import "shared:pegasus/log"

main :: proc() {
	grammar := `
Expr   		<- Space SubOp 

SubOp		<- AddOp (Sub AddOp)*
AddOp		<- DivOp (Add DivOp)*
DivOp		<- MulOp (Div MulOp)*
MulOp		<- PowOp (Mul PowOp)*
PowOp		<- Term (Pow Term)*
Term   		<- Atom / OParen Expr CParen

Pow			<- '^' Space
Mul			<- '*' Space
Div			<- '/' Space
Add			<- '+' Space
Sub			<- '-' Space

OParen 		<- '(' Space
CParen 		<- ')' Space

Atom		<- Numeral

Numeral 	<- Number Space
Number  	<- [0-9]+
Space   	<- (' ' / '\t' / EndOfLine)*
EndOfLine 	<- '\r\n' / '\n' / '\r'
EndOfFile 	<- !.
	`

	subject := "23 + 2 +(1* 2) ^ 2"
	is_match, pos, captures, errors := pegasus.match(grammar, subject)

	if is_match {
		log.success("matched til position", pos, "|", subject[:pos])
		log.info(captures)
	} else {
		log.error("matched til position", pos, "|", subject[:pos])
		for err in errors {
			log.error(err.message)
		}
	}
}

Pegasus includes a command-line tool for parsing files with auto-detected grammars.

# Build the CLI binary
task build    # outputs to ./bin/pegasus

# Or install globally
task cli:install    # copies to /usr/local/bin/pegasus

# Parse JavaScript (auto-detects from .js extension)
./bin/pegasus app.js

# Parse JSON
./bin/pegasus data.json

# Parse with custom grammar
./bin/pegasus parse custom.txt mygrammar.peg

# Show detailed output
./bin/pegasus parse script.peg

# Check version
./bin/pegasus version

Pegasus can output parse trees in a format compatible with Tree-sitter, enabling interoperability with existing tools and IDE integrations.

• Node name mapping: Pegasus rule names are automatically mapped to Tree-sitter type names
• Field labels: Semantic field names (function, arguments, object, property)
• Position encoding: Line/column positions for every node
• Pruned trees: Duplicate and wrapper nodes are removed for clean output

# Parse JavaScript and output Tree-sitter compatible JSON
./bin/pegasus app.js --treesitter

# Combine with JSON output for structured data
./bin/pegasus app.js --json --treesitter

{
  "rule": "program",
  "start": [0, 0],
  "end": [3, 0],
  "children": [
    {
      "rule": "expression_statement",
      "start": [0, 0],
      "end": [0, 15],
      "children": [
        {
          "rule": "call_expression",
          "field": "expression",
          "start": [0, 0],
          "end": [0, 14],
          "children": [
            {
              "rule": "member_expression",
              "field": "function",
              "start": [0, 0],
              "end": [0, 11],
              "children": [
                {"rule": "identifier", "field": "object", "start": [0, 0], "end": [0, 7]},
                {"rule": "property_identifier", "field": "property", "start": [0, 8], "end": [0, 11]}
              ]
            },
            {
              "rule": "arguments",
              "field": "arguments",
              "start": [0, 11],
              "end": [0, 14],
              "children": [
                {"rule": "string", "start": [0, 12], "end": [0, 13]}
              ]
            }
          ]
        }
      ]
    }
  ]
}

match :: proc(grammar: string, subject: string) -> (bool, int, ^memo.Capture, []ParseError)

Parameters:

• grammar — a PEG grammar string (see syntax reference below)
• subject — the input string to parse

Returns:

• bool — whether the grammar matched the subject
• int — how many characters were consumed
• ^memo.Capture — the capture tree (from { } expressions in the grammar)
• []ParseError — any errors encountered during parsing

The flagship grammar at grammars/javascript.peg is a complete ES2025 PEG grammar — ~800 lines, ~304 rules covering the full language:

• Modules — import / export with all specifier forms, ES2022 string literal module export names, import() with options arg, with and assert attribute clauses
• Declarations — let, const, var, using, await using, classes with fields/static blocks/auto-accessors, generators, async generators
• Expressions — optional chaining (?.), nullish coalescing (??), private field in checks (#x in obj), tagged templates, destructuring assignment
• Statements — for-of, for-in, for-await-of, labeled statements (including labeled function declarations), switch, try/catch/finally
• Functions — arrow functions, async arrows, default parameters, rest parameters, computed property names
• Literals — template literals with nesting, regex literals, BigInt, numeric separators, legacy octal literals
• Classes — decorators, static blocks, auto-accessors (accessor x = 1), private fields/methods, computed names
• Unicode — non-ASCII identifiers via UTF-8 byte ranges (café, π, 日本語), \uXXXX and \u{XXXXX} escapes

The grammar has been tested against 76 production JavaScript files (~2.5 MB total, 1.6 KB – 545 KB) from:

• Node.js internals — path, fs, net, http2, streams, crypto, child_process, repl, readline, url, CJS/ESM loaders, buffer, events, errors, zlib, dgram, worker, cluster, console, timers
• Express.js — router, app, response
• Lodash (545 KB), Three.js — WebGLRenderer (106 KB)
• Underscore.js (68 KB), Prettier, Moment.js, D3, npm utilities

JavaScript's Automatic Semicolon Insertion (ASI) requires knowing whether a newline occurred between two tokens. Pegasus supports this through the built-in %begin_line assertion, which succeeds at the start of input or immediately after a newline character.

The grammar uses !%begin_line in the 9 restricted productions where ASI matters:

ReturnStatement   <- RETURN (!%begin_line Expression)? EOS
ThrowStatement    <- THROW !%begin_line Expression EOS
PostfixExpression <- LeftHandSideExpression (!%begin_line ('++' / '--') S)?
ArrowFunction     <- ArrowParameters !%begin_line ARROW ConciseBody
YieldExpression   <- YIELD (!%begin_line STAR? AssignmentExpression)?
# ... and continue, break, async arrow, async method

This means return\n42 correctly parses as return; followed by 42;, while return 42 parses as return 42;.

Three key optimizations keep parsing tractable for large files:

• Arrow parameter lookahead — a balanced-paren scan before => avoids expensive speculative FormalParameters parses on every (expr). ~38% faster.
• Unified LeftHandSideExpression — merges CallExpression / OptionalExpression / NewExpression into a single rule with a suffix loop, eliminating exponential double-parse. ~42% faster.
• Arena allocator — match() allocates into a virtual arena, avoiding per-node allocation overhead. Combined with in-place stack operations and a memo table cap (100K entries), this reduced memory from OOM to 67 MB on Lodash (545 KB) and improved Three.js (106 KB) from 3.4s to 0.06s (57x).

Selective memoization (threshold = 512) keeps memory usage reasonable.

Grammars are defined as a set of rules. The first rule is the start rule.

RuleName <- Pattern

Zero-width assertions that test position without consuming input:

These are useful for line-sensitive grammars. For example, the JavaScript grammar uses !%begin_line to detect newlines between tokens for ASI (Automatic Semicolon Insertion).

Lines starting with # are comments.

The examples/ directory contains standalone Odin packages that embed grammars and parse input programmatically:

• examples/calculator/ — Arithmetic expressions with operator precedence
• examples/json/ — Full JSON parser (objects, arrays, strings, numbers, booleans, null)
• examples/javascript/ — JavaScript subset (variables, functions, control flow, expressions)

Run the full test suite (150 tests across all packages):

task ta    # runs all tests with -thread-count:1 for determinism

Other useful commands:

task t     # run tests for lib only
task b     # build
task r     # run
task c     # clean

Run performance benchmarks with optimized builds:

# Full performance summary
odin test lib -collection:pegasus=./lib -o:speed \
  -define:BENCH=true \
  -define:ODIN_TEST_NAMES=pegasus.bench_performance_summary

# SIMD span throughput test
odin test lib -collection:pegasus=./lib -o:speed \
  -define:BENCH=true \
  -define:ODIN_TEST_NAMES=pegasus.bench_digit_span_comparison

# Multi-byte literal optimization
odin test lib -collection:pegasus=./lib -o:speed \
  -define:BENCH=true \
  -define:ODIN_TEST_NAMES=pegasus.bench_multi_byte_literal_optimization

# AOT compilation test
odin test lib -collection:pegasus=./lib -o:speed \
  -define:BENCH=true \
  -define:ODIN_TEST_NAMES=pegasus.bench_aot_basic

Expected Results:

• JIT speedup: ~29x faster than VM
• SIMD span: 548 MB/s sustained throughput
• Multi-byte literals: ~2.4x faster than single-char matching
• AOT compile time: ~1.2 seconds to native binary

📖 Full documentation website: https://dvrd.github.io/pegasus/

The documentation site includes:

• Getting Started guide with installation instructions
• Complete PEG syntax reference
• API documentation with examples
• Tutorials for building real parsers
• Performance benchmarks and optimization tips
• CLI tool documentation

To view the documentation locally:

# Option 1: Open directly in browser
open docs/index.html

# Option 2: Serve with Python
cd docs && python3 -m http.server 8080
# Then open http://localhost:8080

# Option 3: Use npx serve
npx serve docs

To enable GitHub Pages for your fork:

1. Go to Settings → Pages in your GitHub repository
2. Under Build and deployment:
   • Source: Deploy from a branch
   • Branch: main / root (or main / /docs folder)
3. Select Folder: /docs (the documentation is in the docs/ directory)
4. Click Save
5. Wait ~1 minute and visit https://YOUR_USERNAME.github.io/pegasus/

💡 Note: GitHub Pages serves the static files directly from /docs folder - no build process needed!

Pegasus works in four stages:

1. Parse — The PEG grammar string is parsed into an AST of grammar rules
2. Check — The checker validates rule references, detects left recursion, and annotates the AST
3. Compile — The AST is compiled into a bytecode Program (a sequence of Instruction values), then optimized (dead code elimination, jump threading)
4. Execute — The VM runs the program against the subject string using a packrat memoization table with selective caching (only entries where the parser examined ≥512 characters are memoized)

Key packages:

• lib/ — Core: grammar parsing (grammar.odin), checker (checker.odin), compiler (compile.odin), optimizer (optimize.odin), VM (vm.odin), pattern matching (re.odin)
• lib/charset/ — Character set operations using Odin bit_set
• lib/input/ — Input abstraction over the subject string
• lib/memo/ — Memoization table (tree-based), capture tree, parse tree nodes
• lib/log/ — Logging utilities

MIT