Chapter 1

Parsing

The preceding chapters define what a grammar means rule by rule. This chapter defines a parse as a whole: how it starts, what the input and its positions are, what a parse produces, how a syntax error is determined and reported, what memoization can and cannot change, what a parse costs in time and memory, and the limits and modes of a parse.

#Start Rule

A parse starts at a rule, the start rule of the parse. It MUST be one of the start rules of the grammar, the rules marked @start (see Start Rules). When no rule is named, the parse uses the default start rule of the grammar. On every interface that takes the name of a start rule, an empty name selects the default start rule of the grammar; it does not select the start rule a parser was compiled or generated for.

Naming a rule that is not a start rule is an error that names the rule and says it is not a start rule; naming an undefined rule is an error that says it is not defined. The start rule is called at the beginning of the input with no binding level, so an Operators Rule in it parses the operators of all levels (see Level-restricted calls).

#Input and Positions

The input of a parse is a sequence of Unicode characters. The input is given as text encoded in UTF-8; a byte that is not part of a valid UTF-8 sequence is read as U+FFFD (REPLACEMENT CHARACTER) occupying one position.

#Positions

A position is a number that identifies a place between two characters of the input: 0 is the beginning, and the length of the input is the end. The range of a node is a pair of positions [start, end).

Positions are measured in a position unit, which is selected for each parse. The unit applies to node ranges, the .Start and .End members and the len function in actions, and the line and column of syntax errors.

The unit affects only how positions are counted. Matching is always performed one code point at a time: a character class or . matches exactly one code point in either unit. In bytes, a code point that is encoded in several bytes advances the position by that many, and each byte that is not part of a valid UTF-8 sequence counts as one position (and one character U+FFFD) in either unit.

This decoding also applies to literals. A U+FFFD in a literal matches either its valid UTF-8 encoding or one invalid input byte, in either position unit. For example, rule main = "�" accepts the single byte 0xff; the matched range ends at position 1. Two invalid bytes require two replacement characters. Position units do not change which Unicode characters match. The text of the string node is the matched input: byte mode keeps the invalid byte, while code-point mode substitutes U+FFFD. The literal's spelling need not have the same byte length as the matched input.

The unit is selected with pego.WithUnit(pego.Bytes) in the Go API and with pego parse -unit bytes on the command line.

#Lines and Columns

Lines and columns in syntax errors are 1-based. A new line starts after each line feed (U+000A); a carriage return does not start a line. The column is counted in the position unit. (This differs from grammar source files, where a carriage return can end a line; see Line terminators.)

#Whole Input

Whole-input entry points such as Parser.Parse succeed only if the start rule succeeds and consumes the entire input. Parsing evaluates the start rule at position 0. If the rule fails, the parse fails with a syntax error. If the rule succeeds without reaching the end of the input, end of input is recorded as expected at the position where it stopped, and the parse fails with a syntax error. The error is reported at the farthest position that parsing reached, which can be beyond where the start rule stopped.

rule main = "a" ("b" "c")?

For the input abd a whole-input parse fails at 1:3 expecting "c"; for the input ad it fails at 1:2 expecting "b" or the end of input. Parser.ParsePrefix(name, input, ...) instead evaluates the named rule at position 0 without an implicit end-of-input check. A successful prefix returns both the rule value and the consumed cursor in the selected position unit and original input bytes; an unconsumed suffix is allowed. An explicit anchor $$ inside that rule still requires the actual end of the supplied input. The API does not change the parser's configured start rule or shift positions to an enclosing document.

#Results

A parse has one of the following outcomes.

The value of the start rule is nil if the rule's value is an optional that did not match. For example, rule main = "a"? on empty input succeeds with nil. A rule whose expression has no valued element, such as rule main = -"a", has the unit () as its value.

#Nodes

The value of a rule without an action is a node. The properties of a node, the Go type pego.Node, traversal, and the text and JSON renderings are defined in Nodes and Values.

#Prefix Parsing

Parser.ParsePrefix(name, input, opts...) selects the rule name for one call and returns its successful endpoint without requiring the rule to consume the whole input. It does not change the start rule that the parser was configured with. The rule MUST be defined; an undefined name is an error. The input is decoded as for a whole-input parse.

The result is a PrefixResult:

Each malformed UTF-8 byte counts as one replacement code point in Consumed, while ConsumedBytes still refers to the original bytes. Positions inside Node are local to input; a caller that passes a slice of a larger source adds the slice's starting byte offset to ConsumedBytes to find the endpoint in the source. Both consumption fields come from the parser's cursor and are independent of the span of Node: a rule whose action returns a smaller node, or nil, still reports everything it consumed. With the Bytes unit, node spans and both consumption fields are in bytes. A node span in code points is converted to bytes before a base offset is added. A zero-width success returns zero consumption, and a nil Node does not imply failure. Only the runtime Parser provides ParsePrefix; generated parsers do not.

Outcomes:

A zero result alone cannot distinguish failure from a successful zero-width rule that returns nil; the error does.

ParsePrefix accepts position units, backends, recognition, tracing, nesting limits, context and work limits. Stream diagnostic options are rejected, as for Parse. A grammar that contains #missing is rejected, even if insertion is not enabled; a positive WithMissingTokens limit is rejected for every grammar. Zero keeps strict prefix matching. Options resolve in order. An explicit $$ sees the actual end of the entire supplied string, so a fragment is confined by slicing both its beginning and its end. Cuts and left recursion keep their ordinary meaning. Prefix parsing shares no memo entries with a Document, does not shift positions to absolute coordinates and does not map escaped or noncontiguous fragments. It can run concurrently on one parser. A compiled grammar supports it on the bytecode backends in the mode that serves the parse: a value parse in parse mode, recognition in recognize mode and a traced parse in document mode (see Compiled Grammars).

#Incremental Documents

A Document owns mutable text and the reuse state of earlier parses. A parse of a document returns what a parse of the current text from scratch returns. The document API, versions, snapshots, interruption and change notifications are defined in Incremental Documents.

#Syntax Errors

When the input does not match the grammar, the parser reports the farthest position that parsing reached, together with the items that were expected at that position: literals, character classes, any character (for .) and anchors (beginning of input, end of input, beginning of line, end of line).

1:5: syntax error: expected "(", "-", [0-9]

• The position is given as a 1-based line and column. The column is counted in the position unit (code points by default).
• The expected items are listed in sorted order, without duplicates.
• Failures inside lookahead and inside the skip of an Operators Rule are not included. Predicates and bottom (_|_) contribute no expected items.
• If the start rule matches but input remains, end of input is expected at the position where the start rule stopped (see Whole input).
• If nothing was expected at the farthest position, the message is just syntax error.
• A @error attribute replaces the expected items inside an expression with a message. If a message applies at the farthest position, the message is reported instead of the expected items.

#Errors in Go and on the Command Line

In the Go API, a failed parse returns a *pego.SyntaxError with the fields Pos (the position in the position unit), Line, Col, Expected (the sorted expected items) and Messages (the messages of @error attributes), and the methods Error(), which returns the text above with its position, and Message(), which returns it without the position. A parse that recovered errors returns the node and an error of type pego.SyntaxErrors, a list of *SyntaxError; errors.As tells it apart from a fatal *SyntaxError, and the node is valid. The command pego parse prints the tree and then each error on its own line, and exits with status 1 in both cases. Run-time errors of actions, nesting-limit errors and interruptions are other error values, not SyntaxError.

#Memoization

An implementation memoizes the result of a rule at a position, so that the rule is not evaluated twice there (packrat parsing). Memoization has the following observable consequences, and no others.

• It never changes the result of a parse. The value, the recovered errors and the syntax error are the same with and without memoization. Memoization changes only the cost.
• Node identity is unspecified. Whether two calls of a rule at the same position return the same node, or equal nodes, depends on memoization. To compare what two nodes matched, compare their text or their fields (see Operators).
• Rules that read variables are memoized per combination of values. The result of a rule that reads variables directly or through the rules it calls depends on their values when it is called, so a memoized result is reused only if the variables have the same values; see Predicates and Variables.
• Actions run when a rule is evaluated. An action is evaluated every time the body of its rule is evaluated and matches, even if the enclosing alternative later fails, and also inside a lookahead, under #atomic and under -. An action has no effect other than its value and its run-time errors, so how many times it runs is not observable, but whether it runs is: an error in an action aborts the parse even in a branch that is abandoned.
• Left recursion is evaluated by growing a seed, which relies on the memo (see Left recursion). While a rule grows at a position, every call of it there reads the growing result, whatever the values of the variables it reads.
• The nesting limit can depend on it. A call that is answered from the memo does not nest, so whether a parse that comes close to the nesting limit succeeds can depend on memoization.

#Time and Memory

The cost of a parse depends on the grammar as well as on the length n of the input. Memoization bounds how often a rule body is evaluated at a position, but some expressions do work that the memo does not share. This section defines how that work is measured, what holds for every grammar, and the classes of growth that a grammar can have.

#Work

The work of a parse is the sum of the following:

• the rule bodies that are evaluated, counting each step of a growing left-recursive rule;
• the input that terminals, repetitions of character classes and lookaheads examine, counted again each time it is examined;
• the iterations of repetitions and the operators that an Operators Rule applies;
• the size of the values that actions and predicates build.

Time is proportional to work. The memory that a parse allocates is at most proportional to its work plus the input, because each memo entry, node and value is built by work that is counted. Work is a model of cost: the counters of work limits measure it in units that differ between backends.

#Termination

A parse of a finite input terminates, unless a reader or a callback that the caller supplies does not return.

• A call of a left-recursive rule at a position where that rule is growing reads its current result instead of evaluating its body, whatever the values of variables (see Left Recursion). A rule therefore cannot call itself at the same position without end.
• A repetition stops at the first iteration that consumes no input, an infix operator applied without consuming input ends its Operators Rule expression, and a recovery applies only when its skip expression consumes input.
• Actions have no recursion: a lambda is only an argument of a built-in function, which visits a list once.

No bound that is a polynomial in n holds for every grammar.

#Evaluations of Rules

In the reference implementation and the generated parsers, a rule body is evaluated at most twice at a position for each binding level and each combination of the values of the variables that the rule reads, with these exceptions.

• A rule that calls no other rule, or that is called from one place in the grammar, is not memoized in an ordinary parse. It is evaluated as often as that place is evaluated.
• A rule of a left-recursion cycle is not memoized, except the rule that the cycle grows. It is evaluated at every call, and again at every step of the growth.
• A growing rule evaluates its body once for each step of the growth, and the number of steps is at most two more than the length of the input it consumes.

#Expressions That Repeat Work

The memo shares the result of a rule at a position. It does not share work inside a rule body, nor between results at different positions. The following expressions do work that grows with the input they cover, and repeat it when they are evaluated again over the same input.

#Classes of Growth

A grammar's work as a function of n falls into one of these classes. A class describes the worst input of each length.

The following grammars have the class shown on the inputs shown.

The same grammars with A = "n", or with the bindings {v := "0"} and {v := "1"}, are linear.

#Conditions for Linear Work

A grammar does work at most proportional to n, times a constant that depends only on the grammar, when all of the following hold. The conditions are sufficient, not necessary.

1. Variables. No variable that a memoized rule reads is bound, along a recursion of rule calls, from an expression that reads that variable's own earlier value. When variables are bound from captures instead, the work is linear given an environment bound.
2. Left-recursion cycles. A rule of a left-recursion cycle other than the rule the cycle grows is never evaluated twice at one position outside the growth of its cycle.
3. Repeated expressions. No expression of the table in Expressions That Repeat Work can be abandoned and then evaluated again at a position strictly inside the input that it covered. An expression can be abandoned when it is in an alternative that is not the last of its choice, when a later part of its sequence or repetition element can fail, when it is inside a lookahead, and when it is in the base of a #recover, including through the rules that call it.
4. Values. No action or predicate builds a value whose size can double from one evaluation to the next.

When condition 3 fails, the degree of the polynomial is one more than the number of such expressions nested in one another, through rule calls. When condition 1 or 2 fails, or a value doubles, work can be exponential.

#Memory

• Memo table. It holds at most one entry per memoized rule, position, binding level and combination of variable values.
• Values. A parse keeps the value of its start rule. Values built by abandoned alternatives are not kept, but their construction is work.
• Call stack. It holds at most as many calls as the nesting limit allows.
• Streams and Documents. A stream parse discards memo entries and input before the elements that it has delivered. A Document keeps memo entries and repetition records for its whole text between parses.

#Bounding Work

Work limits bound the work of any parse, whatever its class. In the engine backends, MaxInputWork counts the input that terminals, repetitions of character classes and lookaheads examine, including input examined again, and MaxSteps counts rule calls, repetition iterations, growth steps, and the strings and lists that actions and predicates build, in proportion to their size. A value that grows without reading the input is therefore bounded by MaxSteps and not by MaxInputWork.

#Limits

An implementation MAY limit the nesting depth of rule calls, so that input of unbounded nesting cannot exhaust the memory of the host. When the limit is exceeded, the parse fails with a run-time error and no value. In the reference implementation the error is nesting too deep: more than N rule calls; the default limit is 100,000 nested calls (10,000,000 for the iterative bytecode VM), and the Go API changes it with pego.WithMaxDepth. The operand of a prefix operator and the right operand of an infix operator of an Operators Rule nest like rule calls; chains of left-associative operators do not nest.

#Cancellation and Work Limits

The reference Go API accepts invocation-local cancellation and input-work and execution-step limits through WithContext and WithWorkLimits; generated Go exposes corresponding package-local options. These controls are cooperative and backend-local. A zero limit disables that counter. Each counter is monotonic for one invocation and resets on the next call. A reservation is checked before the corresponding work begins; if it exceeds the remaining allowance, that work is not performed. Counts are implementation-specific and are not elapsed-time, memory, or buffered-input limits.

Cancellation and exhausted limits are fatal interruptions, not ordinary syntactic mismatches. Ordered choice, predicates, recovery, and other grammar constructs cannot absorb them. An interrupted batch parse returns no partial Node or typed value. In streaming mode, elements already delivered to the caller remain delivered; the parser does not retract them. A blocked reader or caller callback cannot be preempted by a synchronous parser; cancellation is observed after the call returns.

For a Document, a cancellation or option error detected before execution has touched reusable state preserves its valid caches and last statistics. Once execution starts, an interruption clears execution memo/repetition state before the next attempt, because entries can depend on unfinished left-recursion work. Fully completed input tables may be retained, but incomplete tables are never published and are discarded. A retry with fresh invocation controls must produce the same result as parsing the current text from scratch.

In the Go API, WithContext(ctx) supplies the context and WithWorkLimits(WorkLimits{MaxInputWork, MaxSteps}) the limits. Input work counts inspected elements of the input representation; steps count backend execution work. Charges are not rolled back by backtracking, and their values depend on the backend, the position unit and the generated artifact. For a given artifact, input and options they are the same on every run: the storage that an earlier parse left in a reused parser, and when a collection releases it, never change them. Reading input MAY charge only input work: a loop that only scans input, such as a repeated character class, can run without charging steps, so MaxSteps alone does not bound scanning and MaxInputWork is the limit that does. A cancelled context returns the error of the context (errors.Is(err, context.Canceled) or context.DeadlineExceeded); an exhausted limit returns an error that matches pego.ErrWorkLimit, and errors.As with *pego.WorkLimitError gives the details. Stream parses and documents are specified in Streaming and Incremental Documents.

#Modes

The same grammar can be run in several modes. Except where stated, each mode gives the results that an ordinary parse gives.