Rewrite a Grammar to Linear Cost

Problem. sxir lint -classify reports that the cost of a parse grows faster than the input, or a grammar declared @linear does not compile, and you want the grammar to cost the same per character on a long input as on a short one. You need, for each cause the specification names, a rewrite, its measured effect, and what it changes in the parse.

Find the cause in the witness that the linter prints, find its row in the table, and apply the rewrite of that section. Each section shows the grammar that grows, the grammar that replaces it, the cost of both, and what the replacement changes. A rewrite that accepts the same language can still change the tree; the sections say how. One pattern has no rewrite that keeps the result.

Cause Class reported Rewrite What changes
A repetition restarted after backtracking polynomial Scan once: put the scan and what may follow it in one alternative The elements of the repetition
A lookahead over a scan polynomial Check once after the scan instead of at every iteration Where the repetition is split
A recovery skip followed by failure polynomial Write the repetition inside skip= Nothing
A left-recursive rule or an Operators Rule called again and again polynomial Call the rule once at a position: factor the caller The tree of runs the choice used to split
Diverging variable bindings exponential Bind a value that does not depend on the earlier value What the variable holds
Self-growing values exponential Count instead of doubling No rewrite keeps the value

Every input in the sections is the character the section names, repeated n times, except where it says otherwise. The cost is the number of steps that compute limits count, measured on the closure backend; the bytecode backends give the same orders. The steps do not depend on the machine.

The closure and bytecode backends keep run records for a repetition that a parse walks again from a position inside an earlier walk, so the first two patterns, which restart such a repetition, cost linear steps there even before the rewrite. The linter classifies a grammar from the grammar alone and does not count those records, and generated Go parsers keep none, so the class reported and the cost of a generated parser are those of the rewrite's original. The rewrites also cost fewer steps on the interpreting backends.

A Repetition Restarted After Backtracking

// scan.sxir
@start
rule main = (a / "a")* $$

rule a = "a"* "c"

On a repeated n times, every iteration tries a, which scans to the end of the input, finds no c and fails; the alternative "a" then takes one character and the next iteration scans again. The memo shares the result of a at one position, not the scan between positions. The linter reports the cost from start rule main is polynomial (n^2).

Make one alternative cover a whole run of a and the c that may follow it:

// scan-fast.sxir
@start
rule main = item* $$

rule item = "a"+ "c"? / "c"

The linter reports the cost from start rule main is linear.

n 100 200 400
scan.sxir 3,078 6,178 12,378
scan-fast.sxir 616 1,216 2,416

What changes. The two grammars accept the same strings of a and c. The elements of the repetition differ. In scan.sxir an a that no c follows is an element by itself, so a run of a is one element for each character, and a run followed by c is one element. In scan-fast.sxir every run of a, with the c that follows it if there is one, is one element, and so is a lone c. A tree that must have one node for each a cannot come from this rewrite.

A Lookahead Over a Scan

// look.sxir
@start
rule main = ("a" !rest)* "a"* $$

rule rest = "a"* "c"

The lookahead !rest scans the rest of the run of a at every iteration, so the loop costs the sum of the lengths of the remainders. The linter reports polynomial (n^2). When the lookahead scans the input that the loop consumes anyway, the question it asks is a question about what follows the run, and one check after the run answers it:

// look-fast.sxir
@start
rule main = "a"* !"c" $$

The linter reports linear.

n 100 200 400
look.sxir 2,078 4,178 8,378
look-fast.sxir 608 1,207 2,410

What changes. Both grammars accept the same strings. In look.sxir the lookahead decides where the first repetition ends and the second begins; in look-fast.sxir the run is one repetition. A grammar that needs the two parts as separate nodes keeps its lookahead, bounded to what it must see, a literal or one character, which costs a constant.

A Recovery Skip Followed by Failure

A #recover skip that is a repetition written in the skip expression is already linear: the walks of the skip share the rest of the input they have walked. Only a repetition that a skip reaches through a rule is not shared.

// skip.sxir
@start
rule main = (x / "a")* $$

rule x = (y #recover(skip=s)) "c"

rule y = "b"

rule s = [a]+

Each x fails at y, skips the rest of the run of a, then fails at "c", and the recovery is abandoned; the next iteration starts one character later and walks the run again. Write the repetition in the skip expression:

// skip-fast.sxir
@start
rule main = (x / "a")* $$

rule x = (y #recover(skip=[a]+)) "c"

rule y = "b"
n 100 200 400
skip.sxir 13,648 47,392 174,976
skip-fast.sxir 4,504 9,112 18,304

What changes. Nothing: the skip matches the same text, so the tree, the errors and the extent of the recovery are the same. The linter reports polynomial (n^2) for skip.sxir and linear for skip-fast.sxir. The repetition must have no upper bound and no #cut that applies to the repetition, and neither it nor the rules it calls may read a variable or contain a #recover. The linter counts the skip as linear only when it calls no rule and has no predicate, and each iteration of its repetition examines at most a constant amount of the input, as a character class does.

A Left-Recursive Rule or an Operators Rule Called Again and Again

// lr.sxir
@start
rule main = (e "q" / "x")* $$

rule e = e "x" / "x"

A left-recursive rule grows to the end of the run of x where it is called. Here e "q" fails at the end of the run, the alternative "x" takes one character, and e grows again from the next one. The linter reports polynomial (n^2), and so for an Operators Rule with the same shape:

// ops.sxir
@start
rule main = (e "q" / "x")* $$

rule e = #operators {
    operand "x"
    level add { infix left "" }
}

The rules are not the problem: called once at a position, each is linear. The caller calls them once for each character. Factor the choice so that e is called once and the part that varies follows it:

// lr-fast.sxir
@start
rule main = (e "q"?)* $$

rule e = e "x" / "x"
// ops-fast.sxir
@start
rule main = (e "q"?)* $$

rule e = #operators {
    operand "x"
    level add { infix left "" }
}
n 100 200 400
lr.sxir 48,160 186,496 733,696
lr-fast.sxir 1,141 2,242 4,444
ops.sxir 21,232 82,432 325,120
ops-fast.sxir 614 1,216 2,416

What changes. The grammars accept the same strings. The associativity of e is unchanged: it is still the rule that groups to the left. What changes is where the groups end: in the original, a run of x that no q follows is read one character at a time by the alternative "x"; in the rewrite it is one e that groups the whole run. A grammar that needs those characters as separate nodes cannot use this rewrite.

Diverging Variable Bindings

// var.sxir
var v string

@start
rule main = r $$

rule r = "(" {v := v + "0"} r ")" "y" / "(" {v := v + "1"} r ")" "z" / "n" {len(v) >= 0}

Both alternatives of r bind v from its earlier value before the recursive call, so the two calls at a position see different values of v, and the memo shares neither result: the cost doubles with each level. The linter reports the cost from start rule main is exponential, with a witness at the binding. Bind a value that does not depend on the earlier one:

// var-fast.sxir
var v string

@start
rule main = r $$

rule r = "(" {v := "0"} r ")" "y" / "(" {v := "1"} r ")" "z" / "n" {len(v) >= 0}

The linter reports the cost from start rule main is linear-env: linear, given a bound on the values the variable takes (two here).

When the variable must depend on its earlier value, bound it with a test right after the binding, with only predicates between them: in "(" {d := d + 1} {d <= 3} r ")" the test rejects a value before any call sees it, so d takes the values 0 to 3 and the linter reports linear (K <= 4) for an int variable d read at the bottom. A test before the binding of the same expression, {len($x) < 10} {n := len($x)}, bounds it too. The test changes the language when it can fail on an input that the grammar should accept.

input: ( n times, n, then )z n times n = 4 n = 8 n = 400
var.sxir 3,352 1,512,448 stopped at 20,000,000
var-fast.sxir 428 896 46,816

What changes. In var.sxir the variable is the path from the root to the current level, handed down the recursion; in var-fast.sxir it is the marker of the innermost level only. No rewrite keeps both the path and the cost when a decision at the bottom reads the path, because the decision then depends on the whole path, and results that depend on different paths cannot be shared. If the decision can wait until the recursion returns, return the information in the rule's value and decide in an action after the call, where the value of each level is built from its child's, once.

Self-Growing Values

// grow.sxir
var s string = "a"

@start
rule main = r $$

rule r = "x" {s := s + s} r / {len(s) > 0}
// fold.sxir
@start
rule main = xs:"x"* => len(foldl("a", $xs, (acc, x) => acc + acc))

A value built from its own earlier value by s + s doubles at every step, so after n steps it has 2^n characters and building it takes that many steps. The linter warns growing-variable about the binding of grow.sxir and reports the class exponential for both grammars. No rewrite keeps the result: a string of 2^n characters cannot be built in a number of steps that is linear in n. If what the grammar needs is a property of the value, such as its length, or a count, keep that property instead:

// grow-fast.sxir
@start
rule main = r $$

rule r int = ("x" n:r => $n + 1) / ("" => 0)
// fold-fast.sxir
@start
rule main = xs:"x"* => foldl(0, $xs, (acc, x) => acc + 1)
n 4 8 400
grow.sxir 205 1,690 stopped at 20,000,000
grow-fast.sxir 109 145 3,676
fold.sxir 209 1,768 stopped at 20,000,000
fold-fast.sxir 89 173 8,416

What changes. The value is a count, not a string. grow-fast.sxir carries the count in the value of the rule, which each level builds from the value of the level below, once; a variable cannot do that, because a binding in a called rule is not visible to its caller, so a binding after the recursive call ({k := k + 1}) counts nothing across levels.

Expected Output

Save the grammars under the file names in their first lines and classify each:

sxir lint -g scan.sxir -classify
sxir lint -g scan-fast.sxir -classify
scan.sxir:5:10: hint: the cost can grow as n^2: after the alternative at 3:14 in rule main fails, the later alternative "a" at 3:18 in rule main can start again inside the input that the repetition "a"* at 5:10 in rule a examined; this repeats in the repetition (a / "a")* at 3:13 in rule main [super-linear]
scan.sxir: the cost from start rule main is polynomial (n^2)
	witness: scan.sxir:5:10: the cost can grow as n^2: after the alternative at 3:14 in rule main fails, the later alternative "a" at 3:18 in rule main can start again inside the input that the repetition "a"* at 5:10 in rule a examined; this repeats in the repetition (a / "a")* at 3:13 in rule main
scan-fast.sxir: the cost from start rule main is linear
	budget: at most 20 * n + 22 compute units for an input of n position units (derived; not applied as the default limit)

How It Works

  • The memo shares the result of a rule at one position. It does not share the cost inside a rule body or between positions, so a scan that runs again from a later position pays again, except where a run record covers it (closure and bytecode backends, repetitions that a parse restarts). The rewrites for repetitions, lookaheads and called rules make every position scan at most once.
  • Left recursion and Operators Rules are linear when called once at a position. The growth restarts when the caller fails after the rule has grown and tries the same position range again.
  • A rule that reads a variable is memoized per value of the variables it reads. Rewrites that keep the number of values bounded, a literal or a count, keep the memo effective.
  • Values that grow from their own earlier value cost their size, whatever the memo shares.

Variations and Limits

  • The measurement depends on the input shape. These inputs are the worst case of each pattern; a real input may not trigger the growth, and the class that the linter reports is an estimate with a witness (see Classifying the Parse Cost).
  • A rewrite changes only what the section says. Compare the trees of the old and the new grammar on real inputs before replacing one with the other; the testing guide shows how.
  • The runtime does not share the scan of a repetition between positions, so the first two patterns need the rewrite. Recovery skips written in the skip expression, a left-recursive rule called once at a position, and right recursion are already linear and need none.
  • To find which rule spends the steps in a real grammar, use sxir profile; see Find Out Why a Grammar Is Slow.