I. Definitions

Parse trees are trees labeled by symbols of a particular CFG.

• Leaves: labeled by a terminal or $ε$.
• Interior nodes: labeled by a variable.
  • Children are labeled by the body of a production for the parent.
• Root: must be labeled by the start symbol.

<aside> 💡 Yield

The concatenation of the labels of the leaves in left-to-right order (Preorder traversal)

</aside>

1. Generalization

We sometimes talk about trees that are not exactly parse trees, but only because the root is labeled by some variable A that is not the start symbol.

Call these parse trees with root A.

<aside> 💡 Basic idea of induction for trees: following the height of trees.

</aside>

II. Ambiguity in Grammars

A CFG is ambiguous if there is a string in the language that is the yield of two or more parse trees.

Ambiguous: there is at least one string $w$ in $T^*$ for which we can find two different parse trees, each with root labeled $S$ and yield $w$.

Unambiguous: each string has at most one parse tree in the grammar

$$ \textrm{Ambiguity is a Property of \textcolor{darkorange}{Grammars}, not Languages} $$

There can be unambiguous grammar for the same language, for example, LL(1) Grammars.