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 other chapters of the specification; for the results a parse must produce, see Parsing. For the design background, see design record 010.

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

#Terminology

#Values

The reserved node types are Match (terminal), Seq, List, Operator and Error. 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.

#Rule table

Value-free twins. When a rule that returns a CST is called from a place where its value is discarded (@, -, !, 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 terminal-type rule, and the body of a rule whose action does not refer to $n, are compiled without building values. Capture targets still build their values.

#Pratt 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), and whether its body is a sequence.

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.

#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; see design record 007), and the loop exits if the iteration consumed no input and otherwise jumps to A. 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. If the memo holds 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; an undefined variable counts as nil), and the result was not computed inside a lookahead, or the VM is currently inside a lookahead, or the result is a provisional result of a growing left recursion, 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. The result must be a node or nil.
• With a terminal type: create a terminal of that type whose text is the text of the rule's range, and give it the rule name.
• 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.

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 Seq 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.

#Pratt expressions

The algorithm is the same as prattParse in the closure backend; see the parsing rules in Pratt Expressions. 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.
• Head: after skip, try the longest match among the prefix operators. 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 Match of the operator part's text). Otherwise build an Operator 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.

#Execution models

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

• Recursive model: CALL and PRATT invoke the procedures in Rule calls and Pratt expressions as host-language functions. The maximum nesting depth is bounded by the host stack.
• Iterative model: execution suspends at CALL and PRATT 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 Pratt 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.

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. 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 ; ). 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 module is stored in the .pegoc version 2 format. 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. Character class table: a list of (negated, expectation string, number of ranges (unsigned), followed by the lower and upper bound of each range).
3. Type table: a list of (name, terminal, list of field names).
4. Field-list table, then scope table: each a list of lists of string indices.
5. Rule table: a list of (name, body, scope, action, body is a sequence, terminal type, memoize, leader, position-dependent, Pratt, value-free twin, transient, variables).
6. Pratt 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); an operator is (index, kind, associativity, level, line).
7. 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 and the instruction-set version are valid, and no data remains after the end.
• Every reference in the tables and instructions (strings, character classes, scopes, field lists, rules, Pratt tables, expression code, built-in functions) is in range.
• Every opcode is known, and every flag operand is within its range.
• Every jump target is forward. Only NEXT jumps backward. The target of EFUNC is also forward.

A runtime does not verify that instruction sequences use the value stack and the entry stack correctly. Runtime errors caused by invalid code are reported as parse errors, but termination is not guaranteed, so load files only from trusted sources.