From fba9a90cfc6aca2a26cce72f55fb261789139781 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 16 Oct 2026 14:01:01 +0800 Subject: new start Now I tested and discussed with claude, and had a working version of this project. The rest is to port the claude version to my own writings. So this serves as the starting point before that attempt. In the new attempt the design is better, and a number of bugs were found and supposedly fixed, so let us see how this goes at the end. --- CLAUDE.md | 174 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 174 insertions(+) create mode 100644 CLAUDE.md (limited to 'CLAUDE.md') diff --git a/CLAUDE.md b/CLAUDE.md new file mode 100644 index 0000000..c6f838c --- /dev/null +++ b/CLAUDE.md @@ -0,0 +1,174 @@ +# CLAUDE.md + +## Project + +A Rust implementation of the relational parsing algorithm from Grzegorz Herman, +"Faster general parsing through context-free memoization" (PLDI 2020; earlier +arXiv version: "Relational parsing: a clean, fast parsing strategy for all +context-free languages", arXiv:1902.06591). + +The parser is a general context-free parser. Beyond recognition, it is +meant to produce the **full derivation forest** (a shared packed parse +forest), not a single tree. Recognition appears to work (update: +**opus found the recognizer bugs**, and seemed to fix them, see the +design document in tests); **forest construction is wrong**. + +Fill in before use: + +- Main source files are contained in the sub-crates: [ "graph", + "receme", "nfa", "chain", "viz", "grammar", "forest", "semiring", + "graph_macro", "tokens" ], and the top-level crate is mainly for + making a dynamic module to load as an Emacs library. +- Forest representation is in the "forest" sub-crate, while the + construction is mainly in the "chain" sub-crate, which is the + hot-point of the entire crate in my opinion. +- Entry point / CLI: this is intended to be an Emacs dynamic module, + and should compile to produce a `rep.so` file. +- Paper PDF files are contained in the directory + "/Users/durand/Desktop/Centre/A propos de programmes/C/parser/references/", + but there are too many papers to read, so ask me to confirm before + trying to consult a paper, to save unnecessary tokens. + +## The task + +Debug forest construction until the parser's forest represents +**exactly** the set of derivation trees of the input, no more and no +fewer, with proper sharing. + +Reference cases with hand-verified expected forests and tree sets: +forest-examples.md + +## Ground rules + +- ONLY MAKE A PLAN FOR ME TO CHANGE. Do not write or change the files + here. I prefer to have this project be fully understood and written + by me by hand, so unless explicitly requested, no actual change is + appreciated. +- When some files do get written, they should all sit inside the + "tests" folder, inside which I permit you to write files. +- Do not weaken, delete, or edit the expected results in + `forest-examples.md` or in tests to make something pass. If you + believe a reference case is wrong, stop and explain why with a hand + derivation. +- Do not change recognition behavior unless you can show a recognition + bug with a failing test. +- Make minimal, targeted changes. Do not rewrite or restructure large + parts of the code to fix one bug. +- When the paper's definition is ambiguous or you are unsure how code + maps to it, say so and ask, rather than guessing silently. +- Every bug you fix gets a regression test that failed before the fix. + +## Workflow (follow in order) + +### 1. Build a brute-force oracle first + +Before touching the parser, write `tests/oracle.rs` (or a +`#[cfg(test)]` module) containing a deliberately naive, obviously +correct enumerator: + +- Input: a grammar, a token sequence, and a height bound `h`. +- Output: the set of all derivation trees of height <= h, as canonical + S-expression strings in the notation used in `forest-examples.md`. + Height = max number of nonterminal nodes on any root-to-leaf path. +- Method: top-down, try every production for every (symbol, start, + end) split, memoize nothing clever. Speed is irrelevant (inputs are + at most ~8 tokens). +- Cycles: the parser represents infinitely many derivations as a cycle + in the forest (see Case 5 of the reference file). The oracle does + not prune cyclic derivations; the height bound is what makes it + terminate. +- Validate the oracle itself against every case in + `forest-examples.md` before trusting it. +- Make it clear that this enumerator is written by claude code. + +### 2. Write an unpacker for the parser's forest + +- Add a function `unpack(forest, h)` that expands the parser's forest + into the same canonical tree-set representation (sorted + `Vec` or `BTreeSet`), keeping only trees of height + <= h. Choose alternatives per occurrence of a node, not once per + node. The forest may contain cycles, so the height bound is what + guarantees termination. Also guard against exponential blowup (bail + out with a clear error above a tree count limit). + + Compare `unpack(forest, h)` with the oracle's output for h = 1, 2, + 3, 4 (and larger for tiny cases). +- This should come inside the above test file. + +### 3. Compare, then classify the failure + +For each case, diff parser tree set vs oracle tree set. Report which +of these applies, because each points to a different bug class: + +- **Missing trees**: lost derivations (alternatives dropped, wrong + completion or sharing key that merges distinct derivations, nullable + handling). +- **Extra trees**: spurious derivations (children not covering their + span, stale or over-shared nodes, memoized result reused in the + wrong context). +- **Duplicate trees / wrong multiplicity**: the same derivation packed + twice (identical nodes not shared, or an alternative inserted more + than once). +- **Right trees, bad size**: forest is correct but not shared properly + (should be polynomial in n, not exponential). + +### 4. Add structural invariant checks + +Implement a `validate_forest` function and call it in tests. It should +assert: + +- Each node's chosen children cover exactly its span `[start, end]`, + in order, with no gaps or overlaps. +- Nodes are unique per (symbol, start, end); no duplicate nodes. +- No two packed alternatives of a node are identical. +- Terminal children match the input tokens at their positions. +- Each alternative corresponds to a real production of the grammar. +- Cycles are allowed, but every node on a cycle must have the same + span `[start, end]`. A cycle through nodes of different spans is a + bug. +- The forest is finite: node count is polynomial in the input length + even for cyclic grammars. + +### 5. Localize with and without memoization (skipped for now) + +My implementation does not handle memoization well yet, so this part +is skipped. + +Run every failing case with memoization disabled (add a feature flag +or runtime switch if none exists). If the bug disappears, the +memoization cache key is missing context the result depends on. If it +persists, the bug is in the core algorithm or the forest construction +itself. + +### 6. Test layers, in this order + +1. Unambiguous, no epsilon. +2. Ambiguous, no epsilon (Cases 1 and 2). +3. Epsilon rules and nullable nonterminals (Cases 3 and 4). +4. Left, right, and hidden left recursion. +5. Cyclic grammars (Case 5). +6. Random small grammars: generate grammars with 1 to 3 nonterminals + and productions of length at most 3 over a 2-terminal alphabet, + random inputs up to length 6, and compare against the oracle. Use + `proptest` or a seeded RNG so failures are reproducible; print the + grammar and input on failure. + +Stop at the first failing layer and fix it before moving on. + +## Commands + +``` +cargo build +cargo test +cargo test -- --nocapture # to see diffs +cargo clippy -- -D warnings +``` + +## Reporting + +When you finish a debugging step, report briefly: + +- The smallest grammar and input that failed. +- Oracle tree set vs parser tree set (the diff). +- The root cause, with the file and line. +- The fix and the regression test added. -- cgit v1.2.3-18-g5258