Derivations and Parse Trees

A derivation is the process of starting from the grammar's start symbol S and repeatedly applying production rules until you are left with only terminal symbols.

Each single application of a rule is called a derivation step, written with the arrow ⟹:

When zero or more steps are chained together we write ⟹* (derives in zero or more steps):

Sentential Forms and Sentences

During a derivation, at each intermediate step you have a mix of terminals and non-terminals. These intermediate strings are called sentential forms.

The key rule:

In a leftmost derivation, at every step you always replace the leftmost non-terminal in the current sentential form.

It is the most systematic, predictable order — and it's the order that top-down parsers (like recursive descent) follow naturally.

Notation: ⟹lm

Example — Grammar for Arithmetic Expressions

Leftmost derivation of "id + id * id":

At every step, the non-terminal that was replaced is the leftmost one in the current sentential form. All non-terminals to its right were left untouched until their turn came.

In a rightmost derivation, at every step you always replace the rightmost non-terminal in the current sentential form.

This is the order that bottom-up parsers (like LALR / yacc) follow — they build the derivation in reverse (from right to left).

Notation: ⟹rm

Example — Same Grammar, Same String

Rightmost derivation of "id + id * id":

Leftmost vs Rightmost — Key Differences

Important: Both leftmost and rightmost derivations of the same string in an unambiguous grammar produce the same parse tree. The tree structure is unique — only the order of expansion steps differs.

A parse tree (also called a derivation tree or concrete syntax tree) is a graphical way to represent an entire derivation in one picture. Instead of showing one step at a time, it shows the complete structure all at once.

Rules for building a parse tree:

• The root is the start symbol S
• Each interior node is a non-terminal
• Each leaf is a terminal (or ε)
• If rule A → X₁ X₂ … Xₙ was applied, then node A has children X₁, X₂, …, Xₙ (left to right)
• Reading the leaves left to right gives the original sentence

Parse Tree for "id + id * id"

Reading the leaves left to right: id + id * id ✓

What the Tree Reveals

The shape of the parse tree encodes operator precedence and associativity — without needing any extra annotations:

• id * id is grouped under a T node — multiplication is at the lower level
• id + (id * id) is grouped under an E node — addition is at the higher level
• This means * binds tighter than + — exactly the correct mathematical precedence

If the grammar had been written differently (e.g., E → T + E instead of E → E + T), the tree shape would be different and would encode right-associativity instead.

Let us work through a complete example from scratch, building the parse tree alongside the derivation.

Grammar:

Goal: Derive and draw the parse tree for "acdb"

Step 1 — Derivation

Step 2 — Parse Tree

Start at the root S, and draw each rule application as a parent → children branching:

Leaves left to right: a c ε d b = acdb ✓

Step 3 — Another derivation: "accdd b" (n=2 for pattern acⁿdⁿb)

Parse tree:

Leaves: a c c ε d d b = accddb ✓

The nesting in the tree exactly mirrors the recursive structure of the grammar.

In a compiler, two closely related trees appear: the parse tree (concrete syntax tree) and the abstract syntax tree (AST).

Parse Tree — faithfully represents every grammar rule application, including punctuation, keywords, and intermediate non-terminals that only exist for precedence/associativity reasons.

Abstract Syntax Tree (AST) — a simplified version that keeps only the semantically meaningful nodes. It strips away the structural scaffolding.

Example: 3 + 5 * 2

Parse Tree (following the expression grammar E → E+T | T, T → T*F | F, F → num):

Abstract Syntax Tree:

The AST discards the E, T, F non-terminal nodes (they were only there to enforce precedence) and keeps only the operators and operands. Every phase after parsing works with the AST, not the parse tree.

Summary