064. Grammar Complexity: a Cost Model, a Classifier and Safeguards

  • Status: Partially Implemented
  • Author: @ornew
  • Date: 2026-10-28

Summary

A SyntaxIR parse does not always run in linear time. Packrat memoization bounds how often a rule body runs at a position, but parts of the language have a cost that the memo does not share, so a small grammar can take quadratic, cubic or exponential time, or build values of exponential size. This record defines what a parse costs, per construct. It proposes:

  • a sound static classifier that labels each start rule Linear, Linear·Env, Unknown, Poly(k) or Exp, with a witness or a reason;
  • two runtime changes that make linear what can be made linear: memoizing the members of left-recursion cycles, and reusing a repetition's run after backtracking;
  • a lint warning for variables that grow themselves;
  • a regression suite that measures cost at n, 2n, 4n and 8n;
  • an opt-in automatic budget of c·n.

The remaining super-linear constructs are reported and bounded by the budget instead.

Motivation

The current claim

The runtime comment on deferred memoization says that evaluating a memoized rule at most twice per position keeps "parse time" linear (internal/runtime/state/runtime.go:490-495). The bound on evaluations is correct. Linear time does not follow from it. Ford's linearity argument assumes that every nonterminal has a constant cost per position besides its calls, and that every repetition is desugared into a memoized right-recursive nonterminal. SyntaxIR deviates in four ways:

  • Repetitions are loops inside a rule body (Repetition). One evaluation of a body can scan any amount of input, and the memo does not share that scan with evaluations that start at later positions.
  • Rules on a left-recursion cycle that are not its leader are not memoized while a growth at their position can change their result (Evaluations of Rules); they are evaluated again at each step of that growth.
  • A left-recursion leader grows a seed at each position, and Operators Rules fold operators at each position. The result at p shares nothing with the result at p+1.
  • Rules that read variables are memoized per combination of values (Interaction with memoization). Bindings can make the combinations diverge without bound, and value actions can build values of any size.

Measured growth

Revision 8acf9918, Go 1.27.1, darwin/arm64, closure backend, code points. Each figure gives:

  • the exact threshold of Limits.Budget, found by bisection to 0.5%;
  • the rule evaluations reported by Profile.Evals;
  • the bytes allocated per parse.

Steps are deterministic for a fixed artifact, input and options (Cancellation and budget limits). The ratios therefore do not depend on timing noise.

Grammar Input family Steps as n grows Order
E0 (control) main = (A / "a")* $$; A = "a" "c" a^n n=1k…8k: 15,040 → 30,080 → 60,160 → 120,320 n
E1 main = (A / "a")* $$; A = "a"* "c" a^n n=1k…4k: 2.02M → 8.06M → 32.1M; 3.6 GB allocated at 8k n²
E7 main = (A / "a")* $$; A = (B / "a")* "c"; B = "a"* "d" a^n n=100…400: 0.78M → 5.77M → 44.4M n³
E9 main = ("a" !Rest)* "a"* $$; Rest = "a"* "c" a^n 1.02M → 4.03M → 16.1M n²
E8 main = (X / "a")* $$; X = (Y #recover(skip=[a]+)) "c"; Y = "b" a^n 0.56M → 2.13M → 8.26M n²
E6 (control) main = (E "q" / "x")* $$; E = "x" E / "x" x^n 43,136 → 86,272 → 172,544 n
E6 the same with E = E "x" / "x" x^n 6.55M → 26.2M → 104M; evaluations ≈ n²/2 n²
E10 the same with E = #operators { operand "x"; level add { infix left "" } } x^n n=500…2k: 0.51M → 2.02M → 8.06M n²
E2 (control) main = C $$; A = "n"; C = "(" C ")" "y" / "(" C ")" "z" / A (^n n )z^n n=8…16: 572 → 824 → 1,076 n
E2 the same with A = C "+" / "n", which puts A and C on a left-recursion cycle led by A the same n=8…16: 7,520 → 29.8k → 119k → 477k → 1.91M 2^n
E3 (control) var v string; R = "(" {v := "0"} R ")" "y" / "(" {v := "1"} R ")" "z" / "n" {len(v) >= 0} as E2 1,388 → 2,112 → 2,840 n
E3 the same with {v := v + "0"} and {v := v + "1"} as E2 n=6, 8, 10: 75k → 1.52M → 29.9M; memo hits 0 ≥ 2^n
E4 var s string = "a"; R = "x" {s := s + s} R / {len(s) > 0} x^n n=16…22: 0.39M → 1.58M → 6.31M → 25.2M; evaluations linear 2^n value size
E5 main = xs:"x"* => len(foldl("a", $xs, (acc, x) => acc + acc)) x^n identical to E4, in one action 2^n value size

E2 grows the same way on the bytecode and iterative backends. The budget limit stops every case above in proportion to the cost, because the closure backend charges value construction by size.

A further case is a correctness defect rather than a cost. var k int; R = {k := k + 1} R "x" / "x" recurses without consuming input until the nesting limit stops it. The time grows quadratically with the limit: 4, 14, 56 and 227 ms for limits of 1k, 2k, 4k and 8k. The left-recursion guard is found through the memo, whose key includes the variable environment (internal/runtime/state/runtime.go:142-148). A call with a different environment therefore does not fail as Left recursion requires. A separate change rejects such a grammar at compile time: a binding of a variable that a left-recursion cycle reads is an error when the binding may run before a left call into the cycle. A binding that runs only after the left call is allowed, because the recursive call has then already been made. The same change keys the runtime guard by rule and position only. The model below assumes both.

Why this matters

A server that parses untrusted input with a fixed grammar cannot tell from the grammar whether an attacker controls the exponent of its running time. The same is true of an editor that parses every keystroke with a user's grammar. Budget limits stop a runaway parse. They do not tell the grammar author that the grammar is the cause, or which rule to change.

Goals

  • State what a parse costs in time and memory, per construct, and the conditions under which it is linear.
  • Classify every start rule soundly: a Linear verdict is never wrong. Other verdicts may be pessimistic and carry a witness path.
  • Make the constructs linear that can be made linear without changing results: repetitions re-scanned after backtracking, and left-recursion cycle members.
  • Warn about variables whose binding grows from their own previous value.
  • Offer an opt-in budget derived from the input length.
  • Prove the classifier's soundness on paper, and check it by measurement with deterministic step counts.

Non-Goals

  • Deciding the exact complexity of an arbitrary grammar. This is undecidable (see Soundness).
  • Linear time for left-recursion growth and Operators Rule folds that a grammar backtracks over. The result at p cannot be shared with p+1; these constructs are classified and budgeted.
  • Restricting what variables and actions may compute. Self-growing bindings are warned about, not rejected.
  • Finite default budgets: parses stay unbounded unless the caller opts in.

Design

Cost Model

A parse is a tree of rule evaluations. Its time is the sum, over every body evaluation, of the evaluation's local cost: the terminals it matches, its loop iterations, the actions and predicates it evaluates and the memo lookups it makes, excluding the bodies of the rules it calls. Its memory is the memo table, plus the values it builds, plus the call stack. Memory never exceeds a constant times time, because every entry and every value costs at least one budget unit to create.

Per construct:

Construct Evaluations per position Local cost per evaluation Shared by the memo?
Memoized rule (Memo, outside a left-recursion cycle) ≤ 2 per (rule, position, level, environment): the first call is not stored, the second is (runtime.go:490-495) body size, plus loops yes, for the whole body
Transient rule (called from one site, or calling no rule) bounded by its caller's evaluations of that site as above through its caller
Left-recursion leader 1 growth per (rule, position, environment) one body evaluation per growth step; steps ≤ span + 1 the final result only
Non-leader member of a left-recursion cycle every call, and once per growth step of its leader as above no
Repetition, Scan, ClassRun once per evaluation of the enclosing body proportional to the span it matches no
Lookahead once per evaluation of the enclosing body the cost of its body; consumes nothing no
#recover(skip=e) once per failure of its base the base's cost plus the skip's span no
Operators Rule as a memoized rule, per binding level proportional to the operators folded the result per level only
Predicate or value action once per evaluation of its body proportional to the sizes of the values it reads and builds no
Variable environment multiplies memo keys by the number of distinct environments at a position equality of the environment per environment

Spans are what makes local cost unbounded. A construct whose local cost grows with its span is called a scanning construct: an unbounded repetition, Scan, a left-recursion leader, an Operators Rule, a recovery skip whose walks are not shared, and a lookahead whose body contains one. A parse is linear when no input position is covered by the spans of more than a constant number of evaluations of each scanning construct, and the number of environments per position is bounded.

Conditions for Linearity

A start rule is Linear when every rule reachable from it satisfies these four conditions.

  • L1, finite environments. No variable that a memoized rule reads is bound, along a recursion of the call graph, from an expression that reads the variable's own previous value. Bindings from literals, from captures and from other variables are allowed; their number of distinct values at one position is treated as a constant K. When K depends on the input, the verdict is Linear·Env, linear times the number of environments that occur at one position. An example is indent := len($s), whose values are bounded by the line length. A binding such as v := v + "0" along a recursion (E3) violates L1 and gives Exp.

  • L2, memoized cycles. Every rule that can be evaluated twice at one position, outside its own left-recursion growth, is memoized. A non-leader member of a left-recursion cycle with two call sites that can reach the same later position (E2) satisfies L2 because members are memoized outside the growth at their position.

  • L3, non-overlapping scans. No scanning construct stands in a backtracking context. A backtracking context is one where its evaluation can be abandoned and the parser can then start another evaluation of the same construct strictly inside the span it covered:

    • a choice alternative that is not the last;
    • a repetition element or a sequence item that something able to fail follows;
    • a lookahead body;
    • the base of a #recover.

    The context of a construct is the chain of such contexts from it through the callers of its rule, memoized or not. A memoized call does not end the context: the memo shares the result of a rule at one position, not its scan between positions. In main = (a "y" / "q" a / .)* with a = x+ and x = "x", every rule that scans is memoized, yet after a "y" fails, . consumes one character and the next iteration calls a one position later, which scans the rest of the input again: n x's cost about n²/2 steps. A memoized recursion brings the scan back in the same way, as in t = a t "!" / . t / "". A context is safe if it is committing:

    • the alternatives that follow have first terminals disjoint from the construct's continuation;
    • or a cut follows the first terminal of the alternative;
    • or what can fail after the construct cannot fail after the construct has consumed input.

    A repetition after the run-reuse change below is not a scanning construct for L3, because a restart inside its run reuses the run.

  • L4, bounded values. No predicate or value action makes a value whose size can double per evaluation. Examples are s + s on a value that flows back into the same binding (E4), and acc + acc or concat(acc, acc) on a fold accumulator (E5). An accumulator extended by bounded pieces (acc + text(x)) is quadratic in time because strings are copied, and gives Poly(2) for that action. Record 071 states when copies of a value of a recursion double it: only when they become part of the value of the rule that the next level copies again.

Classifier

Verdicts form a chain, from best to worst:

Linear  <  Linear·Env(vars)  <  Unknown(reason)  <  Poly(k, witness)  <  Exp(witness)
  • Unknown is assigned when a condition fails without a witness of growth, as when units that are not committing nest without bound through a recursion of rule calls. A witnessed Poly or Exp cause outranks it: a witness is evidence of growth, while Unknown is only the absence of a proof. Record 070 revises this chain: a reason outranks polynomial causes, so that the degree of Poly(k) bounds every condition that fails, and Unknown reports the largest degree of its polynomial witnesses only as a lower estimate.

  • Poly(k) is assigned when L3 or L4 fails. k is one more than the deepest nesting of unsafe scanning constructs along a path of the call graph: E1 has k = 2 and E7 has k = 3. Each unsafe level multiplies the input positions where an inner scan can restart.

  • Exp is assigned when L1 fails, when L2 fails on a cycle whose re-entry multiplies, or when L4 finds a doubling. The witness names the rules, the binding or the call sites involved.

  • A start rule's verdict is the worst verdict of the rules it reaches. A rule's verdict also feeds the verdicts of its callers, because it is part of their local cost.

The automatic budget needs, for a Linear start rule, a constant c_G, an upper bound on cost per input position. It is the sum, over memoized and transient rules, of twice the local cost of one body evaluation without loops, plus the per-iteration cost of each loop. Record 079 defines the constant that the classifier computes, in the units of record 076, and its report.

Soundness argument (sketch). The cost of a parse is the sum, over every body evaluation, of its local cost. For a grammar that satisfies L1–L4, with the left-recursion guard keyed by rule and position:

  1. A memoized rule is evaluated at most 2K times per (position, level) outside growth, by deferred memoization and L1. A transient rule is evaluated at most as often as the call site in its unique caller. The chain of callers ends at a memoized rule or the start rule. Under L2 no other rule is evaluated more than once per growth step.
  2. The non-loop local cost of one evaluation is bounded by the size of its body.
  3. Loop and scan cost is bounded by spans. Under L3, the evaluations of one scanning construct at distinct starts have spans that overlap only at their ends, or the overlap is answered by a memo hit or a reused run. Summed over a parse, each construct therefore covers each position a constant number of times. Left-recursion growth is a scanning construct, so the same argument bounds its steps.
  4. Under L4 every value built is at most linear in the spans of the captures it reads, and its construction is charged to the evaluation that builds it.

Summing gives cost ≤ c_G · K · (n + 1), and memory ≤ cost.

The conditions are sufficient, not necessary. They over-approximate in these ways:

  • Predicates are assumed to be able to both succeed and fail.
  • First terminals are path-insensitive.
  • A backtracking context is assumed to be reachable even when the input can never reach it.

Exact classification is undecidable. For a well-formed grammar G, consider main = W Gadget, where W must parse a word of L(G) and Gadget is E1. This grammar is super-linear exactly when L(G) is non-empty, and emptiness of a PEG's language is undecidable [Ford 2004]. The classifier can only be sound in one direction. A Poly or Exp verdict is therefore a hint with a witness, not a proof that a slow input exists.

Where It Plugs In

  • The classifier (the classifier files of the complexity package) is a pass over the grammar that the compiler runs: inline actions lowered to hidden rules and attributes normalized. It reuses the rule facts of the Core IR (internal/middleend/corepass/facts.go) (nullability, rules that always succeed, the left-call graph, its SCCs, leaders and cycle members) and runs only when asked, not at every compile. It assumes that the memo answers exactly the rules that every parse memoizes, and a test compares that assumption with the flags of the compiled rules, so the two cannot drift apart. Findings in hidden rules are reported in the rules that hold the inline actions.
  • sxir lint reports the results through two checks:
    • growing-variable, a warning on by default: a binding of a string variable that joins the variable's own value at least twice (s := s + s), when the variable can hold a non-empty value there and the bound value reaches a later evaluation of the same binding. Growth by a bounded piece, such as indent := indent + " ", is not reported, nor are int and bool bindings, whose effect is on cost. This is a certain fact about the grammar, so it meets the warning contract of Severities. It needs only the bindings that the classifier collects, so a default lint run skips the rest of the classification.
    • super-linear, a hint at each cause of a Poly(k) or Exp verdict, with its witness path. A hint because the slow input may not exist. It runs only when the classification is requested, with sxir lint -classify or lint.Config.Classify, which also shows the verdict, the degree of a polynomial verdict and the first witnesses or reasons.
  • The right-recursion hint gains a caveat. Right recursion stays linear under memoization in batch parses (E6 control). The repetition or left recursion it suggests is a scanning construct that L3 must check.

Runtime Improvements

Memoizing left-recursion cycle members. A non-leader member of a left-recursion cycle is memoized (optimization record 130). Instead of stamping entries with a growth generation, the parser never stores a result that depends on a seed that can still change:

  • a result that read the seed of a growth in progress when its call started is not stored;
  • while a leader grows at a position, a member result there is evaluated again instead of reused;
  • a result that read the result of a leader that can grow again at its position with another result is not stored.

Documents and interruption already discard state that depends on unfinished growth, and keep doing so. Cost: one memo entry per stored call of a cycle member, and the depth bookkeeping of each memoized call, which grammars without left recursion also pay. E2 is linear.

Reusing a repetition's run after backtracking. A Document already records the run of a repetition of 16 or more elements: positions, examined range, expectations and values per element, about 80 bytes per element. It reuses the run after an edit (docs/optimizations/054, 059, 070). Batch parses can use the same records to answer a restart inside a run:

  • When a repetition site starts at a position that is an element boundary of a recorded run of the same site, with the same environment and the same remaining count for bounded repetitions, the suffix of the run is the result.
  • The elements before the restart are dropped; element values are shared.
  • Recording is deferred like memo entries: a site records its runs only after it has restarted inside an earlier run once.

Cost: nothing on a grammar that never restarts inside a run. On one that does, 80 bytes per element of the runs it records. E1, E7, E8 and E9 become linear, because the inner scan at p+1 is the suffix of the scan at p. A run cannot be reused across a capture scope boundary whose captures the elements read, nor while a left-recursion seed it depends on is growing; such runs are not recorded.

What stays super-linear. Left-recursion growth and Operators Rule folds that a grammar abandons and restarts (E6, E10) build a different result at each position. They stay Poly(2). The classifier names the rule and the backtracking context, and the budget bounds them. Variables violating L1 and doubling values violating L4 stay exponential by design, and are warned about.

Budgets

The single budget keeps charges for value construction proportional to the size built: string concatenation, concat and list materialization, and fold accumulators. A per-call or per-iteration charge alone lets E4 cost 2^n while charging n.

The budget of a Linear start rule is c · (n + 1) + k for the input length n, derived by the classifier (record 079); record 066 makes every parse budgeted by default, so the opt-in option of this record is replaced by the default of Compute. For other verdicts the caller gives the budget. Exhausting the budget returns the ordinary limit error. When the parse has a profile, the error names its hotspot, the rule with the most repeated evaluations at one position (MaxEvals of the rule rows of Profile), as record 078 specifies.

Specification

Time and Memory specifies the cost of a parse, the conditions for linear cost and the classification; Grammar Lint specifies the two checks. The specification promises linear cost only for the classes Linear and Linear·Env, under the memoization that it describes.

Compatibility and Backend Support

The classifier and the lint checks add findings and change no parse. Memoizing cycle members and reusing runs change only cost, which Memoization permits. Node identity becomes different where entries are shared, and it is already unspecified. The closure backend, both VMs and generated Go implement the runtime changes. Generated TypeScript follows when it implements Documents, whose run records it lacks. Compiled grammars carry the memo flag of cycle members, and the format may change before the first release.

Implementation Sequence

  1. The step-ratio regression suite, with the E-series as negative controls (no behavior change).
  2. Memoizing left-recursion cycle members; E2 moves to the positive set.
  3. Repetition-run reuse in batch parses and streams on the engine backends, under which E1, E7, E8 and E9 measure linear; E8 is a positive control through the recovery-skip refinement, and E1, E7 and E9 stay classified polynomial.
  4. The classifier over the grammar that the compiler runs, and the growing-variable and super-linear lint checks.
  5. The automatic budget option, after the single budget lands.
  6. The Complexity section of the specification, and corrected comments where the code claims linear time.

Steps 1, 2, 3 and 4 and the specification of step 6 are implemented, and E2 is a positive control. The closure and bytecode backends keep run records for the walks of #recover skips (Optimization 132) and of restartable repetitions (Optimization 133) in batch parses and streams, so E1, E7, E8 and E9 measure linear there. Generated parsers keep no run records. The classifier relies on none, so E8 is a positive control through the recovery-skip refinement, while E1, E7 and E9 stay classified polynomial. The automatic budget is not implemented.

Alternatives Considered

  • Memoize every repetition suffix, as Ford's desugaring does. This gives linear time for all of L3 except left-recursion growth. It costs a memo entry per element of every repetition. Optimization 018 measured that most memo entries are never used, so this is rejected as the default. Deferred run reuse obtains the same bound only where restarts happen.
  • Elastic or bounded memo tables [Kuramitsu 2015] and cut-driven memo release [Mizushima et al. 2010]. These bound memory, not time. The memo never changes results, so eviction is semantically safe and stays open as a later memory control (see Decisions).
  • Per-construct budgets (left-recursion growth steps, recovery skip length). These add options a user cannot calibrate. A single budget plus a verdict naming the construct gives the same protection with one knob.
  • Rejecting super-linear grammars. Classification is pessimistic and many such grammars are fine on real inputs, so rejection would refuse correct grammars. Lint findings and budgets keep the choice with the author.
  • Analysis on Core IR. It would judge the module after rewrites such as Scans, but Core IR is built only for generated parsers, and the conditions are stated on the grammar. The grammar after lowering and normalization is what every backend compiles; the memo-policy test keeps the classifier aligned with the compiled rules.

Testing

  • Step-ratio suite (the complexity test support). Each E-series control and each corpus grammar is measured at input sizes n, 2n and 4n on the three backends, with steps found by bisection over the budget limit. A control must show its order from the table above; a corpus grammar's worst cost per byte may grow by at most 1.1 from 2n to 4n. Steps are deterministic, so the suite is stable without timing.
  • Classifier verdicts on the controls. Each control has an expected class: a positive control is classified Linear or Linear·Env, a negative control never is, and a polynomial degree matches the measured order.
  • Classifier soundness by differential testing. Random grammars over a small alphabet, in the shapes of the E-series and with string and list rules whose actions and predicates copy, index, measure and compare the values of their recursions, are classified, and every grammar classified linear is measured on several input families on the closure and bytecode backends: its cost per byte at 4n stays within 1.2 times that at n or 2n. A Linear verdict with super-linear growth is a classifier bug. A negative control treats the grammars classified Poly or Exp as linear and must fail, so the test can catch a classifier that claims too much.

Not yet in place:

  • Worst-case search. Mutate inputs to maximize steps per input length, in the manner of SlowFuzz and PerfFuzz [unverified citations], for corpus grammars classified non-linear. Confirmed witnesses become fixtures.
  • Equivalence. The runtime changes keep values, errors and recovered errors identical with and without them, on every backend, in Documents across edits, and under interruption during left-recursion growth.

Classification of the Bundled Grammars

The grammars in testdata/grammars/ and examples/, except json and the two calculators, are classified Poly, Exp or Unknown. The verdicts are upper bounds and the witnesses are paths, not slow inputs, and the corpus inputs are benign, so a verdict alone does not tell whether a cause is imprecision of the classifier, a cost that the runtime can remove, or a cost inherent in the language. Every cause is therefore sorted by measurement.

The causes of each grammar are grouped by shape, and every witness and every reason belongs to exactly one group. the testdata/triage/<grammar>.txt files of the complexity test support lists the causes of each group, and TestTriageCoverage keeps the lists complete and current. Each group has adversarial input families derived from its witness paths, in the triage files of the complexity test support. Each family is measured at three or four doubling sizes, with steps found by bisection over the budget limit, on the closure backend, both bytecode VMs and a generated Go parser:

SXIR_TRIAGE=. SXIR_TRIAGE_GO=1 go test -run TestTriageMeasure -v ./internal/testing/complexitytest

The variable is a regular expression over grammar/group/family. The test prints one row per family and backend, and fails when a measured order differs from the recorded one. The exponent is the logarithm of the cost ratio over the logarithm of the input length ratio between consecutive sizes, so families whose length is not proportional to their size parameter, such as indentation staircases, are judged against the input length. The backends agree on the order of every family except duckdb's runs of signs and minilang's nested operators, which the run records keep linear on the engine backends and which a generated Go parser, keeping no such records, runs in n². The table gives the worst exponent of each group over its families and backends.

The groups are addressed by these mechanisms:

  • Token-scan refinement of the classifier. Token alternatives that scan the same prefix again, and whitespace, comment or name scans that a failed alternative gives back to a continuation starting with the same characters, cost a bounded amount per position. They measure linear.
  • Units nested through a memoized recursion (open). Units that are not committing, nested through a memoized recursion, and a source reached again at one position through memoized calls, measure linear in the bundled grammars, but the memo does not bound them: in t = a t "!" / . t / "" with a = x+ and x = "x", the unit a t "!" is nested in itself through the memoized t, every rule that scans is memoized, and the cost is quadratic, since each restart calls a one position later. Re-evaluating the same calls at the same position (shared literals, continuation paths split at a shared call) removes few of these causes. Their linearity depends on how much input a failing unit examines, as in CEL, where a failing member examines only a constant amount at - before neg_unary calls member one position later; no condition captures this yet, and the causes stay reasons for the class Unknown.
  • Bounded-binding refinement of the classifier. A binding that reads its own earlier value is not exponential when its values come from a set bounded by a constant. Condition 1 exempts a variable with finite values: a bool, a variable bound only to constants, as YAML's context string c, or an int whose values reachable from its initial value form a finite set, each with at most 65536 values (Lemma 8). The product of the sizes of the sets is the bound on K that the class Linear reports, so a large constant is visible instead of being refused; the sets are admitted from the smallest up to a product of 2^32, and a variable left out loses only its own exemption. An int binding is evaluated when it reads only itself, literals and the lengths of captures bounded by a constant; any other binding is bounded by its guard, tests next to it with only predicates between, so that no value that a test rejects reaches a call or a later binding: {v := e} {lo <= v && v <= hi} or {lo <= e && e <= hi} {v := e}. The language has no declared ranges; a grammar states a range with the predicates it already has. The values that reach a binding are those after the earlier elements of its sequence, so the order matters: TypeScript's start rule sets its context flags ctx to 64 or 0 by a choice and then adds 2, which a closure over every value found would repeat without end, and its other bindings clear and set bits, adding len of the captures "*", "async" and list($m). The flags take 128 values, and the TypeScript class is the polynomial of its identifier scans. This also covers Python's isdict. Python's lv counts the format specs around a replacement field with lv := lv + 8192 in its format spec rule, and the nesting limit is tested in the replacement field that calls the rule, which bounds the field's own binding but not this one; the test {lv / 8192 <= 3} after the binding, which never fails, bounds it as well, and the classifier reports K of at most 32080. Python's ind, CUE's sv and YAML's n read the lengths of unbounded captures. For TypeScript the profile shows a constant number of evaluations per byte and at most four evaluations of a memoized rule per position at every nesting depth, so no exponential input exists. Memoizing across variable values that a rule does not read would lower a constant, not the order. A recursive call that follows consumed input does not bound the values: in main = (r / .)* $$ with r = "#" {v := v + 1} r / "y" {v >= 0}, each start reaches every later position with a different value of v, and the cost on n characters # is cubic.
  • Lambdas over bounded lists. A fold or map over a list with a constant bound on its number of elements runs its lambda a constant number of times, so condition 4 checks its copies as copies outside the lambda (Lemma 7). Python's parameter lists and dictionary displays fold over the / marker and a #repeat(,1) value, and they carry no cause; the corpus measures them linear. A bounded fold inside a map over a list that is not bounded still copies its outer values once for each element of that list, and a fold whose accumulator doubles stays exponential, since its factor is exponential in the bound. Whether an accumulator can double is decided by the step matrix of the fold: the size, the largest element and the number of elements of the value of the lambda, each bounded by terms in the same three quantities of the accumulator, times powers of the sizes of the values read from outside the fold and of the element of the step. Counting copies of the accumulator alone cannot tell foldl(list(), acc, (s, l) => list(l, l)), which keeps one element twice and does not grow, from foldl(list(), map(acc, (e) => list(e, "x")), (s, l) => concat(s, l)), which pads every element and doubles the number of elements on each step; the three quantities can. The matrix doubles the accumulator when a cycle of its graph has a coefficient above 1 or a factor of a size, or two cycles share a quantity. Otherwise it bounds each quantity by a polynomial in the input, and a value read from outside counts as large as its size degree allows on every step, while the elements of the step add up to the size of the list over all steps, so acc + text($c) grows quadratically and acc + text(y) linearly. The cost of the steps follows from the same terms, with comparisons and len of a string examining their operands, multiplied where a fold inside the lambda copies its own accumulator once for each of its elements, and a fold over a list that is not bounded is reported with its degree when that is 3 or more. The size degrees of the initial value, the list and the values read from outside come from what the classifier knows of them: an own value, at most a constant times the input its match consumes, has degree 1, and own values of distinct matches add up to the input; a value built by an action has the degree that the same forms give it from what it reads, through the rules it calls, so a rule that joins its whole text once for each of its elements has a quadratic value, and a fold that adds that value on each step costs n^4; a recursion whose values are not own has one more degree than one level adds when it holds each value of the recursion once, and no known degree otherwise. The same sizes bound the copies of elements in a lambda over a list that is not bounded: map(map($b, (q) => text($b)), (y) => y + "x") copies elements that add up to n^2 characters. The matrix is an upper bound: a term it does not follow, such as a block, counts as many copies of what it reads, and an exponential class may over-approximate. A fold inside lambdas over lists that are not bounded runs once for each of their elements, so each of them adds the size degree of its number of elements, except the innermost when the fold runs over its elements, those are own captures of a repetition, with no capture in a positive lookahead, and the list has size degree 1, so that their sizes add up to the input. The accumulator of a bounded fold is taken to hold what any number of steps can add, not at most the bound: a fold over #repeat(,1) that adds the value of the rule's own recursion on each step is reported exponential, though it runs at most once and holds that value once, which condition 4 classes polynomial.
  • Recovery-skip refinement of the classifier. A #recover skip whose unbounded repetitions are skip-run sites, with elements that examine a constant amount of the input, and which calls no rule and has no predicate, is not a scanning source: the walks of its sites evaluate their elements a number of times linear in the input plus a constant per walk (Lemma 9), whatever the width of an iteration. A skip that calls a rule stays a source, since a called rule can examine any amount of the input. The nested recovery s = ("(" s ")") #recover(skip=[a(]+) is then linear. minilang keeps a reason for its recovery: when a statement fails inside a block, its skip stops before the {, and the next statements parse the block again, which only the memoized stmt keeps linear.
  • Constant-cost text in the cost model. The cost model guarantees that the text of a node costs a constant in a whole-input parse and a Document, and that a string comparison costs at most its shorter operand, so the classifier does not count a text as a copy. The text of a recursive capture, as in Python's f-string replacement fields, is then linear, and a scan under a text (the body of a CUE string, a CUE name, a comment in the XML prolog, a DuckDB dollar-quote tag) is reported as the scan itself, which belongs to the token-scan groups or to the open groups of nested units.
  • Repetition-run reuse. duckdb's operator lookahead reads the run of + and - after an operator character, and a prefix operator at each character of the run reads the rest again. The run records make this linear on the engine backends, where SELECT + +^n + 1 costs 51.7k, 102k and 203k steps for 210, 410 and 810 bytes; a generated Go parser keeps none and spends 334k, 1.19M and 4.45M. The same repetition arises in the operator parts after an operand that prefix operators or a right-associative operator nest: each enclosing operator part tries them again where the nested operands end, and a skip that repeats one character class, which no record answers, scans the same whitespace each time. In CEL, -^n a and a?b:^n a followed by n spaces measure n² on a generated Go parser (the space group). minilang's skip repeats a choice, so it is a run site, and its families measure linear on the engine backends; a generated Go parser keeps no run records for it and measures them n², which the classifier, relying on no records, reports.
  • In-place fold accumulators. Python folds that copy their accumulator in each step (acc + "." + name, concat(acc, x)) are quadratic in the list length: a dotted import name of 2k, 4k and 8k bytes costs 2.07M, 8.15M and 32.3M steps. Extending the accumulator in place when the old one is dead makes them linear.
  • Grammar rewrites. Python's try_stmt maps its except* handlers inside a fold over the same handlers (1.63M, 5.78M and 21.6M steps for 6k, 12k and 24k bytes), and CUE builds the elements of an interpolation by a right recursion whose action copies the list of the rest at every level (1.26M, 4.70M and 18.1M steps for 4k, 8.2k and 17k bytes). Replacing the action of the CUE recursion with its tail alone measures 205k, 410k and 824k steps for the multi-line family, so a repetition with one flat concatenation is linear. The classifier reports this copy of a recursion's own value as a polynomial witness of degree 2 in each rule of the recursion, and in each rule that starts an interpolation, which copies the list of the rest once but counts as a copy of the recursion, because the rest is a value on a cycle of such values. CUE's plain multi-line strings test the indentation of each line in a fold that joins the closing indentation with U+10FFFF for every line. Every line that the fold reaches starts with the closing indentation, so the joins copy no more than the input and the families measure linear, but the classifier sees a copy of a value from outside the lambda for each element. Testing the indentation in the check that already tests strings with interpolations removes the fold.
  • Value-size refinement. Folds that read values of a recursion whose size the classifier does not bound: Python's keyword arguments and implicitly joined strings read the values of star_expressions, and TypeScript's union and intersection folds read values of a type recursion. TypeScript's families measure linear; Python's measure n² because of the accumulator copy of the in-place fold group.
  • Lookahead-capture refinement. A value that can hold a capture in a positive lookahead is not bounded by the input that the match consumes. TypeScript's JSX element names compare the capture of the opening tag with the closing tag, which is a false positive: each tag consumes its name right after the lookahead that captures it, and the families measure linear.
  • Unassigned groups. TypeScript's literals (the digits of a decimal literal and the characters of a string, read again by the alternative that follows) measure linear. DuckDB's block comments nest through a recursion in which the alternative that opens a comment is not committing against the one that consumes a character, so a run of /*x that is never closed measures n² (2.00 on the closure backend and the others); no mechanism is assigned to it yet.
Grammar Group Causes Addressed by Families Worst exponent Order
csv quoted-field 1 token-scan refinement 2 1.00 n
xml nested 3 open 3 1.02 n
xml prolog-misc 1 open 4 1.00 n
xml name-scan 4 token-scan refinement 3 1.00 n
xml ws-option 4 token-scan refinement 2 1.00 n
cel nested 19 open 6 1.00 n
cel names 1 token-scan refinement 2 1.00 n
cel space 2 repetition-run reuse 2 1.81 n²
cel number-tokens 5 token-scan refinement 2 1.00 n
cel string-tokens 2 token-scan refinement 1 1.04 n
outline nested 2 open 1 0.97 n
outline blank-lines 2 token-scan refinement 2 1.00 n
minilang recover 2 open 3 1.01 n
minilang nested-operators 1 open 2 1.99 n²
minilang nested-operator-parts 8 open 2 1.99 n²
golang nested 157 open 14 1.01 n
golang comments 16 token-scan refinement 7 1.01 n
golang identifiers 1 token-scan refinement 2 1.00 n
golang line-directives 4 token-scan refinement 2 1.01 n
golang numbers 3 token-scan refinement 2 1.00 n
duckdb nested 624 open 16 1.01 n
duckdb operator-tails 15 repetition-run reuse 5 1.96 n²
duckdb strings 4 token-scan refinement 5 1.00 n
python bounded-variables 2 bounded-binding refinement 5 1.01 n
python except-star-handlers 4 grammar rewrite 2 1.91 n²
python fold-copies 16 in-place fold accumulators 4 2.00 n²
python nested 146 open 11 1.03 n
python module-whitespace 4 token-scan refinement 1 1.00 n
python tokens 17 token-scan refinement 8 1.00 n
python whitespace 53 token-scan refinement 5 1.00 n
typescript nested 257 open 28 1.01 n
typescript identifiers 5 token-scan refinement 5 1.00 n
typescript whitespace-and-templates 2 token-scan refinement 3 1.00 n
cue hash-count 1 bounded-binding refinement 2 1.00 n
cue multi-line-indentation 1 grammar rewrite 2 1.00 n
cue string-bodies 6 token-scan refinement 5 1.00 n
cue interpolation-copies 10 grammar rewrite 0 – n²
cue file-clauses 2 open 2 0.99 n
cue nested 52 open 8 1.01 n
cue definitions 5 token-scan refinement 3 1.00 n
cue numbers 5 token-scan refinement 6 1.00 n
cue raw-strings 10 token-scan refinement 5 1.00 n
cue whitespace 12 token-scan refinement 5 1.00 n
yaml indentation-bindings 2 bounded-binding refinement 3 0.99 n
yaml nested 36 open 5 1.00 n
yaml block-scalars 4 token-scan refinement 3 1.00 n
yaml directives-and-tags 2 token-scan refinement 3 1.00 n
yaml scalars 4 token-scan refinement 4 1.00 n
yaml separation 15 token-scan refinement 6 1.00 n
yaml stream-prefix 1 token-scan refinement 1 1.00 n
duckdb nested-comments 1 unassigned 1 2.00 n²
python value-sizes 8 value-size refinement 1 1.97 n²
typescript literals 6 unassigned 2 0.99 n
typescript value-sizes 2 value-size refinement 2 0.98 n
typescript jsx-names 1 lookahead-capture refinement 2 1.00 n

No cause is inherent. Every group either measures linear on every family derived from its witnesses, or its super-linear cost comes from a construct of the grammar or the runtime (a restarted scan, a copied accumulator, a recursion that copies its own list, the nesting of block comments) that a linear formulation of the same language avoids. No family needs a budget beyond the linear one, so no group carries budget guidance.

Literature

Citations are from memory and are not verified against the publications; titles and venues should be checked before this record is accepted.

  • B. Ford. Packrat Parsing: Simple, Powerful, Lazy, Linear Time. ICFP 2002. Linear time when every nonterminal, including desugared repetitions, is memoized.
  • B. Ford. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. POPL 2004. Well-formedness implies termination. Emptiness of a PEG's language is undecidable.
  • A. Warth, J. Douglass, T. Millstein. Packrat Parsers Can Support Left Recursion. PEPM 2008. Seed growing. Linearity is not preserved in general.
  • S. Medeiros, F. Mascarenhas, R. Ierusalimschy. Left Recursion in Parsing Expression Grammars. Science of Computer Programming, 2014.
  • K. Mizushima, A. Maeda, Y. Yamaguchi. Packrat Parsers Can Handle Practical Grammars in Mostly Constant Space. PASTE 2010. Cut releases the memo table; cuts are inserted where first sets are disjoint.
  • K. Kuramitsu. Packrat Parsing with Elastic Sliding Window. Journal of Information Processing, 2015.
  • R. Grimm. Better Extensibility through Modular Syntax. PLDI 2006. Selective memoization with transient productions.
  • R. Becket, Z. Somogyi. DCGs + Memoing = Packrat Parsing, but Is It Worth It? PADL 2008.
  • N. Weideman, B. van der Merwe, M. Berglund, B. Watson. Analyzing Matching Time Behavior of Backtracking Regular Expression Matchers by Using Ambiguity of NFA. CIAA 2016. Exponential and polynomial degrees from ambiguity.
  • V. Wüstholz, O. Olivo, M. Heule, I. Dillig. Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions. TACAS 2017.
  • Y. Shen et al. ReScue: Crafting Regular Expression DoS Attacks. ASE 2018.
  • J. Davis, F. Servant, D. Lee. Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS). IEEE S&P 2021. Memoizing selected states gives linear-time backtracking; the closest analogue of this design.
  • T. Petsios et al. SlowFuzz, CCS 2017; C. Lemieux et al. PerfFuzz, ISSTA 2018. Worst-case input search.

None of these analyzes PEG grammars for super-linear behavior. The regex results transfer in shape: a polynomial degree comes from nested scanning constructs that can restart inside each other, as in E1 and E7, and that degree is what Poly(k) reports. Ordered choice and greedy repetition remove the ambiguity within one construct that drives regex blow-ups. That leaves unmemoized re-entry and diverging state as the exponential sources.

Decisions

  1. The specification promises a bound only for certified grammars. A parse of a grammar that the classifier certifies as linear has a cost proportional to the input length. Other grammars carry no promise beyond termination. The classifier's soundness is therefore normative. The alternatives were no promise, which leaves users nothing to check, and a promise for every grammar, which restarted left-recursion growth and Operators Rule folds make impossible.
  2. super-linear is a hint, shown only on request. The lint contract requires a warning to be certain, and a Poly or Exp verdict may be pessimistic. The finding carries the witness path. Because many grammars that work well on real input are classified Poly, the hint and the verdict appear only with sxir lint -classify or lint.Config.Classify, and a default lint run stays free of estimates. growing-variable is certain and stays on.
  3. Run reuse is on by default. Recording is deferred until a site restarts inside an earlier run, and an optimization control disables it, as the memo has. It is adopted only if the corpora and benchmark grammars, which never restart inside runs, show no slowdown. Without that evidence it stays behind the control.
  4. Memory has no bound beyond cost. Budget bounds memory linearly. A memo-entry cap with eviction, which is semantically safe except for growing seeds and Documents, is reconsidered when a Document or stream workload shows memo memory as the limit. A byte budget for values is not added. Record 066 revises this decision: a memory measure bounds what the parser holds, beside the compute measure.
  5. The automatic budget uses c_G times a safety factor. The factor is documented, and the caller can override c. For grammars that are not certified linear, the caller must give c. A corpus-measured constant was rejected because it is wrong for unusual grammars.
  6. Restarted left-recursion growth and Operators Rule folds are classified and budgeted. E6 and E10 stay Poly(2), reported with a witness and bounded by the budget. Reusing end positions in recognition mode was rejected: it would be linear only without values, and would add a second growth path to maintain.

Limitations

  • The classifier is sound only in one direction. A Poly or Exp verdict may have no slow input.
  • The soundness argument is a proof sketch. The regression and differential tests check it; it is not mechanized.
  • The constant c_G is in the units of record 076, which are the same on every backend, and depends on the constants of that record's table, so a change of the table changes the budget between releases.
  • The citations in the Literature section are unverified.