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.