Awesome q2a theme
0 votes





ago in Compiler Design by (45 points) | 24 views
Option (c) ?

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

Yes you are right

1 Answer

+1 vote
Best answer
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 by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jan 2020
  1. shashin

    1163 Points

  2. Vimal Patel

    306 Points

  3. Deepakk Poonia (Dee)

    305 Points

  4. Debapaul

    237 Points

  5. Satbir

    192 Points

  6. SuvasishDutta

    137 Points

  7. Pratyush Priyam Kuan

    118 Points

  8. tp21

    108 Points

  9. DukeThunders

    96 Points

  10. pranay562

    95 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
2,989 questions
1,509 answers
89,814 users