GATE CS 2012 Q.52 (CS Q.52): 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 53.

The FIRST and FOLLOW sets for the non-terminals A and B are

$\text{FIRST}(A) = \{a, b, \epsilon\} = \text{FIRST}(B)$
$\text{FOLLOW}(A) = \{a, b\}$
$\text{FOLLOW}(B) = \{a, b, \text{\$} \}$

$\text{FIRST}(A) = \{a, b, \text{\$} \}$ , $\text{FIRST}(B) = \{a, b, \epsilon\}$ , $\text{FOLLOW}(A) = \{a, b\}$ , $\text{FOLLOW}(B) = \{\text{\$} \}$

$\text{FIRST}(A) = \{a, b, \epsilon\} = \text{FIRST}(B)$ , $\text{FOLLOW}(A) = \{a, b\}$ , $\text{FOLLOW}(B) = \emptyset$

$\text{FIRST}(A) = \{a, b\} = \text{FIRST}(B)$ , $\text{FOLLOW}(A) = \{a, b\}$ , $\text{FOLLOW}(B) = \{a, b\}$

Official answer and solution

Official answer: A
From: Official GATE 2012 answer key

Solution

Compute FIRST and FOLLOW sets for non-terminals A and B in the given grammar.

Grammar productions:

S \to aAbB \mid bAaB \mid \epsilon

A \to S

B \to S

Computing FIRST sets:

$\text{FIRST}(S) = \{a, b, \epsilon\}$ .
Since $A \to S$ , $\text{FIRST}(A) = \text{FIRST}(S) = \{a, b, \epsilon\}$ .
Since $B \to S$ , $\text{FIRST}(B) = \text{FIRST}(S) = \{a, b, \epsilon\}$ .

Computing FOLLOW sets:

$S$ is start symbol, so $\text{\$} \in \text{FOLLOW}(S)$ .
In $S \to aAbB$ : $A$ is followed by $b$ , so $b \in \text{FOLLOW}(A)$ . $B$ is followed by nothing, so $\text{FOLLOW}(S) \subseteq \text{FOLLOW}(B)$ .
In $S \to bAaB$ : $A$ is followed by $a$ , so $a \in \text{FOLLOW}(A)$ . $B$ is followed by nothing, so $\text{FOLLOW}(S) \subseteq \text{FOLLOW}(B)$ .
Thus, $\text{FOLLOW}(A) = \{a, b\}$ .
Since $A \to S$ , $\text{FOLLOW}(A) \subseteq \text{FOLLOW}(S)$ , meaning $\{a, b\} \subseteq \text{FOLLOW}(S)$ . Combined with $\text{\$}$ , $\text{FOLLOW}(S) = \{a, b, \text{\$} \}$ .
Because $\text{FOLLOW}(S) \subseteq \text{FOLLOW}(B)$ , $\text{FOLLOW}(B) = \{a, b, \text{\$} \}$ .

Therefore:

$\text{FIRST}(A) = \{a, b, \epsilon\} = \text{FIRST}(B)$
$\text{FOLLOW}(A) = \{a, b\}$
$\text{FOLLOW}(B) = \{a, b, \text{\$} \}$

This matches option (A).

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: 52 of 65, printed as CS Q.52
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.