Context-Free Languages: Simplification & Normal Forms

left factoring

Suppose two menu items both begin 'grilled chicken with...' and differ only at the end. A waiter who must commit after hearing just 'grilled chicken' cannot tell which you want. The fix is to take the order in two parts: confirm 'grilled chicken' first, then ask about the ending. Left factoring does exactly this to grammar rules that share a common beginning, so a parser does not have to decide between them before it has seen enough input.

When a variable has two or more rules whose right-hand sides share a common prefix, like A -> alpha beta1 | alpha beta2, a predictive top-down parser cannot choose between them by looking at just the next symbol, because both start with alpha. Left factoring pulls the shared prefix out into one rule and pushes the differing tails into a new helper variable: A -> alpha A', A' -> beta1 | beta2. Now the parser commits to alpha first and only later decides between beta1 and beta2, by which point it has seen more input. This is purely a syntactic rearrangement; the language generated is unchanged.

Left factoring, like left-recursion removal, is a grammar transformation that makes a grammar suitable for predictive, top-down parsing (LL and recursive descent), where the parser must pick the right rule using limited lookahead. The classic example is the dangling-else ambiguity, where 'if E then S' is a prefix of 'if E then S else S'. As always, the rewrite reshapes the parse trees, so any meaning attached to the original combined rule must be reattached to the factored rules; and left factoring alone does not guarantee the grammar becomes LL(1) — it removes one obstacle, not all of them.

Stmt -> if E then Stmt | if E then Stmt else Stmt shares the prefix 'if E then Stmt'. Left-factored: Stmt -> if E then Stmt S', S' -> else Stmt | epsilon. The parser commits to the common prefix, then decides whether an 'else' follows.

Pull the shared prefix into one rule and defer the differing tails to a helper variable.

Left factoring removes one barrier to LL(1) parsing (a common prefix) but does not by itself make a grammar LL(1) or unambiguous; the dangling-else, for instance, remains ambiguous unless you also fix which 'if' an 'else' binds to.

Also called
left factorizationfactoring common prefixes左提取共同前綴提取