Prove that every CFL is decidable in O(n) space
Let $G$ be a context-free grammar in Chomsky normal form. We will show how to determine whether a nonempty word $w$ of length $n$ is accepted by $G$.

Every parse tree for $w$ is first of all a full binary tree with $n$ leaves. It is known that the number of such trees is $C_{n-1}$. Moreover, there is a bijection with words containing $n-1$ pairs of balanced parentheses and full binary trees with $n$ leaves. We can go over all full binary trees with $n$ leaves in space $O(n)$ by going over all words of length $2(n-1)$ over the alphabet $\{(,)\}$, converting each of them which is balanced to a full binary tree.

For each full binary tree $T$, we consider all possible labelings of nonterminals to the vertices of the tree in which the root is labeled using the start symbol, which can be done in $O(n)$ space (here the constant depends on $G$). We check each such parse tree for validity: for each internal vertex labeled $A$ with children labeled $B,C$, we check that $A \to BC$ is a production, and for the $i$'th leaf labeled with $A_i$, we check that $A_i \to w_i$ is a production. If we find a valid parse tree in this process, then $w \in L(G)$. Otherwise, $w \notin L(G)$.