Difference between Left Factoring and Left Recursion

Question

What is the difference between Left Factoring and Left Recursion ? I understand that Left factoring is a predictive top down parsing technique. But I get confused when I hear these two terms.

Answer 1

Left factoring is removing the common left factor that appears in two productions of the same non-terminal. It is done to avoid back-tracing by the parser. Suppose the parser has a look-ahead, consider this example:

A -> qB | qC     

where A, B and C are non-terminals and q is a sentence.

In this case, the parser will be confused as to which of the two productions to choose and it might have to back-trace. After left factoring, the grammar is converted to:

A -> qD D -> B | C 

In this case, a parser with a look-ahead will always choose the right production.

Left recursion is a case when the left-most non-terminal in a production of a non-terminal is the non-terminal itself (direct left recursion) or through some other non-terminal definitions, rewrites to the non-terminal again (indirect left recursion).

Consider these examples:

(1) A -> Aq (direct)  (2) A -> Bq     B -> Ar (indirect) 

Left recursion has to be removed if the parser performs top-down parsing.