GATE CS 2012 Q.53 (CS Q.53): Parsing and Syntax Analysis (LL and LR)

Linked answer questions

Statement for Linked Answer Questions 52 and 53:

For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. $\epsilon$ is the empty string, $\$$ indicates end of input, and $|$ separates alternate right hand sides of productions.

S \to aAbB \mid bAaB \mid \epsilon

A \to S

B \to S

Non-terminal	$a$	$b$	$\$$
$S$	E1	E2	$S \to \epsilon$
$A$	$A \to S$	$A \to S$	error
$B$	$B \to S$	$B \to S$	E3

Shared with question 52.

The appropriate entries for E1, E2, and E3 are

E1: $S \to aAbB, A \to S$
E2: $S \to bAaB, B \to S$
E3: $B \to S$

E1: $S \to aAbB, S \to \epsilon$
E2: $S \to bAaB, S \to \epsilon$
E3: $S \to \epsilon$

E1: $S \to aAbB, S \to \epsilon$
E2: $S \to bAaB, S \to \epsilon$
E3: $B \to S$

E1: $A \to S, S \to \epsilon$
E2: $B \to S, S \to \epsilon$
E3: $B \to S$

Official answer and solution

Official answer: C
From: Official GATE 2012 answer key

Solution

Populate LL(1) parsing table cells for non-terminals S on a (E1), S on b (E2), and B on end-of-input (E3).

LL(1) table construction rules:

For $X \to \alpha$ , add $X \to \alpha$ to $M[X, t]$ for all $t \in \text{FIRST}(\alpha)$ .
If $\epsilon \in \text{FIRST}(\alpha)$ , add $X \to \alpha$ to $M[X, t]$ for all $t \in \text{FOLLOW}(X)$ .

For cell $M[S, a]$ (entry E1):

$S \to aAbB$ has $a \in \text{FIRST}(aAbB)$ , so add $S \to aAbB$ .
$S \to \epsilon$ has $\epsilon \in \text{FIRST}(\epsilon)$ . Since $a \in \text{FOLLOW}(S)$ , also add $S \to \epsilon$ .
Thus, E1 contains: $S \to aAbB, S \to \epsilon$ .

For cell $M[S, b]$ (entry E2):

$S \to bAaB$ has $b \in \text{FIRST}(bAaB)$ , so add $S \to bAaB$ .
$S \to \epsilon$ has $b \in \text{FOLLOW}(S)$ , so add $S \to \epsilon$ .
Thus, E2 contains: $S \to bAaB, S \to \epsilon$ .

For cell $M[B, \text{\$}\,]$ (entry E3):

$B \to S$ has $\text{FIRST}(S) = \{a, b, \epsilon\}$ .
Because $\epsilon \in \text{FIRST}(S)$ , we look at $\text{FOLLOW}(B)$ , which contains $\text{\$}$ .
Therefore, add $B \to S$ to $M[B, \text{\$}\,]$ .
Thus, E3 contains: $B \to S$ .

Combining E1, E2, E3 matches option (C).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2012 Computer Science and Information Technology (CS)
Question: 53 of 65, printed as CS Q.53
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.