Left Factoring

  An LL(K) parser can recognize a grammar unambiguously only if the grammar is left factored. To understand left factoring consider the grammar given below. The grammar is not left factored.

S→ abX | abY
X→m
Y→n  

The above grammar can not be parsed by an LL(1) parser. An LL(1) parser looks ahead only a single character (Token) to make a parsing decision. But here the the parser should read two characters in advance to make a parsing decision. Thus in general we can say that there exists a non left factored grammar which can not be parsed by an LL(K) parser for any value of K. To parse the grammar it should be left factored. The grammar given below is a left factored grammar equivalent to the grammar given above. 

S→abC
C→X | Y 
X→m
Y→n

This grammar can be parsed by an LL(1) parser.