PEGO Bytecode Specification

This document specifies the bytecode (the module) that a PEGO grammar compiles to, and the behavior of the virtual machine (VM) that executes it. A runtime for another language must implement this document. The meaning of the language that the bytecode implements is defined by the Grammar Language Specification; for the results a parse must produce, see Parsing.

The reference implementation is the Go package internal/bytecode (bytecode.go, the instruction set and module) with the bytecode compiler bcompile.go in internal/compile and the VMs vm.go and ivm.go in internal/engine. A bytecode VM must produce the same results as the closure backend.

#Terminology

#Values

The reserved bytecode node types are the kinds string, tuple, list and error. The Closure-only #missing pragma and missing type have no bytecode encoding; VM parsing, binary serialization and module construction reject those grammars. A node is fresh only while the body of the rule that created it is executing (Rule completion).

#Input and Positions

The input is a sequence of characters. The position unit is chosen for each parse: Unicode code points or UTF-8 bytes. Reading a character returns the character (a code point) at the current position and its size in position units. Each invalid UTF-8 byte is read as one U+FFFD character whose size is one unit (one byte, or one code point).

#Module

A module consists of the following tables and code sequences.

An instruction consists of an opcode and up to three integer operands, A, B and C. A jump target is the index of an instruction in the same code sequence.

Operands are signed 32-bit integers. Repetition bounds that exceed this range use REPEATW or SCANW, whose bound operands index EINT constants in the expression code. These constants preserve the full implementation-int range; they are read directly, without evaluating an action. Ordinary instructions retain their compact representation.

The public grammar AST treats every negative repetition maximum as unbounded. Compilation canonicalizes it to -1 before narrowing operands or creating wide bound constants. The AST's original field is preserved; serialized bytecode uses the existing -1 sentinel for both REPEAT and SCAN variants.

#Rule Table

Value-free twins. When a rule that returns a CST is called from a place where its value is discarded (#atomic, -, !, or a value-free body), the compiler compiles a second version of its body that builds no value. The twin is placed in the rule table after all original rules, and the CALL refers to it. The twin has the same name as the original rule; lookups of a start rule by name ignore twins. Because the twin matches the same input in the same way, results do not change. Rules that belong to a left-recursive cycle have no twin.

Value-free bodies. The body of a rule whose action does not refer to $n is compiled without building values. Capture targets still build their values.

#Operators Rule Table

A line has the start of its code in the match code (the code pushes one value and ends with END), a scope, an action (start in the expression code, or -1), whether its body is a sequence, and the type its value is checked against when the line produces it (as the rule table's check, with the rule's name in the error), or -1. An operand line pushes the value of its scope, as a rule body does. An operator line pushes the operator's value: when its body is a sequence, that value is the tuple node of the operator's values, and the line's captures are attached to it.

Operator kinds are encoded as 0 = prefix, 1 = postfix, 2 = infix. Associativity is encoded as 0 = left, 1 = right, 2 = none.

#VM State

Save and restore. Saving the state records pos, the height of the value stack, the height of the entry stack, the number of repetition states, the length of the capture trail, the environment, the number of recovered errors, and the frame. Restoring returns each of these to the recorded value. Unwinding the capture trail writes each recorded previous value back into its slot.

Value-free recognition uses NEXT mode 0 even for a source repetition marked #stream. Mode 2 requires an element value on the stack; it belongs to a value-building stream-capable program. Element capture frames remain available to predicates in mode 0, but are not attached to an element value.

#Failure

When an instruction fails, the VM pops entries from the entry stack of the current rule body and handles each according to its kind. If there are no entries left, the rule body fails.

#Match Instructions

b denotes an operand that selects whether the instruction pushes a value (1) or not (0). Matching behaves the same either way.

Streaming. NEXT with mode 2 is emitted only for the repetition marked #stream in the start rule. When the VM is parsing a stream and this repetition runs in the start rule's body (call depth 1), the element value is not kept: it is passed to the consumer (no longer fresh), the input up to the current position is committed (earlier input and memo entries are discarded), and the loop exits if the iteration consumed no input and otherwise jumps to A. On reentry, ITER enforces the finite maximum before executing another element; a zero maximum executes no elements. In any other parse, mode 2 behaves like mode 1.

#Recovery

When a recovery entry is popped on failure, the VM:

1. Takes the farthest failure recorded inside (a position and its expectations) and restores the saved farthest failure.
2. Restores the state.
3. Pushes a skip entry (holding a saved state for restoring and the failure from step 1) and jumps to the recorded target (the skip code).

ENDSKIP builds a syntax error from the failure held by the skip entry. The error node spans from the start of the recovery to the current position; its text is the text of that range and its message field is the string form of the syntax error.

#Rule Calls

CALL r, min calls rule r as follows. The call is memoized if the rule is a leader, or if it is marked for memoization and is not transient. In an incremental parse, a transient rule is memoized when it is marked for memoization, so that results from the previous parse can be reused.

A rule is marked transient when it calls no other rule, or when it is referenced only once in the grammar. Re-evaluating the former only scans the input once more; the latter is re-evaluated at the same position only when its single caller is. In both cases a memo entry would never be reused.

1. Look up the memo: a provisional result of a growing left recursion for (r, pos, min), whatever the variable values it was stored with, or else a result for (r, pos, min) and, when the rule reads variables, for the current values of those variables (the rule table's variable list). If there is one, and it is growing, or it was not computed inside a lookahead, or the VM is currently inside a lookahead, use it: record the expectations stored with the result (unless it is growing) and its recovered errors; on success, advance the position and return the value.
2. If the call is memoized, save the farthest failure and reset it to (start position, empty).
3. If the rule is a leader, evaluate it by growing the seed; otherwise evaluate the body once. On failure, remove the errors recovered during this call.
4. If the call is memoized, store in the memo the result, the end position, the recovered errors, whether the call ran inside a lookahead, and the expectations recorded inside; then merge those expectations into the saved farthest failure and restore it.
5. On failure, reset the position to the start position.

#Body Evaluation

To evaluate a body, the VM creates a new frame (sized for the rule's scope), saves the frame, the environment and the length of the capture trail, and runs the body's code. While the body runs, it uses its own base of the entry stack and of the value stack. When the body finishes, the VM restores the frame and the capture trail; on success, it performs rule completion; finally it restores the environment, so variables defined in the body are not visible to the caller.

#Left Recursion

A leader rule is evaluated as follows:

1. Store a failure for (r, pos, min) in the memo, marked as growing.
2. Reset the position to the start position, reset the recovered errors to their state before the call, and evaluate the body.
3. If the body fails, or does not advance beyond the previous success, stop. Otherwise store the result in the memo, marked as growing, and go back to step 2.
4. Finalize the last result (clear the growing mark) and return it.

#Rule Completion

The value of the rule is built from the body value v and the start position:

• With an action: evaluate the action with the $n items set to the children of v if the body is a sequence, and to [v] otherwise. If the result is a node newly created by the action, its range becomes the range of the rule. An int, string or bool result becomes a value node with the range of the rule.
• Otherwise: if the scope has captures, attach them. If v is fresh, give it the rule name if it has none, and clear its fresh mark.

When the rule's node type is a named node type, the value built above is then checked against the rule's check, which names the underlying node type, and converted to the named node type as ENODE converts it; a value that is not a string, tuple or list node fails the parse with cannot convert <value type> to <type> in result of rule <name>.

Attaching captures: if no capture is non-nil, do nothing. If v is nil, is not fresh, or is itself one of the captures, wrap v in a tuple node whose only child is v, whose range runs from the start position to the current position, and which is fresh. Then add each non-nil capture as a field under its name.

#Operators Rule

The algorithm is the same as operatorsRuleParse in the closure backend; see the parsing rules in Operators Rule. Each part's code runs with its own entry-stack base and frame.

• Skip: increment silent, run the skip code, and on failure reset the position.
• Longest match: for each candidate operator, save the state, run the line's code in a new frame, and on success record the end position, the value, the frame, the environment, whether a cut was passed, and the recovered errors; then restore the state (writing the recorded captures back into the frame). A prefix or postfix candidate that succeeds without consuming input is treated as not matching. Select the candidate that advanced farthest; on a tie, select the one declared first. Also record whether some candidate failed after passing a cut, including an empty prefix/postfix match rejected as a candidate. A successful selected candidate takes precedence over this aggregate failure; each candidate's cut scope is isolated.
• Head: after skip, try the longest match among the prefix operators. If none matches and some candidate failed after passing a cut, the whole expression fails without trying operands. Otherwise, if one matches, apply it and parse the right operand at the operator's level. If the right operand fails, fail if a cut was passed; otherwise backtrack and try the operands. Operands are tried in declaration order; if an operand fails after passing a cut, the whole expression fails.
• Tail: after skip, try the longest match among the infix and postfix operators. If there is no candidate, stop (or fail, if a candidate failed after a cut). If the operator's level is less than or equal to min, or the operator is non-associative and a non-associative operator of the same level was just applied, backtrack and stop. A postfix operator is applied immediately. For an infix operator, parse the right operand at the operator's level (level - 1 for a right-associative operator); if that fails, fail if a cut was passed, and otherwise backtrack and stop.
• Values: if the operator has an action, evaluate it with local 0 = $lhs, 1 = $rhs and 2 = $op (a string node of the operator part's text). Otherwise build a tuple node whose children are [op, rhs], [lhs, op] or [lhs, op, rhs] according to the operator kind, whose operator field is the operator's index, and which carries the rule name. The value of an operand is its action's result if it has an action; otherwise its captures are attached and, if it is fresh, it is given the rule name. When the rule's node type is a named node type, the value of every operator (the action's result, or the tuple node, which is then built with that type) is converted to it as ENODE converts it, with the failure cannot convert <value type> to <type> in result of rule <name>; the value of an operand is not converted, and the rule's result as a whole is not converted.

#Execution Models

A runtime implements one or both of two execution models, which differ in how rule calls and the Operators Rule are executed. Both must produce the same results.

• Recursive model: CALL and OPERATORS_RULE invoke the procedures in Rule calls and Operators Rule as host-language functions. The maximum nesting depth is bounded by the host stack.
• Iterative model: execution suspends at CALL and OPERATORS_RULE and resumes when the result is available (after a CALL, on success it pushes the value if keep is 1 and continues with the next instruction; on failure it proceeds as in Failure). Rule calls, left-recursion growth, the Operators Rule loop, longest match and skip are implemented as state machines whose state is kept in stack entries, and they perform the steps above in the same order. Host stack usage is constant, independent of how deeply the input nests.

In the reference implementation, both models share the instruction interpreter (step) and the stages of a rule call (callBegin, growBegin, growStep, growEnd, invokeBegin, invokeEnd, callEnd); they differ only in the order in which these are invoked (vm.go, ivm.go). The reference implementation also limits the nesting depth of rule calls (100,000 by default, 10,000,000 for the iterative model; configurable with pego.WithMaxDepth) and reports a parse error when the limit is exceeded. Actions and predicates may be evaluated with host function calls in either model, because their nesting depth is fixed by the grammar and does not depend on the input.

#Expression Code

Actions and predicates are evaluated by stack-based expression code. An evaluation error in an action is an error of the whole parse (action in <rule name>: <message>); in a predicate it is a failure.

Names (EVAR, EMEMBER), operators (EBIN, EUNARY, EBOOLCHK, written as their source symbol such as + or &&) and type names (ENEW) are string-table indices.

Typed list constructors use ECALL with the list built-in; their element types are checked at compilation and require no additional VM instruction or per-element concrete-type guard.

Calling a function evaluates its code from its start, with the locals captured at creation followed by the arguments as its locals.

Instructions 118–123 are shortcuts with the same results as the general instructions. The reference compiler emits ETEXTCHK after each operand and ETEXTEQ for text(a) == text(b) and text(a) != text(b), which compares the texts without making them values, and ELISTBEGIN, ELISTPUSH/EMAPPUSH per argument and ELISTEND for a concat call whose arguments are all list, map or such concat calls, which builds no intermediate list. In both cases the errors arise in the same order as with ECALL.

Built-in function indices: 0 len, 1 text, 2 foldl, 3 foldr, 4 map, 5 list, 6 concat, 7 filter. Their semantics are defined in Actions.

#Error Messages

A syntax error (see Syntax errors) is formatted as line:column: syntax error: expected A, B (expectations sorted lexicographically). If @error messages apply, it is formatted as line:column: message (multiple messages joined with ; ). @diagnostic changes ordinary expected-item descriptions but does not replace explicit messages. Expectation strings are those the compiler placed in the string table: literals in quotes, character classes in [...] form, any character, and so on.

#File Format

A compiled grammar uses container version 6. It stores one execution-only compile result: the module of one mode and the start rule, with no grammar AST and no output schema (see Compiled Grammars). The container version and the module's instruction-set version are separate version axes. A loader accepts only container version 6. Integers are variable-length: unsigned integers use LEB128 and signed integers use zigzag-encoded LEB128. A boolean is one byte (0 or 1).

The module is laid out in the following order. A list is a count (unsigned) followed by its elements. Indices, positions and other integers inside the module are signed unless stated otherwise.

1. The number of module strings, unsigned (this many strings from the start of the string table form the module's string table).
2. Source information, a boolean: whether the values a parse returns carry the rule names and capture names of the grammar. A loaded program keeps it.
3. Default value, a boolean: whether the program was compiled with default values, which drop value actions and the declared types of rules (except for the rules that make values read by predicates) before compilation. A loaded program keeps it.
4. Character class table: a list of (negated, expectation string, number of ranges (unsigned), followed by the lower and upper bound of each range).
5. Type table: a list of (name, list of field names, underlying node type). The underlying node type is a string index, or -1 for a struct type.
6. Field-list table, then scope table: each a list of lists of string indices.
7. Variable table: a list of (name, type, integer, string). The type is 0 for int, 1 for string and 2 for bool. The integer is the initial value of an int variable, and 0 or 1 for a bool variable. The string is the string table index of the initial value of a string variable, and -1 for the other types.
8. Rule table: a list of (name, body, scope, action, node type, memoize, leader, position-dependent, Operators Rule, value-free twin, transient, where, splice, variables, check).
9. Start rules: a list of the rule table indices of the start rules, the rules marked @start, in increasing order, followed by the rule table index of the default start rule. Parsing begins only at these rules.
10. Operators Rule table: a list of (skip, list of operand lines, list of prefix operators, list of infix and postfix operators). A line is (start, scope, action, body is a sequence, check); an operator is (index, kind, associativity, level, line).
11. Match code, then expression code: each a list of instructions (opcode as 1 byte, then A, B, C).

#Load-Time Validation

On load, a runtime checks the following and rejects the file if any check fails:

• The checksum, the version, the mode and the instruction-set version are valid, the start rule is empty or a start rule of the module, and no data remains after the module.
• Each variable is named once, has a valid type, and has an initial value that matches its type.
• Every reference in the tables and instructions (strings, character classes, scopes, field lists, rules, Operators Rule tables, expression code, built-in functions) is in range.
• There is at least one start rule. The start rules are in increasing order and have distinct names, and the default start rule is one of them.
• Every opcode is known, and every flag operand is within its range.
• The node type of a rule names a named node type, or a declared type with a field Text. The node type of a rule with an Operators Rule names a named node type.
• A named node type has no fields, and its underlying node type is a type text, parsed as the type of ECAST is, of the form node[T]. The type A of ENODE names a named node type, and B is 0.
• Wide bounds reference EINT constants, fit the runtime's implementation int, and satisfy minimum ≥ 0 and maximum = -1 or maximum ≥ minimum.
• B and C of ECAST are not negative. The type text of ECAST parses as a field type naming only declared types, error, node[T], tuple types (T, ...), int, string, bool and nil. These type texts are resolved types, which contain no & or _|_, and no _ other than the argument of node[_].
• Every jump target is forward. Only NEXT jumps backward. The target of EFUNC is also forward.
• Every RECOVER body ends at an ENDRECOVER immediately before its skip target; that instruction jumps past an ENDSKIP. These recovery regions are nested and contain no stream-mode NEXT (mode 2) in either the protected body or skip. Element-local recovery ends before the enclosing streaming repetition's NEXT.

A runtime does not verify that instruction sequences use the value stack and the entry stack correctly, and it trusts the mode as it trusts the module's types: it checks that the mode byte names a mode, not that the module is the one a compiler writes for that mode. A file whose mode does not match its module MAY return wrong results without an error, such as no value from a parse. Runtime errors caused by invalid code are reported as parse errors, but termination is not guaranteed, so load files only from trusted sources.