Awesome q2a theme
0 votes





in Compiler Design by (68 points) | 31 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.
by (1.9k points)
selected 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
Top Users 2020 Aug 10 - 16
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    315 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    128 Points

  5. toxicdesire

    53 Points

  6. Akanksha Agrawal

    36 Points

  7. shashankrustagi2021

    15 Points

  8. Nilabja Sarkar

    12 Points

  9. Mellophi

    11 Points

  10. premu

    10 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    320 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    204 Points

  5. Mellophi

    161 Points

  6. toxicdesire

    53 Points

  7. anurag sharma

    49 Points

  8. Akanksha Agrawal

    36 Points

  9. shashankrustagi2021

    25 Points

  10. premu

    16 Points

7,793 questions
2,048 answers
95,121 users