Left Factoring
You'll learn how to refactor grammars with common prefixes so a parser can make deterministic choices with limited lookahead.
The Problem with Common Prefixes
When writing a recursive descent parser, your parsing function needs to decide which production rule to follow by looking ahead at the next token. But what if two grammar rules start with the same symbols?
Consider this grammar fragment:
statement → if expr then statement
| if expr then statement else statement
Both rules begin with if expr then statement. When your parser sees if, it can't decide which production to use until it looks way past the then clause to see if else appears. This violates the "limited lookahead" principle recursive descent relies on.
The Solution: Left Factoring
Left factoring extracts the common prefix into a single production, then factors out the different suffixes into a new non-terminal:
statement → if expr then statement statement_tail
statement_tail → else statement
| ε
Now when the parser sees if, it confidently chooses the first production. After parsing if expr then statement, it simply checks if else follows to decide between the two statement_tail options—a much simpler decision requiring only one token of lookahead.
Think of it like organizing a flowchart: instead of two diverging paths that start identically, you merge the common beginning and only branch at the actual decision point.
When to Apply It
Apply left factoring whenever two or more productions for the same non-terminal share a common prefix. This makes your grammar LL(1)-friendly, meaning deterministic with one-token lookahead.
Key Takeaway: Left factoring transforms grammars with shared prefixes into equivalent grammars where parsing decisions are deterministic and require minimal lookahead.