The GATE Grind

GATE 2017 CS – Question 27

Compiler Design · Parsing and Syntax Analysis · 1 mark · Multiple choice

Consider the following grammar:

$P \rightarrow xQRS$

$Q \rightarrow yz \mid z$

$R \rightarrow w \mid \epsilon$

$S \rightarrow y$

What is FOLLOW($Q$)?

  1. $\{R\}$
  2. $\{w\}$
  3. $\{w, y\}$
  4. $\{w, \$\}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\{w, y\}$

Explanation

In $P \rightarrow xQRS$, $Q$ is followed by $R$ and then $S$. FIRST($R$) is $\{w\}$, and since $R$ can be empty, FIRST($S$) $= \{y\}$ also follows $Q$. So FOLLOW($Q$) $= \{w, y\}$.