Parse Tree

A parse tree is a tree representation that shows how a grammar generates a string step by step.

• Root: the start symbol of the grammar.

• Internal nodes: nonterminals (variables).

• Leaves: terminals or ε (empty string).

• Edges: applications of productions.

A parse tree gives a structural view of a derivation, independent of the order in which rules were applied.

---

Parse Tree for a Right-Linear Grammar

Grammar (right-linear):

$$S \rightarrow aA \ | \ bB \ | \ \varepsilon$$
$$A \rightarrow aS \ | \ bS$$
$$B \rightarrow aS \ | \ bS$$

This grammar generates strings over $\{a,b\}^*$.

Example String: ab

Derivation:

$$S \Rightarrow aA \Rightarrow abS \Rightarrow ab\varepsilon = ab$$

Parse Tree:

       
        S
       / \
      a   A
         / \
        b   S
            |
            ε

Leaves read: ab ✅

---

Parse Tree for a Left-Linear Grammar

Grammar (left-linear):

$$S \rightarrow Sa \ | \ Sb \ | \ \varepsilon$$

This generates all strings over $\{a, b\}^*$

Example String: ab

Derivation:

$$S \Rightarrow Sa \Rightarrow Sba \Rightarrow \varepsilon ba = ab$$

Parse Tree:

        S
       / \
      A   b
      |
      a

Leaves read: ab ✅

---

Key Difference: Left-linear vs Right-linear Parse Trees

• Right-linear grammar: terminals “grow” to the right in the tree (chain moves downward-right).

• Left-linear grammar: terminals “grow” to the left in the tree (chain moves downward-left).

Both generate regular languages, but the parse trees look mirrored.

---

✅ So in summary:

• A parse tree shows how a string is generated from a grammar.

• For right-linear grammars, the branching goes toward the right.

• For left-linear grammars, the branching goes toward the left.