bnf

package module
v0.1.9 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 21, 2026 License: MIT Imports: 9 Imported by: 0

README

bnf (Go)

The shared compiler behind the BNF-family grammar front-ends for the tabnas parsing engine.

This package holds no notation of its own. It defines a grammar IR and compiles it into a tabnas GrammarSpec; a front-end parses one concrete syntax into that IR:

ABNF / GBNF / EBNF text ──front-end──▶ Grammar ──EmitGrammarSpec──▶ GrammarSpec
Front-end Notation
tabnas/abnf RFC 5234 ABNF
tabnas/gbnf llama.cpp GBNF
tabnas/ebnf EBNF (best effort)

Everything downstream of the IR is shared and lives here: desugaring repetition into helper rules, left-recursion elimination, tail-repeat rewriting, the probe/rewind dispatcher for prefixes beyond the engine's bounded lookahead, literal lifting, token allocation, first-set analysis, and $stepN chain emission.

Install

go get github.com/tabnas/bnf/go@latest

import bnf "github.com/tabnas/bnf/go"

One example

EmitGrammarSpec is the entry point: an IR in, a *tabnas.GrammarSpec and an error out.

spec, err := bnf.EmitGrammarSpec(&bnf.Grammar{
	Productions: []*bnf.Production{
		{Name: "val", Alts: []bnf.Sequence{{
			{Kind: bnf.KindRef, Name: "add"},
		}}},
		{Name: "add", Alts: []bnf.Sequence{{
			{Kind: bnf.KindToken, Name: "#NR"},
		}}},
	},
}, &bnf.ConvertOptions{Tag: "demo"})

A Sequence is a slice of *Element, and an element's Kind picks what it is — a rule reference, a lexer token, or a literal terminal.

Also exported: EliminateLeftRecursion, for a front-end that wants to inspect or test the rewritten IR on its own; AttachActions and AttachActionSlots, to bind alt-actions to an emitted spec; MarkListing, to list the alternate marks a grammar produced; and SpecToJSON / SpecToData, to serialise a spec for inspection or a golden test.

Documentation

Full documentation follows the Diátaxis framework:

  • Tutorial — a guided first compile, start to finish.
  • How-to guide — short recipes for individual tasks.
  • Reference — the public API and every option.
  • Concepts — the IR contract, the compiler passes, and how the Go version differs from TypeScript.

For the canonical TypeScript implementation, see ../ts/README.md.

License

Copyright (c) 2025 Richard Rodger and other contributors, MIT License.

Documentation

Overview

Package bnf is the Go port of @tabnas/bnf: the notation-neutral compiler shared by the BNF-family grammar front-ends (abnf, gbnf, ebnf). It compiles a grammar IR into a tabnas GrammarSpec and parses no syntax itself.

PORT STATUS: not yet implemented. The TypeScript implementation is canonical and lands first by design; this package currently exposes only VERSION so the module builds and the release tooling has something to check. The compiler itself — desugaring, left-recursion elimination, tail repeats, probe dispatch, literal lifting, token allocation, first sets and chain emission — is ported in a later change, mirroring ts/src/compiler.ts.

Until then, use github.com/tabnas/abnf/go, which still carries its own copy of that pipeline.

Index

Constants

View Source 
const MaxInfinity = 1 << 30

MaxInfinity stands in for the TS `Infinity` upper bound on repetition.

View Source 
const VERSION = "0.1.9"

VERSION is this module's version. It MUST equal ts/package.json "version": the release orchestrator rewrites both, and the version test fails the build if they drift.

Variables

This section is empty.

Functions

func AttachActionSlots 

func AttachActionSlots(spec *tabnas.GrammarSpec, refNames []string) error

AttachActionSlots declares user-action slots by name on a pure-data spec, without supplying functions.

func AttachActions 

func AttachActions(spec *tabnas.GrammarSpec, actions ActionsMap) error

AttachActions attaches user semantic actions to a spec in place.

func BuiltinTokens 

func BuiltinTokens() map[string]string

BuiltinTokens maps a bareword name to the engine's lexer token.

func EmitGrammarSpec 

func EmitGrammarSpec(
	grammar *Grammar, opts *ConvertOptions) (*tabnas.GrammarSpec, error)

EmitGrammarSpec compiles a grammar IR into a tabnas GrammarSpec. This is the whole public surface a front-end needs: parse your notation into a *Grammar, then call this.

Opts.Tag should be the notation's own name ("abnf", "gbnf", "ebnf"), so emitted alts stay attributable and diagnostics name the syntax the user actually wrote.

func EscapeRegexp 

func EscapeRegexp(s string) string

EscapeRegexp quotes the regex metacharacters in a literal.

func IsEffectivelyCaseSensitive 

func IsEffectivelyCaseSensitive(el *Element) bool

IsEffectivelyCaseSensitive reports whether a literal's case actually matters — a literal with no ASCII letter is insensitive either way.

func IsProseName 

func IsProseName(name string) bool

IsProseName reports whether a prose text is a compiler directive.

func MarkListing 

func MarkListing(spec *tabnas.GrammarSpec) string

MarkListing returns a human-readable listing of compiler-assigned marks.

func RefsIn 

func RefsIn(alt Sequence, out map[string]bool)

RefsIn collects the rule references in a sequence.

func SpecToData 

func SpecToData(spec *tabnas.GrammarSpec) map[string]any

SpecToData converts a *GrammarSpec into a plain data tree (map/slice/scalar/regexHolder). Action/condition refs are emitted as their `@`-name strings. Closures in spec.Ref are dropped — like the TS CLI's JSON output, which serialises actions as FuncRef strings. Used by the CLI's default (spec-dump) mode.

func SpecToDataErr added in v0.1.5 

func SpecToDataErr(spec *tabnas.GrammarSpec) (map[string]any, error)

SpecToDataErr is SpecToData with the failure surfaced.

specToData can now refuse a spec outright — an option holding a function cannot be emitted as data — and a dump API that swallowed that returned an EMPTY spec while reporting success, which is the silent-wrong-grammar failure this package exists to avoid. It also panicked outright on `data["ref"]` when the nil map met a spec with refs.

The signatures of SpecToData / SpecToJSON are kept so callers do not break; on failure they now yield nil / "" rather than a plausible lie, and this function is how a caller learns why.

func SpecToJSON 

func SpecToJSON(spec *tabnas.GrammarSpec, indent int) string

SpecToJSON renders a spec as JSON text (the CLI default output). Returns "" for a spec that cannot be represented; use SpecToJSONErr to learn why rather than emitting an empty grammar as if it were one.

func SpecToJSONErr added in v0.1.5 

func SpecToJSONErr(spec *tabnas.GrammarSpec, indent int) (string, error)

SpecToJSONErr is SpecToJSON with the failure surfaced.

func TermKey 

func TermKey(el *Element) string

TermKey is the identity of a terminal for token allocation.

func ToJsonic 

func ToJsonic(value any, strict bool, indent int) string

ToJsonic serialises a (function-free) data value as jsonic text.

func ToPureSpec 

func ToPureSpec(spec *tabnas.GrammarSpec) (map[string]any, error)

ToPureSpec reduces a spec to a pure-data, function-free grammar that *keeps* the AST-building `$`-builtins (so the reloaded grammar still builds the full {rule, src, kids} tree), with `v` set to the engine's BUILTIN_SCHEMA_VERSION. It is the Go counterpart of the TS `toPureSpec` export (ts/src/compile.ts); where TS returns a GrammarSpec object, Go returns the generic pure-data tree (map[string]any / []any / scalars — see SpecToData / ToJsonic).

Requires a `Builtins: true` conversion: if any closures remain in spec.Ref it returns a *CompileError, matching the TS throw.

func ToRecognitionSpec 

func ToRecognitionSpec(spec *tabnas.GrammarSpec) (map[string]any, error)

ToRecognitionSpec strips a converted spec down to a function-free recognition grammar: AST-building hooks (`a`/`bo`/`bc` refs into spec.Ref and the tree `$`-builtins, plus their `k.node$`/`k.capture$` config) are dropped, and the result carries `v` set to the engine's BUILTIN_SCHEMA_VERSION. It is the Go counterpart of the TS `toRecognitionSpec` export (ts/src/compile.ts); where TS returns a GrammarSpec object, Go returns the generic pure-data tree (map[string]any / []any / scalars — see SpecToData / ToJsonic).

Grammars whose control logic is still closures (a probe dispatcher converted without `Builtins: true`) cannot be emitted as pure recognition data: those return a *CompileError listing the offending rules, matching the TS function's throw.

Types

type ActionError 

type ActionError struct{ Message string }

ActionError is raised for a malformed or unresolvable action ref.

func (*ActionError) Error 

func (e *ActionError) Error() string

type ActionFn 

type ActionFn = tabnas.AltAction

ActionFn is a user semantic action.

type ActionsMap 

type ActionsMap map[string][]ActionFn

ActionsMap maps action refs to a function or list of functions.

type AmbiguityReport 

type AmbiguityReport struct {
	Rule     string
	AltIdx   int
	OptIdx   int
	Reason   string
	Resolved bool
}

type CompileError 

type CompileError struct {
	Message string
	Rules   []string
}

CompileError is raised when a grammar can't be compiled to a pure-data spec.

func (*CompileError) Error 

func (e *CompileError) Error() string

type CompileOptions 

type CompileOptions struct {
	Start       string
	Tag         string
	Strict      bool
	Indent      int
	Recognition *bool // default true
}

CompileOptions controls compilation. Mirrors CompileOptions.

type ConvertOptions 

type ConvertOptions struct {
	Start    string
	Tag      string
	Builtins bool
	Marks    bool
	// WordKeywords makes a literal ending in a word character match only as a
	// whole word: it is emitted as an anchored regex with a trailing `\b`
	// guard so e.g. `option` does not match inside `optional`. Mirrors the TS
	// `wordKeywords` option (which uses a `(?![A-Za-z0-9_])` lookahead; the Go
	// engine's RE2 has no lookahead, so `\b` — equivalent here — is used).
	WordKeywords bool
	// Provenance emits `Meta["provenance"]` — the map from each generated
	// rule name back to the author-written production it came from (see
	// `Production.Origin`). DEFAULT TRUE, hence the pointer: the names are
	// otherwise unattributable, and every tool that shows a rule name to a
	// human needs it. Point it at false to keep an embedded grammar as
	// small as possible. Mirrors the TS `provenance?: boolean`, which is
	// likewise on unless explicitly `false`.
	Provenance *bool
}

ConvertOptions controls emission. Each front-end passes its own Tag so emitted alts stay attributable to the notation they came from.

type ElemKind 

type ElemKind string

ElemKind is the discriminator for a Element. 

const (
	KindTerm  ElemKind = "term"
	KindRef   ElemKind = "ref"
	KindRegex ElemKind = "regex"
	KindOpt   ElemKind = "opt"
	KindStar  ElemKind = "star"
	KindPlus  ElemKind = "plus"
	KindRep   ElemKind = "rep"
	KindGroup ElemKind = "group"
	// KindToken is an engine builtin lexer token (e.g. #TX/#NR/#ST/#VL),
	// produced by normalizeBuiltinTokens. Its token name is held in Name and
	// is emitted verbatim into a rule's token sequence (no allocation, unlike
	// a literal term).
	KindToken ElemKind = "token"
	// KindProse is an RFC 5234 prose-val (`<free text>`). Prose is
	// informational: it describes a terminal in English rather than defining
	// one. The converter accepts it only as the entire body of a production
	// naming a builtin lexer token (`NR = <number>`), where it documents the
	// token the lexer already provides; resolveProseTerminals then drops the
	// production so refs resolve to that builtin. Anywhere else there is
	// nothing to compile, and it is an error. Text holds the prose body.
	KindProse ElemKind = "prose"
)

type Element 

type Element struct {
	Kind ElemKind

	// Sp is where this element came from in the grammar source
	// (front-end populated, nil when unrecorded). Rewrite passes share
	// element objects by reference — cloneGrammar copies productions and
	// alt slices but not the elements themselves — so a span recorded at
	// parse time survives all the way to the emitter. Elements the
	// compiler synthesises for itself (a group wrapper around
	// left-recursion seeds, say) carry none, which is correct: the author
	// wrote no such group. Mirrors the TS `Element.sp`.
	Sp *SrcSpan

	// term
	Literal       string
	CaseSensitive bool // explicit %s flag (ABNF strings are insensitive by default)
	HasCaseSens   bool // whether CaseSensitive was set explicitly (TS optional flag)
	// TokenName is the preferred lexer token name, set by liftLiteralTokens
	// when this terminal came from a production that names it (`PL = "+"` ->
	// `#PL`). Without it the emitter derives a name from the literal text,
	// which for punctuation degrades to `#T`, `#T1`, …
	TokenName string

	// prose
	Text string

	// NumErr carries a deferred diagnostic from parseNumericValue: an
	// alt-action has no error return, and panicking is no good either
	// because the engine turns a panic into its own `tabnas/internal`
	// wrapper. So the element is built anyway and parseAbnf reports this
	// message once the parse is structurally complete. Unexported: it is an
	// internal signal, not part of the AST.
	NumErr string

	// regex
	Pattern string
	Flags   string

	// ref
	Name string
	// Debt holds the suffix-debt counter mutations to emit on the alt that
	// pushes this reference (`n: {<counter>: 1|0}`). Written by
	// resolveSuffixDebts; see that pass for what the counter means. Nil on
	// every reference in a grammar with no contested tail loop, which is all
	// of them until one is detected. Mirrors the TS `debt` field.
	Debt map[string]int

	// opt / star / plus / rep
	Inner *Element
	Min   int
	Max   int // MaxInfinity for unbounded
	// DebtGuard names the suffix-debt counter guarding a star, set by
	// eliminateDirectLeftRec on the tail loop it generates. desugar carries
	// it onto the helper production the star becomes; resolveSuffixDebts
	// then confirms or drops it. Mirrors the TS `debtGuard` field.
	DebtGuard string

	// group
	Alts []Sequence
}

Element is one element of an ABNF sequence (a term, ref, regex, or EBNF sugar). Mirrors the TS AbnfElement union.

type EmitError added in v0.1.6 

type EmitError struct {
	Message string
	// Rule is the rule being compiled when the failure was raised.
	Rule string
	// Sp is where in the grammar source, when the IR knew. Nil when the
	// front-end recorded no span for the offending node.
	Sp    *SrcSpan
	Cause error
}

EmitError is a compile failure that can say WHERE. Every diagnostic this compiler raises used to be a bare message whose only structure was the `diagName():` prefix, so a caller wanting to underline the offending text had nothing to read and had to parse the message.

Sp is populated only when the offending IR node carries a span, which means only when the front-end recorded one — so this is a strict improvement on every path and a change of behaviour on none. It implements `error` and the message text is unchanged, so existing error handling and message assertions keep working.

It sits alongside ParseError rather than replacing it, mirroring TypeScript: there, five author-facing throw sites became `EmitError` and the other eleven stayed a plain `Error`. The same five sites raise this here, and the rest still raise *ParseError or a bare `fmt.Errorf`.

NOTE one of those five (`eliminateDirectLeftRec`'s purely-left- recursive rule) PANICS in Go where TypeScript throws — inherited behaviour the ABNF front-end's suite pins. It panics with a *EmitError VALUE rather than a string precisely so the span survives the panic: a `recover()` that type-asserts gets the span, where one that only stringifies gets what it always got.

func (*EmitError) Error added in v0.1.6 

func (e *EmitError) Error() string

func (*EmitError) Unwrap added in v0.1.6 

func (e *EmitError) Unwrap() error

type Grammar 

type Grammar struct {
	Productions []*Production
	Ambiguities []AmbiguityReport

	// `<remove>` directives. Remove names rules/tokens to drop; ClearAll is
	// `<all> = <remove>`, which wipes the instance first. Mirrors the TS
	// Grammar `remove` / `clearAll` fields.
	Remove   []string
	ClearAll bool
}

func EliminateLeftRecursion 

func EliminateLeftRecursion(grammar *Grammar) *Grammar

EliminateLeftRecursion runs that pass alone, for a front-end that wants to inspect or test the rewritten IR.

type ParseError 

type ParseError struct {
	Message string
	Line    int
	Column  int
	Cause   error
}

ParseError is raised by the shared compiler for a grammar the IR cannot express. Front-ends wrap or restamp it as they see fit.

func (*ParseError) Error 

func (e *ParseError) Error() string

func (*ParseError) Unwrap 

func (e *ParseError) Unwrap() error

type ProbeDispatchSpec 

type ProbeDispatchSpec struct {
	ProbeRule     string
	Disambiguator *Element
	WithBranch    string
	NoBranch      string
}

ProbeDispatchSpec configures a synthesised dispatcher production for an ambiguous `[X D] Y` subsequence.

type ProbeHelperSpec 

type ProbeHelperSpec struct {
	VocabElements []*Element
}

ProbeHelperSpec carries the vocabulary for a synthesised probe helper.

type Production 

type Production struct {
	Name        string
	Alts        []Sequence
	Incremental bool
	ProbeDisp   *ProbeDispatchSpec
	ProbeHelper *ProbeHelperSpec
	// TailRepeat is set by rewriteTailRepeats on a production of the
	// shape `X = prefix [ sep X ]` (all-terminal prefix and separator,
	// self-ref last). The opt is removed from Alts (leaving just the
	// prefix) and the separator elements are stashed here; the emitter
	// compiles the production to a same-depth close-phase repeat
	// (`r: X`) instead of the opt→group→push helper chain. Mirrors the
	// TS `tailRepeat` flag.
	TailRepeat *TailRepeatSpec
	// DebtGuard is set by desugar on the star helper generated for a
	// left-recursion tail loop whose greediness contests a suffix of the
	// rule it was derived from, and confirmed by resolveSuffixDebts. Names
	// the counter whose value must be zero for the loop to keep going.
	// Mirrors the TS `debtGuard` production flag.
	DebtGuard string
	// DebtOwed lists the loop's own FIRST tokens that an enclosing suffix
	// can actually compete for, set by resolveSuffixDebts alongside
	// DebtGuard. Only the branches that could eat one of these are guarded:
	// a multi-tail loop (`A = A "y" / A "w" / "x" A "y" / "z"`) owes a `"y"`
	// and nothing else, so blocking its `"w"` branch as well would reject
	// `xzwy`. Mirrors the TS `debtOwed` production flag.
	DebtOwed []string
	NodeKind string // "", "user", "core", "helper"

	// RepeatHelper marks a synthetic production standing in for a
	// repetition (`opt`/`star` and the tails of `plus`/`rep`), and the
	// nullable tail helpers left factoring creates. Their terminating
	// alternative is EMPTY, so it names no token — and the engine only
	// offers a matcher at a position where the active rule names it.
	// The emitter therefore guards that alternative with a FOLLOW-set
	// peek, without which a repetition followed by a character class
	// cannot terminate. See computeFollowSets.
	RepeatHelper bool

	// Origin is the author-written production this one descends from. Set
	// by every pass that SYNTHESISES a production (desugar's sugar
	// helpers, left factoring's `$fact` tails, the probe rewriter's
	// dispatch branches) to the origin of the production being rewritten.
	// EMPTY means the production is itself author-written — so the source
	// rule is always `Origin or Name`, which is what originOf returns.
	//
	// A compiled grammar carries an order of magnitude more rules than the
	// author wrote (a 12-production ABNF grammar emits 118), and every one
	// of the extra names surfaces in rule stacks, hover and completion.
	// Carrying the origin is what lets emitGrammarSpec export the map back
	// out (`spec.Meta["provenance"]`) so a tool can name the user's rule
	// instead of the machinery's. Mirrors the TS `Production.origin`.
	Origin string

	// Sp is where the author wrote this production, when the front-end
	// records it. Element spans locate a term or a reference; this locates
	// the rule as a whole, which is what an outline entry or a
	// go-to-definition on a rule name needs. Synthesised productions carry
	// none — Origin is how they are located, by naming the rule they
	// descend from.
	//
	// A pointer, not a value: see SrcSpan. Nil means "not recorded", which
	// a zero-valued span cannot mean.
	//
	// CAUTION: every pass that REBUILDS a production field by field has to
	// carry this across, exactly as it carries Origin — a `&Production{…}`
	// that forgets it silently drops the span. The passes that copy with
	// `cp := *p` get it for free. Mirrors the TS `Production.sp`.
	Sp *SrcSpan
}

type Sequence 

type Sequence []*Element

type SrcSpan added in v0.1.6 

type SrcSpan struct {
	S int
	E int
	R int
	C int
}

SrcSpan is where an IR node came from in the front-end's grammar text. 

S  start offset, inclusive
E  end offset, exclusive
R  row of the start, 1-based (optional)
C  column of the start, 1-based (optional)

Offsets and row/column are in the SAME UNITS the front-end's own engine tokens use, so a front-end copies `sI`/`rI`/`cI` straight across with no arithmetic — the step where an off-by-one would otherwise creep in. That does mean the units are runtime-native and not identical across ports: Go offsets count BYTES and TypeScript's count UTF-16 code units, the same divergence the engine already records for token positions. A consumer that needs LSP positions converts at the LSP boundary, where the document's encoding is known; nothing here can do that conversion correctly, because the IR does not hold the source text.

R and C are 1-based, so a zero in either means "not recorded" — there is no row 0. The span ITSELF is optional a level up: `Element.Sp` and `Production.Sp` are POINTERS, because `SrcSpan{S: 0, E: 0}` is a legitimate empty span at the very start of a file and must not read as "no span".

Spans are optional everywhere. A front-end that records them gets ranged compile errors (see `EmitError.Sp`); one that does not compiles to exactly the same grammar. Mirrors the TS `SrcSpan`.

type TailRepeatSpec 

type TailRepeatSpec struct {
	Sep Sequence
}

Source Files

View all Source files

Directories

Path Synopsis
Package main builds the C-ABI shared library: libtabnasbnf.
 Package main builds the C-ABI shared library: libtabnasbnf.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.