1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
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<String>` or `BTreeSet<String>`), 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.
|
