path: root/forest-examples.md

# 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).