S1. The tokenizer and the PEG matcher

Part of #304. Depends on S0.

The two components between a query string and a parse tree. One is generated from the vendored grammar and the other is hand written, so the hand written one is where the bugs will be.

Nothing executes at the end of this issue either. What we get is the differential harness saying that firepanda's parser and DuckDB's parser agree on accept and reject across DuckDB's entire test corpus, which is the compatibility claim made testable months before there is an engine to be confident about.

### Scope

- [x] The tokenizer: identifiers, quoted identifiers, keywords in five classes, numbers, strings, operators, punctuation, parameters (#317)
- [x] The PEG matcher, a recursive descent interpreter over the S0 rule table (#319)
- [x] Selective packrat memoization using DuckDB's own rule list (#319)
- [x] Furthest failure error reporting with a caret (#319)
- [x] The expected token set at the furthest failure, and keyword typo suggestions at edit distance one (#325)
- [x] The differential parse harness over DuckDB's corpus, 71,438 statements (#323)
- [x] Grammar directed input generation, since the vendored grammar is a generator as well as a recognizer (#344)
- [x] The pathological input suite with wall clock ceilings in CI (#322)

### The tokenizer details that are each a silent compatibility bug

Identifiers fold to lowercase, not uppercase, and quoted identifiers do not fold. Keyword classification comes from the vendored lists, and a word in the wrong class produces exactly the failure we promised never to have, which is a syntax error on valid DuckDB SQL. String literals come in four forms and all four appear in the corpus: single quoted with doubling, `E'...'` with backslash escapes, dollar quoting with no escapes at all, and unicode escapes. An unsuffixed literal with a decimal point is DECIMAL and not DOUBLE, which is why `1.1 + 2.2` is exactly `3.3` in DuckDB, so the tokenizer is already reaching into the type system. Underscore digit separators, hex and binary literals, nested block comments, and three parameter forms where `$` is also dollar quoting.

This is a few hundred lines of hand written state machine standing between us and the compatibility claim, so it gets its own differential fuzzer from the first week. It is the cheapest confidence in the whole milestone.

### Memoization

Full packrat memoizes every rule at every position and pays a table proportional to rules times positions plus a lookup on every rule entry. For SQL, where most rules match or fail immediately, that overhead exceeds what it saves on almost every real query.

DuckDB measured the pathology and published it. A query with nineteen unmatched parentheses took 10.640 seconds unmemoized and 0.001 seconds memoized, from exponential backtracking on the expression rules where the deep ordered choices are. Their answer is a short explicit list of memoized rules, and we vendor the list rather than choosing our own.

What shipped is denser than the open addressed table this issue first described. The generated table says which rules are memoized, so each one gets a slot number and the memo table is one bit per slot per token position, which for twenty two rules and a hundred tokens is two hundred and seventy five bytes. That is small enough to allocate on the first memoized failure and drop with the parse, so a `SELECT 1` never touches it and there is no table to keep or clear between statements.

It started out recording failures only, on the reasoning that a memoized success is a subtree in the node arena and a failing ancestor may have truncated that subtree away since. That turned out to leave a real blowup in place. `TypeModifiers <- Parens(List(Expression)?)` means `f(x)` parses as a type before it parses as a call, so twelve nested function calls took a fifth of a second and every extra one doubled it, and failure memoization cannot see any of it because both walks succeed.

So #322 made the arena stop rolling back. A failed attempt now unwinds only the pending stack and leaves its nodes where they are, unreachable from the tree but reachable from the memo table, and a hit copies the root of what it finds and shares everything under it. The entry is four bytes per memoized rule per token position rather than one bit, which is eighty eight bytes a token, and nothing is allocated until the first memoized rule finishes. Twelve nested calls went from a fifth of a second to under a millisecond.

### The budget

Measured on an M4 with DuckDB 1.5.5, parsing unique statements in a loop, including DuckDB's JSON serialization of the parse tree so these are upper bounds.

| | DuckDB |
| --- | --- |
| TPC-H q1, parse only | 156 microseconds |
| `SELECT 1`, parse only | 6 microseconds |

Our targets are under 60 microseconds for q1 and under 3 for a trivial statement, tokenize and match and transform together, with one arena block and no per node allocation. The allocation line is the one that matters, because a REPL loop over small statements spends its time in the allocator and not in the matcher.

### What the matcher must not do

No semantic decisions. Not whether an identifier is a table or a column, not whether a function exists, not whether a cast is valid. The classic temptation is resolving whether `foo(x)` is a function call or a type constructor, and taking it makes the parser un-regenerable and breaks the property S0 exists to buy.

No lookups outside the token vector and the rule table. No catalog, no settings, no session state. A parse must be a pure function of its text and the vendored grammar, which is what later makes the prepared statement cache sound.

No error recovery. First failure stops the parse. Recovery is for editors and it changes which strings are accepted, which would put a hole in the compatibility claim.

### Exit criteria

- [x] Accept and reject agree with DuckDB on every statement in the corpus. At 2 of 71,300 in the direction that matters, both of them the recursion depth guard firing
- [ ] Accept and reject agree on grammar directed generated SQL over an overnight run
- [x] Every pathological case is inside its wall clock ceiling, and the ceilings are enforced in CI
- [ ] The parse only budget above is met on this machine and recorded with the toolchain version

### Depends on

S0.

Start by running the grammar-directed generated SQL differential harness and review the CI wall-clock checks described in the issue. The remaining work is to make accept/reject agree over an overnight generated-SQL run and record the parse-only budget with the toolchain version on the stated machine.

Written by the indexing model from the issue text.