2
$\begingroup$

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 ?

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

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.

$\endgroup$
  • $\begingroup$ But in 2nd production, B->b/c/d, we have to again check all the 3 productions B-> b, B->c and B-> d individually even after left factoring and we might need to backtrack if we need to use B->d after checking B->b and B->c. So again we have a problem right ? It's like shifting the problem from A production to B production. $\endgroup$ – Sagar P Oct 22 '17 at 20:04
  • $\begingroup$ 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 $ $\endgroup$ – fade2black Oct 22 '17 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.