1 files changed, 298 insertions, 0 deletions
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).