24 views

A)

B)

C)

D)

ago | 24 views
0
Option (c) ?
0

Yes @shashin I also think the answer should be (c).

0
Yes you are right

+1 vote
This becomes simple when you understand why left factoring is required : Non-Determinism.
Informally, non-determinism occurs when the starting symbols in more than one production is the same. Due to this - the compiler cannot accurately pick the production to proceed with. If it picks the wrong one, it will need to backtrack, which most of the parsers don't allow.
The solution to this is to extract the common part from the beginning (left) of each production, and break the production into 2 or more. This process is left-factoring.

In the given grammar, the non-determinism is clearly due to the 'int' part which is common in 3 productions. If the parser sees the 'int' on the input string, it will not know which production to take.  So we extract the 'int' out, while leaving the 4th production  $E-(E)$ untouched (since that is not contributing to non-determinism).

$E \rightarrow intE' | E - (E)$

$E' \rightarrow +E\:| -E\: | \epsilon$

The $E' \rightarrow \epsilon$ is required so we can still generate $E \rightarrow int$ as per the original grammar.

Note: it may seem like option (b) is the same. However, even if it generates the same strings - it is not the result of left factoring. In fact if you flatten it - it will contain $E \rightarrow int-(E)$ which is a redundant production.
ago by (1.2k points)
selected ago