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. --- forest-examples.md | 298 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 298 insertions(+) create mode 100644 forest-examples.md (limited to 'forest-examples.md') diff --git a/forest-examples.md b/forest-examples.md new file mode 100644 index 0000000..e22edef --- /dev/null +++ b/forest-examples.md @@ -0,0 +1,298 @@ +# Reference derivation forests (hand-verified) + +These are ground-truth cases for comparing against the parser's forest +output. Every case was derived by hand from the grammar, so treat a +mismatch as a bug in the parser (or in the oracle), never as a reason +to edit this file silently. + +## Notation + +Trees are S-expressions: `(Symbol child child ...)`. Terminals are +bare tokens. An empty derivation is written `eps`. + +A packed forest is a set of nodes `Symbol[start,end]`. Each node has +one or more packed alternatives; each alternative is a sequence of +children, where a child is a node or a terminal. Ambiguity = a node +with more than one alternative. A node is identified by (symbol, +start, end), and identical nodes must be shared. + +The tree set represented by a forest is obtained by choosing one +alternative per node, recursively, from the root node `S[0,n]`. + +--- + +## Case 1: ambiguous, no epsilon + +Grammar: + +``` +S -> S S | a +``` + +Input: `aaa` (tokens `a a a`, n = 3) + +Packed forest (6 nodes, 5 packed alternatives in total): + +``` +S[0,3]: { S[0,1] S[1,3] } | { S[0,2] S[2,3] } +S[0,2]: { S[0,1] S[1,2] } +S[1,3]: { S[1,2] S[2,3] } +S[0,1]: { a } +S[1,2]: { a } +S[2,3]: { a } +``` + +Tree set (exactly 2 trees): + +``` +(S (S a) (S (S a) (S a))) +(S (S (S a) (S a)) (S a)) +``` + +Tree counts by input length (binary trees with n leaves = +Catalan(n-1)): + +| n | trees | +|---|-------| +| 1 | 1 | +| 2 | 1 | +| 3 | 2 | +| 4 | 5 | +| 5 | 14 | + +Forest size should stay polynomial: for n = 20 the forest must NOT +enumerate the 1,767,263,190 trees. Number of nodes is at most O(n^2), +packed alternatives at most O(n^3). + +--- + +## Case 2: ambiguous expression grammar + +Grammar: + +``` +E -> E + E | n +``` + +Input: `n + n + n` + +Packed forest: + +``` +E[0,5]: { E[0,1] + E[2,5] } | { E[0,3] + E[4,5] } +E[0,3]: { E[0,1] + E[2,3] } +E[2,5]: { E[2,3] + E[4,5] } +E[0,1]: { n } +E[2,3]: { n } +E[4,5]: { n } +``` + +Here positions are token indices: `n`=0..1, `+`=1..2, `n`=2..3, `+`=3..4, `n`=4..5. + +Tree set (exactly 2 trees): + +``` +(E (E n) + (E (E n) + (E n))) +(E (E (E n) + (E n)) + (E n)) +``` + +--- + +## Case 3: nullable nonterminals + +Grammar: + +``` +S -> A A +A -> a | eps +``` + +Input: `a` (n = 1) + +Packed forest: + +``` +S[0,1]: { A[0,1] A[1,1] } | { A[0,0] A[0,1] } +A[0,1]: { a } +A[1,1]: { eps } +A[0,0]: { eps } +``` + +Tree set (exactly 2 trees; the two are distinct because the `a` is +consumed by a different `A`): + +``` +(S (A a) (A eps)) +(S (A eps) (A a)) +``` + +Input: `` (empty, n = 0). Exactly 1 tree: + +``` +(S (A eps) (A eps)) +``` + +Watch out: the empty input must give exactly ONE tree, not two. Both +`A`s derive eps in only one way each. + +--- + +## Case 4: right recursion with epsilon, unambiguous + +Grammar: + +``` +S -> a S | eps +``` + +Input: `a a` + +Packed forest (no ambiguity, every node has exactly one alternative): + +``` +S[0,2]: { a S[1,2] } +S[1,2]: { a S[2,2] } +S[2,2]: { eps } +``` + +Tree set (exactly 1 tree): + +``` +(S a (S a (S eps))) +``` + +--- + +## Case 5: cyclic grammars (infinite ambiguity), represented by forest cycles + +Policy for this repo: **infinitely many derivations are represented by +a cycle in the forest.** The forest stays finite; its tree set is +infinite. Nothing is cut or pruned. + +Consequences for reading the notation: + +- A node's alternative may contain the node itself, or a chain of + nodes leading back to it. +- The tree set is obtained by choosing one alternative **per + occurrence** of a node in the tree being built, not once per node + globally. This matters here: the same node appears several times on + one root-to-leaf path, and each occurrence may choose differently. +- Since every child sequence covers its parent's span exactly, a cycle + can only pass through nodes with the **same span** `[start, end]`, + and only through derivations that consume nothing extra (unit rules, + or rules whose other symbols are nullable). + +Because the tree set is infinite, compare **bounded** tree +sets. Define the height of a tree as the maximum number of nonterminal +nodes on any root-to-leaf path. Let `trees_h` be the set of trees with +height <= h. The parser's forest, unpacked with bound h, must equal +the oracle's `trees_h` for every h tested. + +### Case 5a: self-loop + +Grammar: + +``` +S -> S | a +``` + +Input: `a` + +Forest (one node, two alternatives, one of them cyclic): + +``` +S[0,1]: { S[0,1] } | { a } +``` + +Bounded tree sets (exactly h trees for each h): + +``` +h = 1: (S a) +h = 2: (S a) (S (S a)) +h = 3: (S a) (S (S a)) (S (S (S a))) +h = 4: (S a) (S (S a)) (S (S (S a))) (S (S (S (S a)))) +``` + +### Case 5b: nullable self-loop + +Grammar: + +``` +A -> A | eps +``` + +Input: `` (empty, n = 0) + +Forest: + +``` +A[0,0]: { A[0,0] } | { eps } +``` + +Bounded tree sets (exactly h trees for each h): + +``` +h = 1: (A eps) +h = 2: (A eps) (A (A eps)) +h = 3: (A eps) (A (A eps)) (A (A (A eps))) +``` + +### Case 5c: two-node cycle + +Grammar: + +``` +S -> A | a +A -> S +``` + +Input: `a` + +Forest (a cycle through two nodes with the same span): + +``` +S[0,1]: { A[0,1] } | { a } +A[0,1]: { S[0,1] } +``` + +Bounded tree sets (each trip around the cycle adds 2 to the height): + +``` +h = 1: (S a) +h = 2: (S a) +h = 3: (S a) (S (A (S a))) +h = 4: (S a) (S (A (S a))) +h = 5: (S a) (S (A (S a))) (S (A (S (A (S a))))) +``` + +### Case 5d: cycle combined with ambiguity + +Grammar: + +``` +S -> S S | S | a +``` + +Input: `a a` + +Do not hand-write the expected forest for this one. It is the stress +test: the oracle (bounded by h) is the ground truth. Checks to make: + +- The forest is finite and its node count is polynomial in n. +- Every cycle passes only through nodes with identical span (see + invariants in `CLAUDE.md`). +- For h = 1, 2, 3, 4 the unpacked tree set equals the oracle's + `trees_h`. +- Nodes with span `[0,2]` are shared: `S[0,2]` must exist exactly + once. + +--- + +## Suggested extra cases to add once the above pass + +- Left recursion: `S -> S a | a`, input `aaaa` (1 tree). +- Hidden left recursion: `S -> A S a | a ; A -> eps`. +- Nullable in the middle: `S -> a A b ; A -> eps | A c`. +- Highly ambiguous with epsilon: `S -> S S | a | eps`, input `aa` (`S + -> S S` with `S -> eps` is cyclic, so this exercises Case 5 + behavior; compare bounded tree sets only). -- cgit v1.2.3-18-g5258