Byte Machine

A generator of fast, resumable, byte-level parsers for Chez Scheme, in the manner of llparse.

Documentation: kiyomi-computation-systems.github.io/byte-machine, also readable as Markdown in =docs/=.

✨ AI Disclosure: LLMs are used extensively in the planning and development of this project.

What it is

You describe a parser as a state machine over bytes, built with ordinary Scheme procedures. Byte Machine checks it and emits a plain R6RS library that parses input incrementally: feed it bytes as they arrive, in any split, and it calls you back. The generated library depends only on (rnrs) and a small runtime, (byte-machine runtime). It never needs the builder, verifier or generator at run time.

It is a toolkit for writing protocol and format parsers, not a parser for any one format. chez-httparse, an HTTP/1.x parser built with it, passes llhttp’s conformance corpus at every chunk size.

What it gives you

• Resumable parsing. Every state survives a feed boundary, so a token split across any number of feeds parses exactly as it would in one buffer.
• No input buffering. Spans (a header name, a body) are delivered to your callbacks as ranges into the bytevector you fed. The runtime keeps no reference to it after the feed returns, and the generated per-byte path allocates nothing, unless a 64-bit field’s value reaches 2^60 and becomes a bignum.
• The pieces protocol parsers need. Byte dispatch, byte classes, exact sequences, keyword tables (prefix-tolerant, optionally case-insensitive), unsigned-integer fields with overflow-checked accumulation, counted consumption (read N bytes of body), callbacks that can pause the parser, and spans.
• Precise errors. An error record names its code, the node, the stream offset, whether the fault was at a byte, between two bytes or at end of input, and any span it cut short.
• A machine you can inspect. The machine is an immutable data structure, not a grammar file or a macro expansion, so it can be built, printed and tested like any other value.

What makes it different

• Verified before it is generated. Every machine passes a mandatory verifier before any code is emitted. It reports unreachable nodes, zero-progress loops that would spin forever, end-of-input paths that end in the wrong place, malformed spans and invalid field operations: 33 diagnostic codes, each with the offending path.
• A reference interpreter to test against. An independent interpreter executes the same machine. The test harness runs it beside the generated parser and requires the two to agree, so a generator bug shows up as a disagreement.
• Deterministic, reviewable output. The same machine always emits the same source bytes. You can commit the generated parser and review changes as a diff.
• Pure Scheme. No C and no FFI. The library and the generated parsers use only R6RS, so they also run on Guile and Racket (see Portability).

Quick start

A machine is built with (byte-machine graph), verified and compiled, then emitted as a library that depends only on (byte-machine runtime):

(import (byte-machine graph) (byte-machine verify) (byte-machine compile))

;; a parser that accepts exactly the byte 'A' (0x41), then stops
(define m
  (make-machine 'simple 'start '() '() '()
    (list (make-error-declaration 'eof 'unexpected-eof "unexpected end of input" #f)
          (make-error-declaration 'rejected 'unexpected-byte "expected 0x41" #f))
    (list (make-byte-dispatch-node 'start
            (list (make-byte-case (make-exact-byte-matcher #x41)
                                  (make-edge 'accept 'advance) #f))
            (make-edge 'reject 'reexecute) 'eof-stop #f)
          (make-stop-node 'accept #f)
          (make-error-node 'reject 'rejected #f)
          (make-error-node 'eof-stop 'eof #f))
    'eof #f))

(compilation-ok? (compile-machine m '()))   ; => #t

The runnable version, which constructs, compiles, emits, loads and feeds bytes, is =examples/generate-simple-machine/=:

chez --libdirs src --program examples/generate-simple-machine/generate.sps

Next, read Usage, which builds, generates and runs a small parser step by step, and Building machines for every node kind.

Requirements

• Chez Scheme 10.4.1 or newer (the full system, not Petite)
• CMake 3.26 or newer, to build and run the tests

Install it with Akku (akku install byte-machine), or put this repository’s src/ on Chez’s library path.

Tested on macOS arm64 locally and on Linux amd64 by CI. Windows amd64 and Linux arm64 are supported targets with no CI; see Installing.

Building and testing

make build

make test

make help lists every target. make test-all runs the complete selection, including the mutation suite, and make doctor reports the discovered toolchain. Without make (on Windows, for instance), use the CMake presets directly:

cmake --preset dev

If discovery cannot find Chez, point it at the executable:

cmake --preset dev -DBYTE_MACHINE_CHEZ_EXECUTABLE=/absolute/path/to/scheme

Portability

Everything under src/byte-machine/ imports only (rnrs), and a generated parser imports only (rnrs) and (byte-machine runtime). Only the build and test layer is Chez-specific. Checked locally, without CI: the toolchain runs unchanged on Guile 3.0.11 and Racket 9.3, and on both the emitted library is byte-identical to Chez’s. Racket loads a generated library only once #!r6rs is added as its first line; the emitted text does not carry it.

guile --r6rs -L src your-program.scm
plt-r6rs ++path src your-program.sps

You can also generate on Chez and deploy only the emitted .sls with (byte-machine runtime).

Documentation

Read the documentation online at kiyomi-computation-systems.github.io/byte-machine, built from the latest release. The same pages are Markdown files in =docs/=, starting at its index; those track main, so they can describe changes not yet released.

• Installing: what you need, and how to put the libraries on Chez’s path
• Usage: build, check, generate and run a parser, step by step
• Building machines: every node kind, matcher and edge
• Fields and counts: numbers read from the input or set by your application
• Callbacks and spans: what a callback receives and how long it may keep it
• Running a parser: feeding, finishing, pausing, resetting, and every status
• Errors: input errors, callback failures and programming mistakes
• The verifier: what it checks, and every diagnostic code
• Generated code: what the generator writes, and how to ship it
• Testing a grammar: compare the generated parser with the interpreter
• Why llparse-style parsers: the design, and why it suits HTTP and URI parsing in servers
• API reference: every exported binding
• Building: build and test byte-machine, and render the docs as a site

See the changelog for release history. To work on byte-machine itself, see CONTRIBUTING.md.

---

© 2026 Kiyomi Computation Systems LLC. Released under the BSD 3-Clause License; third-party acknowledgements are in NOTICE.