Back to the 2023 paper

Module 2: Syntax Analysis (Parser)

20232m

Consider a grammar A→aS1∣aS2A \to a S_1 | a S_2. The left factored grammar produced from the grammar is
(i) A→aA′,A′→S1∣S2A \to a A', A' \to S_1 | S_2
(ii) A′→aA,A→aS1∣aS2A' \to a A, A \to a S_1 | a S_2
(iii) A→aA′,A′→S1∣S2,S1→S1,S2A \to a A', A' \to S_1 | S_2, S_1 \to S_1, S_2
(iv) None of these

Worked SolutionAI Assisted

Answer: (i) A→aA′, A′→S1∣S2A \to aA',\ A' \to S_1 \mid S_2

Step 1 — left factoring

Given grammar:
A→aS1∣aS2A \to aS_1 \mid aS_2

The two alternatives share the common prefix a. We factor it out into a new nonterminal A′A':

A→aA′A \to aA'

A′→S1∣S2A' \to S_1 \mid S_2

This is the standard left-factored (CFG) form that removes backtracking uncertainty, because after reading a the parser chooses between S1S_1 and S2S_2 by looking at the next input, not by backtracking.

Hence the correct answer is:

(i) A→aA′, A′→S1∣S2\boxed{\text{(i)}\ A \to aA',\ A' \to S_1 \mid S_2}

Similar questions

AI LearningWeb Platform

Coursify — Personal AI Course Generator

Struggling with a difficult subject or concept? Turn any engineering topic into a structured course with interactive lessons, quizzes, and research-backed explanations.