Parse trees and their yields

Let $G=(V,\mathrm{\Sigma },P,S)$ be a context-free grammar. A parse tree for $G$ is a finite, finitely branching rooted tree of finite sequences in the sense of Rooted trees of finite sequences, levels, branches, and finite branching, with ordered finite successor sets, together with a label on each node, satisfying the following conditions.

• The root is labelled by the start variable $S$.
• Every internal node is labelled by a variable $A\in V$.
• If an internal node labelled $A$ has ordered children labelled $x_1,\dots ,x_k$, then $A\to x_1\cdots x_k$ is a production of $G$.
• A leaf is either labelled by a terminal in $\mathrm{\Sigma }$, or is a variable leaf corresponding to a production $A\to \epsilon$ and contributes no terminal symbol to the yield.

Reading the terminal leaves from left to right gives a word in ${\mathrm{\Sigma }}^{\ast }$, called the yield of the parse tree.

• The finite-sequence address set is what makes "left to right" precise: among siblings, the natural-number labels of successor nodes provide the order.

• The tree itself is finite. This rules out infinite variable chains that do not correspond to a finite derivation.

• An $\epsilon$-production contributes no terminal letter to the yield.