goabnf

package module
v0.5.1 Latest Latest
Warning

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

Go to latest
Published: Sep 14, 2026 License: MIT Imports: 16 Imported by: 22

README

Go-ABNF

reference go report Coverage Status
License CI CodeQL
OpenSSF Scoreboard OpenSSF Best Practices Summary

A dependency-free Go module for Augmented Backus-Naur Form (ABNF). It parses an ABNF grammar into a data structure and then lets you recognise, parse, generate, compile to regex, visualise, and even generate a standalone Go parser from it. It implements RFC 5234 and RFC 7405, with Errata 2968 and 3076.

[!NOTE] Intended use. Go-ABNF is built first and foremost as a testing oracle. Because it can turn one grammar into several independent representations (recognizer, parse forest, regex, generator, transition graph), it is well suited to differential testing and fuzzing: generate inputs from a grammar, feed them to your own implementation, and cross-check the verdicts against this library - or cross-check the library's own views against each other. It favors correctness and generality (ambiguous and left-recursive grammars, Unicode) over being the fastest production parser.

Capabilities

  • Parse ABNF into a manipulable *Grammar (with cycle / DAG detection).
  • Recognize input against a grammar - ambiguous and left-recursive grammars included.
  • Build a full parse forest (SPPF) or binary-subtree set (BSR): count trees, detect ambiguity, extract a tree.
  • Compile a grammar to a regular expression (precedence-aware, size-bounded).
  • Generate inputs (random walk), a minimal covering test set, or structured ASTs - for fuzzing.
  • Visualize a grammar as a transition graph (Mermaid).
  • Generate a standalone, specialized Go parser from a grammar (go generate).
  • Unicode code points and 64-bit numeric values; bounded against DoS.
flowchart TD
	A["ABNF text"] -->|ParseABNF| G["*Grammar"]
	G -->|IsValid| R["recognise<br/>(valid?)"]
	G -->|ParseForest / ParseBSR| F["parse forest<br/>(trees, ambiguity)"]
	G -->|Regex| X["regular expression"]
	G -->|Generate / ASTGenerator| S["sample inputs"]
	G -->|TransitionGraph| T["graph (Mermaid)"]
	G -->|GenerateGoParser| C["standalone Go parser"]
	S -. feed .-> SUT["your implementation"]
	R -. cross-check .- F
	F -. cross-check .- X

How it works

ABNF is self-describing: its own syntax is written in ABNF. Go-ABNF bootstraps from a handwritten parse/evaluation of that meta-grammar, after which any valid grammar parsed by the library can in turn be used to parse new input - so the engine is generic, not specialized to ABNF.

Two parse paths exist by design:

  • Recognition (Grammar.IsValid) answers does this input match? by tracking the set of reachable input positions. It never materializes a tree, so it is cheap and is the reference verdict for the other paths.
  • Parsing builds a derivation representation using a GLL engine [1], which handles arbitrary context-free grammars including ambiguity and (left/right/hidden) recursion. Two representations are available over the same engine: a Shared Packed Parse Forest [2] (ParseForest) and a Binary Subtree Set [3] (ParseBSR). Both expose Valid, NumTrees, Ambiguous and Tree.

Repetition (Min*Max element) is handled natively: it lowers to a single self-recursive nonterminal and the bound is enforced by a counter carried in parser state, rather than unrolled - so a grammar like 0*9999999999 "x" costs $O(1)$ to set up instead of exhausting memory.

The generated-parser work targets BSR representation [3], in the spirit of GoGLL.

References:

  • [1] E. Scott, A. Johnstone. "GLL Parsing," in Electronic Notes in Theoretical Computer Science, vol. 253, no. 7, pp. 177-189, 2010.
  • [2] E. Scott, A. Johnstone. "GLL parse-tree generation," in Science of Computer Programming, vol. 78, no. 10, pp. 1828-1844, 2013.
  • [3] E. Scott, A. Johnstone, L. van Binsbergen. "Derivation representation using binary subtree sets," in Science of Computer Programming, vol. 175, pp. 63-84, 2019.

Usage

Parse a grammar, then recognize or parse input:

g, err := goabnf.ParseABNF(grammarBytes) // []byte of ABNF, CRLF line endings
if err != nil { /* ... */ }

ok, _ := g.IsValid("rule", input)          // boolean recognizer

f, _ := goabnf.ParseForest(input, g, "rule")
fmt.Println(f.Valid(), f.NumTrees(), f.Ambiguous())

bf, _ := goabnf.ParseBSR(input, g, "rule") // same answers, BSR representation

Compile to a regular expression, or render a transition graph:

re, _ := g.Regex("rule", goabnf.WithMaxRegexLen(4096))

tg, _ := g.TransitionGraph("rule")
fmt.Println(tg.ToMermaid())

As a fuzzing oracle

Generate inputs from a grammar to drive Go's fuzzer, even when the input format is too specific for the engine to discover on its own:

func FuzzMyParser(f *testing.F) {
	g, err := goabnf.ParseABNF(myGrammar)
	if err != nil { f.Fatal(err) }

	f.Fuzz(func(t *testing.T, seed int64) {
		input, _ := g.Generate(seed, "rule",
			goabnf.WithRepMax(15),      // cap repetitions
			goabnf.WithThreshold(1024), // cap generated size
		)
		MyParser(input) // must not panic; optionally cross-check verdicts
	})
}

More fuzzing helpers are documented here.

As a differential oracle

The recognizer and the parse forest are independent code paths over the same grammar; agreement between them (and with your own implementation) is a strong correctness signal:

ok, _ := g.IsValid("rule", input)
f, _ := goabnf.ParseForest(input, g, "rule")
if ok != f.Valid() {
	t.Fatalf("oracle disagreement on %q", input) // a bug in grammar or engine
}

Code generation

Generate a standalone, specialized parser for a grammar - a jump-table GLL/BSR parser with inlined terminals, depending only on the standard library:

src, _ := goabnf.GenerateGoParser(g, "rule", "myparser")
// or, straight from ABNF source:
src, _ = goabnf.GenerateGoParserFromABNF(grammarBytes, "rule", "myparser")

Wire it into go generate with the cmd/abnf-gen command:

//go:generate go run github.com/pandatix/go-abnf/cmd/abnf-gen -in grammar.abnf -root rule -pkg myparser -out parser_gen.go

The generated file exposes Parse, Result (Valid/NumTrees/Ambiguous/ Tree) and ParseTree. Its identifiers are package-scoped, so generate one parser per package (e.g. a dedicated internal/myparser/). The generated parser is faithful to the grammar you give it: feeding the raw RFC 5234 ABNF self-definition produces an ambiguous parser (the defect Erratum 2968 fixes), while the corrected grammar produces an unambiguous one - choose deliberately, and assert the expected tree count in a test.

Safety

The engines are bounded to stay usable on untrusted grammars and inputs: WithMaxNodes (transition graph), WithMaxForestNodes / WithMaxSlots (forest), WithMaxRegexLen (regex), and the generated parser's MaxElements. Numeric values are accepted up to 64 bits without panicking, and matching is Unicode-aware.

Troubleshooting

My ABNF grammar does not work

Q: My ABNF grammar does not work. Do you have any idea why ?

A: There could be many reasons to this. First make sure your grammar ends up by a newline (LF), and especially that the input content has a CR LF. As those appear the same, it is often a source of error.

Difference between pap and bap

Q: Is there a difference between pap and bap ?

A: Being written in Go makes pap more portable and easier to embed in workflows. Beyond that, the goals differ: bap aims to produce meaningful end-user errors, whereas pap is built to challenge it - and goes further by building transition graphs for fuzzing Go code and by supporting Unicode code points (useful for, e.g., TOML, which is specified in ABNF).

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	// ErrNoSolutionFound is an error returned when parsing an ABNF
	// grammar and no solution has been found.
	//
	// On the ABNF parsing path it is wrapped by a [*ParseError] carrying the
	// position at which parsing got stuck; errors.Is(err, ErrNoSolutionFound)
	// keeps matching.
	ErrNoSolutionFound = errors.New("no solution found, input ABNF grammar may be invalid")

	// ErrHandlingProseVal is an error returned when an operation tried
	// to produce something on a prose-val, but it can't be handled properly.
	ErrHandlingProseVal = errors.New("can't handle prose-val descriptions")

	// ErrProseValInTransitionGraph is returned when building a transition graph
	// from a grammar that contains a prose-val, which has no defined expansion.
	ErrProseValInTransitionGraph = errors.New("prose value is not supported in transition graphs")

	// ErrRepetitionThreshold is returned when expanding a repetition whose bound
	// exceeds the threshold set with WithRepetitionThreshold.
	ErrRepetitionThreshold = errors.New("repetition threshold reached")

	// ErrRepetitionMinNotOne is returned when a mandatory (max == 1) repetition
	// has a minimum other than 1.
	ErrRepetitionMinNotOne = errors.New("repetition minimum must be 1 when maximum is 1")

	// ErrRepetitionMinGtMax is returned when a repetition has a minimum greater
	// than its maximum.
	ErrRepetitionMinGtMax = errors.New("repetition minimum is greater than maximum")
)
View Source
var ABNF = &Grammar{
	Rulemap: map[string]*Rule{
		abnfRulelist.Name:              abnfRulelist,
		abnfRule.Name:                  abnfRule,
		abnfRulename.Name:              abnfRulename,
		abnfDefinedAs.Name:             abnfDefinedAs,
		abnfElements.Name:              abnfElements,
		abnfCWsp.Name:                  abnfCWsp,
		abnfCNl.Name:                   abnfCNl,
		abnfComment.Name:               abnfComment,
		abnfAlternation.Name:           abnfAlternation,
		abnfConcatenation.Name:         abnfConcatenation,
		abnfRepetition.Name:            abnfRepetition,
		abnfRepeat.Name:                abnfRepeat,
		abnfElement.Name:               abnfElement,
		abnfGroup.Name:                 abnfGroup,
		abnfOption.Name:                abnfOption,
		abnfCharVal.Name:               abnfCharVal,
		abnfCaseInsensitiveString.Name: abnfCaseInsensitiveString,
		abnfCaseSensitiveString.Name:   abnfCaseSensitiveString,
		abnfQuotedString.Name:          abnfQuotedString,
		abnfNumVal.Name:                abnfNumVal,
		abnfBinVal.Name:                abnfBinVal,
		abnfDecVal.Name:                abnfDecVal,
		abnfHexVal.Name:                abnfHexVal,
		abnfProseVal.Name:              abnfProseVal,
	},
}

ABNF is the manually parsed+evaluated+validated ABNF grammar.

Functions

func FuzzGeneratedABNF added in v0.4.1

func FuzzGeneratedABNF(f *testing.F)

func FuzzGeneratedGrammarExhaustiveCombinations added in v0.4.1

func FuzzGeneratedGrammarExhaustiveCombinations(f *testing.F)

func FuzzGeneratedGrammarToTransitionGraph added in v0.4.1

func FuzzGeneratedGrammarToTransitionGraph(f *testing.F)

func FuzzGeneratedValid added in v0.4.1

func FuzzGeneratedValid(f *testing.F)

func FuzzParseABNF added in v0.4.1

func FuzzParseABNF(f *testing.F)

func FuzzRawGrammarExhaustiveCombinations added in v0.4.1

func FuzzRawGrammarExhaustiveCombinations(f *testing.F)

func FuzzRawGrammarToTransitionGraph added in v0.4.1

func FuzzRawGrammarToTransitionGraph(f *testing.F)

func FuzzRegex added in v0.4.1

func FuzzRegex(f *testing.F)

func GenerateGoParser added in v0.5.0

func GenerateGoParser(g *Grammar, root, pkg string) ([]byte, error)

GenerateGoParser emits a standalone Go source file containing a parser SPECIALISED to grammar g rooted at root. Unlike a table-driven interpreter, the grammar is compiled into control flow:

  • the parse loop is a jump-table switch over slot IDs; each case is the straight-line code for that one slot (its symbol, its successor, its completion), so there is no per-step table lookup and no symbol-kind dispatch at runtime;
  • terminals are inlined as byte comparisons / rune decodes against baked literals (no ElemItf, no closure table);
  • nonterminal calls, completions, and the {min,max} repetition gating are baked as constants at each site;
  • only the genuinely grammar-independent machinery (GSS, descriptor worklist, BSR set) remains as fixed runtime, plus a compact metadata table used solely by the reconstruction queries (NumTrees/Ambiguous/Tree), which inherently need grammar structure.

The output depends only on the standard library, is panic-free (input decoded via utf8, no manual indexing) and bounded (MaxElements aborts pathological inputs with ErrTooLarge). It is validated against ParseBSR via the differential harness. pkg is the package name for the emitted file.

func GenerateGoParserFromABNF added in v0.5.0

func GenerateGoParserFromABNF(abnfSource []byte, root, pkg string, opts ...ABNFOption) ([]byte, error)

GenerateGoParserFromABNF is a convenience wrapper that parses ABNF grammar source and generates a specialised parser for it in one step. root is the rule the generated parser starts from; pkg is the package name of the emitted file. It is the natural entry point for a code-generation command (e.g. driven by `go generate`).

func SemvalABNF

func SemvalABNF(g *Grammar) error

SemvalABNF proceed to semantic validations of an ABNF grammar. It currently support the following checks: - for all rules, its dependencies (rules) exist - for repetition, min <= max - for num-val, that the value fits in 7-bits (US-ASCII encoded) To update this list, please open an issue.

func WithRepMax

func WithRepMax(repMax int) repMaxOption

WithRepMax defines the maximum repetition to stop generating at.

func WithThreshold

func WithThreshold(threshold int) thresholdOption

WithThreshold defines the length threshold to stop generating at.

Types

type ABNFOption added in v0.3.0

type ABNFOption interface {
	// contains filtered or unexported methods
}

ABNFOption defines the interface for parsing ABNF functional options.

func WithRedefineCoreRules added in v0.3.0

func WithRedefineCoreRules(redefine bool) ABNFOption

WithRedefineCoreRules returns a functional option to enable redefining a core rule. Default is false.

WARNING: use with caution, as we left to the user the responsibility to ensure the redefinition keeps the ABNF grammar coherent (i.e. there is an isomorphism between the core rule and the redefinition, not especially the same textual representation).

func WithValidation

func WithValidation(validate bool) ABNFOption

WithValidation returns a functional option to proceed to validation or not. Default is true.

type ASTGenOption added in v0.5.0

type ASTGenOption interface {
	// contains filtered or unexported methods
}

ASTGenOption configures an ASTGenerator.

func WithMaxDepth added in v0.5.0

func WithMaxDepth(n int) ASTGenOption

WithMaxDepth bounds rule-expansion (recursion) depth; past it the generator steers toward terminating expansions. Defaults to 32.

func WithMaxLen added in v0.5.0

func WithMaxLen(n int) ASTGenOption

WithMaxLen bounds the output length; past it the generator steers toward terminating expansions. Defaults to 4096. (Mandatory repetitions are always emitted, so the bound is soft -- a single huge fixed repetition can exceed it.)

func WithMaxRepeat added in v0.5.0

func WithMaxRepeat(n int) ASTGenOption

WithMaxRepeat caps how far an unbounded ("*" / "1*") repetition is unrolled. Defaults to 16.

type ASTGenerator added in v0.5.0

type ASTGenerator struct {
	// contains filtered or unexported fields
}

ASTGenerator generates strings admitted by a (possibly recursive) grammar rule, directly from the AST.

func NewASTGenerator added in v0.5.0

func NewASTGenerator(g *Grammar, rule string, opts ...ASTGenOption) (*ASTGenerator, error)

NewASTGenerator prepares a generator for rule. It errors if the rule is undefined, or if any rule reachable from it is undefined or non-productive (cannot derive any finite string), since neither can be generated. Unlike the transition-graph generator, recursive rules are fully supported.

func (*ASTGenerator) Generate added in v0.5.0

func (ag *ASTGenerator) Generate(tape []byte) []byte

Generate maps the tape to a production the grammar admits. Total and deterministic: any tape (including nil) yields a valid production; an exhausted tape biases toward the shortest one.

func (*ASTGenerator) GenerateRand added in v0.5.0

func (ag *ASTGenerator) GenerateRand(r *rand.Rand) []byte

GenerateRand draws a production using r as the entropy source.

type Alternation

type Alternation struct {
	// Concatenations contains the variants that validate the upper
	// object (i.e. rule, group or option).
	Concatenations []Concatenation
}

Alternation represents an ABNF alternation object.

This is exposed for custom evaluation purposes, please don't use it else.

func (Alternation) String

func (alt Alternation) String() string

type BSRForest added in v0.5.0

type BSRForest struct {
	// contains filtered or unexported fields
}

BSRForest is the BSR analogue of Forest: a set of binary subtree elements plus an index for reconstruction. Valid/NumTrees/Ambiguous/Tree mirror Forest.

func ParseBSR added in v0.5.0

func ParseBSR(input []byte, grammar *Grammar, rootRulename string, opts ...ForestOption) (*BSRForest, error)

ParseBSR parses input under rootRulename using the BSR engine. It accepts the same options as ParseForest (WithMaxForestNodes bounds the BSR set size).

func (*BSRForest) Ambiguous added in v0.5.0

func (f *BSRForest) Ambiguous() bool

Ambiguous reports whether the input has more than one distinct parse tree.

func (*BSRForest) Nodes added in v0.5.0

func (f *BSRForest) Nodes() int

Nodes returns the number of BSR elements (the representation's size).

func (*BSRForest) NumTrees added in v0.5.0

func (f *BSRForest) NumTrees() *big.Int

NumTrees returns the number of distinct parse trees represented, or -1 for infinitely many (a cycle, i.e. an infinitely-ambiguous grammar). It mirrors Forest.NumTrees but counts over BSR extents instead of SPPF nodes.

func (*BSRForest) Tree added in v0.5.0

func (f *BSRForest) Tree() *ParseTree

Tree extracts a single parse tree (first element at each extent), or nil if the input is invalid. Synthetic nonterminals (groups, options, repetitions) are collapsed so only original rule names appear, matching Forest.Tree.

func (*BSRForest) Valid added in v0.5.0

func (f *BSRForest) Valid() bool

Valid reports whether the whole input is derivable by the root rule.

type Concatenation

type Concatenation struct {
	// Repetitions contains the following repetitions, order matter.
	Repetitions []Repetition
}

Concatenation represents an ABNF concatenation object.

This is exposed for custom evaluation purposes, please don't use it else.

func (Concatenation) String

func (cnt Concatenation) String() string

type CoverageMode added in v0.5.0

type CoverageMode int

CoverageMode selects what set of strings a TransitionGraphReader produces.

const (
	// CoverageAllTrails (mode A, the default) emits every entrypoint->endpoint
	// trail (a walk using each directed edge at most once) and, for each trail,
	// every combination of its nodes' terminal variations. It is finite and
	// terminating for any graph, but on dense graphs or wide range/charval nodes
	// the number of trail x variation combinations can be very large.
	CoverageAllTrails CoverageMode = iota

	// CoverageCompact (mode B) emits a small set of strings that still covers
	// every reachable vertex, every edge, and every terminal value (each charval
	// casing, each numval range value) at least once, then stops. Its size is
	// bounded by roughly (#edges + #vertices + sum of per-node variations), so it
	// stays small even for grammars where CoverageAllTrails explodes.
	CoverageCompact
)

type Depgraph

type Depgraph map[string]*node

Depgraph contains for each rule the rules it depends on. Notice it does not differentiate between a mandatory dependency or an avoidable one.

func (Depgraph) Mermaid

func (dg Depgraph) Mermaid() string

Mermaid returns a flowchart of the dependency graph.

type ElemCharVal

type ElemCharVal struct {
	// Sensitive is by default false, support clarrified by RFC 7405 hence
	// only works on a-z and A-Z.
	Sensitive bool
	Values    []rune
}

ElemCharVal represents an ABNF char-val object.

This is exposed for custom evaluation purposes, please don't use it else.

func (ElemCharVal) String

func (ecvl ElemCharVal) String() string

type ElemGroup

type ElemGroup struct {
	Alternation Alternation
}

ElemGroup represents an ABNF group object. It will be straightly passed through with its underlying alternation.

This is exposed for custom evaluation purposes, please don't use it else.

func (ElemGroup) String

func (egrp ElemGroup) String() string

type ElemItf

type ElemItf interface {
	fmt.Stringer
}

ElemItf defines the interface of all the element alternations: - ElemRulename - ElemGroup - ElemOption - ElemProseVal - ElemNumVal - ElemCharVal

This is exposed for custom evaluation purposes, please don't use it else.

type ElemNumVal

type ElemNumVal struct {
	Base string
	// Status could be:
	// - `statSeries`: `elems` contains all the expected
	//   values in the order of the grammar defined them ;
	// - `statRange`: `elems` contains the start and end
	//   bounds (so no more than two).
	Status Status
	Elems  []string
}

ElemNumVal represents an ABNF num-val object.

This is exposed for custom evaluation purposes, please don't use it else.

func (ElemNumVal) String

func (envl ElemNumVal) String() string

type ElemOption

type ElemOption struct {
	Alternation Alternation
}

ElemOption represents an ABNF option object. It will be straightly converted to a 0*1 repetition.

This is exposed for custom evaluation purposes, please don't use it else.

func (ElemOption) String

func (eopt ElemOption) String() string

type ElemProseVal

type ElemProseVal struct {
	// contains filtered or unexported fields
}

ElemProseVal represents an ABNF prose-val object.

This is exposed for custom evaluation purposes, please don't use it else.

func (ElemProseVal) String

func (epvl ElemProseVal) String() string

type ElemRulename

type ElemRulename struct {
	// Name is the unique rule name.
	// Notice it is case-insensitive according to RFC 5234 Section 2.1.
	Name string
}

ElemRulename represents an ABNF rulename object.

This is exposed for custom evaluation purposes, please don't use it else.

func (ElemRulename) String

func (erln ElemRulename) String() string

type ErrCoreRuleModify

type ErrCoreRuleModify struct {
	CoreRulename string
}

ErrCoreRuleModify is an error returned when an incremental alternative for a core rule.

func (ErrCoreRuleModify) Error

func (err ErrCoreRuleModify) Error() string

type ErrCyclicRule

type ErrCyclicRule struct {
	Rulename string
}

ErrCyclicRule is an error returned when can't work due to an unavoidable cyclic rule.

func (ErrCyclicRule) Error

func (err ErrCyclicRule) Error() string

type ErrDependencyNotFound

type ErrDependencyNotFound struct {
	Rulename string
}

ErrDependencyNotFound is an error returned during ABNF grammar semantic vaildation, if a rule depends on an unexisting rule.

func (ErrDependencyNotFound) Error

func (err ErrDependencyNotFound) Error() string

type ErrDuplicatedRule

type ErrDuplicatedRule struct {
	Rulename string
}

ErrDuplicatedRule is an error returned when the rule already exist as part of the grammar.

func (ErrDuplicatedRule) Error

func (err ErrDuplicatedRule) Error() string

type ErrForestTooLarge added in v0.5.0

type ErrForestTooLarge struct{ Max int }

ErrForestTooLarge is returned by ParseForest when the SPPF exceeds the configured WithMaxForestNodes budget.

func (*ErrForestTooLarge) Error added in v0.5.0

func (e *ErrForestTooLarge) Error() string

type ErrGrammarTooLarge added in v0.5.0

type ErrGrammarTooLarge struct{ Max int }

ErrGrammarTooLarge is returned by ParseForest when lowering the grammar would exceed the WithMaxSlots budget, typically because of an absurd repetition bound (e.g. a = 9999999999"x").

func (*ErrGrammarTooLarge) Error added in v0.5.0

func (e *ErrGrammarTooLarge) Error() string

type ErrMaxNodesExceeded added in v0.5.0

type ErrMaxNodesExceeded struct {
	Max int
}

ErrMaxNodesExceeded is returned by TransitionGraph when construction would allocate more nodes than the budget set with WithMaxNodes.

func (ErrMaxNodesExceeded) Error added in v0.5.0

func (err ErrMaxNodesExceeded) Error() string

type ErrMultipleSolutionsFound

type ErrMultipleSolutionsFound struct{}

ErrMultipleSolutionsFound is an error returned when a parser found multiple solutions when none or one were expected.

func (ErrMultipleSolutionsFound) Error

func (err ErrMultipleSolutionsFound) Error() string

type ErrRegexTooLarge added in v0.5.0

type ErrRegexTooLarge struct{ Max int }

ErrRegexTooLarge is returned by Regex when the output would exceed the budget set with WithMaxRegexLen.

func (*ErrRegexTooLarge) Error added in v0.5.0

func (e *ErrRegexTooLarge) Error() string

type ErrRuleNotFound

type ErrRuleNotFound struct {
	Rulename string
}

ErrRuleNotFound is an error returned when the rule was not found as part of the grammar.

func (ErrRuleNotFound) Error

func (err ErrRuleNotFound) Error() string

type ErrSemanticRepetition

type ErrSemanticRepetition struct {
	Repetition Repetition
}

ErrSemanticRepetition is an error returned during ABNF grammar semantic validation, if a repetition has min < max.

func (ErrSemanticRepetition) Error

func (err ErrSemanticRepetition) Error() string

type ErrTooLargeNumeral

type ErrTooLargeNumeral struct {
	Base, Value string
}

ErrTooLargeNumeral is an error returned when the numeral value provided to parse cannot be handled as a 7-bit US-ASCII valid value.

func (ErrTooLargeNumeral) Error

func (err ErrTooLargeNumeral) Error() string

type Forest added in v0.5.0

type Forest struct {
	// contains filtered or unexported fields
}

Forest is a shared packed parse forest produced by ParseForest.

func Parse

func Parse(input []byte, grammar *Grammar, rootRulename string) (*Forest, error)

Parse parses input against grammar starting at rootRulename using the GLL engine, returning the shared packed parse forest. Unlike the previous backtracking parser it accepts ANY grammar -- left, right and mutual recursion and ambiguity included -- in worst-case cubic time, so it never stack-overflows on left recursion nor blows up exponentially. Inspect the result with the Forest methods (Valid, Ambiguous, NumTrees, Tree).

func ParseForest added in v0.5.0

func ParseForest(input []byte, grammar *Grammar, rootRulename string, opts ...ForestOption) (*Forest, error)

ParseForest parses input with grammar starting at rootRulename using GLL, returning the shared packed parse forest. It runs in worst-case O(n^3) time and space for ANY grammar -- left/right/mutual recursion and ambiguity included -- so it is safe on untrusted or malformed grammars.

func (*Forest) Ambiguous added in v0.5.0

func (f *Forest) Ambiguous() bool

Ambiguous reports whether the input has more than one distinct parse tree.

func (*Forest) Nodes added in v0.5.0

func (f *Forest) Nodes() int

Nodes returns the number of forest nodes reachable from the root.

func (*Forest) NumTrees added in v0.5.0

func (f *Forest) NumTrees() *big.Int

NumTrees returns the number of distinct parse trees the forest represents. A result of -1 means infinitely many (a cycle in the forest, i.e. an infinitely-ambiguous grammar such as A = A / "x").

func (*Forest) ParseError added in v0.5.0

func (f *Forest) ParseError() *ParseError

ParseError returns the furthest-failure diagnostic for an invalid forest: where parsing got stuck and which terminals were expected there. It returns nil when the forest is valid. The returned error unwraps to ErrNoSolutionFound.

func (*Forest) Tree added in v0.5.0

func (f *Forest) Tree() *ParseTree

Tree extracts a single parse tree (first packing at each node), or nil if the input is invalid. A visited guard keeps extraction finite on cyclic forests.

func (*Forest) Valid added in v0.5.0

func (f *Forest) Valid() bool

Valid reports whether the whole input is derivable by the root rule.

type ForestOption added in v0.5.0

type ForestOption func(*forestConfig)

ForestOption configures ParseForest.

func WithMaxForestNodes added in v0.5.0

func WithMaxForestNodes(n int) ForestOption

WithMaxForestNodes bounds the number of SPPF nodes the forest may allocate. Because a complete SPPF is worst-case cubic in the input length, this caps the time and memory ParseForest can spend on adversarial input. 0 means unbounded.

func WithMaxSlots added in v0.5.0

func WithMaxSlots(n int) ForestOption

WithMaxSlots bounds the number of nonterminals produced while lowering the grammar. A finite repetition m*n lowers to ~n nonterminals, so this caps the cost of an adversarial grammar such as a = 9999999999"x". 0 means unbounded; the default is 65536.

type GenOption added in v0.5.0

type GenOption interface {
	// contains filtered or unexported methods
}

GenOption configures a Generator.

func WithMaxLength added in v0.5.0

func WithMaxLength(n int) GenOption

WithMaxLength bounds the number of bytes a generated production may contain. Once reached the walk steers to the nearest endpoint. Defaults to 4096.

func WithMaxReps added in v0.5.0

func WithMaxReps(n int) GenOption

WithMaxReps bounds how many times a single edge may be traversed, which caps how far repetitions ("*" / "1*" / "n*m") are unrolled. Defaults to 32.

func WithMaxSteps added in v0.5.0

func WithMaxSteps(n int) GenOption

WithMaxSteps is a hard backstop on the total number of walk steps, defending against pathological graphs. Defaults to 100000.

func WithStableAddressing added in v0.5.0

func WithStableAddressing() GenOption

WithStableAddressing makes Generate address the tape by decision number (fixed-width slots) instead of a moving cursor. This improves locality for a coverage-guided engine -- a one-byte tape edit perturbs a single decision rather than reframing every decision downstream of it -- at the cost of consuming the tape less densely. Recommended for use under testing.F.

type GenerateOption

type GenerateOption interface {
	// contains filtered or unexported methods
}

GenerateOption is an option for the *Grammar.Generate method.

type Generator added in v0.5.0

type Generator struct {
	// contains filtered or unexported fields
}

Generator produces strings admitted by a transition graph.

func NewGenerator added in v0.5.0

func NewGenerator(tg *TransitionGraph, opts ...GenOption) (*Generator, error)

NewGenerator prepares a Generator from a transition graph. The graph must be fully expanded -- build it with WithDeflateRules(true) when the target rule references other rules -- because an unexpanded rule node carries no bytes and could not be turned into a valid production. It returns an error naming the first such node otherwise. (Recursive rules cannot be expanded at all; in that case TransitionGraph itself returns ErrCyclicRule before reaching here.)

func (*Generator) ExpectedNext added in v0.5.0

func (g *Generator) ExpectedNext(prefix []byte) (next []byte, accepts bool, ok bool)

ExpectedNext simulates the automaton over prefix and reports the octets that may legally follow it, whether prefix is itself a complete word, and whether the analysis succeeded (ok is false only when the graph uses a feature this analyzer declines to expand, e.g. an enormous multi-byte num-val range). When prefix is not a viable prefix of any word, next is empty and accepts is false.

func (*Generator) Generate added in v0.5.0

func (g *Generator) Generate(tape []byte) []byte

Generate maps the tape to a production the grammar admits. It is total: any tape (including nil) yields a valid production; an exhausted tape biases toward the shortest completion.

func (*Generator) GenerateRand added in v0.5.0

func (g *Generator) GenerateRand(r *rand.Rand) []byte

GenerateRand draws a production using r as the entropy source.

func (*Generator) NearMiss added in v0.5.0

func (g *Generator) NearMiss(tape []byte) (production []byte, label string, ok bool)

NearMiss returns a string just outside the grammar together with a label describing how it violates the grammar, or ok=false if no minimal perturbation within the attempt budget produced a string the grammar rejects. It is deterministic in tape and total.

func (*Generator) NearMissRand added in v0.5.0

func (g *Generator) NearMissRand(r *rand.Rand) (production []byte, label string, ok bool)

NearMissRand is the *rand.Rand-driven variant of NearMiss.

type Grammar

type Grammar struct {
	Rulemap map[string]*Rule
}

Grammar represents an ABNF grammar as defined by RFC 5234. It is constituted of a set of rules with a unique name.

func EvaluateABNF added in v0.3.0

func EvaluateABNF(input []byte, f *Forest, opts ...ABNFOption) (*Grammar, error)

EvaluateABNF evaluates a parse forest -- produced by parsing an ABNF source against the ABNF meta-grammar -- into a ready-to-use *Grammar.

func ParseABNF

func ParseABNF(input []byte, opts ...ABNFOption) (*Grammar, error)

ParseABNF is a helper facilitating the call to Parse using the pre-computed ABNF grammar and evaluated the resulting to produce a ready-to-use grammar.

func (*Grammar) DependencyGraph

func (g *Grammar) DependencyGraph() Depgraph

DependencyGraph creates a dependency graph for a whole grammar. It includes core rules only if necessary.

func (*Grammar) Generate

func (g *Grammar) Generate(seed int64, rulename string, opts ...GenerateOption) ([]byte, error)

Generate is an experimental feature that consumes a seed for a pseudo-random number generator, used to randomly travel through the grammar given a rulename to work on. With this, it provides reproducibility, usefull for fuzz crashers.

You can leverage its capacities (maximum repetitions, length threshold, etc.) with the functional options.

It is a good capability for testing and fuzzing parsers during testing, compliance, fuzzing or optimization.

func (*Grammar) IsDAG

func (g *Grammar) IsDAG() bool

IsDag find Strongly Connected Components using Tarjan's algorithm and returns whether it contains cycle or not. Could be improved by Nuutila's or Pearce's algorithms, or replaced by Kosaraju's algorithm.

func (*Grammar) IsValid

func (g *Grammar) IsValid(rulename string, input []byte) (bool, error)

IsValid checks there exist at least a path that completly consumes input, hence is valid given this grammar and especially one of its rule.

func (*Grammar) PrettyPrint

func (g *Grammar) PrettyPrint() string

PrettyPrint returns a prettified string that represents the grammar.

func (*Grammar) Regex

func (g *Grammar) Regex(rulename string, opts ...RegexOption) (string, error)

Regex builds a regular expression that recognises the given rulename.

The rule must not contain a cycle in its dependency graph: a regular expression (RE2, no subroutines) cannot express recursion.

Because RE2 has no subroutine/backreference, a rule referenced N times is inlined N times, so the output can grow exponentially with reference-nesting depth for diamond-shaped grammars. Pass WithMaxRegexLen to fail fast with *ErrRegexTooLarge instead of exhausting memory. The output is simplified (character classes merged, redundant groups and {1} quantifiers dropped) but is not guaranteed minimal.

func (*Grammar) RuleContainsCycle

func (g *Grammar) RuleContainsCycle(rulename string) (bool, error)

RuleContainsCycle returns whether the rule contains a cycle or not. It travels through the whole rule dependency graph, such that it checks if the rule is cyclic AND if one of its dependency is too.

func (*Grammar) String

func (g *Grammar) String() string

String returns the representation of the grammar that is valid according to the ABNF specifications/RFCs. This notably imply the use of CRLF instead of LF, and does not preserve the initial order nor pretty print it.

func (*Grammar) TransitionGraph added in v0.2.0

func (g *Grammar) TransitionGraph(rulename string, opts ...TGOption) (*TransitionGraph, error)

TransitionGraph builds a transition graph out of a grammar and the given rulename. TODO it is possible to build transition graph out of cylic rules iff it is not concatenated to another repetition (can't pipe O->I as there is no O). For instance, `a = "a" a` can exist.

type Node added in v0.2.0

type Node struct {
	ID   string
	Elem ElemItf

	Nexts []*Node
}

Node of a TransitionGraph. Unically identifiate the node of the transition graph along with its underlying element and its next nodes.

type ParseError added in v0.5.0

type ParseError struct {
	// Offset is the byte offset into the input of the furthest position the
	// parser was able to reach before failing.
	Offset int
	// Line and Col are the 1-based line and column of Offset.
	Line, Col int
	// Expected lists the terminals the parser could have consumed at Offset, if
	// that information was available. It may be empty.
	Expected []string
	// Found describes the input byte at Offset (e.g. `%x0A (LF)`), or "EOF" when
	// Offset is at the end of input. It may be empty.
	Found string
	// Hint, when set, gives a plain-language diagnosis of a common mistake (e.g.
	// bare LF line endings where ABNF requires CR LF).
	Hint string
}

ParseError reports where parsing input against a grammar got stuck. It is returned (wrapped around ErrNoSolutionFound) when an input does not parse, to help locate the offending construct -- in particular when writing or debugging an ABNF grammar.

func (*ParseError) Error added in v0.5.0

func (e *ParseError) Error() string

func (*ParseError) Unwrap added in v0.5.0

func (e *ParseError) Unwrap() error

Unwrap reports ErrNoSolutionFound so that callers matching the historical sentinel with errors.Is keep working.

type ParseTree added in v0.5.0

type ParseTree struct {
	Rule       string
	Start, End int
	Children   []*ParseTree
}

ParseTree is a concrete syntax tree keyed by grammar rules: rule nodes carry the rule name, terminals are leaves with empty Rule.

type ReaderOption added in v0.5.0

type ReaderOption interface {
	// contains filtered or unexported methods
}

ReaderOption configures a TransitionGraphReader.

func WithCoverageMode added in v0.5.0

func WithCoverageMode(mode CoverageMode) ReaderOption

WithCoverageMode selects the coverage strategy of the reader (CoverageAllTrails by default, or CoverageCompact for a bounded covering set).

type RegexOption added in v0.5.0

type RegexOption interface {
	// contains filtered or unexported methods
}

RegexOption configures Regex.

func WithMaxRegexLen added in v0.5.0

func WithMaxRegexLen(n int) RegexOption

WithMaxRegexLen bounds the produced regex length in bytes. When the budget is exceeded, Regex returns *ErrRegexTooLarge. Zero (the default) is unbounded.

type Repetition

type Repetition struct {
	Min, Max int
	Element  ElemItf
}

Repetition represents an ABNF repetition object.

This is exposed for custom evaluation purposes, please don't use it else.

func (Repetition) String

func (rep Repetition) String() string

type Rule

type Rule struct {
	// Name is the unique rule name.
	// Notice it is case-insensitive according to RFC 5234 Section 2.1.
	Name string

	Alternation Alternation
}

Rule represents an ABNF rule, with its name and underlying alternation.

This is exposed for custom evaluation purposes, please don't use it else.

func GetRule

func GetRule(rulename string, rulemap map[string]*Rule) *Rule

GetRule returns the rule by the given rulename, whether it is a core rule or present in the grammar, or nil if not found. It validates the RFC 5234 Section 2.1 "rule names are case insensitive".

func (Rule) String

func (rl Rule) String() string

type Status

type Status int

Status defines the type of a num-val, rather StatSeries or StatRange.

This is exposed for custom evaluation purposes, please don't use it else.

const (
	// StatSeries represents a serie of unique byte value.
	StatSeries Status = iota
	// StatRange represents an interval of possible bytes.
	StatRange
)

type TGOption added in v0.2.0

type TGOption interface {
	// contains filtered or unexported methods
}

func WithDeflateCharVals added in v0.2.0

func WithDeflateCharVals(deflate bool) TGOption

WithDeflateCharVals when passed to true, will replace a single node representing the char value to an exhaustive concatenation of all characters (lower and upper case) and the transitions between them.

func WithDeflateNumVals added in v0.2.0

func WithDeflateNumVals(deflate bool) TGOption

WithDeflateNumVals when passed to true, will replace a single node representing the ranges or series of multiple numeric values to individual nodes. It generates a more complex but exhaustive transition graph.

func WithDeflateRules added in v0.2.0

func WithDeflateRules(deflate bool) TGOption

WithDeflateRules when passed to true, will recursively build the transition graphs of the rules it uses (reuse them if possible) and concatenate the sub transition graphs. It generates a more complex but exhaustive transition graph.

func WithMaxNodes added in v0.5.0

func WithMaxNodes(max int) TGOption

WithMaxNodes bounds the total number of nodes the transition graph may allocate during construction. Unlike WithRepetitionThreshold, which only caps a single repetition, this bounds the *whole* graph and so also defends against the combinatorial blow-up of nested repetitions (e.g. 10( 10( 10("a") ) )) and of wide num-val ranges deflated with WithDeflateNumVals. When the bound would be exceeded, construction stops with *ErrMaxNodesExceeded before the nodes are allocated.

A value <= 0 (the default) means unbounded, preserving the previous behaviour. Set a positive bound when building transition graphs from untrusted grammars to keep the work within a controlled domain.

func WithRepetitionThreshold added in v0.2.0

func WithRepetitionThreshold(threshold int) TGOption

WithRepetitionThreshold defines the threshold to block a large repetition to occur, elseway it may consum all memory to build the transition graph. For instance, a rule defined as follows may self-DoS go-abnf.

a = 9555("a")

WARNING it does not avoid such memory consumption on chained repetitions. For instance, the two following cases could produce large transition graphs without control with this functional option.

a = 10( 10( 10("a") ) )

a = 10 ( 10*"a" ( 10"a" 9"a" 8"a" ) / ( *10"a" *10"a" *10"a" ) ) 10"a"

Defaults to 256.

type TransitionGraph added in v0.2.0

type TransitionGraph struct {
	Entrypoints []*Node
	Endpoints   []*Node
	// contains filtered or unexported fields
}

TransitionGraph represent a grammar transition graph. It contains the list of entrypoints and endpoints. You could travel through the graph starting from the entrypoints.

func (*TransitionGraph) Reader added in v0.2.0

func (tg *TransitionGraph) Reader(opts ...ReaderOption) *TransitionGraphReader

func (*TransitionGraph) ToMermaid added in v0.2.0

func (tg *TransitionGraph) ToMermaid() string

ToMermaid produces a mermaid-encoded representation of the transition graph.

type TransitionGraphReader added in v0.2.0

type TransitionGraphReader struct {
	// contains filtered or unexported fields
}

TransitionGraphReader produces a finite set of strings that COVERS the transition graph: every reachable vertex and edge that lies on some entrypoint->endpoint walk appears in at least one produced string. It does so by enumerating every entrypoint->endpoint *trail* (a walk that uses each directed edge at most once) in order of increasing length, and for each trail every combination of its nodes' terminal variations (char-val casing, num-val ranges). Trails are bounded by the number of edges, so the set is finite and enumeration always terminates -- for any graph, cyclic or not.

func (*TransitionGraphReader) Next added in v0.2.0

func (tgr *TransitionGraphReader) Next() bool

Next reports whether another covering string is available.

func (*TransitionGraphReader) Scan added in v0.2.0

func (tgr *TransitionGraphReader) Scan() []byte

Scan returns the next covering string, or nil once coverage is complete.

Directories

Path Synopsis
cmd
abnf-gen command
Command abnf-gen generates a standalone, specialised Go parser from an ABNF grammar file.
Command abnf-gen generates a standalone, specialised Go parser from an ABNF grammar file.
pap module
examples

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL