130. Memoizing the Members of Left-Recursion Cycles

  • Status: Implemented
  • Date: 2026-10-31

Problem and Mechanism

The rules of a left-recursion cycle other than its leader used to be evaluated at every call. With

main = A $$
A = C "+" / "n"
C = "(" C ")" "y" / "(" C ")" "z" / A

and the input ( n times, n, )z n times, each call of C at a position evaluates C at the next position through two alternatives, so the evaluations double with each level: 2^n on every backend. The same grammar with A = "n" is linear, because C is then memoized.

A member of a cycle is memoized like any other rule. While leaders of its cycle grow at its position, its result depends on the growths there, and the parser records what it depended on so that every reused result equals the result of an evaluation:

  • The context of a call. The context of a call of a rule of a cycle is the run of growths of that cycle at the call's position: the leaders that grow there and the seeds they have reached. Growths of other cycles do not matter, since the call reads none of their seeds, and neither do growths at other positions. A call of a leader that grows at its position reads the seed. A leader that does not grow there grows from failure, with the seeds of the context visible.
  • What a result depends on. A call records the seeds it read, each by its identity, a number that the growth step that produced the seed gives it; for each lookahead whose evaluation read a seed and that leaves nothing after it but its outcome, that outcome and its examined range, in place of those seeds; and the present set, the leaders that grew at the position, one bit each for the leaders of a cycle that a word holds (63 in the engine, 31 in generated parsers), or, where a leader has no bit, a number that the parser gives the set's words of bits. A positive lookahead whose expression makes a capture or binds a variable outside the rules it calls, or that matches after recovering from an error, leaves more than its outcome, so the seeds it read count as read by the call.
  • Where a result goes. A result that read no seed and observed no lookahead goes to the memo with its present set, and answers a call in any context whose leaders it includes. Any other result goes to the table of its context, which lasts while the first growth of the context lasts, and answers a call in a context with the same present set where the seeds it read have the same identities and the lookaheads it observed have the same outcomes. A memo entry holds a word of bits, so in a context whose present set is a number, every result goes to the table of the context and no memo entry answers a call.
  • Growths in a context. A growth in a context memoizes its steps in the table, with its own seed among the seeds a step reads, and records runs of steps that read no seed but their own as jumps: from each seed of the run, the seed at its end, with the observations, expectations and examined input of the steps. A later growth of the leader in the same context takes a run at once when each lookahead that the steps observed has the same outcome now and that outcome read no seed of the leader, so that it holds for every seed of the run. The jumps from a seed are a list scanned in order, and the first that holds is taken; a jump is not added after one whose observations are among its own and that was recorded inside a lookahead only if the new one is, since that one is taken wherever the new one would be. Equal step results of a leader at a position get the same identity, so a result keyed by an earlier seed matches a later equal one.
  • Reuse passes on what the result read. A reused result passes on to the calls around it the seeds it read with their current identities, and for each lookahead it observed, the seeds that the lookahead's outcome read in the current context, as an evaluation there would.

The leaders keep their own memoization. The engine, the generated Go runtime (untyped and typed, with and without the Exec IR compositions) and the TypeScript runtime implement the same rules. The compiled program numbers the cycles (Cycle in the rule table and the rule flags of generated code), so finding the context of a call is a scan of the growths at its position. Documents add a rule across parses: no result that read a seed reaches the memo of a later parse (see Correctness and Tradeoffs).

In the example, C at the next position is reached from the growth of A at the earlier one, but outside the growth of A at the next position. It reads no seed, is stored by its first evaluation with an empty present set, and the second alternative reuses it.

Applicability

Execution profile Applied / Partial / Not applied / Not applicable Reason
Closure, bytecode, iterative bytecode Applied One shared call-end rule and context tables in the engine
Generated Go, ordinary and budget-controlled Applied The call paths, growths and context tables of the runtime, and the same steps in the Exec IR compositions
Generated typed Go Applied The TParser call paths and growths share the context tables
Generated TypeScript Applied callBody, grow and the context tables of the runtime
Documents Applied Results in the memo are reused across parses; results in a context table are dropped with the table

A member that is called from one place is still transient, so a grammar like the left-recursive calculator (add, mul) keeps its call code; its generated parsers only carry the cycle numbers of those rules.

Reproduction

Base 430194ee, Go 1.27.1, Apple silicon, benchlock. Test binaries of the bench package, one per revision, ran interleaved for 10 rounds with -benchtime=200ms -benchmem over the generated forms of Parse and Recognize (left-recursive calculator, JSON, Minilang), Incremental, IncrementalLong and Stream; benchstat compared them. Tests: TestLeftRecursionDependencyMemoRandom, TestLeftRecursionDependencyMemoControls, TestLeftRecursionDependencyMemoUnexamined, TestLeftRecursionDependencyMemoLinear, TestLeftRecursionDependencyMemoDefaultBudget, TestNestedLeaderResultNotReused, TestLeftRecursionMemberMemoLinear, TestLeftRecursionMemberMemoMatchesNoMemo, TestLeftRecursionMemberMemoStale, TestLeftRecursionMemberMemoRandom, TestLeftRecursionMemberMemoRandomRecovering, TestGeneratedLeftRecursionDependencyMemo, TestGeneratedLeftRecursionDependencyMemoControls, TestGeneratedLeftRecursionDependencyMemoLinear, TestGeneratedLeftRecursionMemberMemoLinear, TestGeneratedLeftRecursionMemberMemoStale, TestGeneratedTSLeftRecursionDependencyMemo, TestGeneratedTSLeftRecursionDependencyMemoControls, TestGeneratedTSLeftRecursionDependencyMemoLinear, TestGeneratedTSLeftRecursionMemberMemoLinear, TestGeneratedTSLeftRecursionMemberMemoStale, TestDocumentLeftRecursionMemberReparse, TestDocumentLeftRecursionMemberReparseRandom, TestGeneratedDocumentLeftRecursionMemberReparse and their controls.

Results

Rule evaluations on the example (Profile.Evals, the same on the three engine backends):

n 8 16 32 64
Two members (A, C) 25 41 73 137
Four members, two call sites each 85 149 277 533

Before the change the example runs out of the default budget (2^20 units) at n = 16. After it, generated Go (ordinary and controlled, untyped and typed) and generated TypeScript parse n = 300.

Speed (medians of 10 interleaved samples against the base; differences within noise unless noted):

Workload Change
Parse, left-recursive calculator +6.0% (p < 0.001) on generated typed ParseValue, +2.5% in code points and +2.8% in bytes (p = 0.003)
Recognize, left-recursive calculator +5.6% (p < 0.001)
Parse and Recognize JSON and Minilang +2.2% to +3.5% (p ≤ 0.001) on Minilang; JSON ParseValue 1.2% faster; the other JSON cells within noise
Incremental (Minilang), IncrementalLong (CSV), Stream (CSV) within noise, except a fresh generated Minilang parse +2.3% (p < 0.001), iterative +0.5% and closure IncrementalLong +0.6%, a generated Minilang Document parse 2.7% faster and closure Stream 1.0% faster

The cost on the calculator comes from the bookkeeping of each growth: a record of the growth in progress, the search of the context of every call of a rule of a cycle at the position of a growth, and the present set stored with each result. The calculator has no growth inside another at one position, so it records no dependency and keeps no context table. Bytes per operation fall on the calculator (−2.0% in code points, −5.0% for ParseValue, −20% for Recognize), since a growth step writes its result in place of allocating a memo entry. Allocations are unchanged except 3 more per ParseValue on the calculator (1%), and one more per operation for the closure Document of Incremental and for IncrementalLong on the engine backends; generated Recognize on the calculator allocates 21 to 23 times per operation depending on how many iterations -benchtime=200ms runs, as the setup of the run is divided by that count. The memo entry of the generated runtimes stays at 128 bytes: the present set takes the place of the depth and the unstable mark.

Correctness and Tradeoffs

Memoization proves that a reused result equals the result of an evaluation in the current context: a result in the memo read no seed and observed no lookahead that read one, so the growths that its present set includes do not change it; a result in a context table is reused only where every seed it read has the same identity and every lookahead it observed the same outcome and examined range, and the identities of equal step results are equal only when the results are. Two step results with the same end are not equal when they differ in the rule that produced a node. In

main = A $$
A = C / "a" / C / "b" C C
B = B "b" / A "a" / C / "a" "a"
C = B A / &A "a" "c"

with the input aaa, B at 0 grows to ("a" "a")@B, and inside the growth of A there, with the seed "a"@A, to ("a"@A "a")@B, which ends at the same offset. Giving both the same identity reuses the first where the second belongs, and the tree loses the rule of its first leaf.

Five more shapes show what the other rules exclude. In

main = S $$
S = M P S "q" / "y" ("qqqqqqqq")?
P = M ""
M = &(x:S) => $x
U = P P

the capture that the lookahead of M makes holds, after the lookahead, the seed it read. Reusing a call of M by the outcome of its lookahead returns an earlier seed: on yqqq a node ends at 2 instead of 3. The same grammar with M = &(S (("!") #recover(skip=[q]))) "" reuses an error recovered at the end of an earlier seed, and the same grammar with

var v int
M = &(S ("qq" {v := 2} / "q" {v := 1} / {v := 0})) (({v == 2} => "two") / ({v == 1} => "one") / ("" => "zero"))

reuses a binding that depends on the seed the lookahead read: on yqqq a node of M holds two instead of one. In

main = T $$
T = &S S "!" "z" / S "q" "!" "z" "#" / T "!" / "yqq!z#@" / "yqq"
S = &L S "q" / "y"
L = T "!" / &T S "q" "q"

the lookahead &L reads only T while the seed of T is yqq, and also the seed of S once it is yqq!z. A run of S recorded under the first seed of T is checked under the second only for the first seed of S, where &L still matches; taking it skips a step where &L fails, and yqq!z# does not parse. In

main = O $$
O = &O &L L "o" / &O L "q" "o" "!" / "yz"
L = M L ("z" / "q") / "y"
M = &(L "z" / &L O "q")
U = M M

L grows twice while the seed of O is yz, first inside &L. The second growth reuses the call of M made under the seed y of L, where its lookahead read only L, under the seed yz, where the outcome memoized for the lookahead also read O. A reuse that passed on only the seeds the lookahead read where the call was made would leave the call of L independent of O, and reusing it once O is yzqo rejects yzqo!. Last, a reused result that passed on the seed identities that its lookaheads read where it was made, instead of the current ones, let a result around it be kept under identities it did not read: random recovering cycle grammar 2964 then rejects baabcac where generated parsers and the engine without examined ranges must accept it.

The engine records the input that every evaluation examines, because its traces report it, so equal step results and equal lookahead outcomes also need equal examined ranges there. Generated Go and TypeScript parsers record it only in Document parses and observed parses, whose traces report it; elsewhere they take a step or reuse an outcome that differs only in its examined range, which the engine evaluates again. The results are the same, and those parses report no traces whose evaluation counts could differ. The tests that compare the traces of generated parsers with the engine's therefore compare them with the engine as it is. A test option of the engine leaves examined ranges out, as an unobserved generated parse does, to check that the results do not depend on them.

A differential test compares every engine backend with the engine's reference that evaluates every call in a context again, on the random grammars of 800 seeds: for each seed, a grammar of cycles with several leaders and members, read inside and outside lookaheads, the same with cuts, and one whose items recover errors. Generated Go (untyped and typed, with and without the Exec IR compositions, ordinary and budget-controlled) and generated TypeScript are compared with the engine on the grammars of the first 60 seeds, and each check broken in turn is detected on every implementation: a reuse that ignores the identities of the seeds read, one that ignores the observations, a memo result reused whatever its present set, equal step results given one identity without comparing them, a jump over observations whose outcomes read the growing seed, a reuse that passes on the seeds its observations read where it was made with the identities they had there, one that passes on those seeds with their current identities but not the seeds that the current outcomes of its observations read, and an observation of a lookahead that recovered errors. The grammars above are among the compared grammars on every implementation. The grammars of the first 120 seeds detect every broken check but the second broken replay, which only the grammar of the reused observation above detects. The engine detects the first broken replay with the test option that leaves examined ranges out, as generated parsers do, and the second only with that option. A wider sweep, run once, found no difference: the grammars of seeds 800 to 3,999 on every engine backend, with and without examined ranges (9,173 grammars), and the grammars of the first 600 seeds with generated Go and generated TypeScript (1,734 grammars, 103,812 TypeScript results).

A result that read a seed is kept in the table of its context, never in the memo, and the table is dropped when the first growth of its context ends, so no such result reaches a later parse of a Document. A Document parse that reused one would depend on the order in which its parse evaluated the calls: on the seed grammars 117 of RandomCycleGrammar and 5077 of RandomRecoveringCycleGrammar, a runtime that also puts the results of the context tables in the memo gives another tree and other syntax errors on the second parse of an unchanged Document than on the first. Tests parse Documents of the member grammars, the seed grammars and random cycle grammars twice without an edit and after deleting and inserting again each character, on every engine backend and with generated Go (untyped and typed, ordinary and budget-controlled, with and without the compositions), and compare each outcome with a parse from scratch; their controls detect the difference on both seed grammars. A second parse of an unchanged Document on the left-recursive calculator or on the member example evaluates no rule body.

The dependency bookkeeping charges the budget for each dependency recorded and each table lookup and store. On the random grammars, against the reference that evaluates every call in a context again (closure backend, inputs that neither stops at a limit):

Corpus Budget units Reference units Difference Evaluations Reference evaluations
400 random cycle grammars 2,834,471 2,820,502 +0.5% 116,728 195,277
800 recovering cycle grammars 7,981,622 9,881,280 −19% 302,413 492,099

A grammar without leaders that grow inside each other at one position records nothing: a call of a rule of a cycle where no growth of its cycle is in progress at its position stores its result in the memo with an empty present set.

Decision and Limits

Adopted on every backend. A growth that begins from a result that includes the seed of another growth at its position is new in each step of that growth; when it covers the input that later steps cover, it covers it again in each step, which Conditions for Linear Cost excludes as condition 5. A set of more than six seeds and observations keys its results by the values of the first six and the bytes of the others, in a second map. In a parse with missing-token insertion, a rule that contains #missing, directly or through the rules it calls, keeps no result in a context. The rules of a cycle call each other, so either all of them contain it or none does: a cycle that inserts tokens evaluates its results again on every call, as without this mechanism, and any other cycle keeps them as in a parse without insertion. The jumps from a seed are a list that a growth scans for one whose observations hold. In a shape where every step reads a successful lookahead over another leader (S = &R S "q" / "y", R = &S R "q" / "y" on y and n q), each step records a jump from the same seed that differs from the earlier ones only in the identities of other seeds that it replays. Recording all of them would make the scan quadratic: generated Go would parse n = 1,000, 2,000 and 4,000 in 19, 71 and 274 ms, and the engine would run out of the default budget from n = 793. Leaving out the jumps that an earlier one shadows keeps the list from growing with n: the times are 2.4, 4.8 and 9.6 ms in generated Go, 3.8, 7.6 and 15 ms in the engine and 4.2, 8.8 and 19 ms in generated TypeScript, and the engine parses n = 100,000 within the default budget. A list still grows with jumps whose observations have different outcomes, one for each combination of outcomes that occurs. Not measured: grammars with many members called from several places, where memoization could cost more than it saves, as no example grammar of the repository has them.