Chapter 7

Generated Parsers

pego gen translates a grammar into the source of a standalone parser, in Go or in TypeScript. A generated parser does not load or compile a grammar at run time and does not depend on the PEGO engine. This chapter defines the generator, the API of the generated Go and TypeScript code, the features each target supports and where its behavior differs from the engine. Where this chapter does not state a difference, a generated parser returns the same value, the same positions and the same errors as the engine for the same grammar, input, start rule and position unit.

#Scope and Terminology

The engine is the pego.Parser that parses with a compiled grammar. A generated parser is the source that gen.Go, gen.TypeScript (package github.com/ornew/pego/gen) or pego gen writes. The generation options select optional parts of the output. The generated package is the Go package named by -pkg; the generated module is the TypeScript file. The generated Go code uses the runtime package, which is the same for every grammar of one generator release, as a copy in internal/runtime or imported from this module; the TypeScript module includes its own runtime.

#Contract

#The Generator

pego gen -g <grammar> [-lang go|ts] [-module <import path>] [-pkg <package>]
         [-runtime embed|import|only] [-s <rule>] [-o <path>]
         [-types] [-document] [-stream] [-recognize] [-observability]
         [-source-info] [-default-value] [-nodoc] [-max-depth <n>]

• The output is deterministic: generating twice yields identical bytes. Omitted, zero and an explicit 100,000 depth default generate identical source.
• Go output is formatted as by gofmt. Generated Go with the default embed runtime depends only on the standard library, and generated TypeScript has no dependencies. Generated TypeScript uses only erasable syntax and needs ES2020; it is type-checked under strict settings.
• Grammar errors are reported with positions before any file is written, in the same form as in other commands. An unknown start rule, an invalid package name, a compiled grammar (gen needs the grammar source), -stream without a #stream repetition in the start rule and a grammar that contains #missing are errors.
• A Go package may contain only one generated parser, because every generated file defines the same names. api.go re-exports the runtime names the users of the parser need, as aliases of the runtime's types and wrappers of its functions.
• With -types the Go types of the typed values are declared in the package <module>/types (the file types/types.go), which the parser package imports; a module path is required. The types package imports only the runtime, and declares a constant PegoSchema_<digest> that the parser package refers to once (see below). The parser package refers to the types as types.Name, and the users of the parser import <module>/types for them. The grammar's types therefore share no namespace with parser.go and api.go: a grammar type may be named Node, Parser, Walk, ParseOption or like any other export of the runtime.

#Generated Go API

func Parse(input string, opts ...ParseOption) (*Node, error)
func ParseRule(name, input string, opts ...ParseOption) (*Node, error)

type ParseOption func(*parseOptions)
func WithUnit(unit PositionUnit) ParseOption
func WithMaxDepth(n int) ParseOption
func WithContext(ctx context.Context) ParseOption       // with work controls
func WithWorkLimits(limits WorkLimits) ParseOption      // with work controls

type PositionUnit int
const (
	CodePoints PositionUnit = iota // the default
	Bytes
)

• Parse parses the whole input with the start rule. ParseRule does the same with the named start rule, a rule marked @start; another rule is the error rule <name> is not a start rule; parsing can begin only at a rule marked @start, an unknown name the error rule <name> is not defined, the name of a hidden rule the error that the rule is hidden, and an empty name selects the default start rule of the grammar. Both require the rule to consume the whole input. Generated parsers contain entry code only for start rules.
• Node, Fields, NodeField, SyntaxError and SyntaxErrors are types of the generated package (aliases of the types of its runtime) with the members of their engine counterparts, defined in Nodes and Values and Parsing. They are different Go types from those of package pego; errors are tested with errors.As against the generated types. Node JSON is identical to the engine's.
• Options apply in order. A negative final WithMaxDepth returns a configuration error before matching, actions or named-rule lookup; zero restores the generated default. A nil option panics when applied. A call with no options uses code points and the generated depth default.
• A generated parser is safe for concurrent use: each call has its own state.
• Errors in actions (such as division by zero) and exceeding the nesting limit return plain errors as in the engine. The depth limit counts nested rule calls; a larger limit does not guarantee stack capacity. The default error is nesting too deep: more than 100000 rule calls.
• A Go parser generated with work controls (-work-controls, WorkControls) exports WithContext, WithWorkLimits, WorkLimits, WorkLimitKind, WorkLimitError, ErrWorkLimit, InputWorkLimit and StepWorkLimit. A parser generated without them holds no code that charges work or reads a control: one form of each function; with -document it is the form that serves a Document, without charges. A parser generated with work controls has the controlled form only, and a parse that sets no limit runs it unchanged. A parse that passes either option with a context or a limit, from the runtime package, returns an error that the parser was generated without work controls; no option is ignored. A nil context and a zero WorkLimits set no control and are accepted.
• WithContext and WithWorkLimits apply the semantics of Cancellation and Work Limits to each invocation, with counters that restart for every call. They apply to named rules, recognition, typed parsing and conversion. The last context and the last complete WorkLimits win; a nil context means no cancellation; zero limits are unlimited. An exhausted limit matches ErrWorkLimit, and errors.As retrieves a *WorkLimitError with Kind (InputWorkLimit or StepWorkLimit), Limit, Used and Requested. An interrupted entry point returns its zero result, and recovery does not turn an interruption into a successful partial tree. Cancellation is cooperative.

#Typed Values

With -types, the Go package also defines a Go type for each type of the grammar and the functions

func ParseAST(input string, opts ...ParseOption) (T, error) // T: the Go type of the start rule's type
func ParseRuleAST(name, input string, opts ...ParseOption) (any, error)

ParseAST returns the errors of Parse. The mapping of types is:

• TNode[T] is struct { Span; Value T }; TupleN is struct { E0 E0; ...; En En } and Unit is struct{}. A missing element of a tuple is nil. A list node's Value is a slice.
• A grammar type keeps its name. The types package declares, besides the grammar's types, TNode, Error, PegoHooks and, when used, Unit, TupleN and PegoNodeTypes, and a constant PegoSchema_<digest>; generation fails, naming the type, if a grammar type has one of these names. The digest covers the package's declarations, not its comments or formatting. The parser package refers to the constant once, so a parser.go and a types/types.go generated from different schemas do not compile together; the runtime relies on this when it reads a string node as its named node type. A grammar type named Unit is an error only when the generated code uses the empty tuple, and one named TupleN only when it uses a tuple of that arity. A struct field named like a field or method of the embedded Span (Start, End, Range) or like a method of the typed values (TName, ...) gets a trailing underscore in Go (Start_), so Start and End always read the span; the value still reads back under the grammar name. Every declared alias is exported.
• After #recover, an error value in a list of a join type stays in the list as *Error; where a struct type is expected it becomes nil.
• ParseRuleAST consumes the whole input, applies options once before it looks up the name, and returns the selected start rule's typed value as any. Names that ParseRule rejects, with the same errors, and invalid options return nil with an error. A parse failure returns the zero value of the selected type. ParseRule continues to return *Node.
• A generator MAY build typed values directly instead of converting the tree that Parse returns when every value has a Go type of its own; the result is the same either way.

Typed TypeScript output (-types) exports an interface for every struct and alias and the functions parseAST and parseASTWithOptions, which parse the configured start rule and convert the node result. They return { value, error }: a successful nil result has a null value and a null error; a failure has a null value and the error; recovery keeps the converted value and SyntaxErrors. The mapping is:

Names collide the same way as in Go, with trailing underscores. Typed parsing by rule name is not available in TypeScript.

#Recognition

With -recognize, Go gains Recognize(input string, opts ...ParseOption) error and TypeScript gains recognize and recognizeWithOptions. They check that the whole input matches the start rule without building a tree and return the errors that Parse returns, including SyntaxErrors for recovered errors. Actions whose values are not read by predicates are skipped; actions that predicates read still run and can report runtime errors.

#Incremental Documents (Go Only)

With -document, the Go package gains NewDocument(text string, opts ...ParseOption) (*Document, error) and a Document with these members: Parse, Edit(start, end, replacement), Text, Stats and, with -types, ParseAST.

• Edit replaces a half-open range in the position unit chosen at construction. It rejects an invalid range, and a position inside a UTF-8 character in Bytes mode, without changing the text. Text() returns the exact current input.
• Construction options become the defaults of later calls. A call MAY set the depth, the context and the work limits; it MUST NOT change the unit.
• ParseStats has the fields Evaluated and Reused.
• A parse returns what a parse of the whole current text returns. An interruption discards memo history so that a later call can retry.
• A Document is for one goroutine. A returned tree can share nodes with later parses; Node.Clone makes a detached copy that preserves cycles and repeated references. With -types, ParseAST returns read-only values that share storage with the document and with earlier results. Caller mutation can therefore change what later results contain, as with Node values. CloneAST(value) returns an independent copy that shares nothing with the document or other results, and preserves aliases within the copy. Every slice in a returned value has capacity equal to its length, so append on a result cannot write into another result.
• The returned SyntaxError values and their Expected and Messages slices are owned by the caller. Parsing, diagnostic copying and typed publication share one work budget.
• It supports a subset of the engine's Incremental Documents: there is no EditBatch, no Version, no snapshots and no change notifications.

#Streaming (Go Only)

With -stream, the Go package gains ParseStream(r io.Reader, emit func(*Node) error, opts ...ParseOption) error, Iterate with StreamIterator and ErrStreamClosed, and the options WithDiagnosticCallback and WithDiagnosticLimit with TruncatedSyntaxErrors. They follow the contract of Streaming, with these differences: a nil emit parses the stream without delivering elements, and the diagnostic options are accepted only by the stream entry points (Parse, ParseRule, ParseAST, Recognize, NewDocument and Document methods reject them). Parse treats #stream as an ordinary repetition.

With -types as well, the package gains StreamValue, ParseStreamAST and IterateAST with StreamASTIterator. StreamValue is the Go type of one element of the #stream repetition, not of the start rule. Each element is converted on its own when it is committed, so the value stays valid after the callback returns. The conversion counts toward the work limits and observes the context.

#Generated TypeScript API

export function parse(input: string | Uint8Array, unit?: Unit): ParseResult;
export function parseRule(name: string, input: string | Uint8Array, unit?: Unit): ParseResult;
export function parseWithOptions(input: string | Uint8Array, options?: ParseOptions): ParseResult;
export function parseRuleWithOptions(name: string, input: string | Uint8Array, options?: ParseOptions): ParseResult;

export interface ParseOptions {
  unit?: Unit;
  maxDepth?: number;
  signal?: CancellationSignal | null;      // with -work-controls only
  maxInputWork?: number;                   // with -work-controls only
  maxSteps?: number;                       // with -work-controls only
}
export interface ParseResult { node: Node | null; error: Error | null }
// With -work-controls:
export interface CancellationSignal { readonly aborted: boolean; readonly reason?: unknown }
export type ParseInterruptionKind = "canceled" | "input-work-limit" | "step-work-limit";
export class ParseInterruptionError extends Error {
  readonly kind: ParseInterruptionKind;
  readonly limit: number;
  readonly used: number;
  readonly requested: number;
  readonly cause: unknown;
}
export type Unit = 0 | 1;
export const CodePoints: Unit; // the default
export const Bytes: Unit;
export function marshal(n: Node | null): string;

• parse does not throw for bad input: it returns { node, error } with a node and no error; no node and an error; or, after #recover, a node and SyntaxErrors. It throws only for defects that are not parse errors.
• Node has type, rule, start, end, text, children, fields, field(name), isTerminal(), toString() and toJSON(), with the meaning given in Nodes and Values. A field value is a Node, a number, a bigint, a string, a boolean or null.
• SyntaxError has pos, line, col, expected, messages and reason(), and its message is the text of the engine's error; SyntaxErrors has errors.
• The SyntaxError values of SyntaxErrors, the errors that #recover recovered from, carry only the header line in stack; the error of a parse that failed keeps the stack of the point where it was made.
• marshal(node) returns exactly the bytes that encoding/json writes for the engine's node. JSON.stringify yields the same keys in the same order, except that integers beyond the safe range are rounded and, in Bytes mode, an invalid input byte is written as the surrogate that represents it.
• marshal and toString write trees of any depth. JSON.stringify recurses and can exhaust the stack for deep trees.
• maxDepth MUST be a positive safe integer or zero; negative values, fractions, NaN, infinity and unsafe integers return a configuration error in the result before matching. Omitted or zero selects the generated default.
• A parser generated without -work-controls emits no code that charges work and sets no control, so a parse charges nothing, and its ParseOptions has no signal, maxInputWork or maxSteps; it does not export CancellationSignal, ParseInterruptionKind or ParseInterruptionError. A call that passes a signal or a nonzero limit anyway returns an error in the result, before matching, that says the parser was generated without work controls; no option is ignored. An absent or null signal and zero limits set no control and are accepted. A parser generated with -work-controls has the controlled form only, and a call that sets no limit runs it unchanged. The rest of this list describes the controlled form.
• signal is a structural cancellation signal: any object with aborted and an optional reason, such as an AbortSignal. maxInputWork and maxSteps MUST be finite nonnegative safe integers, and zero means unlimited; other values return a configuration error in the result. The units of the limits are those of Cancellation and Work Limits.
• An interrupted parse returns node as null and error as a ParseInterruptionError whose kind is "canceled", "input-work-limit" or "step-work-limit". For a limit, limit, used and requested give the accounting; for cancellation, cause is the reason of the signal. Recovery does not turn an interruption into a partial result, and the parser keeps no reference to the signal after the call returns. Typed conversion (parseAST) and recognition report interruptions the same way.
• A synchronous parse does not yield to the event loop: a signal that changes only through timers or other tasks of the same thread is not observed during the call. A signal that is already aborted is observed at the first poll, and the work limits do not depend on the event loop.
• With -recognize, recognize and recognizeWithOptions return null if the input matches and an Error otherwise. With -observability, the batch entry points accept the tracing and profiling options of Observability.
• A generated TypeScript module exports the same names for every grammar, so two parsers are imported under different namespaces. A parser keeps no state between calls.

#Input and Positions in TypeScript

Positions count Unicode code points (the default) or UTF-8 bytes (Bytes), as in the engine, and not UTF-16 code units. The parser decodes the input first.

• A string is parsed as its UTF-8 encoding would be. A lone surrogate becomes U+FFFD.
• A Uint8Array is parsed as UTF-8 bytes; an invalid sequence decodes to U+FFFD, one per byte, as in Go. In Bytes mode, positions count the original bytes.
• In Bytes mode, text keeps the bytes: each invalid byte b is represented by the lone surrogate U+DC00+b in node text and in text(...). marshal writes such a byte as U+FFFD.
• String operations in actions follow Go: + concatenates, comparisons order by code point, and len counts code points or UTF-8 bytes. Integers are signed 64-bit and wrap on overflow; division truncates toward zero and % takes the sign of the dividend. An integer is a number while it is a safe integer and a bigint beyond.

#TypeScript Errors and the Stack

The host stack of a JavaScript runtime is far smaller than the stack of a Go program, so a TypeScript parser can reject nesting that the engine accepts.

#Validation and Errors

#Compatibility and Support

A generated parser carries the runtime of the generator that produced it (embed) or imports it (import), and does not follow later changes of the grammar or of the generator.

#Conformance

The repository tests every grammar in examples/ and the grammars of the engine tests against the generated Go and TypeScript parsers, in both position units and with strings and bytes as input, and require identical trees (as JSON) and errors. TypeScript output is type-checked with tsc --strict and additional strict flags.