# How does left-factoring prevent backtracking?

I read that deterministic grammar helps in preventing backtracking.

Consider a grammar

$$A \rightarrow ab \mid ac \mid ad$$.

Here if input is "ad" then the compiler needs to check each of ab, ac .. and backtrack until it gets to last production.

To eliminate non determinism we modify the grammar as

$$A \rightarrow aB$$ $$B\rightarrow b\mid c\mid d$$

I don't understand how will this modified grammar prevent backtracking . If we again give the same input "ad" then in B production , it will again back track for b and c until it reaches d.

So how does left factoring actually solve this problem ?

• Please clarify which parts of your post are quoted, and from where.
– Raphael
Oct 22 '17 at 19:50

Suppose the input is ab. In compiler terms you have two tokens a and b which are read in linear sequence. So, when you read a it is not clear which production rule to apply since you have three possible rules which begin with a: $A \rightarrow ab \mid ac \mid ad$. To choose the right production rule you need check all possible rules which is done by backtracking.
However, if you factor this grammar then you have only one production rule which begins with a: $A \rightarrow aB$ which is the only single possible rule and thus there is no need in backtracking.
Nondeterminism, when parsing, can be resolved using lookahead technique, where left-factoring is one of the steps in order to transform the initial grammar into $LL(k)$-grammar. For more details please read about $LL(k)$-parsers.
• You don't have to check all three production rules since the second (input) token is b and so you deterministically choose the rule $B \rightarrow b$ Oct 22 '17 at 20:06