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

Left Factoring

Factoring out common prefixes in productions to enable predictive parsing and reduce backtracking.

Left Factoring

What you'll learn: How to transform a grammar by factoring out common prefixes so a parser can make decisions without guessing or backtracking.

The Problem with Common Prefixes

Imagine you're a parser reading input left-to-right, and you encounter a grammar like this:

S → a b c | a b d

When you see a b, you don't yet know which production to choose—you need to look ahead further to see if a c or d follows. This creates ambiguity at parse time and forces backtracking: "Oops, I guessed wrong; let me go back and try the other option."

What Is Left Factoring?

Left factoring extracts the common prefix (a b in our example) into a single production, then delegates the decision about what comes after to a new nonterminal:

S  → a b S'
S' → c | d

Now when the parser sees a b, it confidently chooses the first production, then decides between c and d only when it reaches the next symbol. No backtracking needed!

Why This Matters

Left factoring is essential for predictive parsing (like LL(1) parsers), which make decisions based on a limited lookahead. Without left factoring, the parser can't tell which production to apply until it's already committed to the wrong path.

Analogy: It's like a fork in a road where both paths start with the same long driveway. Instead of walking down one driveway only to discover it's the wrong house, you walk the shared driveway once, then decide at the actual fork.


Key Takeaway: Left factoring eliminates common prefixes in productions, enabling parsers to make confident, forward-moving decisions without backtracking.