Lesson 4.6 — Error-resilient and incremental parsing¶

Techniques: resilient LL parsing with recovery sets (rust-analyzer; Kladov 2023), error nodes vs error productions (yacc's error token, Johnson 1975), incremental LR parsing with subtree reuse (Wagner & Graham 1998; tree-sitter), block-level reparsing with persistent trees (rust-analyzer; the lab's ★ item-level reparser) · Pebble implements: multi-error recovery in the parser (exercises E5–E6, pebble-spec §13.1) and ★ item-level incremental reparsing (lab L6) · Prerequisites: Lesson 2.7 (panic mode, phrase level, repair), Lesson 3.7 (LR recovery) · Time: 3 hours

A batch compiler may stop at the first syntax error; an editor may not. While you type let x = 1 +, the language server must still know where fn g starts, what its parameters are and which completions fit — on every keystroke, in milliseconds. That asks two things of the parser: it must turn any text into a useful tree (resilience), and it must turn the previous tree plus a small edit into the new tree without starting over (incrementality). Chapter 2 and 3 gave the recovery methods of batch parsers; this lesson shows how IDE-grade parsers organize recovery around the tree, and how they reuse work across edits.

1. Problem and motivation¶

The problem. (a) Resilience: for every token sequence, produce a tree that contains every token, marks the erroneous regions, and keeps every well-formed construct intact, together with a list of errors without cascades. (b) Incrementality: given the tree for text \(x\) and an edit \(x \mapsto x'\) (replace a range by new text), produce the tree for \(x'\) in time proportional to the size of the change, not of \(x'\).

Resilient LL parsing¶

Hand-written recursive-descent parsers recover by panic mode (Lesson 2.7): skip to a synchronizing token. rust-analyzer's parser turns this into a discipline [Kla23]: parsing functions never fail; at each loop that parses a list (items, statements, arguments, fields) the parser either sees a token that can start an element, or a token in the loop's recovery set (something an enclosing construct handles: }, fn, let), in which case it stops, or anything else, which it wraps in an ERROR node and skips. Every token ends up in the tree, errors are reported where they are, and a missing } never swallows the rest of the file. pebblec's parser follows the same rules (pebble-spec §13.1).

Error nodes vs error productions¶

There are two ways to represent a syntax error in the output. yacc's error productions [Joh75] (stmt : error ';') put recovery into the grammar: the LR parser pops states until one can shift the special error token, then discards input until it can continue (Lesson 3.7). Error nodes put it into the tree: the parser builds an ERROR node (rust-analyzer, tree-sitter, Roslyn's skipped-token trivia, pebblec's ErrorExpr) wherever the input does not fit, and the grammar stays clean. The first is natural for generated LR parsers, the second for hand-written parsers and lossless trees.

Incremental LR with subtree reuse¶

Tim Wagner and Susan Graham's incremental LR parser [WG98] (from the Ensemble environment at Berkeley) keeps the previous parse tree, marks the nodes on the path to the edit as changed, and reparses by shifting whole unchanged subtrees as if they were single tokens whenever the parser state allows it, breaking a subtree down to its children when it does not. Max Brunsfeld's tree-sitter [TS-Reuse, Bru18] applies the same idea to a GLR parser with error recovery; it powers syntax highlighting and code navigation in GitHub, Neovim, Zed and Helix.

Block-level reparsing¶

rust-analyzer uses a simpler scheme [RA-Reparse]: if the edit stays inside one token that relexes to a token of the same kind, only the token is replaced; otherwise it finds the smallest enclosing {…} block whose new text is still bracket-balanced, reparses just that block, and splices the new green node into the old tree, sharing every other node (persistent "red–green" trees, Lesson 4.7). The lab's ★ milestone L6 does the same at the granularity of Pebble's top-level items.

2. Definitions and algorithms¶

Resilient LL parsing¶

Definition 4.6.1 (Resilient parse, error node)

A parser is resilient if for every token sequence \(t_1 \cdots t_n\) it returns a tree whose leaves, read left to right, are exactly \(t_1 \cdots t_n\) (every token belongs to the tree), in which each maximal region the grammar cannot derive is under an error node (a node of kind ERROR, or an ErrorExpr-like placeholder when an expected piece is missing), together with a list of diagnostics, each attached to a position.

Definition 4.6.2 (Recovery set of a loop)

For a list loop in a parsing function (a block's statements, a parameter list, the items of a file), its FIRST set is the set of tokens that can start an element, and its recovery set \(R\) is a set of tokens that some enclosing parsing function can use: closing delimiters of enclosing brackets and the starting keywords of enclosing constructs. In pebblec: statements recover at }, statement keywords and item keywords; items at fn, struct, extern (pebble-spec §13.1 rule 5).

Algorithm 4.6.3 (Resilient list loop)

Input: the current token position; FIRST set \(F\) and recovery set \(R\) of the list; the closing token \(c\) (or eof).
Output: a list node whose children cover every token up to \(c\) (or up to a token of \(R\)), with error nodes for tokens that fit neither.
Precondition: the element parser consumes at least one token when it is started on a token of \(F\); \(c \in R\).
Postcondition: the loop stops at \(c\), at a token of \(R\) (left for the caller), or at eof; no token before that point is outside the list node.
Invariant: every iteration consumes at least one token or ends the loop (Theorem 4.6.9).

function ParseList(F, R, c):
    open a LIST node
    while not at(c) and not at(eof):
        if look ∈ F:
            ParseElement()                     # itself resilient; never fails
        else if look ∈ R:
            break                              # an enclosing construct takes over
        else:
            error("expected an element")       # report once, at this token
            open an ERROR node;  bump();  close it         # err_and_bump
    expect(c)                                  # "expected '}'" if missing, with a note at the opener
    close the LIST node

Inside an element, a missing piece (an expression after =) is reported at the current token and represented by an empty error node without consuming (err_recover when the token is in the recovery set); the element then continues, so let x = ; still yields a let with an error initializer.

rust-analyzer's resilient parse of two broken statements

Reproduce (rust-analyzer 1.94.1, rustup component add rust-analyzer):

printf 'fn f() {\n    let x = 1 +;\n    foo(;\n}\nfn g() {}\n' > broken.rs
rust-analyzer parse < broken.rs | grep -E 'ERROR|SEMICOLON|LET_STMT|CALL_EXPR|ARG_LIST|R_CURLY|^  FN'

Output (complete):

  FN@0..37
        LET_STMT@13..25
            ERROR@24..25
              SEMICOLON@24..25 ";"
        CALL_EXPR@30..35
          ARG_LIST@33..35
            ERROR@34..35
              SEMICOLON@34..35 ";"
        R_CURLY@36..37 "}"
  FN@38..47
        R_CURLY@46..47 "}"

What to notice: each ; that no rule could use became an ERROR node exactly where it is (Algorithm 4.6.3's err_and_bump); the let statement and the call are still there with their parts, the block still ends at its own }, and fn g is intact at bytes 38..47. The recovery sets are constants in crates/parser/src/grammar (EXPR_RECOVERY_SET, ITEM_RECOVERY_SET) used by Parser::err_recover in crates/parser/src/parser.rs [RA-ParserCore]. The errors, printed through the ra_ap_syntax crate, are expected expression at 24, expected SEMICOLON at 25, expected expression at 34, expected R_PAREN at 35 (set up the crate as in the box after Algorithm 4.6.7, then print SourceFile::parse(text, Edition::CURRENT).errors(); each range is empty, as in error 24..24: expected expression).

Error nodes vs error productions¶

Definition 4.6.4 (Error production)

An error production is a grammar rule \(A \to \alpha\ \mathtt{error}\ \beta\) with the reserved terminal error. An LR parser that detects an error pops states until one has a shift on error, shifts it, then discards input tokens until the next one is acceptable in the new state (Lesson 3.7, yacc's recovery [Joh75]); the semantic action of the rule then runs as for any reduction and may build a placeholder.

Bison: an error production resynchronizes at ;

Reproduce (bison 3.8.2, gcc 14.2.0):

cat > stmts.y <<'EOF'
%{
#include <stdio.h>
#include <ctype.h>
int yylex(void); void yyerror(const char *s);
%}
%define parse.error verbose
%token NUM
%%
prog : %empty | prog stmt ;
stmt : NUM '+' NUM ';'  { printf("stmt: %d\n", $1 + $3); }
     | error ';'        { printf("error production: skipped to ';'\n"); yyerrok; }
     ;
%%
int yylex(void) {
  int c = getchar();
  while (c == ' ') c = getchar();
  if (c == EOF || c == '\n') return 0;
  if (isdigit(c)) { yylval = c - '0'; return NUM; }
  return c;
}
void yyerror(const char *s) { printf("%s\n", s); }
int main(void) { return yyparse(); }
EOF
bison -o stmts.c stmts.y && gcc-14 -w stmts.c -o stmts && echo '1+2; 3 4; 5+6;' | ./stmts

Output (complete):

stmt: 3
syntax error, unexpected NUM, expecting '+'
error production: skipped to ';'
stmt: 11

What to notice: the recovery lives in the grammar (stmt : error ';') and its effect is a reduction: the tree (here, the actions) contains a stmt built by the error rule, not a node marking the skipped tokens 3 4. That is the difference from the ERROR nodes above, which record exactly which tokens were skipped. Bison's generated yyerrlab1 code pops states until one shifts error [BISON-Manual].

Incremental LR with subtree reuse¶

Definition 4.6.5 (Edit, reusable subtree)

An edit replaces the byte range \([a, b)\) of the old text by a string \(s\). After the edit, a subtree of the old tree is clean if its span lies entirely before \(a\) or entirely after \(b\) (then shifted by \(\lvert s \rvert - (b - a)\)), and it does not end at the edit's boundary within the lookahead distance of the lexer or parser. A clean subtree rooted at nonterminal \(X\) is reusable at a point of the new parse if the parser, in its current state \(q\), would shift \(X\) (the goto on \(X\) is defined in \(q\)) and the new lookahead after the subtree is the old one.

Algorithm 4.6.6 (Incremental LR parsing with subtree reuse)

Input: the old tree, the edit, the LR tables.
Output: the parse tree of the new text.
Precondition: the old tree was built by the same tables; each node records its parse state (or enough to test reusability, e.g. its first leaf's lookahead state).
Postcondition: the result equals a batch parse of the new text (Theorem 4.6.11); clean subtrees are shared, not copied.
Invariant: the parse stack is a valid LR stack for the new text up to the current input position; the input "stream" is a sequence of old subtrees and new tokens covering the rest of the new text.

function Reparse(old, edit):
    stream ← the old tree's top-level subtrees, with the path to the edit broken down and the
             edited region replaced by freshly lexed tokens
    stack ← [initial state]
    loop:
        x ← first element of stream
        if x is a subtree (not a token):
            if x is clean and GOTO(top(stack), kind(x)) is defined and reduces are not pending:
                shift x as one symbol;  remove x from stream           # reuse, O(1)
            else:
                replace x in stream by its children                     # breakdown
            continue
        act ← ACTION(top(stack), x)                                     # x is a token
        if act = shift: shift x
        else if act = reduce A → α: pop |α|, push GOTO(…, A) with a new node A
        else if act = accept: return the tree
        else: error recovery

tree-sitter reuses the untouched function, and most of the edited one

Reproduce (tree-sitter CLI 0.25.10 and tree-sitter-javascript from npm; Node 22.22.2):

mkdir -p ts && cd ts && npm install --no-audit --no-fund tree-sitter-cli@0.25 tree-sitter-javascript > /dev/null
cat > demo.js <<'EOF'
function f(a) { return a + 1; }
function g(b) { return b * 2; }
EOF
cd node_modules/tree-sitter-javascript
npx tree-sitter parse ../../demo.js --edits "1,27 1 3" -d 2>&1 | awk '/^done/{n++; next} n==1' \
  | grep -E '^(reuse_node|cant_reuse)' | head -12

Output (the first 12 decisions of the second parse):

cant_reuse_node_has_changes tree:program_repeat1
reuse_node symbol:statement
cant_reuse_node_has_changes tree:statement
cant_reuse_node_has_changes tree:declaration
cant_reuse_node_has_changes tree:function_declaration
cant_reuse_node symbol:function, first_leaf_symbol:function
reuse_node symbol:identifier
reuse_node symbol:formal_parameters
cant_reuse_node_has_changes tree:statement_block
reuse_node symbol:{
cant_reuse_node_has_changes tree:statement
cant_reuse_node_has_changes tree:return_statement

What to notice: --edits "1,27 1 3" replaces the 2 of b * 2 (row 1, column 27) by 3 and reparses. The first reuse_node symbol:statement shifts the whole first function as one symbol (Algorithm 4.6.6's reuse). Then the parser walks down the changed path — has_changes breaks a node down — and reuses the untouched pieces of g: its name, its parameter list, the {. ts_parser__reuse_node and ts_parser__breakdown_top_of_stack in lib/src/parser.c [TS-Reuse] are these two cases. On a 20 000-function file the CLI's -t flag reported 374 ms for the full parse and 62 ms for the reparse after a one-character edit on this container (timings vary run to run).

Block-level reparsing¶

Algorithm 4.6.7 (Block-level reparsing, rust-analyzer style)

Input: the old lossless tree and text; an edit.
Output: the new tree, sharing every node outside the reparsed region.
Precondition: blocks {…} can be parsed on their own (their parse depends only on their tokens) and the lexer is context-free outside strings and comments.
Postcondition: the new tree equals a full parse of the new text when the algorithm does not fall back (Theorem 4.6.12).
Invariant: the nodes not on the path from the root to the replaced node are the old nodes (pointer-equal).

function Reparse(tree, edit):
    tok ← the token containing the edit
    if the edit lies inside tok and relexing tok's new text gives one token of the same kind
       (an identifier, a literal, whitespace, a comment):
        return ReplaceNode(tree, tok, new token)                   # token-level reparse
    blk ← the smallest node of kind BLOCK/STMT_LIST/… containing the edit
    text ← blk's text with the edit applied
    if Lex(text) has balanced brackets and parses as a block:
        return ReplaceNode(tree, blk, ParseBlock(text))            # block-level reparse
    return FullParse(new text)                                     # fallback

function ReplaceNode(tree, old, new):                              # path copying
    rebuild each ancestor of old with one child replaced; share all other children

rust-analyzer's syntax crate reparses one block and shares the rest

Reproduce (ra_ap_syntax 0.0.331 from crates.io, rowan 0.15.18, rustc 1.94.1; newer ra_ap versions need a newer rustc, and unicode-ident must be pinned to match unicode-properties):

cargo new -q rareparse && cd rareparse && printf 'ra_ap_syntax = "0.0.331"\n' >> Cargo.toml
cargo update -q -p unicode-ident --precise 1.0.22
cat > src/main.rs <<'EOF'
// rust-analyzer's syntax crate: incremental reparse of one block, and red-green sharing.
use ra_ap_syntax::{AstNode, Edition, NodeOrToken, SourceFile, SyntaxKind, TextRange, TextSize};
use ra_ap_syntax::GreenNode;

fn show(old: &GreenNode, new: &GreenNode, depth: usize, max_depth: usize) {
    for (o, n) in old.children().zip(new.children()) {
        let kind = SyntaxKind::from(n.kind().0);
        let shared = match (o, n) {
            (NodeOrToken::Node(o), NodeOrToken::Node(n)) => std::ptr::eq(o, n),
            (NodeOrToken::Token(o), NodeOrToken::Token(n)) => std::ptr::eq(o, n),
            _ => false,
        };
        println!("{}{:?} {}", "  ".repeat(depth), kind, if shared { "shared" } else { "new" });
        if let (NodeOrToken::Node(o), NodeOrToken::Node(n)) = (o, n) {
            if !shared && depth < max_depth {
                show(&o.to_owned(), &n.to_owned(), depth + 1, max_depth);
            }
        }
    }
}

fn main() {
    let text = "fn a() { let x = 1; }\nfn b() { let y = 2; }\n";
    let old = SourceFile::parse(text, Edition::CURRENT);
    // Replace the `1` (offset 17) by `10 + 20`.
    let new = old.reparse(TextRange::at(TextSize::from(17), TextSize::from(1)), "10 + 20", Edition::CURRENT);
    println!("{:?}", new.tree().syntax().text().to_string());
    show(&old.syntax_node().green().into_owned(), &new.syntax_node().green().into_owned(), 0, 3);
}
EOF
cargo run -q

Output (complete):

"fn a() { let x = 10 + 20; }\nfn b() { let y = 2; }\n"
FN new
  FN_KW shared
  WHITESPACE shared
  NAME shared
  PARAM_LIST shared
  WHITESPACE shared
  BLOCK_EXPR new
    STMT_LIST new
      L_CURLY new
      WHITESPACE new
      LET_STMT new
      WHITESPACE new
      R_CURLY new
WHITESPACE shared
FN shared
WHITESPACE shared

What to notice: 1 → 10 + 20 changes the token structure, so the token-level path fails and reparse_block in crates/syntax/src/parsing/reparsing.rs [RA-Reparse] reparses the smallest block, the STMT_LIST { let x = 1; }: everything inside it is new. Its ancestors BLOCK_EXPR, FN and the file node are rebuilt (path copying), and every other node — fn b, the name and parameters of fn a, the whitespace — is the same green node, pointer-equal (Algorithm 4.6.7's invariant).

3. Worked example¶

Recovery. pebblec's parser on tests/ch04/Inputs/err-statements.pbl (the reference solution, pebble-spec §13.1). One row per diagnostic or synchronization step:

fn f() -> int {
    let x = 1
    let y = x + ;
    var z;
    x = = 3;
    ) ;
    return x
}

fn g() -> int { return 2; }

step	at	what happens	rule
1	4:5–4:14	`let x = 1` parsed
2	5:5 `let`	`;` expected: E0201 at 5:5; sync: `let` is a statement keyword, stop without skipping	statement sync set
3	5:17 `;`	operand of `+` missing: E0203 at 5:17, `ErrorExpr` (nothing consumed)	error node
4	5:17 `;`	the `let` needs `;`: it is there, consumed
5	6:10 `;`	`var z` without `:` or `=`: E0202 at 6:10; `;` consumed
6	7:9 `=`	expression after `=` missing: E0203 at 7:9, `ErrorExpr`	error node
7	7:9 `=`	expected `;` — same location as step 6: suppressed (rule 1); sync skips `= 3 ;`	one error per location
8	8:5 `)`	no statement starts with `)`: E0203 at 8:5; statement dropped; sync skips `) ;`	statement sync set
9	10:1 `}`	`return x` needs `;`: E0201 at 10:1; sync stops at `}`
10	10:1 `}`	the block closes normally; `fn g` parsed in full	item-level structure intact

Six errors, no cascades, and the recovered AST keeps let x, let y = x + (error), var z, x = (error), return x and all of fn g (the lit test err-statements.test checks both).

Incremental reuse. The lab's ★ reparser on the five-item program of tests/ch04/unit/IncrementalTest.cpp inserts print(7); after a ; inside fib: the item boundaries are found by relexing (tokens fn/struct/extern at brace depth 0), the text of fib changed, so fib is reparsed; the texts of Point, putchar, sum and main are unchanged, so their ASTs are reused from the cache: ItemsReparsed = 1, ItemsReused = 4, and the dump equals a full parse (the test checks both over 60 random edits).

Try it

build/<preset>/bin/ch04-parsedump tests/ch04/Inputs/err-conditions.pbl shows recovery inside if/while/for headers; edit a copy and predict the diagnostics first. There is no random drill for recovery: its behavior is defined by a language's sync sets, which the tests of E5–E6 pin down instead.

4. Invariants and correctness¶

Theorem 4.6.9 (A resilient recursive-descent parser terminates in linear time and loses no token)

Suppose every list loop follows Algorithm 4.6.3, every parsing function either consumes at least one token or returns without consuming only when the current token is in an enclosing recovery set or is eof, and every caller that gets back control without progress either is at its own closing token, breaks its loop, or bumps the token into an error node. Then the parser terminates after \(O(n \cdot D)\) steps, where \(D\) is the maximum nesting depth of the grammar's list constructs at one position, and every token is a leaf of the returned tree.

Proof

Progress: each iteration of a list loop either calls an element parser on a token of \(F\) (which consumes at least one token, by the precondition of Algorithm 4.6.3), or bumps one token into an error node, or exits. So a loop iteration that does not exit consumes a token. A function returning without consumption does so only at a token of an enclosing recovery set; the enclosing loop then either handles it (its closer, or its own \(F\)) or passes it further out. At most \(D\) nested loops can pass the same token outward before one of them consumes it or the top level bumps it, so each token causes \(O(D)\) non-consuming steps. No token lost: tokens are only ever consumed by bump into the current node (a list, an element, or an error node), and the top-level loop runs until eof, so every token becomes a leaf. pebblec also caps the recursion depth (rule 4), which bounds \(D\) by 256.

Theorem 4.6.11 (Incremental LR reuse is exact)

Algorithm 4.6.6 returns the same tree as a batch LR parse of the new text.

Proof sketch (full proof: [WG98, §4–5])

The batch parser and the incremental parser see the same sequence of terminals if every subtree is expanded to its yield. A reused subtree \(X\) is shifted only when \(\mathrm{GOTO}(q, X)\) is defined in the current state \(q\) and the subtree is clean, i.e. its yield and the lookahead at its end are unchanged. For an LR(1) grammar the batch parser, reading that yield from state \(q\), performs the reductions that build exactly \(X\) (the subtree was built from the same yield by the same deterministic tables, and the context outside the yield influences these reductions only through the state \(q\) at its left end and the lookahead at its right end, both of which match). So shifting \(X\) whole leads to the same stack as parsing its yield. Any other subtree is broken down to its children, which only changes the granularity. Wagner and Graham show the stronger result that reuse is optimal up to the nodes on changed paths, and extend it to non-deterministic (GLR) parsing.

Theorem 4.6.12 (Block reparsing is exact when it does not fall back)

If the grammar parses a block { … } from its tokens alone (the tree of a block is a function of its token sequence) and the lexer's tokenization of the block's text does not depend on the text around it, then Algorithm 4.6.7's result equals a full parse of the new text whenever it does not fall back.

Proof

A full parse of the new text tokenizes it; outside the edited block the tokens are those of the old text (the lexer is context-free there by hypothesis, and the block's text is bracket-balanced, so no string or comment opened inside it can extend beyond it). The full parser therefore builds the same nodes outside the block as before — they were built from the same tokens by the same deterministic parser, and their parse only depends on the block through its node kind, which is unchanged ("parses as a block"). Inside, it builds the tree of the block's new tokens, which is what ParseBlock returned, by the first hypothesis. Path copying then assembles the same tree. The token-level case is the same argument with a single token of unchanged kind. The two fallbacks exist exactly where a hypothesis could fail: an unbalanced edit (a new " or /* or } changes tokens or structure outside the block) goes to the full parse.

5. Complexity¶

Let \(n\) be the file size in tokens, \(e\) the edit size, \(d\) the depth of the tree and \(b\) the size of the reparsed block or item.

Technique	Time (worst)	Time (typical edit)	Space	Notes
Resilient LL	\(O(n\,D)\) (Theorem 4.6.9)	linear; recovery adds \(O(1)\) per error	the tree	\(D \le 256\) in `pebblec`
Error productions (yacc)	\(O(n \cdot \text{stack depth})\) per error (popping states)	linear	the LR stack	Lesson 3.7
Incremental LR (Wagner–Graham, tree-sitter)	\(O(n)\) (a full reparse)	\(O(e + d \cdot \log n)\) for balanced trees [WG98]	old + new nodes, shared	measured: 62 ms reparse vs 374 ms full on 20 000 JavaScript functions
Block-level reparsing	\(O(n)\) (fallback)	\(O(b + d)\)	path copying: \(O(d)\) new nodes	the lab: 1 item reparsed per edit inside a function

Pathological cases. An edit that inserts a " or /* changes the tokenization of the rest of the file: tree-sitter's changed ranges then cover everything after the edit, rust-analyzer falls back to a full parse (the block is no longer balanced), and the lab's item-level reparser relexes and reparses every item after the quote — incremental parsers are only as incremental as the lexer. For tree depth: tree-sitter's program_repeat1 list nodes are balanced binary trees precisely so that \(d\) stays \(O(\log n)\) for long statement lists; a naive right-recursive list would make every edit near the end of a file rebuild \(\Theta(n)\) ancestors.

Resilient LL parsing¶

Recovery by insertion as well as deletion (Roslyn, swift-syntax): synthesize a missing token node (zero width) instead of an empty error node — trade-off: the tree has the grammar's shape even when wrong, which simplifies consumers; the parser must choose between inserting and skipping.
Precedence-based recovery (swift-syntax's canRecoverTo [SWIFTSYNTAX-Recovery]): skip tokens only if they bind more loosely than the construct being parsed — trade-off: better choices on missing closers, more logic per decision.

Error nodes vs error productions¶

Error productions with semantic placeholders (yacc, Menhir's error token): trade-off: very little code, but coarse and hard to make precise (Lesson 3.7).
Skipped tokens as trivia (Roslyn's SkippedTokensTrivia): unused tokens are attached to the next token as trivia, keeping the tree grammatical — trade-off: tools that ignore trivia do not see errors.

Incremental LR with subtree reuse¶

Sentential-form parsing vs state matching [WG98]: reuse a subtree when its leftmost state matches (precise) or when the parser can shift its nonterminal (the tree-sitter check) — trade-off: storing states in nodes vs recomputing them.
Changed ranges (tree-sitter's ts_tree_get_changed_ranges [TS-Reuse]): compute which ranges of the new tree differ, so that highlighting is updated incrementally too — trade-off: a tree diff per edit.

Block-level reparsing¶

Reparse at item granularity (the lab's ★; rust-analyzer's salsa-based item trees for later phases): coarser units, simpler invariants — trade-off: more reparsing per keystroke, still bounded by the item.
Relexing only around the edit (tree-sitter tracks lexer lookahead per token; Lesson 1.10) — trade-off: token-level precision requires recording how far the lexer looked ahead.

7. In real compilers¶

Resilient LL parsing¶

rust-analyzer: crates/parser/src/parser.rs (Parser::err_recover, Parser::err_and_bump) and the recovery sets in crates/parser/src/grammar [RA-ParserCore]; swift-syntax Sources/SwiftParser/Recovery.swift [SWIFTSYNTAX-Recovery]; pebblec's parser (pebble-spec §13.1). Batch compilers use the same sets with less tree discipline: Clang's SkipUntil (Lesson 2.7). The box after Algorithm 4.6.3 shows rust-analyzer.

Error nodes vs error productions¶

Error productions: Bison's error token [BISON-Manual] (box after Definition 4.6.4), PostgreSQL's and Ruby's grammars; error nodes: rust-analyzer ERROR, tree-sitter ERROR/MISSING, pebblec's ErrorExpr.

Incremental LR with subtree reuse¶

tree-sitter lib/src/parser.c (ts_parser__reuse_node, ts_parser__breakdown_top_of_stack, ts_parser__can_reuse_first_leaf) and lib/src/subtree.c (ts_subtree_edit) at v0.25.10 [TS-Reuse]; tree-sitter's design is described in Brunsfeld's Strange Loop talk [Bru18]. The box after Algorithm 4.6.6 shows the reuse decisions.

Block-level reparsing¶

rust-analyzer crates/syntax/src/parsing/reparsing.rs (incremental_reparse, reparse_token, reparse_block, is_balanced) [RA-Reparse]; the lab's ★ solutions/labs/ch04-paradigms/incr/Incremental.cpp at item granularity. The box after Algorithm 4.6.7 shows rust-analyzer.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Resilient LL parsing	Any input → a tree with every token; well-formed parts intact	\(O(n\,D)\) · no measurable cost over a non-recovering parser	Errors at the offending token, no cascades (6 errors, 0 cascades on `err-statements.pbl`)	Medium: recovery sets per list, discipline in every function	rust-analyzer, swift-syntax, `pebblec`
Error nodes vs error productions	Error nodes: exact skipped regions in the tree; error productions: grammar-level resynchronization	Both linear	Error nodes: precise and tool-friendly; productions: coarse ("skipped to `;`")	Nodes: in the parser; productions: in the grammar	Nodes: IDE parsers; productions: yacc/Bison grammars
Incremental LR with subtree reuse	Exact (Theorem 4.6.11) for LR and, in tree-sitter, GLR grammars	\(O(e + d)\) per edit · 62 ms vs 374 ms full on 20 000 functions	Keeps error nodes across edits; changed ranges for highlighting	High: stateful nodes, breakdown, lexer lookahead tracking	tree-sitter (GitHub, Neovim, Zed, Helix), Ensemble
Block-level reparsing	Exact when it does not fall back (Theorem 4.6.12)	\(O(b + d)\) · one block or item	Same as the underlying parser	Low–medium: persistent trees + a fallback	rust-analyzer, the lab's ★

Choose resilient LL when you write a recursive-descent parser for an editor or for multi-error batch compilation. Choose error productions when you use an LR generator and need simple resynchronization. Choose incremental LR reuse when the parser is generated and must serve many languages in an editor at keystroke speed. Choose block-level reparsing when you already have a lossless persistent tree and a block-structured language: most of the benefit for a fraction of the machinery.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Resilient LL parsing	`recovery-count`, `recovery-location`	— (defined by sync sets; E5–E6 tests pin it down)	`resilient`	E5, E6
Error nodes vs error productions	`error-prod-vs-node`, `bison-error`	—	`error-nodes`	E6
Incremental LR with subtree reuse	`ts-reuse`, `wg-condition`	—	`incremental`	lab L6 ★
Block-level reparsing	`ra-shared`, `incr-reparsed`	—	`block-reparse`	lab L6 ★

These four techniques have no random drill: their outcomes depend on a concrete grammar's recovery sets or on tree layouts, which the implementation tests (ch04.PebbleParser.E5_*, E6_*, ch04.Incremental.*) and the quiz cover instead.

References¶

See the chapter references.

Lesson 4.6 — Error-resilient and incremental parsing¶

1. Problem and motivation¶

Resilient LL parsing¶

Error nodes vs error productions¶

Incremental LR with subtree reuse¶

Block-level reparsing¶

2. Definitions and algorithms¶

Resilient LL parsing¶

Error nodes vs error productions¶

Incremental LR with subtree reuse¶

Block-level reparsing¶

3. Worked example¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

Resilient LL parsing¶

Error nodes vs error productions¶

Incremental LR with subtree reuse¶

Block-level reparsing¶

7. In real compilers¶

Resilient LL parsing¶

Error nodes vs error productions¶

Incremental LR with subtree reuse¶

Block-level reparsing¶

8. Comparison¶

9. Assessment¶

References¶