Cost View
Arata Furukawa · Last revised 2026-11-10
The classifier decides the Conditions for Linear Cost on the cost view of the rule bodies, and the Linear Cost proof bounds a parse of that view. This proof transfers the bound to the grammar as written: on every input, the parse of the written grammar costs at most a constant times the parse of its view, in the units of Cost and in the compute units of each backend (the theorem). It covers every rewrite that the view applies, N1 to N6 and N8 to N12 of Normalization; N7 and N13 are off for the classifier.
Lemma 1 shows that no predicate observes a value that a rewrite changes, so every rewrite keeps what the grammar matches; the rewrites that change a value are listed under Rewrites That Change Values, each with the condition under which the view applies it. Lemma 2 bounds an evaluation that the written grammar makes again, Lemma 3 compares one rewrite at a time, Lemma 4 shows that the written grammar calls no rule in a state in which the view does not, and the theorem adds them up with the memo. The values that actions build from a value that a rewrite reshapes, and the run-time errors of those actions, are not covered: Scope states what is left open.
Setting
Fix a grammar G as the classifier reads it, with inline actions replaced by calls of their hidden rules and built-in attributes by their constructs, and let V be its cost view. V has the rules of G with other bodies; the memoized rules, the left-recursion cycles and their leaders, the variables and the run sites are those of G. The parse of V is the parse with the rule bodies of V and those decisions of G, as the Setting of the Linear Cost proof reads it, and with the capture scopes of G: a name that a predicate or an action of V reads denotes the capture of that name in G. States, outcomes and the facts (F1) to (F5) are those of Grammar Laws, and the memo is that of Evaluations of Rules.
Rewrites. The view rewrites each body from the inside out until no rewrite
applies. Each change replaces one expression e of a body by an expression
e', under conditions that hold of e as the earlier changes left it. So V
is reached from G = G_0 by a sequence G_0, G_1, \ldots, G_m = V in which
G_{i+1} differs from G_i only in one occurrence of one body, and m depends
only on G, since every rewrite lowers the measure of
Normalization (Termination). A rewrite only
removes or regroups parts of e: by Cost View
no rewrite adds a call, a predicate, an action, a recovery, a stream, an
Operators Rule or a #missing, and none copies a part, so the parts that e
and e' share are the same expressions in G_i and G_{i+1}. A call is
inside a discard, a lookahead or an #atomic after a rewrite exactly when it
was before, and these are the constructs that make a call one of the value-free
twin of its rule (Evaluations of Rules):
K1 and K2 replace a lookahead by a lookahead. So every call that the two share
calls the same variant of its rule.
Cheap expressions. The cheap rules and the expressions evaluated again cheaply are those of Cost View. Since the set of cheap rules is the least one, a cheap rule that is not memoized calls only cheap rules, and the calls of cheap rules that are not memoized form no cycle: they nest at most |\text{rules}| deep. The bodies of the G_i keep the property, since no rewrite adds what it excludes.
Own cost. A keyed evaluation is a body evaluation of a memoized rule that
is neither a growth step nor in a context of growths: the evaluations that
Lemma 3 of the Linear Cost proof
counts. Its key is its variant, position, binding level and the values of
the variables that the rule reads. The lookahead state is left out: it decides
only whether failures are recorded and what the errors of #recover say ((A1)
of Memoization), which C does not count.
A growth run is the growth of a leader that a call outside every context of
growths starts: its growth steps and the evaluations in the context of that
growth. Its key is the key of the call. The own cost of an evaluation of an
expression is the part of C that it makes outside the keyed evaluations and growth runs that it
starts: its steps, the input that its terminals examine, its iterations and
operators, the values that its actions and predicates build, and each call that
it makes, which C counts as a constant and the lookup of its key whether or not
the memo answers it. The own cost of a call includes the evaluation of the body of
a rule that is not memoized, since that body is evaluated at every call. The own
cost of a growth run is the sum of the own costs of its steps and of its
evaluations in context. A body evaluation costs at least 1.
Rewrites That Change Values
By Values,
a sequence is a tuple of the values of its items that have one, even when there
is only one; a parenthesized sequence in a sequence adds its elements to it; a
group creates no value; and a choice of which some alternative has a value is
one element, the value of the alternative that matched, or nil when that
alternative has none, while a choice of which no alternative has a value has no
value and adds no element, as an optional expression of an expression without a
value does. A recovery makes an
expression with a value one element (#recover),
so a sequence gives its tuple node, and leaves
an expression without a value without one, except an expression of type _|_,
whose recovery is the error value alone, whatever elements the expression would
have if it matched (#recover). A sequence
with an element of type _|_ has that type, as a choice whose alternatives all
have it does, a repetition of at least one element of that type, a capture or
an #atomic of an expression of that type, and a call of a rule without an
action or a declared type whose body has it (Top, Bottom, Join and
Meet). A choice joins the types
of its alternatives, so one of type _|_ adds nothing to its value; an optional
expression of an expression of type _|_ is nil, of type *_|_, one element
as for any optional expression with a value; and a repetition of it that may
match no element is the empty list, of type []_|_.
Measured by these rules, a rewrite of the view changes the value of the expression that it replaces only
in the cases of the table. The conditions are those of
Cost View: an expression is guarded when
it is not free of value conditions, that is, inside a read capture of its rule
or in the body of a value-read rule, and observed as defined there (Lemma 1).
| Rewrite | How the value changes | Condition |
|---|---|---|
| N1: a sequence of one item becomes the item | the tuple of one element becomes the value of the item | not guarded and the item not observed; or the item is a bottom: the sequence then has an element of type `_ |
| N2, N3: the alternatives after one that always succeeds or begins with a cut, and an alternative that an earlier one subsumes, are dropped | when every alternative with a value is dropped and one without stays, the choice, one element (nil when that alternative matched), gives none; otherwise only the type of the choice changes, not its value, since a dropped alternative never gives it |
not guarded; otherwise no alternative but a bottom is dropped |
K4 of N12: !X X becomes `_ |
_` | !X X has the type of X, and `_ |
| N6: a sequence left with one item, or none, once its cuts are dropped becomes the item, or a top | as in N1; a tuple of no elements becomes no value | not guarded and the alternative whose cuts are dropped not observed; otherwise it stays a sequence of the item, or of a top, which keeps the tuple |
| A choice left with one alternative becomes that alternative, after N2, N3, N4, N6 or N8 dropped or merged the others | an alternative that is a sequence, or a call of a splice rule (a hidden rule without an action) whose body is one, adds its elements to a sequence around the choice instead of being one element. One without a value has none in both places: the choice of it has no alternative with a value, so it adds no element, as the alternative alone does | not guarded and the alternative not observed; or the alternative is a literal, a class, ., a repetition, an optional, an #atomic or a bottom, each with the same value alone and as the only alternative (one element, or none for an optional without a value), or a call whose body is not spliced as a sequence, one element or none in both places |
| V1 of N6: a recovery of an expression that always succeeds is dropped | an expression with a value that a sequence around it splices (one that is sequence-shaped by Cost View: a sequence, grouped or with attributes other than recovery, or a call of a splice rule whose body is one) adds its elements to that sequence instead of being one element | not guarded and the expression not observed; otherwise the recovery stays. An expression that no sequence splices, or that has no value, has the same value either way |
| N9, N10, N11 | one list replaces a tuple that holds a list, or a list of lists | not guarded and no item observed |
| The left factoring of N12 | the rests of the alternatives become one element after the shared prefix | not guarded and no alternative of the run observed |
| N13 | the body of the rule takes the place of the call | off in the cost view |
The other rewrites keep the value. N1 removes a group, which creates no value,
splices a sequence into a sequence, which adds the same elements, and flattens a
choice into a choice, which has the value of the alternative that matched
either way. N4 drops bottom alternatives, which never match and which the
choice leaves out of the join of its alternatives, so the choice keeps its
value; the alternatives left are unchanged (for the captures in the dropped
ones, see Lemma 1). N4 replaces _|_ a by _|_: a sequence with an element of
type _|_ has that type, so both have the type _|_ and never give a value,
and wherever the value model looks at the type they agree: a recovery gives
each the error value, an optional expression of either is nil, a repetition
of either that may match no element is the empty list, and a choice drops
either from the join of its alternatives. N5 changes
only lookaheads, which have no value, and K1 only where the expression binds nothing
outside its calls. N6 drops a cut, which has no value, so a sequence that keeps
two items or more is the same tuple. N8 replaces literals of one code point by
a class, and both give a string node of the matched text.
A value is reshaped when it is the value of an expression that a rewrite of the table replaces where it changes that value (every case of the table but a bottom in the first row, the drops of N2 and N3 that keep an alternative with a value or drop none, the alternatives that have the same value alone or that have no value in the row of the choice of one alternative, and in the row of V1 an expression that no sequence splices or that has no value), or when it includes such a value: the value of a capture around it, of a sequence or choice around it, of a rule whose body value includes it, and so on outward. By Lemma 1 no predicate reads a reshaped value; an action can, since the conditions of the table follow only the captures that predicates read.
Scope
The parses are those that the classes of Classification promise: without missing-token insertion, which is outside the classes, and stopped by no limit. A parse of a Document and a stream are covered at the end of the theorem. The cost is that of the Linear Cost proof: the walks of run sites are counted without their records, as that proof counts them, and the records of scan sites add at most two steps for each walk (Lemma 5 of Run Sites).
What is not covered. An action of G that reads a reshaped value, through a
capture or the value of a rule, reads another shape than the classifier sees in
the view: x:("a"* "a"*) => concat($x[0], …) copies a list in G and an
element in the view, and len($x) of x:("abc" #cut / "z") is one element in
G and three characters in the view. It can build values of other sizes, and
stop the parse with a run-time error where the view does not, or the reverse.
The theorem therefore bounds C'_G, the cost C_G less the values that such
actions build, on inputs on which no action that reads a reshaped value stops
either parse with a run-time error. Step 7 of the open
steps states what remains: prove that the values
which actions build from a value that a rewrite of Rewrites That Change
Values reshapes (a sequence of one item or a
choice of one alternative replaced by its item under N1, N6 or the drop of the
other alternatives, a choice that loses its last alternatives with a value under
N2 or N3, a recovery dropped by V1, N9, N10, N11, !X X replaced by _|_ under
N12, or the left factoring of N12), and the run-time errors of those actions, stay within a
constant factor of what the classifier bounds on the view (or make the view keep
the shape of every value that an action reads). Predicates are covered: by Lemma
1 none reads a reshaped value.
Lemma 1 (Context)
Let G_{i+1} replace e by e'. Then every predicate of G_i reads, in every evaluation, the value that it reads in G_{i+1} in the same state. In particular, when the rewrite changes the value of e (Rewrites That Change Values), no predicate of G_i observes a value of e or a value that includes one.
Proof. A predicate observes a value only by naming a capture: $x, the capture
access $x.$y into the node of a rule, or the elements of $xs through the
parameter of a lambda. A variable is set only by a binding of a predicate, so a
variable that holds a captured value was set by a predicate that names the
capture. Positional references are not part of the language
(Grammar Laws, the context condition of the
cost view). Let a predicate of the rule r_0 name the capture c of r_0, and
let the value of c include a value of e, which lies in the body of the rule
r. A value passes outward through the value of every expression around it,
except a discard, an #atomic, a negative lookahead, and a positive lookahead
outside the captures in it, which drop it; a capture in a positive lookahead
keeps its value beside the tuple of its scope
(Capture). Call the other positions
value positions. So either r = r_0 and
c lies around e or inside e, or c lies around a call, in a value position,
of a rule r_1 whose body calls in a value position r_2, and so on to r.
By Cost View, c is a read
capture of r_0, a call in a value position inside c is a call of a
value-read rule, and so is a call in a value position in the body of a
value-read rule. Every position through which a value passes outward is a value
position there; a position under an #atomic is one too, which only adds
value-read rules. In the first
case, c around e makes e guarded, and c inside e makes e observed.
In the second, r is value-read, so its whole body is guarded.
Each rewrite of the table of Rewrites That Change
Values changes a value only where the expression is
neither guarded nor observed. For N9, N10, N11 and the left factoring, the view
checks that the expressions that e is made of are not observed: both items,
the repetition, every alternative of the run. So neither
case holds, and these rewrites change no value that a predicate observes. For
the drops of N2 and N3 and for K4, the view checks only that the expression is
not guarded, and it suffices. N2 and N3 leave the alternatives that
stay as they are, and K4 replaces !X X, in which X makes no capture
(a bounded terminal makes none), by _|_, which makes none: the captures that
remain keep their values, and those that are dropped are never set (below). What
changes is the value of the choice from which alternatives are dropped, or of the
expressions whose type follows the type of !X X: the sequences, choices,
groups, labels, captures and #atomics around it in the body of r, and the
value of r when its body takes the type _|_. A predicate observes these only
through a capture around them in r, which makes them guarded, or
through the value of r, read directly or through the rules that call r in
value positions, which makes r value-read and its whole
body. In the
rows of N1, N6 and the choice of one alternative, e is a sequence or a choice of one expression x, besides
the cuts that N6 drops, and e' is x itself (or a top); in the row of V1, e
is x with a recovery, whose skip has no captures, and e' is x. The
captures of e are those of x, which keeps them and their values. Only the
value of e itself changes, and a predicate observes it only through a capture
around e or through the value of a rule whose body contains e. A read
capture around e makes e guarded, and a read capture inside the alternative
from which N6 drops the cuts makes that alternative observed; N6 requires the
alternative to be free (Cost View). A rule
whose body contains e and whose value a predicate reads is value-read. For V1,
the view requires x itself to be free. In each case
the view keeps the sequence of x, the choice of x or the recovery, unless
x has the same value alone: a bottom, which has the type _|_ as the
sequence or the choice of it does, since a sequence with an element of that
type and a choice of alternatives of that type have it, so a recovery around
either gives the error value and an optional expression of either is nil; or
for a choice an expression with the same value alone: a literal, a class,
., a repetition, an option, an #atomic or a bottom, which has the same
value alone and as the only alternative (one element, or none for an optional
without a value), or a call that is not spliced, which is one element or none
in both places. That last case rests
on two facts. First, a call of a rule that is not a splice rule is one element,
the value of the rule, in both places, and the body of a splice rule that is not
sequence-shaped gives at most one element with a value: only a sequence, a
group or an expression with attributes other than recovery of one, or a call of
a splice rule whose body is one, gives several
(Values,
Hidden Rules, and a recovery makes one
element by #recover). If the body gives one, it is the value of
the call alone and of the choice of it. If it gives none, the call alone adds
no element, and the choice of it, of which no alternative has a value, adds none
either. So (_r / _|_) with _r = -"a" becomes _r whether or not it is guarded: N4 drops
_|_, which the choice leaves out of its join in any case, and neither the
choice of _r nor _r alone adds an element. Second, whether a call is spliced is
decided on the bodies as the grammar writes them, while G_i
runs them as rewritten so far. The test decides a value only where the call is
guarded or observed, and only for a call in a value position:
one under a discard, a negative lookahead or a positive lookahead outside its
captures has no value either way. A call in a value position inside a capture
that a predicate reads or in the body of a value-read rule is a call of a
value-read rule, and an observed call is one of a value-read rule, so the callee is
value-read, and so is every splice rule that its body calls in a value position in
turn: all their bodies are guarded. There no rewrite
makes a body that is not a sequence into one. N1 splices sequences only into
sequences and removes groups, through which sequence-shaped looks; a sequence of one
item becomes the item only if the item is a bottom, and a choice of
one sequence stays, since a sequence does not have the same value alone; V1, the
drops of cuts that leave fewer than two items, N9 to N11, K4 and the left
factoring are off on guarded expressions
(Cost View); and N4
makes only _|_, which is not a sequence. A rewrite that makes a sequence into something
else, as N4 does with _|_ a, can only make the test say that a body is a
sequence where the rewritten body is not one, and then the choice stays, with
the value it has in G_i. A recovery it keeps even then. So no rewrite changes a value that a predicate observes. This is the context condition of
Normalization.
The other rewrites keep the value of e
(Rewrites That Change Values), except that N2,
N3 and N4, guarded or not for N4, can drop
the only occurrence of a capture: in an alternative after one that always
succeeds or begins with a cut, which is never tried; in an alternative that an
earlier one subsumes, which fails wherever it is tried; or after _|_ in a
sequence, which is never evaluated. No rewrite drops an item before _|_: N4
keeps the items up to the bottom, and K4 replaces only !X X, whose X makes
no capture. In
each case the capture is never set in G_i, since a capture made in a match
that backtracking undoes does not survive and one that did not match is nil
(Capture). Under the capture scopes
of G, a read of it gives nil in both. \square
With Lemma 1, each rewrite preserves \equiv_E in its context (Equivalences), so its law applies inside every body.
Lemma 2 (Evaluating Again)
Let x be evaluated again cheaply, and let G_i evaluate x at a state \sigma and later, within the same evaluation of the enclosing rule body, at \sigma again. Then the second evaluation has the outcome of the first, makes its calls with keys of calls of the first, starts no growth run and no keyed evaluation of a rule of a left-recursion cycle, and has an own cost of at most the own cost of the first. Neither evaluation evaluates the occurrence of a body that contains x outside the keyed evaluations that it starts.
Proof. The outcome is that of the first by (F1) and (F4). Both start in \sigma, so by (F1) they make the same steps in the same states, except inside the calls that the memo answers in one and not in the other, and a call that the memo answers ends as its evaluation would (the theorem of Memoization). A rule that x calls is cheap, so it is on no left-recursion cycle, and it is not a leader. A cheap rule that is memoized is in no context of growths, since only the growths of a rule's own cycle form its context (Evaluations of Rules), so its body evaluation is a keyed evaluation. A cheap rule that is not memoized is evaluated at each call, and its body is evaluated again cheaply, so by induction on the depth of these calls, which the least fixed point bounds, its two evaluations make the same steps outside the keyed evaluations that they start. So outside the keyed evaluations the two evaluations examine the same input, make the same iterations and the same calls with the same keys, and build no value: x and the bodies of the cheap rules that are not memoized have no predicate, inline action or rule action. Each call costs the same in both, whether the memo answers it or not.
Let x lie in the body of the rule r. If an evaluation of x evaluated the body of r outside the keyed evaluations that it starts, a chain of calls of cheap rules that are not memoized would lead from x to r; then r is cheap and not memoized, and the chain closes a cycle of such rules, which the least fixed point excludes. \square
The memo can answer in the second evaluation a call that it did not answer in the first, which only removes a keyed evaluation. An entry that answered a call of the first answers it in the second, since nothing between them removes it: the growths of \sigma are still in progress, its lookahead state is that of \sigma, and the rules called are on no cycle, so their entries read no growing result. A stream discards entries only before the elements that it has delivered, and after delivering an element it never evaluates anything that starts before the element's end. If it delivers one between the two evaluations, the second starts at the position of \sigma, so the element ends at or before it, and every call of the first is at a position at or after it: no entry of these calls is discarded. In a Document parse, an entry stored in the parse has no pending edit.
Lemma 3 (One Rewrite)
Let G_{i+1} replace e by e' by the rewrite \rho. For every state \sigma in which G_i evaluates e, the evaluation of e' at \sigma in G_{i+1} has the same match or failure, end, environment and captures after it and escape of cuts, every call that e makes there has the key of a call that e' makes there, and the evaluations that e makes there and e' does not are evaluations again of expressions evaluated again cheaply, of the kind of Lemma 2, or make no call. Each evaluation that e makes and e' makes too has the same own cost in both, up to the occurrence of e itself in the bodies that it evaluates, and the rest of \mathrm{own}_{G_i}(e, \sigma) is at most (a_\rho - 1) \cdot \mathrm{own}_{G_{i+1}}(e', \sigma) + b_\rho, with the constants of the table, where k is the number of alternatives that N8 merges, j the number of alternatives that N12 factors, \ell the length of the literal that N3 drops, and d the most input that the expression of K4 can examine plus the iterations of its bounded repetitions. The conditions are those of Cost View.
| Rewrite | Condition | a_\rho | b_\rho |
|---|---|---|---|
| N1 splice a group or a sequence in a sequence, flatten a choice, unwrap a sequence of one item; replace a choice of one alternative by it | a choice that is not the last alternative only without a loose cut in its alternatives; the unwrapping and the replacement as in Rewrites That Change Values | 1 | 0 |
| N2 drop the alternatives after one that always succeeds or begins with a cut | not guarded; an alternative that always succeeds or begins with a cut | 1 | 0 |
| N3 drop an alternative that an earlier one equals or prefixes | not guarded; the earlier one is evaluated again cheaply; a literal prefix only between literals matched with case | 2 | \ell for a literal prefix, 0 otherwise |
| N4 drop a bottom alternative, cut a sequence after a bottom | a `_ | without attributes, so a labelled |
_` stays |
| N5 stacked lookaheads (K1, K2) | K1 only when the expression binds nothing outside its calls | 1 | 0 |
| N6 cuts that cannot commit, recoveries that never fire (T2, V1) | a cut that ends an alternative, any loose cut of the last alternative; a base that always succeeds; the sequence that is left and the recovery as in Rewrites That Change Values | 1 | 0 |
| N8 merge single characters (C9) | classes without negation or U+FFFD, literals of one code point with case | k | 0 |
N9 X* X*, X+ X* to the first; X X* to X+; X? X* to X* |
not guarded, neither item observed, X repeats safely; for X? X* also X not nullable |
2 | 1 |
N10 (X*)*, (X+)*, (X*)+ and (X?)* to X* |
unbounded repetitions, not guarded, not observed, X repeats safely; for (X?)* X not nullable |
2 | 2 |
N11 X* (Y X*)* and X* (X / Y)* to (X / Y)* (R7) |
not guarded, neither item observed, X not nullable and without a loose cut, X repeats safely; for the unrolling also Y without a loose cut and binding nothing outside its calls | 2 | 2 |
N12 !X X to `_ |
_` (K4) | not guarded; X made of literals, classes, ., sequences, choices, groups and bounded repetitions, without calls |
1 |
| N12 left factoring (C6) | not guarded, no alternative of the run observed, at least two alternatives without a loose cut, factored by their whole shared prefix, which is evaluated again cheaply | j | 0 |
X repeats safely when it is evaluated again cheaply, has no loose cut, and cannot match without consuming input or binds nothing outside its calls.
Proof. The matching part is the law of the rewrite (Grammar Laws) under the condition of the view, which the table shows to imply the condition of the law, in a context that Lemma 1 allows. The parts of e that e' keeps are the same expressions, evaluated in G_{i+1} in the states in which G_i evaluates them, by the law; so an evaluation that both make has the same own cost in both, but for the occurrence of e in the bodies of the rules that are not memoized that it calls, which the next part bounds. What remains is what G_i evaluates that G_{i+1} does not, case by case.
- N1, N2, N4, N5, N6. G_i makes no evaluation that G_{i+1} does not. N1
only regroups: a group, a sequence of one item, a choice of one alternative and
the nesting of sequences and choices are no step of their own. N2: no alternative after one that always
succeeds is tried, and an alternative that begins with a cut commits the
choice before it examines anything. N4:
_|_fails at once and examines nothing, and nothing after it in a sequence is evaluated. N5: the inner lookahead evaluates the same expression in the same state, and a lookahead costs nothing of its own beyond what its expression examines (Linear Cost, Input that a lookahead examines). N6: a cut that the view drops commits nothing that is still to be tried, so both evaluate the same, and the sequence of one item or of a top that the view keeps in its place is no step of its own; a recovery whose base always succeeds never evaluates its skip. - N3. G_i evaluates the dropped alternative a only after the earlier alternative p that subsumes it failed without a cut escaping, in the state in which p started (F2). If a equals p, or p is a proper prefix of the items of a, G_i evaluates the items of p again in the states in which p evaluated them, and they fail as before (F4); by Lemma 2 this costs at most the own cost of p, which G_{i+1} also evaluates, and no item after them is evaluated. If p is a literal l that prefixes the literal a, the input does not begin with l, so a fails after examining at most \ell characters. Each dropped alternative is one rewrite, which gives a_\rho = 2, with b_\rho = \ell for a literal prefix and b_\rho = 0 for the others, where \ell is not defined.
- N8. Each of the k alternatives examines at most the one character at the position, and the class examines it once; at the end of the input none examines any.
- N9.
X* X*andX+ X*: the first repetition stops at q because X failed there, which leaves the state as it was (F2), or matched without consuming input, and then X binds nothing outside its calls; the second evaluates X at q in that state, so by Lemma 2 at most the own cost of the evaluation of X at q that the view makes, plus one failed iteration.X X*andX+make the same evaluations.X? X*: when X fails at the start,X*evaluates it again there, as above; when it matches, the two make the same evaluations. - N10.
(X*)*,(X+)*,(X*)+: after the inner repetition stops at q, the outer one starts it again at q, which evaluates X at q again, as in N9, and stops; that adds one evaluation of X, bounded by Lemma 2, and at most two iterations.(X?)*evaluates X whereX*does, with one more iteration at the end that matches nothing. - N11. At each position both evaluate X first and Y after X fails, in the same
states (R7). The unrolled form adds an evaluation of X only when Y matches
without consuming input: then
X*evaluates X again where it failed, in the state after Y, which differs only by bindings that Y makes outside its calls, of which there are none; by Lemma 2 it costs at most the evaluation of X there that the view makes. Its iterations are those of X and Y, one outer iteration for each match of Y, so at most one more failed iteration for each repetition that it starts and one at the end: at most twice those of the view and two more. The absorptionX* (X / Y)*evaluates X once more whereX*stopped, as in N9. - N12, K4. X calls no rule and its matches have a bounded length, so
!XandXexamine at most 2d characters and iterations together;_|_examines none. - N12, left factoring. In
p b₁ / … / p b_j, G_i evaluatespin the state \sigma of the choice for each alternative that it tries, after the earlier ones failed without a cut escaping (F2); each such evaluation after the first costs at most the first by Lemma 2, and the first is the one thatp (b₁ / … / b_j)makes. Whenpmatches, eachb_tstarts at the end ofpin the state after it, as in the view (F1), and the view tries the same rests in the same order. So G_i makes at most j - 1 more evaluations ofp.
The calls that G_i makes in an evaluation that G_{i+1} does not make are those of an evaluation again, which by Lemma 2 have the keys of calls of the first, which G_{i+1} makes; N8 and K4 call no rule. \square
One rewrite in every evaluation. Let the occurrence of e lie in the body B of the rule r, let M_e be the product of the upper bounds of the bounded repetitions of B around it, at least 1, and let c_i = a_\rho + b_\rho M_e. Then for every body evaluation of a rule at a state, which G_i and G_{i+1} both make, \mathrm{own}_{G_i} \le c_i \cdot \mathrm{own}_{G_{i+1}}.
Proof. By induction on the nesting of the bodies of rules that are not memoized inside the own cost, which is finite in each evaluation. Split the own cost of a body evaluation in G_{i+1} as X + \sum_N \mathrm{own}_{G_{i+1}}(N), where N ranges over the body evaluations of rules that are not memoized, inside it and not inside another such N, that evaluate the occurrence in their own cost, and X is the rest. The same N are made in G_i, and the induction hypothesis bounds each by c_i. If the body evaluation is not one of r, its part outside the N evaluates no occurrence and is the same in both. Otherwise e is evaluated in it at most M_e (1 + I) times, where I is the number of iterations of the unbounded repetitions of B around e: each such repetition evaluates its element once for each iteration and once more where it stops. The context of e in B is the same in G_i and G_{i+1} and is evaluated in the same states, and X \ge 1 + I, the body evaluation and those iterations. By Lemma 3, each evaluation of e adds to what e' makes at most b_\rho and the evaluations again of parts of e' that the table counts in a_\rho - 1. Each evaluation again costs at most the evaluation of e' that it repeats, which by Lemma 2 evaluates the occurrence nowhere in its own cost, so it lies in X and costs the same in G_i and G_{i+1}. So \mathrm{own}_{G_i} \le a_\rho X + b_\rho M_e (1 + I) + c_i \sum_N \mathrm{own}_{G_{i+1}}(N) \le c_i \cdot \mathrm{own}_{G_{i+1}}. A growth run is a sum of body evaluations, so the bound holds for it too. \square
Lemma 4 (Calls)
Every call that the parse of G makes has the key, and is in the context of growths, of a call that the parse of V makes.
Proof. Let \mathcal{R}_i be the reference parse of G_i, which evaluates every call (Memoization). By Lemmas 1 and 3 and the congruence of \equiv_E in a context that reads no value of the replaced expression in a predicate (Equivalences), \mathcal{R}_i and \mathcal{R}_{i+1} evaluate every expression outside the occurrence of e in the same states, and every call that \mathcal{R}_i makes inside an evaluation of e has the key of a call that \mathcal{R}_{i+1} makes inside the evaluation of e' in the same state, by induction on the nesting of the evaluations; the calls that only \mathcal{R}_i makes are in evaluations again, and by Lemma 2 they have the keys of calls of the first evaluation, which \mathcal{R}_{i+1} makes. A state fixes the growths open at its position, so the contexts agree. So the calls of \mathcal{R}_0 have keys among those of \mathcal{R}_m. A memoized parse evaluates the same expressions in the same states as its reference parse, less those inside the calls that the memo answers (the reference-parse argument of Lemma 15); a call that the memo answers has the key of the call whose evaluation stored the entry, which made the same calls. \square
Keys of the view. In the parse of V from scratch, the first call with a key of a memoized rule outside every context of growths finds no entry under its key, so it is evaluated: for a rule on no cycle and for a member that is not a leader it is a keyed evaluation, and for a leader it starts a growth run. So every key of a keyed evaluation or a growth run of the parse of G is the key of at least one keyed evaluation or growth run of the parse of V, of the same kind, since the memoized rules and the leaders are those of G.
Theorem (Cost View)
For every input, a parse of G in the scope above and the parse of V from scratch satisfy C'_G \le 3A \cdot C_V, \qquad A = \prod_{i < m} c_i = \prod_{i < m} \big(a_{\rho_i} + b_{\rho_i} M_{e_i}\big), where \rho_i and e_i are the rewrite and the occurrence of step i. A depends only on G. In the compute units of each backend b, U'_b(G) \le 3A\,u_b \cdot U_b(V), where U_b(G) is the units that b charges for the parse of G, U'_b(G) is U_b(G) less the units that it charges for the values that actions build from reshaped values, and u_b is the largest number of units that b charges for one unit of the cost, counting the steps that records add as the scope does, a constant of the grammar and the backend.
U_b(V) is a definition, not a quantity that a backend measures: the units that b would charge for the parse of V, with the rule bodies of V and the memoized and transient rules, left-recursion leaders and run sites of G, and with every walk of a skip run, a run site or a scan site charged as a walk without records, as the cost counts it. No backend runs that parse, since a parser never runs the view (Cost View), and a compilation of V would decide those for V. The proof uses only that U_b(V) \ge C_V + I_b, with I_b as below, which holds because, without records, b charges at least one unit for each unit of the cost of a parse. A measurement approximates U_b(V) by compiling V as a grammar of its own, as the measured controls do. Where the compiler decides the same memoized and transient rules, leaders and run sites for V as for G, the parse of the compiled V is the parse of V and the measurement is U_b(V); where it decides otherwise, the measurement can differ from U_b(V) in either direction, and so can the records that the measured parse uses, which leave out the charges of the walks they skip; the measured ratio is evidence, not a check of the bound.
Proof. Every unit of C'_G is in the own cost of exactly one keyed evaluation, growth run, or of the evaluation of the start rule where the parse begins. The own cost of a keyed evaluation is a function of its key: by (F1) the evaluations with one key make the same steps outside the keyed evaluations and growth runs that they start, in either lookahead state by (A1), and each call costs the same whether the memo answers it or not. So is the own cost of a growth run: the growth starts in the state of its call and evaluates its steps and the calls in its context as that state and the input decide, and the evaluations again that G adds inside it call no rule of a cycle (Lemma 2), so they change no result of the context. Applying One rewrite in every evaluation along G_0, \ldots, G_m, the own cost in G of the keyed evaluation, growth run or start with a key or state is at most A times the own cost of the one of V with the same key or state.
By Lemma 3 of the Linear Cost proof, which holds for every grammar, the parse of G makes at most three keyed evaluations with one key, in both lookahead states together. It starts at most two growth runs with one key, one in each lookahead state: a leader is memoized at every call, the result of a growth outside every context reads no growth that was open when its call started, so it is stored (condition (S) of Memoization), and an entry stored outside a lookahead answers the calls in both states. By Keys of the view the parse of V makes at least one with each such key. The evaluation where the parse begins is one in both. Summing gives C'_G \le 3A \cdot C_V.
By Cost, each backend charges at most u_b units for each unit of the cost of a parse (a call, a character that a terminal matches or rejects, an iteration, an operator applied and each value that an action builds), with the steps that records add counted as the scope counts them; a walk that takes the rest of a walk from a record charges nothing for what it skips, so the records only lower the charges of G. Without records it charges at least one unit for each unit of the cost, which gives the bound on U_b(V) above. The units that it charges for the input as a whole, before the parse, are the same for G and V; call them I_b. So U'_b(G) \le u_b C'_G + I_b \le 3A\,u_b C_V + I_b \le 3A\,u_b (C_V + I_b) \le 3A\,u_b\,U_b(V), the last by the definition of U_b(V).
Streams. A stream parse is a parse in which the streaming repetition of the
start rule delivers its elements and discards the input, the memo entries
before them, and their values. It evaluates what an ordinary parse evaluates
(Lemma 15, The reference parse), Lemma 3 of
the Linear Cost proof holds of it, and Lemma 2 holds of it by the remark after
Lemma 2, so the count above holds. The evaluations that the view drops contain
no stream and build no value, so the input that text
copies in a stream is copied by actions, which the theorem covers when they read
no reshaped value.
Documents. Let P be a parse of a Document. It memoizes the rules that a parse from scratch memoizes and also the transient rules (Reuse Model, Results that are stored), whereas the parse of V takes the memoized rules of a parse of G from scratch (Cost View). Split the cost of P by the decisions of a parse from scratch: its keyed evaluations and growth runs are those of the rules that a parse from scratch memoizes, and a call of a transient rule, whose results only a Document stores, counts, in the own cost of its caller, as a call of a rule that is not memoized: the call, and the evaluation of the body when P makes it. Let D be the lookups and stores of these calls, which a parse from scratch does not make.
By the Documents theorem and its proof, P evaluates the expressions of the reference parse of G on its text at the same states, less those inside the calls that the memo or a carried entry answers and the iterations that a repetition reuses from a recorded run. So outside D the keyed evaluation, growth run or start of P with a key makes the steps of the one of the parse of G from scratch with that key, by (F1) and (A1), with three differences, each of which only removes cost: a call of a rule that both memoize can be answered in one and evaluated in the other, and costs the same either way; a call of a rule that only a Document memoizes can be answered by an entry, which leaves out the evaluation of its body; and a repetition can resume a recorded run, which leaves out the evaluation of the iterations that it reuses, whose operations are Document units (Lemma 12). So the own cost in P outside D is at most the own cost in G from scratch with the same key, which the proof above bounds by A times that of V.
The calls of P have the keys of calls of that reference parse, which the proof of Lemma 4 gives to the parse of V. Lemma 3 of the Linear Cost proof counts the parse itself, and the proof of Lemma 12 applies it to a Document parse: at most three keyed evaluations with one key. No leader is memoized only by a Document, and a carried entry holds no result that read a growing result, so a growth run with a key is started at most once in each lookahead state, as above. The count above gives C'_P - D \le 3A \cdot C_V, with C_V of the parse of V from scratch.
D is Document work, and it charges no unit: a call of a rule that only a Document memoizes pays its unit and no key, and its lookups and stores charge nothing (Lemma 12, The units that the default budget counts). Each such lookup belongs to a call that C'_P - D counts and compares the strings of its key by identity, at a constant for each variable, and a key has at most the variables of G, so the work of D is at most a constant of G for each unit of C'_P - D. The other Document units are those of Lemma 12, which bounds them in terms of the parse itself; this proof adds nothing to them. \square
Measured Controls
The constant is a bound, not an estimate. Each grammar below makes one rewrite,
or a few, repeat its work on every element of the input. The written grammar
and its view, each compiled as a grammar of its own, parse the same input on the
three backends of the engine and in generated Go, with n = 500, 1,000 and
2,000 repetitions of the element. Each cell is a range that contains the ratio
of the units that the written grammar charges to those of the view at every
n, its bounds rounded down and up to two decimals. No
grammar reads a value in a predicate, so the view keeps no sequence of one item
and its formatted text is its syntax tree. Neither the written grammar nor its
view memoizes a rule: main is called from nowhere and k calls no rule, so
both are transient. The run sites that the compiler chooses for the view are not
compared with those of the written grammar, so the measurement approximates
U_b(V) as the theorem describes.
| Rewrites | Written grammar | Input | 3A | Closures | Bytecode | Iterative | Generated Go |
|---|---|---|---|---|---|---|---|
| N1, N8 (k = 2) | (("a" ("b" "c")) / ("d" / "e"))* $$ |
abcde |
6 | 1.07 to 1.08 | 1.07 to 1.08 | 1.07 to 1.08 | 1.09 to 1.11 |
| N2, N1 | ("a"* / "b") "c" $$ |
a, then c |
3 | 1.00 | 1.00 | 1.00 | 1.00 |
| N3 | ("aaaaaaaa" "c" / "aaaaaaaa" "c" "d" / [a-z])* $$ |
a |
6 | 1.56 to 1.57 | 1.68 to 1.69 | 1.68 to 1.69 | 1.58 to 1.59 |
| N4 | ("x" _|_ "y" / _|_ / "a")* $$ |
a |
3 | 1.00 | 1.16 to 1.17 | 1.16 to 1.17 | 1.00 |
| N5 | (!!"b" "b" / &(&"a") "a")* $$ |
a |
3 | 1.00 | 1.00 | 1.00 | 1.00 |
| N6, N8 (k = 2) | ("a" #cut / "b" / "c" #cut "d")* $$ |
acd |
6 | 1.00 | 1.23 to 1.24 | 1.23 to 1.24 | 1.05 to 1.06 |
| N8 (k = 8) | ("a" / "b" / … / "h")* $$ |
h |
24 | 1.16 to 1.17 | 2.39 to 2.40 | 2.39 to 2.40 | 1.16 to 1.17 |
| N9 | (k* k* [a-c])* $$ |
a |
9 | 1.66 to 1.67 | 1.69 to 1.71 | 1.69 to 1.71 | 1.66 to 1.67 |
| N10 | ((k*)* [a-c])* $$ |
aaaaaaaaaba |
12 | 1.34 to 1.35 | 1.31 to 1.33 | 1.31 to 1.33 | 1.33 to 1.34 |
| N11, unrolling | (k* ("x"? k*)* [a-c])* $$ |
a |
12 | 1.54 to 1.55 | 1.66 to 1.67 | 1.66 to 1.67 | 1.66 to 1.67 |
| N11, absorption | (k* (k / "x")* [a-c])* $$ |
a |
12 | 1.63 to 1.64 | 1.60 to 1.61 | 1.60 to 1.61 | 1.63 to 1.64 |
| K4 (d = 8), N4, N1 | (!"aaaaaaaa" "aaaaaaaa" / "a")* $$ |
a |
51 | 2.50 to 2.51 | 2.80 to 2.82 | 2.80 to 2.82 | 2.50 to 2.51 |
| Left factoring (j = 3), N8 (k = 3) | (k "x" / k "y" / k "z" / [a-c])* $$ |
aaaaaaaaab, then a |
27 | 1.95 to 1.96 | 2.24 to 2.26 | 2.24 to 2.26 | 2.02 to 2.03 |
Each grammar is the body of rule main, and k is rule k = "aaaaaaaaab".
The ratios do not grow with n and stay below 3A, since the evaluation that
the written grammar makes again is only a part of the cost of the view around
it.
A second control checks the conditions of Rewrites That Change Values. In
rule main = x:("abc" #cut / "z") {len($x) == 1} (e "q" / "x")* $$
rule e = e "x" / "x"
the predicate reads the value of "abc" #cut, a tuple of one element, so the view
keeps it as a sequence of one item. On abc followed by n times x, for
n = 250, 500 and 1,000, the written grammar and its view charge the same
units on all four targets, ratio 1.000, and both grow as n^2 through the
tail. The same holds with the cut in the last alternative,
("w" / x:("abc" #cut)), and for a choice left with one alternative that is a
sequence, x:("a" ("b" "c" / _|_)) {len($x) == 2}, and on q followed by
n times x for a recovery of a sequence that always succeeds,
x:("q" ("a"? "b"?) #recover(skip="z")) {len($x) == 2}, whose recovery the
view keeps. A view that replaced the sequence by its item, or dropped the
recovery, would reject the input at the predicate and skip the tail, and the
ratio would grow linearly in n, to about 1,000 at
n = 1000. The same holds on qab followed by n times x for a choice left
with one call of a splice rule whose body is a sequence,
rule main = x:("q" (_r / _|_)) {len($x) == 2} (e "q" / "x")* $$
rule _r = "a" "b"
where the call as the only alternative is one element, the node of ("a" "b"),
and alone would add "a" and "b" to the tuple of $x: the view keeps the
choice, and the ratio is 1.000 on all four targets. Measured on a view that
replaces the choice by the call, the ratio grows linearly in n, to 671.576 on
closures and 1,001.636 on the bytecode, the iterative backend and generated Go
at n = 1000. With rule _r = "a", whose call is one element in both places,
the view replaces the choice by the call under the predicate, and without the
predicate it does so for either body; the ratio is 1.000 in each case. The
formatted text of a view writes a sequence of one item and a choice of one
alternative so that they parse as the bare item, so this control compiles the
syntax tree of the view instead of its text.
A third control checks the drops of N2 and N3 and the replacement of K4 where a predicate reads the choice around them. In
rule main = x:("q" (_ / "b")) {len($x) == 2} (e "q" / "x")* $$
rule main = x:("q" (-"c" / -"c" "d")) {len($x) == 2} (e "q" / "x")* $$
rule main = x:("q" (-"b" / !"a" "a")) {len($x) == 2} (e "q" / "x")* $$
each with the rule e above, the choice has an alternative without a value and
one with a value, so it is one element, nil on q, qc and qb
respectively, and the predicate accepts. The view keeps every alternative, and
on that prefix followed by n times x, for n = 250, 500 and 1,000, the
written grammar and its view charge the same units on all four targets, ratio
1.000. Without the predicate the view drops "b", -"c" "d" and !"a" "a",
and the ratio is 1.000 as well. A view that dropped them under the predicate
gives the choice no element, rejects the input at the predicate and skips the
tail: measured on such a view, the ratio at n = 1000 is between 671 and 673
on closures and between 1,003 and 1,006 on the bytecode, the iterative backend
and generated Go.
The same control covers the drop of the alternatives after one that begins with a cut (T2 in N2) and the drop of an alternative equal to an earlier one (C1 in N3). In
rule main = x:("q" (#cut -"b" / "c")) {len($x) == 2} (e "q" / "x")* $$
rule main = x:("q" ("b" "c" / "b" "c" / -"d")) {len($x) == 2} (e "q" / "x")* $$
on qb and qbc followed by n times x, the view keeps every alternative
under the predicate and drops "c" and the second "b" "c" without it; the
ratio is 1.000 on all four targets in each case. A view that drops "c" under
the predicate gives the choice no element where it was nil, and its ratio
grows to 672.914 on closures and 1,003.629 on the other targets at n = 1000.
C1 cannot change the value, since the alternative it drops has the value of
the one it equals: a view that drops the second "b" "c" under the predicate
also measures 1.000, so the gate is conservative there.