Course contentsShow
← Computer Science
Lesson 1815 of 2,87241. Context-Free LanguagesFree lesson

Leftmost and Rightmost Derivations

Explore different derivation orders and their significance in parsing strategies.

Leftmost and Rightmost Derivations

What you'll learn: You'll understand how different derivation orders systematically expand grammar rules and why this matters for parsing algorithms.

The Core Idea

When deriving a string from a context-free grammar, you have choices: which non-terminal symbol do you replace first? A leftmost derivation always replaces the leftmost non-terminal at each step, while a rightmost derivation always replaces the rightmost non-terminal first.

Think of it like reading a sentence with blanks: leftmost derivation fills in blanks from left to right, rightmost from right to left. Both strategies eventually produce the same final string, but the intermediate steps look different.

Why This Matters

Consider a simple grammar:

S → S + S | a

Deriving the string "a + a + a":

Leftmost derivation:

  1. S → S + S (expand leftmost S)
  2. S + S → a + S (expand leftmost S)
  3. a + S → a + S + S (expand the only S)
  4. a + S + S → a + a + S (expand leftmost S)
  5. a + a + S → a + a + a (expand last S)

Rightmost derivation:

  1. S → S + S (expand rightmost S)
  2. S + S → S + S + S (expand rightmost S)
  3. S + S + S → S + S + a (expand rightmost S)
  4. S + S + a → S + a + a (expand rightmost S)
  5. S + a + a → a + a + a (expand last S)

Different order, same result!

Significance in Parsing

Parsing strategies directly mirror these derivations. Top-down parsers (like LL parsers) naturally perform leftmost derivations, predicting and expanding from the left. Bottom-up parsers (like LR parsers) trace rightmost derivations in reverse, reducing from the right.

Key Takeaway: Leftmost and rightmost derivations provide systematic, deterministic ways to expand grammars, forming the theoretical foundation for predictable parsing algorithms.