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.
| Interface | How the start rule is selected |
|---|---|
| Go API | The compiler.WithStart option of compiler.Compile and compiler.CompileGrammar, where an empty name selects the default start rule; Parser.WithStart makes a parser with another start rule for whole-input parsing; Parser.ParsePrefix selects a start rule for one prefix parse without changing the configured start rule. Both take an empty name for the default start rule |
| Command line | sxir parse -s <rule>. It defaults to the start rule saved in a compiled grammar (.sxirc), and otherwise to the default start rule |
| Generated parsers | Parse uses the start rule selected when the parser was generated, the default start rule unless another was named; ParseRule and ParseRuleValue (parseRule and parseRuleWithOptions in TypeScript) take the name of a start rule, or an empty name for the default start rule |
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.
| Position unit | A position is the number of ... from the beginning of the input |
|---|---|
| Code points (default) | Unicode code points |
| Bytes | bytes of the UTF-8 encoding |
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 runtime.WithUnit(input.Bytes) in the Go API and with
sxir parse -unit bytes on the command line. In the Go API, parse names the package
syntaxir.dev/sxir/pkg/runtime and its subpackages, which hold the types that the compiled parsers and generated
parsers share: limits, position units, syntax errors, edits and statistics.
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.
| Outcome | What the parse returns |
|---|---|
| Success | The value of the start rule, which is a node or nil |
| Success with recovered errors | The value, together with the list of syntax errors that #recover recovered from |
| Syntax error | No value; the syntax error. If errors were recovered before, only the final syntax error is returned |
| Run-time error | No value; the error of an action or a limit that was exceeded. It aborts the whole parse |
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 value.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:
| Field | Meaning |
|---|---|
Node |
The value of the selected rule, as for a whole-input parse (a node, a value node or nil) |
Consumed |
The successful cursor in the parser's position unit (code points by default) |
ConsumedBytes |
The endpoint in bytes of the original UTF-8 input |
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:
| Outcome | Result |
|---|---|
| The rule matches | The PrefixResult and a nil error |
The rule matches after #recover |
The PrefixResult and SyntaxErrors, as a whole-input parse returns a node with recovered errors |
| Syntax failure, including a failure after an earlier recovery, or a fatal error | The zero PrefixResult and the error. No speculative endpoint is exposed |
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 compute 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 asend of inputor 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.Expectedholds them all in this order. -
The text of a literal item is the literal as the grammar writes it, so it can be copied back into a grammar unchanged. It is enclosed in double quotes. The quote and the backslash are written
\"and\\, and line feed, tab and carriage return\n,\tand\r. A character that is not a Unicode letter, mark, number, punctuation or symbol, and is not the space U+0020, is written\u{h}, with its code point in lowercase hexadecimal digits and no leading zeros; this covers the other control characters,\0as\u{0}, separators, format and unassigned characters. Every other character, ASCII or not, stands for itself. A case-insensitive literal keeps its suffixidirectly after the closing quote ("select"i). For example, the literal"\u{1F600}\0"iis shown as"😀\u{0}"i. -
The message lists at most the first ten items. A longer list is cut after the tenth and ends with
, ... and N more, whereNis 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
skipof an Operators Rule are not included: an evaluation there records neither expected items nor a farthest failure, so it moves neither the farthest position nor the items expected there. Predicates and bottom (_|_) contribute no expected items. -
If the start rule matches but input remains,
end of inputis 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
@errorattribute 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.
Expectedis empty,Messagesis empty and the message issyntax error. The messages of@errorand the names of@diagnostictake part in recording, so a grammar that uses them reports them only when expectations are recorded.- Errors that
#recoverand#missingreturn as values have the same positions and spans, and the messagesyntax error. - Trees, spans and values are identical.
Recording is requested as follows.
| Parse | Request |
|---|---|
Parser.Parse, ParseStream, ParsePrefix, Document |
The option runtime.WithExpectations(). A Document fixes the mode when it is created; a later parse that asks for the other mode is an error |
| Generated Go and TypeScript parsers | Generate with the option Expectations (-expectations in sxir gen), which gives the parser its table of expectations and a parse option WithExpectations (Go) or expectations (TypeScript). A parse records them only when it passes the option; a generated parser without the generation option has no table and no such option, and a parse of it that passes the runtime's WithExpectations or expectations: true returns an error |
sxir parse, sxir debug, sxir trace, sxir explain, sxir profile, sxir test, sxir editfuzz and the playground |
Always on |
Errors in Go and on the Command Line
In the Go API, a failed parse returns a *value.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 value.SyntaxErrors, a list of *SyntaxError; errors.As tells it
apart from a fatal *SyntaxError, and the node is valid. The list holds only the
recoveries that the result keeps: one that backtracking undoes, or that is
inside a lookahead or the
skip of an Operators Rule, is not in it. The command sxir 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. Whether two calls of a rule at one position return one
node is not observable, because
==and!=do not compare nodes (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. Finding a memoized result costs in proportion to the size of the key (the number of variables and the length of their string values), not to the number of combinations of values that the position holds. In a parse of a Document, a lookup also counts the edits it applies to the entry it finds.
- 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
#atomicand 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.
- Traces and evaluation counts can differ between backends. Which calls a parse evaluates and which it answers from the memo is part of the cost. The rules above leave implementations a choice, such as whether examined ranges keep the results of left-recursion contexts apart (Evaluations of Rules), so the calls in a trace and the evaluations that a profile counts can differ between the engine and generated parsers. The value, the positions, the recovered errors and the syntax error do not.
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 calls of rules and the rule bodies that are evaluated, counting each step of a growing left-recursive rule, and for each call of a memoized rule the size of its memo key;
- 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;
- the elements that a walk of a run site copies from the record it takes behind its own values (its suffix copies).
A text value, the result of text of a node, denotes a range of the
input. In a parse of a whole input, in bytes or in code points and whether or
not the input is valid UTF-8, and in a parse of a Document,
text costs a constant, whatever the length of the range: it is not a value
that the action builds in proportion to its size. Materializing a text value
as a string of the host language is not part of the cost of the parse, so a
backend can return a view of the input or a string that it builds when the
caller reads it. To make texts constant, a backend can do work in a parse
that adds up to at most a constant times the length of the input, such as
decoding an input that is not valid UTF-8 when the first text is taken, or
copying the texts that cross the pieces of an edited Document until it joins
the pieces; a parse that takes no such text does not do that work. A stream discards input, so in a
stream text costs the length of its result. Comparing two strings examines
no more than the shorter one, so it costs at most the length of the shorter
operand, plus a constant.
Outside a Document, and apart from the exceptions below, time is
proportional to cost, including the time to list the recovered errors of a
result: a result reports at most a constant times the input that its parse
matched, and a parse outside a Document examines that input at a cost that is
counted (linear cost proof).
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,
and the list of recovered errors is at most a constant times the input. A parse
with missing-token insertion is an exception to both, as below: the specification
gives no bound of the number of its errors by the input or the cost.
The cost of a parse is measured in compute units, which
differ between backends, and the budget of
compute limits caps it. Each backend that
counts compute units, the engine's closure backend and bytecode machines as
well as Go parsers generated with limit controls, charges at least one unit for
each call, each character that a terminal matches or rejects, each iteration
that it evaluates, each operator applied and each value that an action builds,
and at most a constant of the grammar and the backend for each of them, besides
the units that it charges for the input as a whole before the parse. An
iteration of a repetition (*, + and #repeat) charges exactly one unit, on
every backend, before its element is evaluated: each evaluation of the element
counts, the last one included, which fails or consumes no input, and nothing
else does. A repetition that stops at its maximum evaluates no further element
and charges no further unit, and an option is no repetition and charges
nothing. A call of a rule charges exactly one unit, on every backend, the
entry of a parse into its start rule included, and each evaluation of a rule
body one more, each step of a growing left-recursive rule included; a call that
the memo or a growing seed answers evaluates no body. A call of a rule that an
ordinary parse memoizes (Evaluations of Rules) also
pays for the lookup of its memo key: one unit for each variable that the rule
reads and one for each byte of the UTF-8 encoding of each string value that
such a variable holds, whatever the memo holds and whether or not the call
looks the key up, which a first call whose memoization is deferred does not.
Deferring memoization, looking a key up, comparing keys and storing a result
charge nothing else. A walk that
takes the rest of a walk from a record of a skip run, a
run site or a scan site neither evaluates nor
charges the iterations and characters that it skips, and the lookup that
finds the record ends the walk without an iteration. Likewise, a repetition of
a Document parse that resumes a recorded run
(Runs) neither evaluates nor charges the elements
that it reuses, and finding them charges no iteration. Growing the storage of a
parse charges no unit: the memo table and the record of the rules called at
each position grow to the positions and rules of calls that are counted, and
growing them by doubling, or by pages of positions, copies and clears at most a
constant times their final size. A cut
charges no unit either: the choices, repetitions and lookaheads it passes on
its way to the one it marks are open in the body of the rule that holds it,
at most a constant of the grammar. A parser generated without
limit controls counts no units.
The values that the parse builds rather than an action, the terminals, sequences, tuples and lists of the grammar's expressions and the nodes that wrap captured values, are not an item of the cost and charge nothing; neither do gathering the values of a repetition or a sequence, taking them off into their list, dropping them, or attaching captures as fields. Each is a constant of the grammar for the evaluation, iteration or examined input that is counted where it is built. The suffix copies of a run site are the exception: a list keeps its elements contiguous, so a walk that takes a record copies the record's elements behind its own, and these copies are not bounded by the other items. They are an item of the cost, and a walk charges a unit for each element it copies; the copies are at most the iterations that taking the record spares.
Converting the result of a parse into the typed values that the ParseValue or
parseValue of a generated parser returns charges nothing either: the
conversion visits each value of the result at most once for each type it
converts it to, a constant of the grammar for each value the parse built. It
still observes cancellation and the memory limit.
Some values are built by the runtime rather than by an action, and each backend charges them as follows:
-
Syntax errors. A syntax error that a recovery builds is charged:
- one unit for each expectation that it is given;
- the steps of sorting their descriptions;
- the steps of finding its line in a table of line starts.
The first such error of a parse of a whole input also charges one unit for each code point of the input, which builds that table. The table is built lazily, so a parse without errors does not charge for it. A stream finds the line from its own record of line starts.
-
Error messages. The message of a recovered error that a value holds is charged as a value of its size: one unit, one for each byte of its text and one for each of its parts. The value is an error node of the Node runtime or the value of the error in a typed parse.
Compute units also count work that the cost does not, and the budget caps it too. In a parse that recovers errors, a memo entry, a result of a growth or an attempt of an Operators Rule shares the list of the errors recovered in it, and a call that reuses the result records that list as one entry. On every backend, the recovered errors of a parse are a sequence of entries, each an error or a list of entries, and a list never changes once made:
- a recovery records the error that it makes as one entry;
- where a memo entry, a result of a growth or an attempt of an Operators Rule is stored, the entries recorded since its evaluation began are taken as its list: none give an empty list, one is taken as it is, an error or a list, and two or more become a new list that takes their place in the sequence; taking them charges one unit for each entry taken;
- a call that reuses such a result records its list as one entry, and an empty list not at all, and a growth that ends puts the list of its result in place of the entries recorded since it began in the same way; neither charges a unit for the list;
- backtracking drops the entries recorded after the point that it returns to, a stream forgets the entries whose errors it has delivered, and listing the errors of the outcome charges no unit.
These charges add up to at most a constant times the cost (linear cost proof), except in a parse with missing-token insertion, which records the errors of every reused result one by one. A store under a key that a long chain of memo entries holds walks the chain, which cost does not count; that matters only where K grows with the input, and has not been measured.
A parse of a Document also does work that the cost does not count: it applies pending
edits to the memo entries it finds, moves or copies the values it reuses, and works through
what the Document retains from earlier parses. Its time includes that work, so it is not
proportional to its cost, but no Compute limit counts it (the generated TypeScript runtime
still counts it under an explicit limit until it leaves that work out);
Work of a Document Parse bounds what each
of its operations does, and the
linear cost proof
states the bound of their sum. The memory limit caps the storage a parse
takes into use in bytes.
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 three times at a position for each binding level and each
combination of the values of the variables that the rule reads, with the
exceptions below. A first evaluation may leave no result in the memo, except a
growth of a leader, which stores its result as a later one does. A result
computed inside a lookahead or the skip of an Operators Rule answers only the
calls inside them, and a result computed outside them answers every call,
whether or not it has recovered errors. Whether a call is inside a lookahead or a
skip is thus part of the key of a result computed there, and not of one
computed outside them. The memo answers a call from one entry of its key. A store under a
key whose entry the parse can use keeps one entry that answers every call
that the entry or the new result answered: the result computed outside a
lookahead if exactly one of the two was, and the new one otherwise, with the
leaders recorded for both, as the item on contexts below describes. An entry that the
parse cannot use, as one that lags behind too many edits of a
Document, is replaced. So a store never narrows the calls
that the entry of its key answers, and at most one evaluation in each of the
two states, outside every context of growths, stores a result. A rule without an action that is on no left-recursion
cycle can have a value-free twin, which matches as the rule does and builds
no value of its own: it builds a value only inside a capture, and every
capture in it builds the value of what it captures, as in the rule. It evaluates the
body of the rule as the rule does: the same expressions at the same positions,
with the same matches and ends, its predicates and bindings reading the same
values, and at each call the rule that the rule calls there or the twin of that
rule. A call whose value is not used, such as a call inside a discard, a
negative lookahead or an #atomic, evaluates the twin. Which of the two a call
evaluates depends only on the discards, lookaheads, #atomics and captures
around the call in its rule body, on the action of that rule, and on which of
the two the body is evaluated for. A rule and
its value-free twin count as two rules, with memo entries of their own: an entry
of one answers no call of the other. The twin is memoized exactly when its rule
is, as the exceptions below decide for the rule, even where the twin is called
from fewer places. Of the evaluations of a memoized rule at a position outside
every context of growths, only the first may leave no result in the memo,
whatever its binding level, the values of its variables and its lookahead
state, and the same holds of the evaluations of its twin: every later one
stores its result, in the state, inside a lookahead or a skip or outside
them, in which it is made. Which first evaluations leave no result is exact
and the same on every backend, because the cost counts the
evaluations of rule bodies. In an ordinary parse, neither a stream nor a parse
of a Document, each memoized rule, and its twin separately,
counts its calls, and among them its repeated calls: those at a position where
it was called before in the parse. A call at a position where the rule was
not called before evaluates the body and leaves no result, until the repeated
calls exceed a sixteenth of the calls, rounded down, the current call
included; from then on every evaluation of the rule stores its result, the
first at a position included. A call that makes the count of calls
231 halves both counts, rounding down. A stream stores the
result of every evaluation. The
result stays in the memo for the rest of the parse, except that a
stream drops the results at positions before an element that
it has delivered, where the parse makes no later call.
Conditions for Linear Cost takes this as a
condition of its bound; which results are stored never changes the result of
a parse. A recognition builds values only for the rules that a call
inside a capture that a predicate can read reaches, directly or through other
rules, and builds them there as a parse does, with their twins, even where no
predicate reads the value of such a rule. A predicate can read a capture of its
own scope whose name it reads, other
than as the parameter of a lambda, and whose value that name can hold when the
predicate runs: not one in another
alternative of a choice, which backtracking undoes, nor one made after the
predicate, nor one that a later capture of the same name replaces on every way
to the predicate. Every other rule builds no value
there and has no twin, so its calls, whether their value is used or not,
evaluate the rule itself, with one memo entry. The
exceptions are these.
-
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 start rule that its own body calls, directly or through rules called from one place, is memoized all the same: a parse can enter it without a call, so the place in the grammar is not its only one. A leader (see Conditions for Linear Cost) is memoized in every case. A call with a level restriction,
level(e, name), is a call ofe; the parse of a right operand inside an Operators Rule is not a call. -
While rules grow at a position, a call there of a rule of their left-recursion cycle, a leader (see Conditions for Linear Cost) or another rule, is in the context of those growths. Only the growths of the rule's own cycle form its context: a call reads no growing result of another cycle. A call there of a rule on none of their cycles is in no context of growths: the memo answers and stores it as any call outside a growth. Its result is the result of evaluating its body with the growing results that they have reached. A memo entry records the leaders whose growths at its position formed the context of the call that stored it, none for a call outside every context, and a store that keeps one entry for two results records the leaders of both. The memo stores a result only if it read no growing result and observed no lookahead that read one; such a result is the one that the call has outside every context, and its evaluation calls no leader that it records at its position, so it is the result in any context whose leaders it records. A call in a context reuses a memoized result only if the entry records every leader whose growth is in its context; a call outside every context does not look at the leaders. Otherwise it reuses a result computed in a context of the same growths only if every growing result that it read is equal to the one there now and every such lookahead has the same outcome. Where the parse records the input that evaluations examine, equal growing results and equal outcomes also need equal examined ranges: in every parse of the engine, whose traces report the range, and in a Document parse or an observed parse of a generated Go or TypeScript parser; a generated parser in any other parse compares no range. A result that read a growing result is kept only until the first growth of its context ends, and never enters the memo of a later parse. A lookahead counts as observed by its outcome only if nothing else of it remains after it: a positive lookahead whose expression makes a capture or binds a variable outside the rules that it calls is not observed, and the growing results that it read count as read by the result around it. The errors recovered inside a lookahead do not remain after 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. A leader that grows at a position where another growth of its cycle is in progress grows again in each context in which it is called there, unless the call reuses a memoized result or a result kept in a context of the same growths, as the item above describes. A step of such a growth reuses the step that an earlier growth of the leader took from the same growing result under the same condition, and a run of steps that read no other growing result is taken at once when every lookahead that those steps observed has the same outcome now and that outcome read no growing result of the leader itself.
Until the first growth of a context at a position ends, a call there of a memoized rule in that context, and a step of a growth in it, is evaluated at most once in each of the two lookahead states for each variant, binding level, combination of the values of the variables that the rule reads, present set and combination of the growing results that it reads, directly or through the lookaheads that it observes and those that they observe in turn, and of the outcomes of those lookaheads, apart from the first call of the variant at the position, which may leave no result, as outside every context. Two growing results count as one there only where the parse finds them equal: it may compare results by their structure only up to a bound, and takes results that it has not found equal as different. A kept result records at most one growing result for each leader and binding level of the cycle and one outcome for each lookahead in the bodies of the rules of the cycle, so finding and keeping it costs a constant of the grammar besides comparing the values of its variables. A lookup of a call or step finds a kept result with the same key and present set when each growing result that the result recorded is equal to the one there now and each outcome that it recorded is equal to the outcome kept there now for that lookahead, which the lookup finds in the same way, by the growing results and outcomes that the outcome recorded, each lookahead at most once on the way, a repeated one matching nothing; a lookahead with no outcome kept there matches no result. A result kept inside a lookahead answers only lookups inside one. In a parse with missing-token insertion this holds only of rules and leaders that do not contain
#missing, directly or through the rules they call.
Every other result of a rule of a left-recursion cycle is memoized like that of any rule. Calls at a later position finish their own growth, outside the growth at the earlier position, and are memoized. A growth that begins from a result that includes the growing result of another growth at its position is new in each step of that growth, since each step reads another growing result; when the steps drop its result and it goes on over the input that later steps cover, it covers that input again in each step. Condition 5 of Conditions for Linear Cost excludes it.
An ordinary parse without missing-token insertion therefore memoizes every rule
that it reaches, a rule of a left-recursion cycle outside the contexts of
growths, except the rules that the first exception of this section leaves out,
none of which is a leader: a rule that calls no rule, and a rule called from at
most one place. The one call of a rule of the second kind is in the body of a
memoized rule or of another rule of that kind, and following those calls ends at
a memoized rule or at the start rule where the parse begins: when every rule of
a cycle of calls is called from one place, that place is on the cycle, so a
parse reaches the cycle only by beginning at a start rule on it, and that start
rule is memoized. A parse with missing-token insertion takes its cycles and
leaders from the analysis with insertion
(Left Recursion), and also
leaves unmemoized every rule other than a leader that contains #missing,
directly or through the rules it calls; such a parse is outside the classes of
Classification.
A parser may skip an alternative of a choice by the next character, without
evaluating it, only where the alternative must begin with a terminal, a
non-empty literal or a character class, reached through expressions that begin
by evaluating it and fail when it fails: the first item of a sequence, a
capture, a discard, an #atomic and a call of a rule other than a leader or an
Operators Rule. It skips the alternative only where that terminal cannot match
there, by the next character or, for a literal that may insert its text, by an
insertion, or where no character remains, and only where the calls on the way
stay within the nesting limit. The evaluation that it skips would fail at the
position, inside a lookahead or not: it would consume no input, enter no
repetition, make no call other than those on the way to the terminal, each of
which would fail there, and record only the expectation of the terminal. The
skip records that expectation too, though it need not where recording it
could not change the expectations that the parse reports, as inside a
lookahead or the skip of an Operators Rule, whose failures are not reported,
before the farthest failure, or in a parse that does not record expectations. A lookahead, an option, a
repetition, a choice, a predicate or an expression with an @ attribute or
the pragma #recover or #stream is not on the way: an alternative that
begins with &([a-z]*) "q" is evaluated where the next character is not q,
and its lookahead consumes input inside it. The pragmas #ignorecase and
#missing annotate a literal, which stays a terminal: a case-insensitive
literal and a literal that may insert its text. Parsers need not skip the same
alternatives, so they can differ in the calls that they make
(Observability) but not in the outcome of any evaluation.
Growths of Left Recursion
The growth of a left-recursive rule (see Left Recursion) and the rules above for the memo and the contexts of growths rest on the following, which every backend keeps.
- Calls before consuming input are found. Every call that an evaluation
makes at the position where the body of its rule started is one that the
analysis of Left Recursion
finds as a call that may run before consuming input. The analysis includes
the calls in lookaheads, repetitions, options and
#recover(skip=...), and leaves out only the calls that it proves cannot run there. A call of a rule of the caller's left-recursion cycle found in this way is a left call (see Conditions for Linear Cost). - Every cycle passes through a leader. The leaders are chosen until every cycle of left calls passes through one, so no cycle of left calls is left without a leader.
- Positions do not decrease. A call is made at a position that is not before the start of the body that contains it. A choice, a lookahead, a repetition and a recovery go back only to a position where one of their subexpressions started, never to one before the body began.
- A growth is kept for each binding level. A growth is told apart by its
leader, its position and its minimum binding level: 0 for a call without a
level, and for a call with a level restriction
level(e, name), which is a call ofe, the number of levels looser than the named one. A restriction to the loosest level applies every level, as a call without one does (Level-Restricted Calls), so the two are the same call and share a growth. A call reads the current result only of the growth of its own leader and level at its position; a left call of the same leader at another level starts a growth of its own there. The values of variables do not tell growths apart (see Left Recursion). - A leader grows at every call. A leader is memoized in every case (see Evaluations of Rules), whatever the number of places that call it, so a call of a leader whose result at the position is not yet in the memo grows it there.
- Runs taken at once hold adopted steps. A run of steps that a growth takes at once (see Evaluations of Rules) consists only of steps whose result became the current result. The step that stops a growth is evaluated, or answered from an earlier step under the same condition, on its own.
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.
| Expression | Cost of one evaluation | Repeated when |
|---|---|---|
| A repetition | Its iterations, up to the input it matches | The body that contains it is evaluated again at an earlier position, so the repetition covers the same input again |
| A lookahead | The cost of its expression | It is evaluated at each of many positions and its expression examines the input after them |
#recover(skip=e) |
The cost of the base expression and of e |
Its result is abandoned and parsing continues inside the skipped input, except for the walks of skip runs, which share their cost |
| A growing left-recursive rule | One evaluation of its body per growth step | It is called at many positions of one input, because its result at one position is not built from its result at the next |
| An Operators Rule | One step per operator it applies | As for left recursion |
| A rule that reads variables | As for any rule, once for each combination of values | Calls at one position bind its variables to many different values |
| An action or predicate | Proportional to the sizes of the values it reads and builds | A value grows from its own earlier value, as s + s does |
An Operators Rule that nests through the right
operands of its operator parts can end an inner level and the levels that
enclose it at one position, and each of those levels evaluates the skip and
tries the operator parts there again. After a level applies an infix or prefix
operator, it applies next only an operator that the right operand of that
operator does not admit by its binding level. An infix operator applies only
where the level admits it, so its right operand admits no part that the level
around it does not; only a prefix operator, which applies at the start of a
right operand whatever its binding level, can give its own right operand parts
that the right operand around it does not admit. So when every infix operator
part that the right operand of a prefix operator part admits is also admitted
by the right operand of every infix and prefix operator part, none of the
levels that end at one position parses the right operand of an operator part
again once one of them has tried it and refused the part: every right operand
around the level that tried the part admits it, so each level around ends
without trying it. This changes no result: the longest match is deterministic,
so it is the same part at every level, and its right operand would be the same
parse with the same minimum binding level, so the part would be refused again.
So the right operand of a refused part is parsed once at a position, and what
the enclosing levels repeat there is the skip and the operator parts alone.
Otherwise the right operand can be parsed again at each level: with
level low { prefix "-" }, level mid { infix left "*" } and
level high { infix right "^" }, the right operand of each - in
a^-a^-b*--; admits * and tries it; the right operand of * scans the -
and fails at ;, and each ^ level around tries * and that right operand
again, since its own right operand does not admit *.
Skip Runs
The skip expression of a #recover runs at every position where the base
expression fails, and a repetition in it walks forward from there. When the
base fails at many positions one after another, as when a repetition retries
a failing recovery at each position, each walk covers the input that the walks
before it covered. The walk of an unbounded repetition from a position ends
where the walk from any later position it passes ends, so the implementations
record the rest of each walk and share it.
A skip-run site is a repetition written in a skip expression, not inside another repetition of that expression that is a site, for which all of the following hold:
- it has no upper bound;
- its expression contains no predicate that reads or binds a variable (a skip expression has no captures);
- its expression contains no
#cutthat applies to the repetition, that is, one outside every choice, option, repetition and lookahead of the expression; - neither its expression nor a rule that the expression calls, directly or
indirectly, reads a variable, contains a
#recover, or is a rule of a left-recursion cycle.
A repetition in a rule that a skip expression calls is not a site, nor is a repetition inside a site. Bindings made inside a called rule are undone when the rule returns, so only the predicates of the expression itself count.
An evaluation of a site is a walk that visits the positions where its iterations start. The parser keeps a slot for each position, per site and separately inside and outside lookaheads; a slot is fresh, visited or recorded. A recorded slot holds the record of what the rest of a walk from its position did: where it ended, its farthest failure and the expectations there, and the range of the input it examined.
A walk starts plain: it records nothing, and marks the position of each iteration as visited when it moves past it, at the next iteration or when it starts recording there. A walk that ends at its first iteration marks nothing. At its first iteration at a position whose slot is not fresh, which an earlier walk of the site visited, it starts recording, and stays recording to its end. A recording walk that has matched the minimum number of iterations looks up the slot of the position before each further iteration. When the slot is recorded, the walk ends where the record ends, records its expectations again, and extends the range that the enclosing results examined by the recorded range, as a memoized result does. When a recording walk ends, at an iteration that fails or consumes no input, or at a recorded position, it records every position it visited while recording, from the last back to the first: the record of a position combines its own iteration with the record of the next position. A walk that does not end, because the parse stops, records nothing.
Records never change the result of a parse, and a parse in which the base of
no #recover fails evaluates no skip expression, so it keeps no slots;
neither does a parse whose walks all end at their first iteration, as when the
base fails at the end of a list and the skip fails at once. The
slots of a parse last for that parse: an incremental document
starts each parse without them, and its results examine what the walks behind
them examined. A stream drops the slots of the positions
before the input it commits. A parse with missing-token insertion keeps no
slots.
A walk under compute limits charges these units in addition to those of its iterations; marking a slot is free:
- in a recording walk, 1 for the lookup before each iteration from the minimum on;
- 1 more when the slot is recorded, and the charges of recording its expectations, as for a memoized result;
- for each iteration of a recording walk, the charges of keeping its expectations and of recording them in the enclosing result;
- 1 for each record stored.
Per site and lookahead state, the element of a site is evaluated at each position at most once while its slot is fresh and once more before it is recorded, plus, per walk, at most the minimum number of iterations, the last iteration of a walk that ends plain, and one lookup; the proof gives the bound. The slots of a site take a bit for each position between the first and the last position its walks visit, and a record for each position that recording walks visit.
A skip expression is a reused skip when every repetition without an upper
bound written in it, other than inside another such repetition, is a site
whose expression examines at most a constant amount of the input, and the skip
expression calls no rule and contains no predicate, #recover or Operators
Rule. The expression of such a site has no repetition without an upper bound
and none of those either; it may consume any constant number of characters in
an iteration, as [^;\n] and ("ab" / "a") do. A reused skip costs a
constant in each of its evaluations outside its sites, and the walks of its
sites evaluate their expressions a number of times linear in the input plus a
constant per walk, whatever the number and order of the walks, so the
classification does not count it as a scanning source
(Lemma 9). A skip that calls
a rule stays a scanning source, because a called rule can examine any amount
of the input in one iteration, and so does a repetition in a rule that a skip
calls, which is not a site.
Run Sites
A repetition outside a skip expression walks the same input again each time a failed alternative leads back to its start. A run site is a repetition whose walks keep the records of a skip-run site, with the walks, slots and charges described in Skip Runs, extended as below. It is a repetition for which all of the following hold:
- it has no upper bound and no
#cutapplies to it from its expression, as for a skip-run site, and it does not repeat a single character, which an implementation scans without records; - its expression contains no Operators Rule, no
#streamor#missing, and no@erroror@diagnosticattribute; it may contain captures (which live in one iteration), actions, predicates, variables,#recoverand calls; - every repetition without an upper bound in its expression, or in a rule its
expression calls, directly or indirectly, is a run site, a skip-run site or
repeats a single character; this includes the
skipexpressions of#recover, so a recovery whose skip repeats without records keeps the repetition from being a run site; - every rule its expression calls, directly or indirectly, is called without a
level, is not in a left-recursion cycle and contains no
#streamor#missingand no@erroror@diagnosticattribute; it may be an Operators Rule; - it is restartable: it is in the expression of another repetition whose maximum is neither 0 nor 1, or in a rule that calls itself, directly or indirectly, or in a rule that such an expression or such a rule calls, directly or indirectly. Any other repetition is reached once by a derivation through sequences, alternatives and calls, so a walk of it begins at each position at most once per environment and no walk could reuse the record of another.
The result of the rest of a walk from a position is a function of the position, the variables and the input: an iteration reads the variables that its predicates, its actions and the rules it calls read, and the captures of a repetition element are visible to the iteration alone. A run site is free of the environment when its expression has no predicate that reads or binds a variable, no inline action that reads one, and calls no rule that reads one, directly or indirectly, in a predicate or an action. A binding made in a called rule is undone when the rule returns, so the rest of a walk of such a site is a function of the position and the input, and it ends in the environment it began in. Its records are kept by position alone, and a walk that reuses one keeps its own environment. Skip-run sites are free of the environment by their conditions.
The rest of a walk of any other run site from a position reads the variables that the predicates of its expression read and those that the rules it calls read, directly or indirectly, and changes only the variables that the predicates of its expression bind. The key of the site is the set of the variables that the predicates of its expression read or bind and those that the rules it calls read, directly or indirectly. Its records are kept for a position and the values that the variables of the key held at the start of the walk from that position, and a walk reuses one only where those values are equal, compared as the values of a memo key are: a record for the same position and other values is neither used nor replaced. Environments that hold equal values of the key share the records, whether or not they were built apart and whatever the values of the other variables. So the walks of such a site at one position evaluate its expression once for each combination of the values of its key there, as a memoized rule that reads variables is evaluated once for each combination of them. The key holds the variables that the expression binds even where it does not read them: where the rest of a walk leaves such a variable alone, its value at the end is the one it had at the start, which the key fixes.
Besides what a record of a skip-run site holds, it holds
- for a site that is not free of the environment, the values that the variables its expression binds hold at the end of the rest of the walk: a walk that reuses the record binds those variables to them, and keeps the values of the others;
- the elements of the rest of the walk, for a run site whose iterations have values: a walk that reuses the record lists them after its own elements. The list a walk returns and the records of its positions share one sequence of elements, which later lists hold as a suffix; a list that is made from its own elements and a recorded suffix copies the suffix, except where the sequence has room before the suffix that no record uses. The elements of a record are final: no later step of the parse changes them. A rule and its value-free twin walk the same sites, and a walk whose iterations have values takes no record that a walk without values made, which holds no elements; it records the position again. A record without elements never replaces one with them, so a position holds a record without elements only until a walk with values records it, and never after;
- the errors that the rest of the walk recovered: a walk that reuses the record recovers them again, as a memoized result does.
An implementation may keep records only once the walks of a site have shown that they restart. One way: the site keeps the furthest position that its walks of a minimum length (a constant) reached, and keeps records from the first walk that begins below that position and walks at least that constant length of input below it. Until then the site is an ordinary repetition. Each walk then costs its length, of which the part below the furthest position is shorter than the constant, so the walks of the site cost in total at most the input length plus the constant for each walk, however the walks alternate between positions. A site whose walks never go back, as a list that a parse reads once, keeps nothing. Under compute limits, testing whether a site keeps records and noting the end of a walk at a site that does not yet keep them are free, as marking a slot is.
A walk of a run site whose iterations have values and that ends without making a list, as one that fails below its minimum, drops the elements it holds and those of the record it took; as for a repetition that fails below its minimum, dropping them charges nothing.
A walk that reuses a record does not enter the calls that the recorded walk made, so their nesting does not count toward the nesting limit, as for a call answered from the memo: whether a parse that comes close to the limit succeeds can depend on records.
The walks of run sites nest: the expression of a site can call rules that walk sites of their own, and the walks in progress are a stack. Records never change the result of a parse, and they last for one parse, as those of skip runs do. The Run Sites proof shows that a reused record gives what the rest of the walk would, and bounds the evaluations of a site's element. In a parse of an incremental document outside a lookahead, a run site that the document can resume is resumed as before.
Parsers generated as Go or TypeScript source keep the records of run sites as this section describes, with the same threshold for turning a site hot, the same keys and the same charges for looking up and storing records, taking a record over and moving and copying the elements of lists. A generated Document resumes no run: each walk of a run site in its parse walks as in a parse of the text alone, with the input it examines tracked as for a memoized call. A generated stream drops the records of the positions before the input it commits, as for skip-run sites.
Scan Sites
A repetition of one character, as a run of blanks, is walked again by every
failed alternative that leads back to its start, and its walk keeps no record
because a run site does not repeat a single character. A scan site is a
repetition without an upper bound whose expression is a character class or any
character, in a rule that calls no rule, unless it is a site of a
skip run or a #stream repetition. The rule may be called from any
number of places, and the repetition may stand under a capture, a label, an
action or an attribute: an iteration tests one character and nothing else, so
the walk from a start ends at a position, matches a number of characters,
builds elements and examines a range of input that depend on the start and the
input alone, whatever the rule does with them. A capture or an action reads only
the list that the walk gives, and a predicate, lookahead or call around the
repetition is evaluated as without records.
A rule that matches input, calls no rule and is a pure scan rule has, in addition, all of the following:
- it is called from two places in the grammar at least;
- it has no attribute but
@start, no type and no action; - its expression is made of literals, character classes, any character,
sequences, alternatives, groups, optionals, repetitions and discards: no
capture, predicate, lookahead, assertion, variable,
#recoveror other attribute.
Every repetition of a pure scan rule that is not a scan site is made restartable, so that it is a run site wherever the conditions of Run Sites otherwise hold. The result of a pure scan rule and the input range it examines depend on the position and the input alone, so its records need no environment.
A walk of a scan site charges and examines as an ordinary repetition for its
first 16 characters, the constant T (which is not the hot span of run sites:
a site turns hot after walks of T characters that overlap, as a run site does
after its own hot span). If the site is hot, the walk that has matched T
characters looks for the record of its start. A scan site keeps at most one
record for a walk, at the start of the walk, and none for the positions inside
it. A walk that builds a value and one that does not are recorded apart.
A record holds what a later walk from its start cannot obtain without walking again:
- the position where the walk ended;
- the number of characters it matched;
- for a walk that builds a value, the elements;
- the range of input the walk examined, which runs from the start to the character whose test ended the walk, or further when a test of an earlier character examined units after it, as the test of an invalid byte of a bytes-unit input can. A parser whose test of a character examines no unit after that character need not store it, since the walk that takes the record makes the last test again and that test reaches furthest.
A walk that finds a record moves to the recorded end, takes the number of characters and the elements from the record, and examines the recorded range; the test of the next character fails there as it did when the walk was recorded, and gives the same expectation. Otherwise the walk goes on, and when it ends it makes the record. A record holds no expectation and no failure: the only ones a walk produces are those of that last test, which every walk makes. The lookup costs one step, the slot of a record that it finds one more, the record that a walk makes one, and the skipped characters nothing. A site has one table of records for the walks inside lookaheads and the walks outside them: a lookahead silences only the expectations, which the walk does not put in the record, so both make the same record. (Whether a site is hot is kept apart for the two.) A walk records only if the input it examined is available: the parse has all of its input, or the examined range lies in the part of a stream that has been read. The input is filled up to the character that a walk examines, so the range always lies in the part that has been read unless the input has ended, and the test is a safeguard only. A stream drops the records of the starts before the input it commits.
The elements of a record are shared with the lists of the walks that take them. They are final, as those of run sites are. A walk whose number of characters falls short of the repetition's minimum fails as it would without records.
A scan site that a document resumes is resumed as before: a repetition that is resumed neither looks up nor makes records. That affects only cost and reuse, since every record is exact (see the proof). The records of scan sites last for one parse. A parse with missing-token insertion keeps no records of scan sites.
A parse with scan sites gives the result of a parse without them, with the same
expectations and examined ranges. The steps a parse charges exceed those of a
parse without scan sites by at most two steps for each walk that reached
T characters. A walk that starts at another position than a recorded start
inside the same run does not reuse the record, and costs its own length.
Parsers generated as Go or TypeScript source keep the records of scan sites as
this section describes, with the same T and the same charges; they keep no
records of run sites.
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.
| Class | Cost | Example grammar | Input |
|---|---|---|---|
| Linear | At most proportional to n | main = (A / "a")* $$; A = "a" "c" |
a repeated n times |
| Linear given an environment bound | Proportional to n times the number of combinations of variable values that occur at one position and the size of the strings they hold | A rule that reads indent, bound from the length of a captured run of spaces |
Lines of increasing indentation |
| Polynomial of degree k | Proportional to n^k on its worst inputs | main = (A / "a")* $$; A = "a"* "c" (k = 2) |
a repeated n times |
| Exponential | Can double when n grows by a constant | var v string; R = "(" {v := v + "0"} R ")" "y" / "(" {v := v + "1"} R ")" "z" / "n" {len(v) >= 0} |
( n times, n, then )z n times |
The following grammars have the class shown on the inputs shown.
| Grammar | Input | Class | Cause |
|---|---|---|---|
main = (E "q" / "x")* $$; E = "x" E / "x" |
x n times |
Linear | The result of E at a position is built from its memoized result at the next |
main = (E "q" / "x")* $$; E = E "x" / "x" |
x n times |
Degree 2 | E grows to the end of the input at every position, and "q" then fails |
main = (E "q" / "x")* $$ with E an Operators Rule with the operand "x" and the infix operator "" at one left-associative level |
x n times |
Degree 2 | As above, for the operators that E applies |
main = ("a" !Rest)* "a"* $$; Rest = "a"* "c" |
a n times |
Degree 2 | The lookahead scans to the end of the input at every position |
main = A* $$; A = "a" &(x:W) => text($x) + "!"; W = "a" W / "" |
a n times |
Degree 2 | The lookahead is linear, since W is memoized, but each iteration copies the rest of the input, which the capture in the lookahead holds |
main = A* $$; A = "a" y:L => text($y) + "!"; L = &(x:W) => $x; W = "a" W / "" |
a n times |
Degree 2 | As above: L consumes nothing, but its value is the capture in its lookahead |
main = (X / "a")* $$; X = (Y #recover(skip=[a]+)) "c"; Y = "b" |
a n times |
Linear | The skip consumes the rest of the input, "c" then fails, and the recovery is abandoned, but [a]+ is a skip run: the walk from each later position takes the rest of the walk from its record |
main = (X / "a")* $$; X = (Y #recover(skip=S)) "c"; Y = "b"; S = [a]+ |
a n times |
Degree 2 | As above, but the repetition is in a rule that the skip calls, so it is not a skip run, and each skip walks to the end of the input again |
main = (A / "a")* $$; A = (B / "a")* "c"; B = "a"* "d" |
a n times |
Degree 3 | A repetition that can restart inside another one that can restart |
main = R* $$; R = (R [ab] S . . .)*; S = ([a]* "ab"+ " "*)? |
a n times |
Degree 3 | Each step of the growth of R runs the repetition, and each iteration of it restarts the scan in S |
main = S $$; S = &R S "q" / "y"; R = R "q" / S |
y, then q n times |
Degree 2 | In each step of the growth of S, the lookahead grows R from the growing result of S over the rest of the input, and drops it |
main = S $$; S = &R S "q" / "y"; R = R ("q" / "r") / S "t" / "y" |
y, then q n times |
Linear | R grows from the growing result of S only after a "t", where S cannot grow; its growth from "y" is the same in every step and is reused |
main = C $$; A = C "+" / "n"; C = "(" C ")" "y" / "(" C ")" "z" / A |
( n times, n, )z n times |
Linear | A and C form a left-recursion cycle grown at A. The result of C at a position outside the growth of A there is memoized, so the two calls of C at the next position share it |
var v string; R = "(" {v := v + "0"} R ")" "y" / "(" {v := v + "1"} R ")" "z" / "n" {len(v) >= 0} |
As above | Exponential | The two calls of R at a position see different values of v, so neither reuses the other's result |
main = xs:"x"* => len(foldl("a", $xs, (acc, x) => acc + acc)) |
x n times |
Linear evaluations, exponential value size | The accumulator doubles for each element |
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
grammar with A and C as linear, as the table does, and the two grammars with
S and R as unknown, not linear or of degree 2: their 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 action expressions.
-
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, converting a value to a string, building a list with
list,concat,maporfilter, taking the length of a string value withlen, 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. Solistcopies one element for each argument, which the grammar bounds;concat,mapandfiltercopy the elements of the lists they read, and the list of a repetition has one element for each iteration;lenof 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, whilelenof 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. Taking the text of a node is not a copying operation, since it costs a constant (see Cost); its result has the size of the range, which counts where another operation copies it. -
The size degree of a value is the degree, in the size n of the input, of the bound on its size that the classifier knows, where the size of a list is one more than its number of elements plus the sizes of its elements, and a node has the size of its text or of the values of the captures in it, whichever is larger. A value is own when its size is at most a constant times one more than the input that its match consumes, so that the own values of distinct matches, such as the elements of a repetition, add up to at most a constant times n. The value of a match is own when no capture in a positive lookahead, which stays in effect over input that the match does not consume, is part of it, and every rule and action in it builds an own value. An action builds an own value from literals, ints, Booleans and own captures that are not in a positive lookahead, by
+,text,list,concat,filter, constructors, members and elements, and bymapand folds over own lists whose lambdas read nothing from outside them that is not bounded by a constant and read the first parameter of a fold at most once, when it reads a capture that holds a call on a recursion with its rule at most once, and as the list of a lambda only when it is a capture of a repetition, whose elements are distinct matches, and that lambda and every lambda in it read each member of each of their other parameters at most once, where distinct members of an element, such asx.$aandx.$b, are disjoint parts of its match; the value of a variable is not own. An own value has size degree 1. A capture or a call has the size degree of its value, the list of a repetition one more than its elements unless they are own, and a value built by an action the degree that the forms of condition 4 give it from the size degrees of what it reads. The values of the rules of a recursion that are not own have one more than the degree of what one level of the recursion adds, when each of them holds the value of each call on the recursion at most once: as a capture not made in a positive lookahead that is read once, outside lambdas or as the list of such a lambda over a repetition. Such a value is a tree whose nodes are distinct matches, at most a constant times n of them. Otherwise their size degree is not known. -
A value holds another when it is that value, passes it on, or builds a string or a list from it: by
+,text,listorconcatfrom their operands, byfilterfrom its list, bymapfrom the values of its lambda, and byfoldlorfoldrfrom the initial value and the values of the lambda, but not from the list that the fold visits. A member of a node holds what the capture that it names holds. A read of a variable holds what the values that the bindings which can reach it bind hold: the bindings of the variable in the body of the rule that reads it that can be evaluated before it, a later one in a repetition included, and those in the rules that can call that rule, directly or indirectly. A comparison, an arithmetic operation,len, a predicate and a binding hold none of what they read. The value of a rule is the value of its action, of the actions of an Operators Rule, or, in a rule without an action, of an inline action that is its expression or an alternative of it, through groups. A capture holds the value of what it captures, through choices, options and groups; the node of a sequence holds only the input that it matches, and so does its text, not the values of the calls in it. The value of a call on a recursion with a rule feeds back into the rule when it holds the value of the rule, directly or through the values of the rules that it holds; the value of a call of the rule itself does. -
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: while some cycle of left calls passes through no leader, the rule declared first among all the rules on such cycles becomes a leader, so a cycle can have several. Given the graph of left calls, the leaders depend on declaration order only. 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, which a call inside a growth at its position does only from an entry that records every leader whose growth is in its context, or a result kept in a context of the same growths (see Evaluations of Rules), and its left calls reach a leader, which grows there. A call that is not a left call is outside every growth of its cycle at its position: such a growth would be evaluating the caller, and every rule that it evaluates on the way from the growing leader to the call, at that position, so all of them would be on the cycle and the call would be a left call. So a call of a rule of the cycle other than a leader that is not a left call is memoized at the call unless the rule is not memoized for another reason, as one called from one place is not. The growth that such a call starts at its position ends, after its last step, in the body of the rule that the call evaluates, after the left call of the leader that grew, and the parser continues from there and then after the call. 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
#recoverthat is not a reused skip, the growth of a left-recursion cycle at every call of a rule of the cycle other than a left call and at every call of a leader in the body of another rule, 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 secondEinE = 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. A call of a leaderRin the body of another rule starts a growth ofRwherever that body is evaluated whileRdoes not grow at the position: where a rule that is not a leader is called and no growth of the cycle is in progress, and in a step of another leader. A unit around such a call can throw away what the growth consumed, asR "z"does inS = R "z" / "a"withR = R [ab] / S "b"onabab..., and a call ofSat each lateragrowsRagain over the rest of the input. 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 bounded scan is a repetition without an upper bound whose iterations at any one position number a constant, however the units around it fail. It costs a constant times the input in all, wherever it is evaluated, so the conditions do not check it: in the conditions and the action expressions below, and in the classes of Classification, a scanning source is one that is not a bounded scan, and the cost of a bounded scan is left out of what a action expression says is bounded or repeated. A bounded scan needs two bounds, and neither implies the other.
The alphabet of a repetition is the set of characters that an evaluation of its expression can consume, through its calls and outside its lookaheads. The first bound is the run bound or the region bound. The run bound is on its run: at most 32 characters of the alphabet stand directly before any position where the repetition is evaluated and the next character is in the alphabet. A repetition that reaches a position has consumed only characters of its alphabet since it started, so it can have started only in the first positions of the longest stretch of the alphabet that ends there. The classifier follows the length of the run forward through the grammar from 0 at the start of the input. A character outside the alphabet ends the run, one in the alphabet extends it, and one that can be either extends it or ends it. The run is also empty where the next character is known to be outside the alphabet: after a greedy repetition of an expression that surely consumes every character of the alphabet, after a negative lookahead of such an expression, after a positive lookahead that cannot match nothing and whose first characters are outside the alphabet, and at the end of the input. It takes every path that an Operators Rule, a
#recoveror a#missingallows, and a repetition or an Operators Rule whose body extends the run has no bound.An expression surely consumes a character when every evaluation of it with that character next succeeds and consumes input, whatever else the input holds. The classifier knows this of a terminal of one character, of a repetition with a minimum of 1 of an expression that surely consumes it, and of a choice when an alternative surely consumes it and no alternative before that one can match nothing or has a cut that commits the choice, a cut in the skip of a
#recoverincluded: an alternative that fails after such a cut fails the whole choice, so the alternatives after it are not tried. It knows it of a sequence when one part surely consumes it, the parts after that one always succeed, and the parts before it are options, repetitions with a minimum of 0 and negative lookaheads of expressions that cannot match nothing, whose first characters do not hold it and whose options and repetitions have no such cut. And it knows it of a call of a rule whose body surely consumes it, when the rule is not on a left-recursion cycle, reads no variable and takes no level: a call on a cycle can read the failing seed of a growth, however its body would match.The region bound is for the body
X*of a trivia rule (defined below under units), whose alphabet often holds every character, as inws = [ ]* (c [ ]*)*withc = "/*" [^*]* "*/": its run has no bound, yet its evaluations that reach a position start at that position or at one other. The classifier chooses a set of region rules, and the body of a trivia rule among them has the region bound. The candidates are the trivia rules, other than the start rule, whose body has no run bound, and a rule that holds a crossing of one that is not guarded, such as a string whose body holds blanks, is tried once as a further region rule. A rule that breaks one of these conditions is dropped, and the others are checked again, since the terminals of a dropped rule are then outside the regions:- Fixed ends. Neither the rule nor a rule that it reaches reads or binds a
variable, has a predicate, an action, a call of a level, an attributed
expression, a
#recover, a stream or an Operators Rule, or is on a left-recursion cycle. Whether one of them matches at a position, and where it ends, then depends on that position and the input alone. - No nesting. The body of a region rule reaches no region rule, and no rule that it reaches is reached from the start rule other than through a region rule. An expression is outside the regions when it is in a rule that the start rule reaches without passing a region rule.
- Disjoint openers. The openers of a region rule are the characters that can begin a match of its body. Two region rules have no opener in common: of two that share one, a further region rule is dropped when the other is a trivia rule, and both are dropped otherwise.
- Guarded crossings. A crossing of a region rule
Ris a terminal outside the regions and outside checks that can consume an opener ofR. A check is a negative lookahead whose expression is made of literals, character classes, any character, sequences, alternatives, groups, optionals and repetitions, with no call. A crossing is guarded when it can consume an opener only as its first character, andRis a trivia rule that is settled where the crossing starts, or no character can follow the text of the crossing at the start of a match of the body ofR, or the next check of the crossing surely consumes every character that can.
The classifier finds what can follow a text in a match of a body by reading lookaheads as matching nothing, each alternative as possible and each repetition as any number of iterations, and a call of a rule as each match of its body. A trivia rule
Ris settled where every path through the rules outside the regions reaches the place only after a call ofRwith nothing since that consumes input: a terminal consumes input; a call ofRsettlesRalone; a call of another rule outside the regions ends with what the end of its body has settled; a rule starts with what is settled at all its calls, and the start rule with nothing; a lookahead, a predicate, an anchor and a cut keep what is settled; an alternative, an option or a repetition ends with what every way through it settles; and a#recover, an attributed expression, a stream and an Operators Rule settle nothing. The next check of a terminal is the check that is evaluated as soon as the terminal ends: the element after it in a sequence when that element is a check, and, when the terminal is the last element of a sequence or the expression of a group, capture, discard, atomic group, inline action, alternative or option, the next check of that sequence or expression. A repetition, a lookahead and the body of a rule pass on no next check.The second bound is on its evaluations: the repetition stands at a counted place. An expression stands at a counted place when it is in the body of a counted rule, outside the skip, the operands and the operator parts of Operators Rules, only rigid expressions come before it in that body, and every repetition that encloses it there is rigid. A rule is counted when it is memoized and not on a left-recursion cycle, or when it is not memoized, not recursive and not on a left-recursion cycle, and every call of it stands at a counted place. An expression is rigid when a constant bounds the positions from which an evaluation of it can end at a given position: a terminal, a lookahead, a sequence, choice or option of rigid expressions, a repetition of a rigid expression with an upper bound, a repetition without an upper bound that has the run bound or the region bound, and a call of a rule that is not recursive and whose body is rigid. A
#recover, an attributed expression, an Operators Rule and a stream are not rigid.For example, in
main = (n ws)* $$,n = double / int,double = [0-9]+ "." [0-9]+,int = [0-9]+,ws = [ ]*, each[0-9]+is a bounded scan, sointreading again whatdoubleread costs one more pass. Memoization alone gives no such bound: it counts the evaluations at one position, and a run has many positions.[0-9]+in(t "y" / t "z" / .)*witht = d "x",d = [0-9]+is memoized and quadratic, since.extends the run and starts it at every digit. Nor does a bound on the run suffice:sp = [ ]*ine = "a" e (sp "!")? / "b"is evaluated once for each level of the recursion at the end of the same nest, which is quadratic onan times,band n spaces.The classifier decides both bounds, as it does the conditions, on the cost view of the rule bodies, a rewriting that keeps what they match and keeps their cost within a constant factor, apart from the values that actions build from a value that the view reshapes (Cost View; those values, and the run-time errors of the actions that build them, are step 7 of the open steps of the linear cost proof), with the memoized rules and the left-recursion cycles of the grammar as written.
- Fixed ends. Neither the rule nor a rule that it reaches reads or binds a
variable, has a predicate, an action, a call of a level, an attributed
expression, a
-
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 eachoperanditem 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 that can evaluate a left call, directly or through calls of rules of the cycle, before it examines the input, such as the alternative
E "+" TinE = E "+" T / T. What comes before the left call on such a path examines no input there: a predicate, as in the alternative{ok} E "!", or a call of a rule off the cycle that can match without examining the input, asZinZ E "!"withZ = "". A unit that examines the input before its left call on every path, such as("y")? E S "q"orZ E "!"withZ = "z"?, is not a growing unit. A unit that can examine the input before its left call on some paths and not on others, such as({ok} "z")? E "!", is checked as both, as a growing unit and as an alternative that is not growing. A unit that follows something that can match nothing can be reached in both ways, such as the alternativeEinE = "y"? (E / "z") "q" / "x": without the"y"it is a growing unit, and after the"y"its call is at a new position, where it reads no seed. The same holds when the part that can match nothing is before a call of the unit's rule, in the body of the rule that calls it, as forfinr = "y"? f "q" / "x"; f = r / "z", or before a call of a rule that reaches it through left calls. Such a unit is checked as both, as a growing unit and as an alternative that is not growing. 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, and the unit fails with it when it reaches the leader only through expressions that fail when it fails and through choices whose later alternatives cannot succeed without their own left call, in its body and in the rules of the cycle on the way, and not through an option, a repetition, a negative lookahead or the base of a#recover, which go on after the call fails, asaddinexpr = add / term; add = expr "+" term. Otherwise, as throughFinE = F "+" X / Y; F = E / Mor through the group inE = (E "z" / M) "+" X / Y, the unit can go on at its start after a path through its left call fails, in the first step and in every later one, and matchMand continue after it. Such a unit is also checked as an alternative that is not growing, on the paths that go on at its start in this way, from there, against the later alternatives of its choice. A body of a leader is evaluated only in the steps of its growth, and in the first step its own left calls read the failed seed, so for a unit of a leader this check follows only the paths that examine the input before a left call of that leader, from there. For a unit of a leader that contains a scanning source, those paths must also be committing against the later alternatives at their own start: no later alternative can begin with a character with which one of the paths can begin, unless the words of the paths exclude it. Here no shared call or literal is removed first, and a path counts whether or not it contains a scanning source. A path that can match without consuming input matches at any character, so it begins with every character, whatever its lookaheads examine: inE = ((E [x]* / "") !";" / "x" F) "x"; F = E ","the path"" !";"matches at anx, which"x" Fcan then consume, though the lookahead examines only;. In a later step, the unit can fail after it read the seed, and the step goes on to the later alternatives at the position where the rule grows; when one of the paths matched there in the first step, the first step did not evaluate them. A later alternative that consumed the character there would evaluate, at the positions after it, what no step evaluated before, as"x" Fdoes inE = (E [x]* / "") "x" / "x" F; F = E ";": onxn+1 times and;n times, each such step starts a growth ofEat the next position, whose own later step scans the rest of thexagain, so the cost grows as n^2, although the path"x"that goes on at the start contains no scanning source and shares its literal with the later alternative. A unit of another rule of the cycle whose paths can go on at its start in this way is checked as an alternative that is not growing on all its paths, those through its left calls included, and not only on the paths that go on at its start: in a later step of the growth its left call reads the seed, the unit can fail after it, and the later alternatives of its choice then run at the position where the rule grows. Moving the unit of the example above into such a rule keeps the cost n^2, as inE = F; F = (E [x]* / "") "x" / "x" H; H = E ";". A unit of another rule of the cycle is checked as an alternative that is not growing also when a call that is not a left call, or one after something that can match nothing, evaluates its rule, directly or through left calls of rules of the cycle other than leaders: that call evaluates the unit once more, outside the steps, where the leader that its left call reaches grows and gives its final result. In a cycle with more than one leader, a path of a unit of another rule of the cycle through a left call of a leader also goes on at its start, since the growth that evaluates the unit can be one of another leader, where that call starts a growth of its own instead of reading the seed, so the unit is then checked as an alternative that is not growing on all its paths. -
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: a call of a leader of
the cycle that is not a left call, followed by what follows it, and a call
of another rule of the cycle that is not a left call, followed by what
follows the left calls of leaders that its body reaches through left calls
of rules of the cycle and then by what follows the call. Such a left call
of a leader starts the growth when that call evaluates it, and reads the
seed only in the steps of a growth, so at the end of the body of a leader
what follows the growth continues after it too. What follows a call
that starts the growth continues at the end of a rule body through every
call of the rule, the reads of the seed included: when that call lies in
the body of a leader of the cycle, as
"(" eine = e R "x" / "(" e / ".", the end of that body is followed by the next step of the leader's own growth, which reads its seed there. A later growing unit that succeeds ends the step with a longer result, which the next step reads as the seed, so at the end of a rule body it continues through every call of the rule, the reads of the seed included: as inA = A S [^!]* "!" / A S / "n", the next step can scan again, from the end of the new seed, the input that the unit examined. 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, at the start of the paths that go on there for a unit of a leader, 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
#cutin 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, followed by what follows the#recover; - for a unit of an Operators Rule, the other operator parts and
operanditems that the rule can try at the same position, each followed by what the rule tries after it (the right operand of an infix or prefix operator part, then the operator parts that the rule tries after an operand, then what follows the Operators Rule expression), and what follows the Operators Rule expression. A lateroperanditem that succeeds through the memo answer of a call that the failed one made ends where that call ended, so what follows it there is part of the continuation, as for the later alternatives of a choice. The Operators Rule nests when it has a prefix operator part or a right-associative infix one, whose right operand applies operators of its own level, or a call from the rule that nests at one end (below), such as the call ofxin an operand"(" x?ofx, which parses the rule again at the end of an operand or an operator part. An inner level can then end where every enclosing operator part or operand ends, and each enclosing level tries the operator parts after an operand again there: for an operator part after an operand, those operator parts are a continuation too, unless every infix operator part that the right operand of a prefix operator part admits is admitted by the right operand of every infix and prefix operator part, and theskipand every operator part after an operand evaluate a scanning source only inside calls that are memoized at the call and read no variable or calls of scan-only rules (below). The enclosing levels then repeat a constant cost at each level, besides the walks that record the scan sites of those rules, since they do not parse the right operand of a refused part again (Expressions That Repeat Cost). An Operators Rule without an infix or a postfix operator part tries nothing after an operand or after the application of a prefix operator and evaluates noskipthere, so a chain of its prefix operators does not evaluate theskipagain at each level.
- 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: a call of a leader of
the cycle that is not a left call, followed by what follows it, and a call
of another rule of the cycle that is not a left call, followed by what
follows the left calls of leaders that its body reaches through left calls
of rules of the cycle and then by what follows the call. Such a left call
of a leader starts the growth when that call evaluates it, and reads the
seed only in the steps of a growth, so at the end of the body of a leader
what follows the growth continues after it too. What follows a call
that starts the growth continues at the end of a rule body through every
call of the rule, the reads of the seed included: when that call lies in
the body of a leader of the cycle, as
-
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.
-
An expression can match nothing when its form allows it, whether or not an evaluation of it ever succeeds without consuming input. This holds of
"",_, a lookahead, a predicate, an option, a cut, an anchor, a literal marked#missing, a repetition with a minimum of 0, or of 1 and an expression that can match nothing, a sequence whose parts all can, a choice with an alternative that can, an Operators Rule with anoperanditem that can, a call of a rule whose body can, and a group, a capture, a#recoveror any other wrapper whose expression can. A character class,., a literal that is not empty and not marked#missing, a repetition with a minimum of 2 or more, and a_|_of the normal view cannot: the first iteration that consumes no input ends a repetition and counts once (Repetition), so("q" / "") #repeat(2,)needs input. The rules whose calls can match nothing are the least set closed under these clauses, so a call ofQ = Q "q" / "q"cannot. So{ false },!""and("a" / "") &"a"can match nothing, although no evaluation of any of them succeeds without consuming input. -
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 at each of the two calls or calls no rule, itself included. Only the shared call must read no variable: the calls whose bodies the unit and the continuation evaluate on the way to it may be calls of rules that read variables, since what those bodies evaluate before it examines no input and the result of the shared call does not depend on the values of the variables. In
main = A "!" / B ws "y", withA = Y { v == 1 } ws "x",B = Y { v == 2 } ws "x"andY = "a"+, the two alternatives share the call ofY, and after it the calls ofwsand the literal"x", althoughAandBreadv. A continuation that goes on through the end of a rule body goes on through every call of the rule, so it shares a call only when, through each of them, it evaluates the call before anything else that examines the input or examines nothing more there, as at the end of the expression of a lookahead or of the parse and at a check for the end of the input; a lookahead or a dead symbol (below) there examines the input, and a predicate ({ ... }) there examines nothing and is passed over. Inmain = Y "b" / B, withB = Y ws "x"andY = "a"+ (ws ";")?, the option inYshares no call with what follows it, which is"b"through one call ofYandws "x"through the other. A unit that decides every one of its continuations (below) is compared with each of those ways on its own, and can be committing without a shared call. A rule memoized in every parse is memoized at each of its calls, and a rule of a left-recursion cycle other than a leader at a call that is not a left call. A call of a rule of a left-recursion cycle is shared only when the two calls lie in the same growths of that cycle: neither is reached through a call of a rule of the cycle that the unit or the continuation starts with, nor after leaving the body of a rule of the cycle. Inside the expression of a lookahead, a left call of a leader that reads the seed of its growth at the position is not shared with what follows the lookahead: it is compared as a call that is not shared. The call has the same result in both: the memo answers it the second time, or, for a leader in a context of growths, it grows again or reuses a memoized result or one kept in its context, or the rule repeats only its own scan, so the continuation pays for it at most what the unit paid. In the same way the two share a literal that is not empty when every path of both that examines the input begins with it, and the literal has the same case sensitivity in both: both consume it or both fail where they begin, so the calls after it are made at the same position in both. Below, a shared literal counts among the shared calls. Calls of one rule with different level restrictions, such aseandlevel(e, hi), are different calls with different results. An Operators Rule evaluates itsskipbefore anything else at its start, before an operand or a prefix operator part, and continues at the same position when theskipdoes not match, so the call that itsskipevaluates 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#recoverand#missing, which change what the parser does when the body fails. Because the parser continues when theskipdoes not match, askipthat cannot match nothing 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 call of a rule that is not memoized at the call and contains a scanning source is not shared either when the continuation reaches it after the end of a rule body, in what follows a call that nests at one end, or after an operand of an Operators Rule that nests, unless the rule is a scan-only rule: it reads no variable, calls no rule, contains no#recover, Operators Rule or#stream, and each of its scanning sources is a scan site. Evaluating such a call again at a position costs at most a constant once the walks of its sites from there are recorded, which takes at most three walks from each position in each mode, inside or outside lookaheads and with or without a value: two that turn the site hot and one that records. A call nests at one end when the evaluations of its caller can nest through it without a bound, each in the call of the one around it, with all of those calls ending where the innermost one ends. A calltof a ruleYfrom a ruleZof its recursion does so whenYis in the smallest set of rules of the recursion that containsZwhen what followstcan match nothing, each rule that calls a rule of the set at a call that what can match nothing follows, and each rule with a unit that condition 2 below checks and a continuation that share calls, as below or as the comparison of a decided unit passes them alike, one of which, in the unit, istitself or a call in the body thattevaluates, which the unit reaches by looking throught, after which the continuation can reach the end of the rule body without consuming input. When the continuation has left that body before the shared calls, through its end and a call of the rule, the rule in the set is the one in whose body the continuation is at the shared calls, whose evaluation contains that of the unit, if the continuation can reach the end of that body. A step of a growth after the first that condition 2 checks is such a unit, with the first characters and the continuations that condition 2 gives it; its continuations follow the calls that start the growth, so they have always left the body of the leader, and the rule in the set is the one in whose body the continuation is at the shared calls. The last case is a restart: ine = "(" (e R "x" / e) / "."withR = [ ]*, the alternativee R "x"fails after its call ofeended at a position, and the alternativeeendseat the same position through the memo answer of the same call, so every level of the nesting ends there and scans the spaces inRagain. Ine = "(" f e / "."withf = (e R "x")?, the option fails in the same way,fends, and the call ofeafterfendseat that position:eis in the set. The other units add nothing: a unit that can fail only before its scanning sources have examined input has evaluated none when it fails, so neithertnor a call that it looked through contains one, and since each rule of the recursion oftcalls the rule oft, no rule of the recursion contains one either, and a nesting throughtrepeats no scan. A left call from a rule of a left-recursion cycle to a rule of the same cycle nests at one end too when a call of a rule of that cycle does: each evaluation of a leader of the cycle that ends at a position grows there, and the next step of its growth evaluates what follows the left calls there again, after its seed, asRine = e R "x" / "(" e / ".". Each of the nested evaluations that ends at the position then evaluates the call there again: ine = "(" e? (ws ")")?withws = [ ]*, the option at each level fails afterwsand the option of the level around it evaluateswsagain over the same spaces, so the continuations together pay for the call once for each level. The same holds when the continuation reaches the call there after other calls or literals that the two share, aswsine = "(" e? ("x" ws ")")?, where each level matchesxagain before it scans the same spaces, and ine = "(" m e? (m ws ")")?withm = mx, which calls a rule and is therefore memoized, where each level matchesmagain, from the memo once its entry is stored, andwsscans the spaces again. -
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. At most sixteen are removed: when the two share more, what remains after sixteen is compared, and it begins with a call that both evaluate. The removal also stops at a shared call that the continuation evaluates again with a cost that nothing bounds, which then begins what remains of both. 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, apart from what bounded scans examine, 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 but a bounded one, whose iterations at each position are a constant however often it restarts. 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 literalwthat is not empty, optionally followed by a negative lookahead!Y, whereYis 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 withw, followed, when the word has!Y, by a character outsideYor 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!KwhereKis known to match, before it reaches the end ofw. Along a path, an expression that cannot examine the next character ofwand can match nothing is passed over, and one that cannot match nothing fails there; a literal, a character class or.consumes the characters ofwthat it matches, and a literal fails where it differs fromw;!KwhereKis known to fail is passed over.Kis 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,#atomicand 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 aKdoes not depend on how the parser reaches it. Its literals are tried in order against the rest ofw: a literal that differs from it fails, the first that matches decides, and one thatwends inside of leavesKunknown. The lookahead ofKis evaluated on the next character ofw, or, at the end ofw, it is known to succeed only when it has the same characters asY. Soident = !keyword [a-z]+, withkeyword = ("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 unit that is not a lookahead is also committing when it decides every one of its continuations; one that decides some of them and commits against the others in the ways above is not. A path of an expression is a sequence of symbols, each a call, a literal, a character class,.or a lookahead, and the paths of the expression are such that every evaluation of it, whether it succeeds or fails, passes the symbols of one path in order, each starting where the one before it ended, until it fails or has passed them all. So the paths cover the evaluations that fail as well as those that succeed:"a" W &"b" [a-z]* "c"never succeeds, since[a-z]*consumes thec, but its path is still those symbols, and an evaluation that fails at"c"has examined the input thatWand[a-z]*consumed. An expression that is not looked into, such as#recoveror an Operators Rule, ends the path without deciding anything. A_|_of the normal view, such as the one to which it reduces!"b" "b", is a dead symbol and ends the path too. A predicate ({ ... }) examines nothing and is passed over, even one that no evaluation passes, such as{ false }; it is not a dead symbol. Under the strict conditions (below), one with a copying operation that is a scanning source ends the path instead. The evaluations that fail at a dead symbol follow the paths that end there, so a unit that never succeeds has the paths of what it evaluates before it fails, and these must part like any other. The unit decides the continuation when every path of the unit, compared with every path of the continuation from their common start, passes symbols that both evaluate alike and then parts at a decisive symbol that at most one of them can pass, within three symbols: the symbols passed alike and the decisive one together. Two symbols are alike when they are calls of one rule that is not on a left-recursion cycle and reads no variable, or reads variables and is called with the same variables on both sides, equal literals, equal character classes or., or calls of one trivia rule (below). A literal that is a prefix of the other, literals that are equal up to case, overlapping character classes, and a literal and a class that contains its first character are passed by the characters that they have in common, each step counting as one symbol; a call that is not alike stands for the paths of the body of its rule, each of which must part. Every decision expands calls finitely: where the expansion of a call comes back to a call of the same rule, directly or through other calls, the comparison stops there and the unit decides nothing on that path. The decisive symbol is one on each side that cannot both match at the position: two symbols that are disjoint, which means that neither can match nothing and that no character is a first character of both, two literals of which neither is a prefix of the other, or two character classes with no character in common; a negative lookahead!Kon one side that the rest of the other side must match, in the form below, or a positive lookahead&Kon one side whose expression and the next symbol of the other side are disjoint, so that a lookahead&KwhoseKcan match nothing, such as&{ true },&{ false },&"",&(!"")or&(("a" / "") &"a"), decides nothing (a nested lookahead such as&(&"q")is first reduced to&"q"by the normal view); a dead symbol on one side; or, in the continuation, the end of the parse, which costs a constant. A symbol at which neither side can go on is not decisive: the two do not part where each, before it consumes more input, reaches a dead symbol, a symbol that no input matches, a negative lookahead!Kthat the rest of its own path must match, or a positive lookahead&Kwhose expression and its own next symbol are disjoint. So a path of the unit never parts from its own copy, which the continuation reaches through a left call of the rule of the unit: in a growth that call reads the growing result instead of evaluating the copy, while each step of the growth evaluates the unit again. The rest of a side must matchKonly in this form. Through groups and through calls of rules that are not on a left-recursion cycle and make up the whole expression,Kis a choice, or a single alternative, and one of its alternatives,A, is a sequence of calls, literals, character classes and., through groups, captures, discarded expressions and#atomic. No alternative ofKbeforeAhas a cut that commits the choice, a cut in the skip of a#recoverincluded: an alternative that fails after such a cut failsKwithout tryingA. Every path of the rest of the other side passes the symbols ofAin order: a literal ofAby literals of the same case sensitivity that it begins with or that begin with it, a class ofAby a class that it contains or by a literal whose first character it contains,.by.or by a literal, and a call ofAby an alike call that is cheap (below). A call or a repetition of that side that does not pass the symbol ofAat hand stands for its paths, each of which must pass the rest ofA, and a lookahead of that side is passed over when it costs a constant. The check expands calls finitely, as every decision does: where the expansion comes back to a call of the same rule,!Kdecides nothing on that path. The rest of the other side then matches only whereAmatches. When!Kis on the side of the unit, which alone evaluates it,Kcontains no scanning source, and neither does a negative lookahead that a path of the unit passes before it parts; when!Kis on the side of the continuation, the alternatives ofKbeforeAcost a constant, as a lookahead that only the continuation evaluates does, and no call ofAthat the unit passes alike contains a scanning source: where the continuation reaches a copy of the unit through a left call, each step of the growth evaluates the unit again, and the scan of such a call would repeat in every step. So!("c" L "y"), withLa recursion of its own, decides nothing against"c" W "y"with another ruleW: no symbol of that side passes the call ofL. The strict conditions make what the continuation evaluates again bounded:- every symbol passed alike is cheap: evaluating it again where the unit evaluated it costs the continuation at most a constant or what the unit paid for it there. An expression without a scanning source is cheap, as is a call that the memo answers, a call of a rule that calls no rule, which repeats only its own scan, and a call of a rule whose body is cheap in all its parts, where the rule is not on a left-recursion cycle, the call has no level restriction, and a call of the same rule met again while that body is checked is not cheap. Nothing else is cheap. A call of a rule that reads variables is cheap only where both sides have the same variables, which holds until either side passes a predicate that binds a variable or the end of a rule body that binds. A call that the memo does not answer and that contains a scanning source is not cheap when the continuation reaches it after the end of a rule body, in what follows a call that nests at one end, or after an operand of an Operators Rule that nests, unless it calls a scan-only rule (which reads no variable);
- an option, choice or repetition that a path passes is looked into only when it has no scanning source of its own and all its parts are cheap; otherwise it ends the path. One whose parts are cheap only with the same variables is looked into only where both sides still have them. A lookahead is not looked into: one that the unit passes before it parts contains no scanning source, and one that only the continuation evaluates costs a constant (below);
- a lookahead that only the continuation evaluates, or an alternative of it before the one that the unit's match implies, costs a constant: it has no scanning source of its own, and each call in it is answered by the memo or reaches no scanning source;
- a predicate or a binding whose copying operation is a scanning source ends the path, as an unbounded repetition does, instead of being passed over, and so does an inline action with such a copy, after its expression: the copy can examine as much input as the path consumed before it, which the cheap symbols do not bound. An action at the end of a rule body, or an action of an Operators Rule, with such a copy ends the path where it leaves that body or an operand of the rule, and where a call of the rule stands for the paths of its body. The end of the parse after the start rule is the exception: the action of the start rule runs there once.
A trivia rule is a rule whose body is a greedy repetition
X*, atomic or not, whereXcannot match nothing, and that neither it nor a rule that it calls runs an action or contains#recover, an attributed expression, a stream, an Operators Rule or a call of a left-recursion cycle, whose body binds no variable that it reads and has no#cutof its own. A call of it always succeeds, and the position where it ends depends only on the position where it starts and the variables that it reads, so two calls at one position with the same variables end alike, and they are passed without counting toward the three symbols. A call that follows a call of the same rule across symbols that consume nothing, with no predicate that binds a variable between them when the rule reads variables, starts where the first one ended, whereXfails again, so it matches nothing and is dropped from the path. The dropped call costs a constant only whenXhas no scanning source, so it is not dropped otherwise.After a unit that its continuation decides is abandoned, the continuation evaluates again only cheap symbols before it parts. At the decisive symbol it does not consume the character at which the two part, fails within a cheap lookahead, or ends the parse, and a unit that ends after cheap symbols examined no more than the continuation evaluates again at their costs. Nothing then starts a scanning source again inside the input that the unit examined beyond the cheap symbols that both evaluate alike.
-
A path of a later alternative of an alternative of a rule of a left-recursion cycle enters the growth again when it reaches a left call of a leader of the cycle before it examines the input, directly or through left calls of other rules of the cycle, as the last alternative
adoes inc = "(" c ")" "y" / "(" c ")" "z" / awitha = c "+" / "n". The call of the leader examines nothing that the alternative examined: while a growth of the cycle is in progress at the position, it reads the growing result, and otherwise the memo answers it after the growth there has ended, or it starts that growth, once for each position. Each step of that growth evaluates the bodies of the cycle again at the position, the alternative included. The alternative is committing for such a path when all of the following hold: the alternative makes no left call of the cycle and evaluates its scanning sources only inside calls that are memoized at the call and read no variable; the bodies of the rules of the cycle evaluate in the same way every scanning source that they can evaluate before a left call of a leader that they always evaluate, at positions that are the same in each step; and what follows the call of the leader, through every call of a rule whose body it ends, up to the end of the parse, contains no scanning source. The steps after the first then find those calls in the memo, and what follows the call examines a bounded amount of the input. Otherwise the path is compared as any other.
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. The bound also needs the memo to store results as
Evaluations of Rules describes: of the evaluations of
a memoized rule, or of its twin, at a position outside every context of
growths, only the first may leave no result.
The reference implementation and the generated parsers store so in every
parse outside the contexts of growths, apart from the entries that a
Document keeps from earlier parses. The conformance tests TestMemoStorePolicy
(the engine's closure and bytecode backends, and streams),
TestMemoStorePolicyDocument (the engine's Documents),
TestGeneratedStorePolicy (generated Go, streams and Documents) and
TestGeneratedTSStorePolicy (generated TypeScript, Documents) hold the evaluations
of a rule to what a memo that stores every first call and one that defers each
leave, and each has a mutant of the memo that it must fail. A mode that leaves
other results out of the memo, such as one that evicts entries, gives no linear
bound by these conditions, and has to say so.
-
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. The binding can be at any depth of the expressions that keep the bindings made in them after they succeed, which are all expressions but a negative lookahead and a call, such as groups, options, choices, captures, discards, atomic expressions, attributed expressions and positive lookaheads, so that
&({v := v + v}) "y" rpasses the value of the binding to the callr. The call can be at any depth of its element, a negative lookahead included: a call sees the bindings made before it wherever it is evaluated, so inr = {v := v + v} "(" !(r "]") ")" / "a"each call ofrin the lookahead doubles the value again. Or the value can reach a later evaluation when the binding is part of the element of a repetition or of an Operators Rule, which applies its parts again at each operator, with no negative lookahead between the binding and the repetition or the operator part. A negative lookahead undoes its bindings only when it ends, so the iterations of a repetition inside it see one another's bindings, as in!(("x" {s := s + s})* {len(s) < 0}). 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; the value can still reach the caller through the value of the rule, which condition 4 follows through the reads of the variable. The variables with finite values are exempt from this condition: theboolvariables, theintvariables whose values form a finite set, the least set that holds the initial value and, for each of the variable's bindings, the values that the binding leaves bound from the values that can reach it, and the variables whose initial value and bindings are all constants, such as astringbound only to literals, each with at most 65536 values. The value set of aboolholds its initial value and the values that its bindings can bind: a constant binding adds its value, a binding that fails to evaluate adds none, and any other adds both, so aboolnever bound, or bound only to its initial value, counts 1. A variable bound only to constants holds at most one value for each distinct constant. The value sets are taken from the smallest up while the product of their sizes is at most 2^{32}; a variable whose set would bring the product past that has no finite values. Its bindings are then subject to the condition above: bindings that satisfy it, such as bindings to constants, make the cost linear given an environment bound, while a binding that reads the variable's own earlier value, as a counter{u := u + 1}before a recursive call, fails it. No value set depends on another variable, so a variable without finite values leaves the others as they are. A binding of anintvariable whose values the classifier evaluates reads only the variable itself,intandboolliterals, and operandslen($c)of a capturecwhose value has a length of at most 256 that the classifier can see: the text of an expression that matches a bounded number of characters, a list or tuple with a bounded number of elements, or the value of a rule whose action gives such a value. The tuple of a sequence has at most one element for each item, where a plain group of a sequence and a call of a splice rule whose body is a sequence splice their own elements into it, sox:("#" ("a" "b"))has 3, and so hasx:("#" _r)with_r = "a" "b", while a capture, an option, a choice, a repetition or a call of any other rule is at most one element. It combines them with+,-,*,/,%, comparisons,&&,||, unary-and!and parentheses. The binding is evaluated at every length of each operand up to its bound, at most 4096 combinations, and a value whose evaluation is an error, as a division by zero, is not bound; a value beyond 2^{53} in magnitude is not one that the classifier evaluates. A binding that reads anything else, or whose value it does not evaluate, binds the values within the bounds of its guard, and leaves the variable without finite values when the guard does not bound them.The guard of a binding
v := eis made of the tests that run next to it with only predicates between them, so that nothing between them reads the input or calls a rule. Its tests after are the predicates or block statements after the binding, up to the first element that is not a predicate or the next binding ofv, that read onlyvand literals, as in{v := e} {lo <= v && v <= hi}or{v := e; v <= hi}. A failed test fails the sequence that holds the binding, and backtracking undoes the binding, so a value that a test rejects reaches no call and no later binding; the binding leaves bound only the values on which every test after it can succeed. Its tests before are the predicates or block statements before the binding, back to the first element that is not a predicate or to a binding of any variable, as in{lo <= e && e <= hi} {v := e}: they evaluatee, written alike, with the same variables and captures as the binding, and every action expression of the action language is a function of those, so the binding binds only values on which the tests succeed. A predicate with attributes counts as a predicate when all of them are@attributes, such as@error, which do not change matching; a predicate under a pragma, such as#recover, does not, since a recovery can succeed after the test fails. Each test that is a comparison with<,<=,>,>=or==ofv, for a test after, or ofe, for a test before, with a constantintexpression on either side, or a conjunction with&&of such comparisons and other tests, bounds the value on one side or both. A side that no test bounds is bounded by the range ofe: a literal is its value,vranges over the values that reach the binding,lengives at least 0, and unary-, and binary+,-and*, combine the ranges of their operands. Sox:"#"+ {v := len($x)} {v < 10}binds the values 0 to 9, while{v := v + len($x)} r {v < 10}, with the callrbetween the binding and the test,({v := v + len($x)} / {v := 0}) {v < 10}, where the test is not next to the binding, and{v := v + len($x)} {v <= w}, which compares with a variable, bound nothing.The values that reach a binding are those of the set after the earlier elements of the sequences around the binding, from the outermost sequence that it is in through groups, options, choices, captures, discards and atomic expressions only, and after the earlier statements of its predicate block. A binding of the variable applies to the values as above; a predicate that reads only the variable and literals keeps the values on which it can succeed; a choice or an option joins the values of its paths;
@attributes change nothing; a negative lookahead keeps the values before it, since it undoes its bindings; a call keeps them, since bindings in a called rule are not visible to its caller; and any other element that binds the variable, as a repetition or a positive lookahead around a binding, can leave any value of the set. So in("0" {v := 64} / {v := 0}) {v := v + 2}the second binding reads only 64 and 0, and in{v < 3} {v := v + 1} rthe binding reads only values below 3, while a test after the callrfilters nothing that the binding reads. When every binding is a literal or binds a variable with finite values, a constant number of combinations of values occurs at a position, at most the product of the sizes of the value sets, which the class Linear reports as its bound on K (see Classification). When another binding reads a capture or a variable, the cost is linear given an environment bound. -
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. A unit that contains a scanning source and can evaluate a left call before it examines the input, and that is not an alternative of a choice, fails this condition, as the lookahead&EinE = &E "A" [a-z]* "?" / E [a-z] / "A"does. The checks of growing units are made for alternatives, and after such a lookahead succeeds, the unit around it goes on at its start, where it examines the input as an alternative that is not growing would, though no path through its left call failed. A step of a growth after the first is checked as a unit too. A step that fails is dropped, the growth ends with the seed, and the parser goes on at the end of the seed with what follows the calls that start the growth, which can examine again the input that the step examined there though no unit failed: inmain = (S / [ac-z])* $$withS = (S "a" / "b") TandT = "c" / "d" [a-z]* "!", onbcadrepeated, the step after the seedbcmatchesa, scans the rest of the input in the last alternative ofTand fails at its end, and the next growth, two characters on, scans it again. The step tails of a leader are what its body evaluates after a left call of the leader that reads the seed, made in the body or through left calls of other rules of the cycle: from the end of such a left call to the end of the body, through the ends of the bodies of the rules of the cycle on the way,"a" TinSabove. A step after the first is a unit that starts at the end of the seed, whose continuations are what follows the calls that start the growth, at the end of the seed, as for a growing unit. It is compared with them one step tail at a time, as each growing alternative is: after a read of the seed, the step examines the input from the end of the seed only in a step tail, from the end of that read, so the first characters and the shared calls are those of each step tail on its own. Ins = E R "?" $$withE = E R "!" / E "+" "x" / "x"andR = [ ]*, the tailR "!"shares the call ofRwith the continuationR "?", though the tail"+" "x"begins otherwise, and is committing, since!and?differ. It is checked when a step tail contains a scanning source and can fail after it, as a unit can, also where no unit holds both the source and what fails after it: inS,Tfollows the group that holds the growing unitS "a", and a left call can as well be in the last alternative of a choice. SoSabove fails the condition, sinceais a first character of both the step and[ac-z], and so doesS = F TwithF = S "a" / "b"; withT = "c" / "d" "!"or with"!"?at the end ofT, no step tail can fail after a scanning source, and withS ";"inmain, the step is committing. A step that succeeds with a result no longer than the seed is dropped as well, but it gives back the input that it examined beyond its result only through the units in it that are abandoned, which this condition checks in turn. A unit whose only scanning sources are bounded scans contains no scanning source in this sense: a restart repeats them, and their bound counts the repetition. -
Growth. No scanning source can be evaluated, outside the left calls of rules of the cycle, 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, memoized at the call, of a rule that is not on the cycle. Each step of the growth evaluates these bodies again at that position.
-
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 first parameter of the lambda of
foldlorfoldrover a list that is not bounded. A list is bounded when its number of elements is bounded by a constant of the grammar that the classifier can see: the value of a capture of an expression whose matches are bounded in length, or of a repetition with an upper bound, such asx:a #repeat(,2), through choices and options; alist(...)or a list literal; and a value built only from bounded lists and literals, byconcat,map,filteror a fold, whose list operands are not a variable, a lambda parameter or the value of a call on a recursion with the rule; the lambda may read them, somap($b, (y) => y)is bounded when$bis. 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$xdoes, is an element of it, as$x[0]is, or is built from it by+,text,concat,maporfilter, or by a fold over a bounded list whose initial value or lambda includes it. So the text of a capture of the recursion includes the text of the calls nested in it, which counts where the text is joined or compared, while a list of nodes of the recursion, as built bylist($x), has one element per node whatever the node contains;concat(list($x), $t)withtthe list of the rule's own recursion includes it. A read of a variable includes what the values that the bindings which can reach it bind include, as holds defines those bindings. A read sees a binding only while the evaluation of the rule that made the binding runs, so an operation that copies such a read is checked as an operation of the rule of each of those bindings as well: inr = ("(" c:r ")" {x := $c} => x + x) / ("a" => "a")the action copies the value of the call ofrtwice, as$c + $cwould, and the value ofrdoubles at each level. A value of a rule on a cycle of such values, and the value of an Operators Rule, are taken to include it. In the action of an operator part,$lhsand$rhsare the values of an operand or of an earlier application of a part, which the rule applies again at each operator, so they count as values of a call on a recursion with the Operators Rule:$lhs + $lhsdoubles the value at each operator, and$lhs + $rhscopies the left operand, which grows by an operand at each operator. In the whole-rule action,$valueis the value of a part, so it counts as a value of a call on a recursion where the value of a part holds one other than$lhsand$rhs, as$xdoes inoperand "(" x:e ")" => $x. 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. No copying operation copies a value that is not bounded by a constant and whose size can come from a capture made in a positive lookahead, directly or as a member, or through the values of the rules and captures that it reads, measured as above, so thatlist($x)has one element whatever$xholds, and whatever input those rules consume. Such a capture holds input that the match does not consume, so it can be as large at every position: inA = "a" &(x:W) => text($x) + "!"each iteration ofA*copies the rest of the input, and so it does inA = "a" y:L => text($y) + "!"withL = &(x:W) => $x, a rule that consumes nothing; the classification reports the class unknown for such a copy. A copying operation in the lambda ofmap,filter,foldlorfoldrover a list that is not bounded 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, and the elements that it copies add up, over all the evaluations of the lambda, to at most a constant times n. In each evaluation of the call they add up to the size of its list, and the call is evaluated once for each element of the lists of the lambdas around it that are not bounded, except that the elements of the innermost of them add up to at most the input when they are own and the list of the call reads only them; so the degree of the sum is the size degree of the list plus the size degrees of the numbers of elements of those lists, and it is not known when one of them is not. The lambda over a bounded list runs at most a constant number of times, so its copying operations are checked as copies outside it, in the lambdas around it, and the first parameter of a fold over it holds what the initial value and the value of the lambda hold, at most a constant multiple of their sizes, unless the fold can double it. The classifier bounds one step of a fold by its step matrix: it bounds the size, the size of the largest element and the number of elements of the value of the lambda each by a sum of action expressions, each a constant times one of the same three quantities of the first parameter, or times none, and times powers of n and of the size of the element of the step, where a value read from outside the fold counts as n to its size degree. The size of a list is one more than its number of elements plus the sizes of its elements. A list, a tuple or a struct adds the quantities of its items, and+andconcatadd those of their operands; an element taken by[]is at most the largest element, whatever its index; a member is at most the value it is taken from; afiltercounts as its whole list, since it can keep every element; amapholds, for each element of its list, the value of its lambda for that element, so a part of the lambda that does not depend on the element counts once for each element; a fold inside the lambda that does not read its own first parameter holds its initial value or the value of its lambda, and one that joins its own first parameter once byconcator+with values that do not read it holds its initial value and those values summed over the elements of its list. A part that multiplies two quantities of the first parameter, as the first parameter read inside a lambda over a list that grows with it, and an action expression whose value the classifier does not follow, such as a block or a fold of another form, count as many copies of what they read. The fold can double its first parameter when, in the graph of the three quantities with an edge for each action expression that reads one, a cycle has a coefficient above 1 or a factor of a size, or two cycles share a quantity, asacc + acc,list(acc[0] + acc[0]),map(acc, (e) => e + e),map($c, (z) => acc)andfoldl(list(), map(acc, (e) => list(e, e)), (s, l) => concat(s, l))do. Such a fold is checked as a fold over a list that is not bounded. Otherwise each quantity is bounded over all the steps by a polynomial in the size of the input: keeping one element twice, asfoldl(list(), acc, (s, l) => list(l, l))does, does not grow the first parameter; adding to every element, asmap(acc, (e) => e + "x")does, grows the size by the number of elements on each step; and adding a value read from outside, asacc + text($c)does, grows it by up to the size of that value on each step. The quantities start from those of the initial value, by their size degrees; the steps are the elements of the list, and the sizes of their elements add up to the size of the list, by the size degrees of the three quantities of the list. The classifier bounds the cost of one step by such action expressions as well, where an action expression may multiply quantities: a comparison of values that are not ints andlenof a string examine their operands, and a fold inside the lambda copies its own first parameter on each of its steps. A fold inside the lambda of a call over a list that is not bounded runs once for each element of that list, so the degree of its cost and of each copy of its first parameter gains the size degree of the number of elements of each such list around it, but not that of the innermost of them when its list reads only elements of that list and those are own captures of a repetition, distinct parts of the input whose sizes add up to at most the input. A fold over a list that is not bounded that reads a value whose size degree is not known fails this condition. A copying operation that copies the value of a variable, when that value includes no value of a call that this condition checks, is linear given an environment bound. -
Carried growth. No leader R grows, at the position where another leader S of its cycle grows, from a result that includes the growing result of S, where the step of S that calls R can drop the result of R and still grow, and the growth of R can go on over input with which the growth of S goes on. Each step of S reads another growing result, so no two steps share the growth of R, which covers again the input that later steps cover. The step can drop the result when the call is in a lookahead, an option, a repetition or the base of a
#recover, in an alternative followed by an alternative, the last one included, that can evaluate a left call before it consumes input, whether or not it examines the input first, asS "q"inS = R "z" / S "q"and"w"? S "q"inS = R "z" / "w"? S "q" / "y"can, or in a rule of the cycle that is not a leader. The growth of R can go on with the growth of S when what follows the left calls of S in the body of R, followed by what follows R, and what follows the reads of the growing results of the cycle outside the body of R can begin with the same character. Otherwise R grows past the result of S only where the growth of S stops. In a cycle with more than one leader, moreover, no#cutin a body of a rule of the cycle can be passed after a left call in the alternative, iteration or option that it commits, and no lookahead in such a body, nor theskipof an Operators Rule of the cycle, can make a left call. A leader can grow again in each step of another leader at its position, and the first step of that growth reads its own failed seed: a cut passed after a left call, or a lookahead that reads the growing result, can make a later step take an alternative that the first step did not reach. Askipcounts as a lookahead here, since the results computed in it are kept apart from those computed outside it as the results computed in a lookahead are (see Evaluations of Rules). InS = S "w" / R "z"withR = (R #cut "b" / S "y" / "c") / S "x", the cut keeps a later step ofRfrom ending with"c", so that it reachesS "x", and oncb...bz xz...xzeach step ofSgrowsRover thebcharacters again beforeRreads the growing result ofS.
The bound also needs the parse to keep records of the walks of its
repetitions, the records condition of the
Linear Cost proof. A recorded site is
a repetition without an upper bound, outside the skips whose walks are
reused, that is a run site or repeats a single
character, and is no #stream repetition; its walks are recorded unless a
Document resumes a run at them. For a constant c_R ≥ 1:
- (R1) a walk that takes a record leaves what the walk that evaluated its remaining iterations would leave: the same end, outcome, examined range, values, recovered errors and environment, so that the parse gives what it gives without records;
- (R2) the recorded walks of a site evaluate its element, in the whole parse and in both variants of its rule, at most c_R · (K_σ · n + W_σ) times, where W_σ is the number of its recorded walks, K_σ = 1 when the site is free of the environment, and otherwise K_σ is the largest number of distinct combinations of the values of the variables of its key, the variables that its element reads or binds and those that the rules it calls read, directly or indirectly, among the visits that its recorded walks make to one position;
- (R3) outside the iterations that it evaluates, a recorded walk makes at most c_R steps, and at most c_R more for each iteration that it evaluates, counting the hash and each comparison of a value of the key of a site that is not free of the environment at most L + 1, as in a memo lookup, and apart from its suffix copies, the elements of a record that a walk whose iterations build values copies behind its own when it takes the record, and apart from the recovered errors that it takes over with a record.
The bound is then the one of Classification with K the greater of its K and the largest K_σ of the recorded sites, apart from the suffix copies. The condition is shown for a parse that inserts no missing token, of the reference implementation or of a parser generated as Go or TypeScript source, in which every recorded site that the parse walks is a run site. It is not shown for a parse that walks a repetition of a single character outside the reused skips, whose record answers only a walk from the same start; the proof says nothing of such a parse.
Cost View
The classifier decides the Conditions for Linear Cost on the cost view of the grammar, not on its rule bodies as written. A parser never runs the view.
Grammar. The view starts from the grammar with each
inline value action replaced by
a call of its hidden rule and each
built-in attribute replaced by the construct that it denotes (a recovery for
#recover, a stream for #stream, and so on). The view has the rules of that
grammar, with other bodies. Which rules are memoized, the left-recursion cycles
and their leaders, the variables and the run sites are those of the grammar,
not of the view.
Rewrites. Each body is rewritten from the inside out until no rewrite
applies. A rewrite replaces one expression by another; it removes or regroups
parts of the expression and adds none: no call, predicate, action, recovery,
stream, Operators Rule or #missing, and a call is inside a discard, a
lookahead or an #atomic after a rewrite exactly when it was before. Every rewrite shortens the expression or lowers its number of
alternatives, repetitions or attributes, so rewriting ends. The rewrites are
these, each only under the conditions given here and below.
| Rewrite | Replaces | Conditions |
|---|---|---|
| N1 | a group by its expression; a sequence in a sequence by its items; a choice that is an alternative of a choice by its alternatives; a sequence of one item by the item | a choice that is not the last alternative only when none of its alternatives has a loose cut; a sequence of one item only when the item is `_ |
| N2 | the alternatives after one that always succeeds, or after one that begins with a cut, by nothing | the choice is free of value conditions |
| N3 | an alternative by nothing when an earlier alternative is the same expression, has items that are a proper prefix of its items, or is a case-sensitive literal that is a proper prefix of it, a case-sensitive literal | the earlier alternative is evaluated again cheaply; the choice is free of value conditions |
| N4 | a `_ | alternative without attributes by nothing; the items after a |
| N5 | &&X and !&X by &X and !X, &!X by !X, !!X by &X |
!!X only when X makes no binding outside the rules it calls |
| N6 | a cut that ends an alternative of a choice, every loose cut of the last alternative of a choice outside the skips of recoveries, and a recovery of an expression that always succeeds, by nothing | a sequence left with one item or none becomes the item, or _ for none, only when the alternative is free; otherwise it stays a sequence of the item, or of _. A recovery is dropped only when its expression is free |
| N8 | a run of two or more alternatives that each match one character (a class without negation, or a case-sensitive literal of one code point, neither of which matches U+FFFD) by one class of their characters | none |
| N9 | X* X* and X+ X* by the first repetition, X X* by X+, and X? X*, for an X that cannot match nothing, by X* |
X repeats safely; both items are free |
| N10 | (X*)*, (X+)* and (X*)+ by X*, and (X?)*, for an X that cannot match nothing, by X* |
X repeats safely; the outer repetition is free |
| N11 | X* (Y X*)* by (X / Y)*, and X* (X / Y ...)* by (X / Y ...)* |
X cannot match nothing, has no loose cut and repeats safely; Y has no loose cut and makes no binding outside the rules it calls; both items are free |
| N12 | !X X by `_ |
_`; a run of two or more adjacent alternatives of at least two items each that begin with the same item by their longest shared prefix followed by the choice of what follows it in each |
| (choice of one) | a choice left with one alternative by that alternative | the choice is free and the alternative is not observed, or the alternative has the same value alone; never when the alternative has a loose cut, in which case the choice stays as written, with none of the rewrites of its parts |
In these conditions:
- In N9, N10 and N11, whether
Xcan match nothing is decided without token insertion: a literal marked#missingcounts there as one that cannot. - A loose cut of an expression is a cut in it that would commit a choice, option or repetition around the expression (Cut).
- An expression always succeeds when the classifier shows that it matches wherever it is evaluated; the classifier may fail to show it, and then the rewrite does not apply.
- A bounded terminal is built only of literals, classes,
., sequences, choices, groups and repetitions with an upper bound: it calls no rule, makes no capture and examines a bounded amount of input. - An expression is evaluated again cheaply when every rule that it calls
is cheap and called without a binding level, and it contains no predicate,
inline action, recovery, stream, Operators Rule or
#missing. The cheap rules are the least set that holds every memoized rule on no left-recursion cycle and every rule on no such cycle, without an action, whose body is evaluated again cheaply. Xrepeats safely when it has no loose cut, either cannot match without consuming input or makes no binding outside the rules it calls, and is evaluated again cheaply.
Value conditions. Some rewrites change the value of the expression that they
replace (Values):
a sequence of one item has a tuple of one element where the item has its own
value, N9 to N11 and the left factoring of N12 regroup lists and tuples, N2 and
N3 can drop every alternative with a value and keep one without, and _|_ has
the type _|_ where !X X has the type of X. The view applies them only
where no predicate can read the value:
- A read capture of a rule is a capture of the rule whose name a predicate
of the rule names, as
$xor$x.$y; a lambda parameter is not one. - A call is in a value position unless it is inside a discard, a negative lookahead, or a positive lookahead and outside every capture in that lookahead.
- A rule is value-read when it is called in a value position inside a read capture, or in a value position in the body of a value-read rule.
- An expression is free of value conditions when it is neither inside a read capture of its rule nor in the body of a value-read rule.
- An expression is observed when it contains a read capture of its rule, or calls a value-read rule in a value position.
- An expression is free when it is free of value conditions and is not observed.
- An expression has the same value alone as the only alternative of a
choice when it is a literal, a class,
., a repetition, an option, an#atomic,_|_, or a call that is not spliced. A splice rule is a hidden rule without an action, not even=> ..., whose body is not an Operators Rule. An expression is sequence-shaped when it is a sequence, a group of a sequence-shaped expression, an expression with attributes of which none is a recovery around a sequence-shaped expression, or a spliced call; a call is spliced when it calls a splice rule whose body as written is sequence-shaped, read without following a call of a splice rule that the same reading already followed.
N4, N5 and N8 do not change a value, and N1 changes one only in a sequence of one item; the rewrites that change a value have the conditions above.
Classification
sxir 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 and reasons. A
polynomial grammar has causes and no reason, so every condition for linear cost
that fails has a witnessed cause, and its degree is the largest degree of
those causes. A reason for the class unknown outranks polynomial causes,
because the reason leaves the cost open where the degree of the causes cannot
bound it. An exponential cause outranks a reason, because it is evidence of
growth that no polynomial bounds. A grammar of the class unknown that has
polynomial causes reports the largest of their degrees as its witnessed
degree: a lower estimate from the witnesses, not a bound. Each polynomial or
exponential cause produces a super-linear hint, with
its witness, whatever the class; the reasons for the class unknown are shown
with the classification and produce no finding. Without the request, there is
no classification and no super-linear finding. A grammar can also require the
class Linear with @linear,
which makes every cause and reason an error.
A grammar of the class Linear also has a budget: a bound c * n + k on the
compute units of a parse of an input of n position units, for constants c
and k that the classification derives from the structure of the grammar, in the
units of Cost. n is the length of the input in the position unit of
the parse, as for the default of Compute; the bound holds
for both position units. The bound is on the units of Cost as that section
defines them; a backend that charges other units for the same parse can report
Used above it. The budget is reported with the classification and is
not applied: it never changes the default of Compute or any limit. No other class has a
budget, because no constant of the grammar bounds its cost.
| Class | Promise |
|---|---|
| Linear | Every parse from the start rule has a cost of at most c · (n + 1) |
| Linear given an environment bound | Every parse has a cost of at most c · K · (L + 1) · (n + 1) |
| Polynomial of degree k | None; an estimate of a bound |
| Unknown | None; the classifier cannot bound the cost |
| Exponential | None; an estimate |
In a stream, where text costs the length of its result (see
Cost), the promises of the first two classes add the total length of
the results of text.
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 a parse of the same text from scratch that memoizes nothing, which evaluates every call that the language chapters define. Every call of a parse is one of those calls, so K is at least the number among the calls of the parse itself, and it is a property of the grammar and the text, not of what a parse kept from earlier parses: a parse of a Document, which can answer calls from what its earlier parses kept and so make fewer combinations itself, is bound by the same constant as a parse of its text from scratch. For a parse that is not a Document parse, the two numbers are equal wherever each call of the evaluation from scratch repeats, at its position and with its values, a call of the parse; the linear cost proof shows where it does, and lists the places where that is not shown. In the class Linear both are at most the bound below. L is the largest size of a variable's value that a copying operation copies or that a memo lookup or the lookup of a run-site record 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 through a number of joins and other copies that the grammar bounds, though it can pass through one binding many times without being copied, 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.
In the class Linear, c includes K, and the classification reports a bound on it: the product of the sizes of the value sets of the variables with finite values, 1 when there are none. The bound is a constant of the grammar, but a large one shows that the memo can keep that many results for one rule at one position: until the input is long enough for the parse to reach them all, the cost can grow faster than n.
The first two classes are guarantees under the memoization that Evaluations of Rules describes, the skip runs that Skip Runs describes and the scan sites that Scan Sites describes; an implementation or a parse that keeps fewer of any of them, as one can for testing and as a parse with missing-token insertion does, 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. Each polynomial or exponential cause comes 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, however many times it copies the value of the call, unless it
doubles the value of its rule (see Exponential below): each copy costs the
size of a value that grows by what one level adds, so the copies add up to
n² over the levels, as for
{len($x + $x) >= 0}in a predicate ortext($s) + text($s)of a nodes. So does a scanning source evaluated in each step of a growth. A fold over a list that is not bounded gives the degree in the size of the input of the cost of all its steps, which the step matrix of condition 4 bounds, when that is 3 or more: a term of the cost adds the degrees of the quantities that it multiplies, the size degrees of the values read from outside, and the degree of the number of steps, or of the sum of the powers of the element, for the sum over the steps. A fold inside lambdas over lists that are not bounded adds to either degree the size degrees of the numbers of elements of those lists, as condition 4 describes, so thatmap($b, (y) => foldl("", $b, (s, l) => s + text(l)))gives 3. A copying operation in such a lambda whose copies of elements add up to more than linear size gives the degree of their sum, as condition 4 describes, so thatmap(map($b, (q) => text($b)), (y) => y + "x")gives 2. - Exponential. A binding that makes a variable depend on its own earlier
value; a copying operation that copies a fold accumulator more than once,
as
s + sdoes; a copying operation whose result the value of its rule holds and that copies, more than once, the value of a call on a recursion with the rule that feeds back into the rule; or a fold whose step matrix of condition 4 can double its first parameter, though no single copying operation copies it twice, as by duplicating its elements and joining them. The step matrix bounds the growth from above, so a fold that it classes exponential can grow more slowly. A copy into the value of the rule makes the value of each level of the recursion at least twice the value of the level inside it: withE = l:A rest:(o:"+" r:A)* => foldl($l, $rest, (acc, i) => acc + text(i.$o) + i.$r + i.$r)andA = ("x" => "x") / ("(" v:E ")" => $v), the value ofEholds the value of theEnested in it twice, and each level ofx+(doubles it. The same copies made outside the value of the rule, or of a value that does not feed back into the rule, as whenAreturns a literal, give 2 (see Polynomial above). Like the step matrix, this cause takes the values to be non-empty: copies of an empty value do not grow. - Unknown. A condition for linear cost fails that no polynomial or exponential cause accounts for, 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, and a lookup finds one. The table of a Document keeps the entries of earlier parses, and a deletion can bring entries of one key to a position, at most one more for each edit since the table was last dropped. While growths are in progress at a position, the results there that read their growing results are kept apart, one for each combination of the growing results and lookahead outcomes that they read, and dropped when the first of those growths ends; each records at most a constant of the grammar of them and is built by counted cost.
- 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
Compute limits bound the cost of any parse,
whatever its class. Compute 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, except texts, which cost what Cost states. 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 a LimitError of kind LimitDepth, whose
message 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 Limits.Depth. Unlimited disables the limit on the iterative bytecode VM
only, whose call stack is on the heap; on a backend that nests rule calls on the
host stack it is an option error. Every backend reaches the limit at the same
nesting of the same input.
Cancellation and Compute Limits
The reference Go API accepts invocation-local cancellation and a compute 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. Compute counts
are implementation-specific and are not elapsed-time, memory, or buffered-input
limits; the memory limit counts bytes.
Reporting the Units Spent
The option runtime.WithComputeReport(out) stores in *out the compute units
that the invocation spent, when it ends: after a success, after a failure and
after an interruption by a limit or by the context. They are the units used
that Reservations and Interruptions
define, so an invocation that succeeded with report r is accepted by a
Compute limit of r, and one that stops at a Compute limit reports the
units used when it stopped. An invocation that ends before it starts, because
an option is invalid or the input is longer than the Input limit, stores
zero. Every entry point that runs a parse reports, one that streams when its
stream ends. The work that only a Document parse does (on pending edits,
entries and moves) is no unit of the Compute limit and not of the report. The
option turns the count on for an invocation that sets no limit and no context,
and a nil out is the absence of the option. A generated Go parser takes it
only if it was generated with limit controls, as it does a context or a finite
Compute limit. The computeReport option of a generated TypeScript parser
is the same: an object whose units the parse sets to zero when it starts and
to the units spent when it ends, taken only by a parser generated with limit
controls, as it takes a signal.
Reservations and Interruptions
The engine and generated Go parsers with limit controls count the work of an invocation (one call of an entry point) as follows; a cancellation or an exhausted limit is an interruption, which ends the invocation with its error.
- Reservations are atomic. A reservation of n units either proceeds and adds n to the units used, or interrupts with a limit error, or interrupts with the error of the context. The work that it covers is performed only if it proceeds.
- Observing the context. A reservation observes the context when the units reserved since it was last observed reach the polling interval of 256 units, or when the reservation would exceed the limit; a checkpoint observes it without reserving. When a reservation observes a context that has an error, that error wins over an exhausted limit. An observation that finds no error starts the interval again.
- Generated Go keeps the same count. The runtime of generated Go reaches the same sums of units used as the procedure above, and so exhausts a limit at the same reservation. Where it observes the context is, as in the engine, a function of the reservations and checkpoints before, but need not be where the engine observes it.
- A reservation precedes its work. Each unit of work that the budget counts is covered by a reservation made before it: in the same straight-line work, or before a loop whose number of steps is a function of the logical state before the loop, in the sense of the last rule of this list, and which ends early only by an interruption or a fatal error. The units of the steps that such an end leaves undone stay counted. Allocation, runtime growth, garbage collection and the callbacks of the caller are outside the budget.
- Reservations keep their place among what is observed. No reservation is moved or merged across a trace event, the delivery of a stream element or of recovered errors to a callback, any other callback of the caller, or the commit of an element. An interruption therefore exposes exactly the trace events, deliveries, callbacks and commits that precede the reservation that interrupted, in the order of evaluation, and none that follow it, on every backend and whatever the optimizations. Only the profile statistics of calls that began but did not complete may differ, as Generated Go Document Tracing and Profiling allows.
- Streams. In a stream, an error other than the end of the input that a reader returns together with data wins over a cancellation first observed after that read. The emission of an element observes the context before it calls the callback and again after the callback returns, and the commit of the element follows, demands no input and makes its reservations after that second observation, on every backend.
- Nothing absorbs an interruption.
#recover, ordered choice, lookaheads and repetitions are evaluated by failing, not by catching an interruption; predicates and bindings of typed parsers catch only the run-time error of an action; tracing passes an interruption on. An interruption therefore reaches the boundary of the invocation unchanged. - Input caches are published complete. A cache of a Document's input, such as a table built from its text, is published only after the reservations that cover building it, and no reservation or checkpoint comes between the steps that publish it, so a cache is complete or absent.
- Charges depend on logical state only. The size of each reservation follows from the grammar, the input, the options and the values of the parse, never from the address, capacity or contents of reusable storage, the order of iteration over a map, or time. The reusable state of a Document is part of its input: the charges of a Document parse are a function of the operations on it since its creation, provided that no earlier operation was interrupted by a context.
Default Limits
Limits has four fields, and a zero value selects the default of its field:
| Field | Bounds | Default |
|---|---|---|
Compute |
the cost of the parse | max(2^20, 1024 * n) |
Memory |
the storage the parse takes into use, in bytes (Memory Limit) | Unlimited |
Input |
the length of the input | Unlimited |
Depth |
the nesting of recursive rule calls (Limits) | 100,000; 10,000,000 on the iterative bytecode VM; the generated default |
Here n is the length of the input in the position unit of the parse: bytes
for Bytes, code points for CodePoints. Input has no finite default
because the default Compute already grows with n, and Memory has none
because, outside missing-token insertion, the memory a parse allocates is at
most proportional to its cost plus the input
(Time and Memory). Memory does not count the list
of reported errors, which the parse hands to the caller.
WithLimits sets the fields field by field. A nonzero field overrides the
value an earlier WithLimits of the same invocation set, and a zero field
leaves it unchanged; a field that no option sets takes its default. The
options of a Document call apply in the same way over the limits the
Document was constructed with. No value resets a field to its default once
an option has set it.
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 and no finite Memory
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.
Input 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 Input units is
accepted. A longer input fails with a LimitError of kind LimitInput: Limit
is Input, 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 Input 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 generated parser checks it whether or
not it has limit controls.
A stream does not know its length. With a finite Input, 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 Input units completes. As with the default
budget, the outcome does not depend on how the reader splits the input into
reads. With Input at its default, a stream tracks no length.
The default is resolved once per entry point, from the input the entry point
receives. 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 limit controls spends no budget and
accepts only a zero Compute and Unlimited.
For a Document, n is the length of the text at each Parse, and the default
counts the work that a parse of that text from scratch counts: the unit of each call, the key
of each call of a rule that a parse from scratch memoizes, the evaluation of rule bodies, the
examination of the input and the operations on recovered errors. The work that only a
Document does is not counted: applying pending edits to the memo entries that it finds, moving
the values it reuses, and copying the diagnostics it returns. The memo charges nothing else, in a
Document as in any parse (Cost): looking a key up, walking a chain of memo entries,
hashing and comparing keys, storing a result and growing the memo table charge no unit, whatever
the memo holds. A rule that only a Document memoizes (a transient rule) pays no key, as in a
parse from scratch, which does not memoize it. The counted units of a Document parse therefore
do not depend on the entries that earlier texts left in the memo or on the edits pending: each
call that it makes is a call of the parse from scratch, and a result that it reuses answers a
call whose body the parse from scratch evaluates. A Document parse under the default limit
therefore succeeds whenever a parse of the same text from scratch under the default limit does,
and it returns the result of that parse; the
linear cost proof argues this and does not
prove it. This holds under an explicit Compute limit as it does under the default: the work of
the Document is no event under either, and Limit and Used of a LimitError leave it out.
The work that no limit counts is bounded by that proof. Pending edits add at most 128
units to a call, since a memo entry that lags behind by more edits is evaluated again instead of
brought up to date; the moves of reused values and the copy of diagnostics depend on what the
Document retains, and no limit bounds them. The work of the memo, which no unit
counts, is bounded as Work of a Document Parse states:
each entry that a lookup or a store passes was stored by a counted call, and a Document drops
an entry that more than 128 edits have passed since a parse stored it or found it to answer a
lookup. A grammar whose counted
work is far above the default limit stops on a Document as it does on a parse from scratch,
also with the most pending edits.
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{Compute}) the limit. The compute 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
Compute. 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
runtime.ErrLimit, and errors.As with *runtime.LimitError gives the
details. Stream parses and documents are specified in Streaming
and Incremental Documents.
A LimitError of kind LimitCompute reports the reservation that failed:
Requested is the units of that reservation and Used the units reserved
before it, so Used is at most Limit and Used + Requested exceeds it. Every
backend reserves the examination of the input (each code point of a literal and
each character it reads), the test of each range of a character class, each
operator that an Operators Rule tries, and each execution step one unit at a
time, also where it charges several of them together; a failure there reports
Requested 1 and Used equal to Limit. Work that the cost model charges as one
reservation, such as a chunk of the preparation of the input, the copy of a text
or an operation on a list, is reserved at once, and a failure there reports the
whole reservation in Requested and the units before it in Used. Taking the
n elements of a list or a tuple that an action expression makes off the values gathered for it
is one reservation of 2n units, one for copying each element and one for taking
it off, made before any element moves, however long the list. The lists that
the parse builds charge nothing (Cost).
A LimitError of kind LimitCompute also has Hotspot, the rule that the
profile of the parse ranks first when the limit is exceeded:
the rule with the highest MaxEvals, the most evaluating calls at one position
and level, at least 2; a tie goes to the rule with more Repeats, then to the
first name in order. Every backend records the profile while the parse runs and
ranks it this way. Hotspot is empty when the parse has no profile and when no
rule evaluated twice at one position and level; a profile that earlier parses
also filled ranks all of them. The message of the error names it
(, hotspot rule R). It is not the rule that the parse was evaluating when the
check found the limit exceeded.
Every backend must make the same charges, so that every backend reports the
same Used and Requested for the same grammar, input and options; a backend
that charges differently has a defect, not a permitted variation. The current
backends do not yet meet this rule everywhere: on some grammars the bytecode
machine, which runs Flow bodies, and the
closure backend charge different units.
Memory Limit
Memory bounds the storage a parse takes into use, in bytes. The count is
the element count of each buffer the parser takes into use times the size of
its element type, and for a map the size of its keys and values: node, list,
field and capture chunks, memo entries, slots, first-call sets and hash
indexes, typed values, the decoded input and its line table, a stream's
buffers, the working stacks by their capacity, the records of left recursion,
context memoization, skipped runs, missing-token insertion and Document
reuse, the variable environments and syntax errors the parse builds, and the
strings that actions concatenate and the text they copy out of the input. Not
counted are the caller's input string, which Input bounds; the compiled
grammar and other state shared by every parse of it; values handed to the
caller, such as the elements a stream delivers, after they are handed over;
trace and observation output, which goes to the caller's sink; and what the
allocator adds beyond the logical size, such as size-class rounding and map
overhead. Storage abandoned by backtracking is not returned; a stream
returns the storage of the elements it has delivered, so the count of a stream
bounds its window, not its length. Recovered errors are the exception: a stream
retains them for its result unless a diagnostic limit keeps only the latest
ones, so without one they grow the count of a stream
(Streaming). Counts depend on the backend, the position
unit and the generated artifact, and for a given artifact, input and options
they are the same on every run, whatever an earlier parse left in a reused
parser.
A finite Memory makes a parse controlled, and the control then polls every
256 compute units even without a context. At a poll, the context is
consulted first, then the memory count, then the compute counter; the context
and the memory count are checked again at the end of the parse. A count above Memory fails the parse with a LimitError of kind
LimitMemory, message parse memory limit exceeded: limit N, used M, whose
Limit is Memory, Used the count, and Requested zero: memory is checked
at polls, not reserved before an allocation, so the count can pass Memory by
what the parse allocates between two polls. A parse whose final count is at
most Memory succeeds.
A Document parse counts the caches the Document retains from earlier parses
from its start. If they alone exceed Memory, the Document drops them before
the parse, as ResetHistory does, and parses from scratch. Retained caches
within Memory are kept, so a parse that reuses them can fail where a parse
from scratch would fit; the interruption clears them, and the next parse starts
without them.
The reference engine, generated Go and generated TypeScript have the memory limit; generated TypeScript counts by a model of the sizes of its objects, as Generated Parsers states.
Modes
The same grammar can be run in several modes. Except where stated, each mode gives the results that an ordinary parse gives.
| Mode | Difference from an ordinary parse |
|---|---|
| Backends | The reference implementation has three backends (closure, recursive bytecode and iterative bytecode). They give identical values, errors and positions, and differ in speed and in the limit of nesting depth. Generated Go and TypeScript parsers implement the same matching semantics; the entry points, features and limits that differ are defined in Generated Parsers |
| Recognition | The parse only tells whether the input matches. It gives the same success or failure and the same syntax errors, builds no tree, and skips actions whose values are not needed by predicates. Actions needed by predicates still run and can report run-time errors. The captures that predicates read are still built |
| Stream | A parse that reads its input incrementally and hands each element of the #stream repetition of the start rule to the caller as it matches. The elements are not part of the value. See Streaming. Generated TypeScript parsers have no stream mode |
| Incremental | A document that is edited and reparsed reuses results of the previous parse. The result of a parse is the same as that of a parse of the whole new text. See Incremental Documents. Generated Go and TypeScript parsers support a subset, which reuses memoized results |
| Prefix | A named rule is parsed at the beginning of the input without requiring the whole input to be consumed. See Prefix Parsing |