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 zp.WithUnit(zp.Bytes) in the Go API and with zp 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 zp.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 budget 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. When the parse records expectations, the error also lists 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 without duplicates: first the names (any item whose text starts with neither " nor [, such as end of input or a name given by @diagnostic), then the literals (starting with "), then the character classes (starting with [). Within each group they are in the byte order of their text. Expected holds them all in this order.

• The message lists at most the first ten items. A longer list is cut after the tenth and ends with , ... and N more, where N is the number of items left out:

  1:1: syntax error: expected end of input, "(", "-", "[", "false", "null", "true", "{", [ \t\r\n], [0-9], ... and 2 more
  

• 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, or the parse does not record expectations, 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. Messages are reported only when expectations are recorded.

#Recording Expectations

Recording what each failed terminal expected costs time and code on every alternative, and most parses never show the list. A parse therefore records expectations only on request. Without it:

• A syntax error has the same position, line and column, and the parse succeeds or fails exactly when it does with recording. The farthest position is tracked either way.
• Expected is empty, Messages is empty and the message is syntax error. The messages of @error and the names of @diagnostic take part in recording, so a grammar that uses them reports them only when expectations are recorded.
• Errors that #recover and #missing return as values have the same positions and spans, and the message syntax error.
• Trees, spans and values are identical.

Recording is requested as follows.

#Errors in Go and on the Command Line

In the Go API, a failed parse returns a *zp.SyntaxError with the fields Pos (the position in the position unit), Line, Col, Expected (every expected item, in the order above) and Messages (the messages of @error attributes), both empty unless expectations are recorded, 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 zp.SyntaxErrors, a list of *SyntaxError; errors.As tells it apart from a fatal *SyntaxError, and the node is valid. The command zp 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 have a cost that the memo does not share. This section defines how that cost is measured, what holds for every grammar, and the classes of growth that a grammar can have.

#Cost

The cost 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 cost. The memory that a parse allocates is at most proportional to its cost plus the input, because each memo entry, node and value is built by cost that is counted. The cost of a parse is measured in budget units, which differ between backends, and the budget of budget limits caps it.

#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 rule, itself included, or that is called from at most one place in the grammar, its own body included, is not memoized in an ordinary parse. It is evaluated as often as its calls are evaluated. A call with a level restriction, level(e, name), is a call of e; the parse of a right operand inside an Operators Rule is not a call.
• While a rule grows at a position, a call there of a rule of a left-recursion cycle other than its leaders, the rules that grow (see Conditions for Linear Cost), evaluates the rule's body instead of reusing a memoized result, which may have read an earlier result of the growing rule. The growth that started last decides: the calls inside it are at its position or later.
• A result that read the growing result of a growth already in progress when the call started is not memoized, because it depends on the step of that growth. The results of growths that started and ended within the call are final, and reading them does not prevent memoization.
• A growing rule can grow again at its position in one parse, and then have another result, when its growth read the growing result of an enclosing growth and its result was computed inside a lookahead or recovered errors, so that a call in the other kind of context, outside or inside a lookahead, does not reuse it. A result that read such a result, directly or through the rules it called, is not memoized either, at any position; a call of the growing rule reads its result when the growth ends, as when it reuses it.
• 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.

Every other result of a rule of a left-recursion cycle is memoized like that of any rule. Within one step of a growth at a position, the calls of the rules of the cycle at that position are evaluated again, and their number depends only on the grammar. Calls at a later position finish their own growth, outside the growth at the earlier position, and are memoized. A result that is not memoized because it read the result of a rule that can grow again is evaluated again at each call, together with the calls that enclose it; condition 5 of Conditions for Linear Cost excludes such results.

#Expressions That Repeat Cost

The memo shares the result of a rule at a position. It does not share cost inside a rule body, nor between results at different positions. The following expressions have a cost 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 cost 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 variable grammar with the bindings {v := "0"} and {v := "1"} grows linearly. The classification reports it as linear given an environment bound, since it counts len(v) as copying all of v, whose size only the values of the variables bound. The classification reports the left-recursive grammar as unknown, not linear: its cause is a growth restarted inside a recursion of rule calls, which the classifier does not bound.

#Conditions for Linear Cost

The conditions below use these terms.

• A copying operation is an operation of an action, predicate or binding whose cost the classifier counts in proportion to the size of the values it builds or examines: joining strings, taking the text of a capture, converting a value to a string, building a list with list, concat, map or filter, taking the length of a string value with len, and comparing two strings. The size of a string is its number of characters, and the size of a list its number of elements; the elements themselves are shared, not copied. So list copies one element for each argument, which the grammar bounds; concat, map and filter copy the elements of the lists they read, and the list of a repetition has one element for each iteration; len of a string value is counted as copying all of it, whatever the position unit, a conservative reading, since the engine can take some of these lengths in constant time, while len of a node or a list is not counted, since it takes constant time; the classifier tells a string value from a node by the types of the checker, and counts an operand whose type it does not know as a string value; and a comparison examines no more than the shorter string, so it is counted as copying only one of its operands, and comparing with a literal costs a constant.
• A left call is a call of a rule of a left-recursion cycle, in the body of a rule of the same cycle, that can run before that body consumes input. The rules that grow are the leaders, fixed by the grammar: until every cycle of left calls passes through a leader, the rule declared first on a cycle that passes through none becomes one, so a cycle can have several. A call of a leader grows it at the position of the call, and a left call of a leader at that position reads the seed that the growth has reached. A call of another rule of the cycle evaluates its body, unless it reuses a memoized result outside a growth at its position (see Evaluations of Rules), and its left calls reach a leader, which grows there. Condition 3 covers what each step of the growth evaluates again, and the first step of a growing unit and condition 3 are checked with the leaders as the rules that grow.
• A scanning source is one of the following: a repetition without an upper bound, the skip expression of a #recover, the growth of a left-recursion cycle at every call of a rule of the cycle other than a left call, the operators that an Operators Rule applies, and a copying operation with an operand, other than the value of a variable, that is not bounded in size by a constant of the grammar. A call of a rule of the cycle after input has been consumed in a body of the cycle, such as the second E in E = E "+" (E "q" / "x") / "x", starts a growth of its own at a new position. In the same way, the right operand of an operator part is parsed at a new position and can apply operators itself (see Parsing Rules), so a unit of an Operators Rule contains a scanning source when its right operand can apply an operator. Copying the value of a variable costs at most L, the bound of Classification, in each evaluation, which condition 4 counts instead. An expression contains a scanning source when the source is part of it, or of the body of a rule that it calls, directly or indirectly.
• A unit is an expression after whose failure the parser continues at the position where the unit started: an alternative of a choice other than the last, one iteration of a repetition, the expression of an option, the expression of a lookahead, which is abandoned whether it matches or not, the base of a #recover, and, in an Operators Rule, each operator part together with its right operand and each operand item other than the last. A unit fails when something inside it fails, including a later part of its own sequence and a rule that it calls.
• A growing unit is a unit whose evaluation begins with a left call: the left call is the first expression that it evaluates, directly or through calls of rules of the cycle, such as the alternative E "+" T in E = E "+" T / T. A unit that evaluates anything before its left call, such as ("y")? E S "q", is not a growing unit. In each step of a growth after the first, the left call reads the seed, and the unit examines the input from the end of the seed. In the first step, the left call fails before the unit examines any input when the unit reaches the leader only through rules of the cycle that cannot succeed without their own left call, as add cannot in expr = add / term; add = expr "+" term. Otherwise, as through F in E = F "+" X / Y; F = E / M, the first step can match M and continue the unit after it, and the unit is also checked as an alternative that is not growing: from its start, against the later alternatives of its choice.
• The continuations of a unit are the expressions that the parser can evaluate next at the position where the unit started:
  • for a growing unit, the growing units that the same step can evaluate after it, which also start at the end of the seed, and what follows the calls that start the growth, at the end of the seed. What the step evaluates after the unit fails runs at the position where the rule grows, and condition 3 covers its cost. When the left call fails in the first step, that evaluation is the one of the first step after the same failure, except that later growing units read the seed, so unless one of them succeeds, the step ends where the first step ended, at the end of the seed. Otherwise the check as an alternative that is not growing keeps the later alternatives from consuming the character at the position where the rule grows, so the step again ends no farther than the seed. Either way the growth ends with the seed and the parser continues at its end;
  • for any other alternative, the later alternatives of the choice, unless every way in which the alternative can fail lies after a #cut in it;
  • for an iteration, an option or a lookahead, what follows the repetition, option or lookahead, through the ends of the enclosing expressions and, at the end of a rule body, through every call of the rule;
  • for the base of a #recover, its skip expression;
  • for a unit of an Operators Rule, the other operator parts and operand items that the rule can try at the same position, and what follows the Operators Rule expression.
• The first characters of an expression are the characters with which an evaluation of it can examine the input beyond its start position: those it can consume first, and those that every lookahead it can evaluate before it consumes input can consume first, through rule calls. The first characters of the continuations include, where a continuation can match without consuming input, the first characters of what follows it. The first characters of a growing unit, compared with its own continuations, and of a growing unit that is a continuation of another growing unit, are those of the part after its left call. As a continuation of a unit that is not growing, a growing unit examines the input from that unit's start, through the seed.
• A unit and a continuation share a call when, at the position where the unit starts examining the input, both evaluate the same call before anything else that examines the input, directly or as the first thing that the bodies of the calls they start with evaluate: a call of the same rule with the same level restriction, or with none in both, of a rule that reads no variable and that is memoized or calls no rule, itself included. The call has the same result in both: the memo answers it the second time, or the rule repeats only its own scan, so the continuation pays for it at most what the unit paid. Calls of one rule with different level restrictions, such as e and level(e, hi), are different calls with different results. An Operators Rule evaluates its skip before anything else at its start, before an operand or a prefix operator part, and continues at the same position when the skip does not match, so the call that its skip evaluates first is a call that a rule whose body is the Operators Rule evaluates first. This holds for a body that is the Operators Rule alone or under attributes other than #recover and #missing, which change what the parser does when the body fails. Because the parser continues when the skip does not match, a skip that cannot match without consuming input is optional wherever it is tried, before an operand or an operator part, and the first characters there include those of what follows it. A call of any other rule is not shared, because evaluating its body again also evaluates again the units inside it, at every level of a recursion.
• A unit is committing when, for each of its continuations, the first characters of the unit and of the continuation are disjoint after the calls that the two share are removed from their starts, one after another, each at the end of the one before. After a committing unit is abandoned, nothing that the parser evaluates next consumes the character at which the unit and the continuation part, so nothing starts again inside the input that the unit examined after its shared calls, and the shared calls are not repeated beyond their own cost. A unit is also committing for a continuation when no scanning source remains in it after those calls are removed: its scanning sources lie entirely inside the shared calls. The input that the unit examines beyond the shared calls is then bounded by the other conditions, as for a unit without a scanning source, and the continuation pays for the shared calls no more than the unit paid, so a restart repeats no scan. A unit is also committing for a continuation that its words exclude. The word of a path of a unit is the text with which the path begins after the shared calls, through groups, captures, discarded expressions -e, #atomic, actions, choices and calls of rules that read no variable and have no level restriction: a case-sensitive literal w that is not empty, optionally followed by a negative lookahead !Y, where Y is a character class or a call of a rule whose body is one, as in "let" !idchar. Every path of the unit must have a word. A unit that fails within a word examines no more of the input than the word and the character after it. After a unit matches a word, the input at its start begins with w, followed, when the word has !Y, by a character outside Y or by the end of the input. A word excludes a continuation when every path of the continuation, evaluated at the same position on that input, fails, examines nothing more, or evaluates a negative lookahead !K where K is known to match, before it reaches the end of w. Along a path, an expression that cannot examine the next character of w and can match without consuming input is passed over, and one that cannot match without consuming input fails there; a literal, a character class or . consumes the characters of w that it matches, and a literal fails where it differs from w; !K where K is known to fail is passed over. K is evaluated only when it is a choice of case-sensitive literals that are not empty, or one such literal, optionally followed by a negative lookahead of a character class, reached through groups, captures, #atomic and calls of rules that read no variable and have no level restriction, with no predicate, other lookahead, cut, #recover, action or level restriction in it. Such a K does not depend on how the parser reaches it. Its literals are tried in order against the rest of w: a literal that differs from it fails, the first that matches decides, and one that w ends inside of leaves K unknown. The lookahead of K is evaluated on the next character of w, or, at the end of w, it is known to succeed only when it has the same characters as Y. So ident = !keyword [a-z]+, with keyword = ("if" / "let") !idchar, is excluded at the start of a unit that begins with "let" !idchar, and a continuation "=" !"=" at the start of an operator part "==" with its right operand.

A grammar's cost from a start rule is at most proportional to n, times a constant that depends only on the grammar, when every rule that the start rule reaches satisfies all of the following. The conditions are sufficient, not necessary.

1. Variables. No binding of a variable reads, through any chain of bindings, captures and rule values, the variable's own earlier value, when the value it binds can reach a later evaluation of the same binding: when a sequence of the rule body has the binding in one element and a call that can reach its rule again in a later element, each at any depth of groups, options and choices, or when the binding is part of the element of a repetition, outside a negative lookahead. A binding and a call in different alternatives of one choice are not on one path of evaluation, because a failed alternative undoes its bindings before the next is tried. A binding after the recursive call binds a value that no later evaluation of it sees, because bindings in a called rule are not visible to its caller. When every binding is a literal, a constant number of combinations of values occurs at a position. When a binding reads a capture or a variable, the cost is linear given an environment bound.
2. Repeated scans. Every unit that contains a scanning source and can fail after one of its scanning sources has examined input is committing. A unit can fail after a source when something that can fail is evaluated after the source: a later element of a sequence that contains the source, a later required iteration of a repetition that contains it, or a negative lookahead around it, in the unit or in the body of a rule that it calls. A source that is a copying operation in a predicate can make the predicate itself fail. A unit that fails only before its sources have examined input, such as an iteration of ([^"]+ / "\"\"")*, gives back to its continuation no more input than its parts before the sources examined, which the other conditions bound as for a unit without a scanning source; a unit that succeeds is not restarted, and a failure after it is a failure of an enclosing unit, which this condition checks in turn. The expression of a lookahead is abandoned even when it matches, and a growing unit and a unit of an Operators Rule are checked whether or not they can fail after a source.
3. Growth. No scanning source can be evaluated, outside the left call that grows, at the position where a left-recursive rule grows, in its body or in the body of another rule of its cycle, other than inside a call of a memoized rule that is not on the cycle. Each step of the growth evaluates these bodies again at that position.
4. Copies. No copying operation copies a string or list whose size can include the size of the value of a call on a recursion with the rule that performs the operation, nor a fold accumulator. The size is the one that the operation copies: the characters of a string, or the elements of a list. A value includes the value of such a call when it is the value of the call, passes it on, as $x does, is an element of it, as $x[0] is, or is built from it by +, text, concat, map or filter. So the text of a capture of the recursion includes the text of the calls nested in it, while a list of nodes of the recursion, as built by list($x), has one element per node whatever the node contains; concat(list($x), $t) with t the list of the rule's own recursion includes it. A value of a rule on a cycle of such values, and the value of an Operators Rule, are taken to include it. A copy whose size does not include such a value does not add up over the levels of the recursion; when it is not bounded by a constant, it is a scanning source, which condition 2 covers. A copying operation in the lambda of map, filter, foldl or foldr runs once for each element, as in a repetition: it copies nothing from outside the lambda that is not bounded in size by a constant of the grammar. A copying operation that copies the value of a variable is linear given an environment bound.
5. Left recursion in lookaheads and recoveries. No rule grows inside a lookahead, or recovers an error while it grows, at a position where another rule grows and while its growth reads the growing result of that rule.

#Classification

zp lint -classify (lint.Config.Classify in Go) classifies the cost of the start rule that it checks and shows the class. The classes are ordered from best to worst, as in the table: each is a weaker claim than the classes before it. A grammar has the worst class of its causes. A witnessed polynomial or exponential cause outranks a reason for the class unknown, because it is evidence of growth, while unknown is only the absence of a proof. The classes polynomial and exponential produce a super-linear hint at each cause, with its witness. The other classes produce no finding; the reasons for the class unknown are shown with the classification. Without the request, there is no classification and no super-linear finding.

The constant c depends only on the grammar and on the backend. K is the largest number of distinct combinations of the values of the variables that memoized rules read, among the calls at one position of the parse. L is the largest size of a variable's value that a copying operation copies or that a memo lookup compares; it is zero when no variable holds a string. Under the conditions, a variable's value is built from literals, captures and other variables without feeding back into itself, so L is at most proportional to n, and the cost of the second class is at most proportional to K · n². A caller that needs a cost proportional to n needs the class Linear.

The first two classes are guarantees under the memoization that Evaluations of Rules describes; an implementation that memoizes fewer rules, as one can for testing, is outside them. The classifier reports them only when the conditions of Conditions for Linear Cost hold, and it over-approximates where it cannot be exact. It assumes that every predicate can both succeed and fail, that every continuation is reachable, and that first characters do not depend on the path that reaches an expression.

The other classes carry no promise. Deciding the cost of a grammar exactly is impossible, because it would decide whether a grammar's language is empty, so a class worse than linear can be pessimistic: no slow input need exist. The classes polynomial and exponential come with a witness, a path of rule calls and expressions that shows the cause, and the class unknown comes with a reason:

• Polynomial. A scanning source in a unit that is not committing, the continuation that can start again inside it, and the enclosing repetition or recursion. The estimated degree is one more than the number of such sources nested in one another through rule calls, so that a repetition restarted inside a restarted repetition gives 3. A copying operation whose size includes the value of a call on its own recursion, or a fold accumulator, gives 2, and so does a scanning source evaluated in each step of a growth.
• Exponential. A binding that makes a variable depend on its own earlier value, or a copying operation that copies a value of its own recursion, or a fold accumulator, more than once, as s + s does.
• Unknown. A condition for linear cost fails without a witness of a polynomial or exponential cause, as when sources that are not committing are nested in one another without bound through a recursion of rule calls. Memoized calls in the recursion can keep such a grammar linear, which the classifier does not decide. Its reason is the first unit that is not committing, or the condition that fails, with the expression where it fails.

#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 cost.
• 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 Cost

Budget limits bound the cost of any parse, whatever its class. Budget is one counter for all of it: it counts the input that terminals, repetitions of character classes and lookaheads examine, including input examined again, rule calls, repetition iterations, growth steps, and the strings and lists that actions and predicates build, in proportion to their size. Each unit adds one to the counter, so a loop that only scans input, a deep recursion and a value that grows without reading the input are all bounded by it.

#Limits

An implementation MAY limit the nesting depth of recursion, so that input of unbounded nesting cannot exhaust the memory of the host. A rule is recursive if it is on a cycle of the call graph: it can reach itself through rule references, directly or through other rules (a rule that references only itself is on a cycle). The nesting depth is the number of entries of recursive rules that are active at once, plus the entries of Operators Rules (below), whether or not they are recursive; the entry of any other rule does not count. A rule outside every cycle appears at most once on the call stack of a parse, so the rules that do not count add a bounded depth that depends only on the grammar. The value-free twin of a rule is as recursive as the rule.

The operand of a prefix operator and the right operand of an infix operator of an Operators Rule nest like entries of recursive rules, and so does the entry of an Operators Rule; chains of left-associative operators do not nest. 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 nested recursive rule calls; the default limit is 100,000 (10,000,000 for the iterative bytecode VM), and the Go API changes it with zp.WithMaxDepth. Every backend reaches the limit at the same nesting of the same input.

#Cancellation and Budget Limits

The reference Go API accepts invocation-local cancellation and a budget limit through WithContext and WithLimits; generated Go exposes corresponding package-local options. These controls are cooperative and backend-local. A zero limit selects the default of that limit and the value Unlimited disables it. The budget 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. Decoding is the one exception: a reservation may follow the decode of at most one character (at most 4 bytes) and must precede storing or using that character. Counts are implementation-specific and are not elapsed-time, memory, or buffered-input limits.

#Default Limits

Limits has two fields, and a zero value selects the default of its field:

Here n is the length of the input in the position unit of the parse: bytes for Bytes, code points for CodePoints. MaxInput has no finite default because the default Budget already grows with n.

Every parse has a budget. A parse that has neither a limit nor a context therefore runs controlled. The value Unlimited (the largest uint64 in Go, Number.MAX_SAFE_INTEGER in TypeScript) disables the budget; with no context either, the parse runs without a control. LimitError.Limit reports the resolved limit, and the default is Unlimited - 1 at most. One constant disables every field of Limits, and a field added to Limits takes the same zero and Unlimited meaning.

MaxInput bounds the length of the input in the position unit. A batch parse, a recognition and the creation of a Document compare the length of the input with it before any parsing work; a Document does so again at every Parse, for the text it holds after its edits. An input of exactly MaxInput units is accepted. A longer input fails with a LimitError of kind LimitInput: Limit is MaxInput, Used is zero and Requested is the length of the input. The check costs O(1), except that CodePoints counts the code points of an input whose byte length passes the limit. It needs no budget and no context: a finite MaxInput alone does not make a parse controlled. It is checked before a context is consulted, so an input over the limit fails with LimitInput even if the context is already canceled. A parser that has no budget controls accepts only a zero MaxInput and Unlimited.

A stream does not know its length. With a finite MaxInput, it fails when the parser asks for a unit beyond the limit and the stream has one, and Requested is the number of units the parser asked for, or the length of the stream if that is shorter. A stream of exactly MaxInput units completes. As with the default budget, the outcome does not depend on how the reader splits the input into reads. With MaxInput at its default, a stream tracks no length.

The default is resolved once per entry point, from the input the entry point receives. For a Document, n is the length of the text at each Parse. A stream does not know n up front, so its default is max(2^20, 1024 * d), where d is the number of units up to the furthest position the parser has demanded from the stream so far, and it never shrinks. d depends on the input and the grammar, not on how the reader splits the input into reads. A parser generated without budget controls spends no budget and accepts only a zero limit and Unlimited.

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 WithLimits(Limits{Budget}) the limit. The budget counter adds the inspected elements of the input representation and the backend's execution steps, one unit each. 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. A stream also charges one unit for each call to its reader's Read, so its spend depends on how the reader splits the input as well; its default limit does not. Reading input charges the budget counter in proportion to the elements examined, so a loop that only scans input, such as a repeated character class, is bounded by Budget. 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 zp.ErrLimit, and errors.As with *zp.LimitError 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.