The GATE Grind

GATE 2016 CS – Question 56

Compiler Design · Syntax-Directed Translation · 2 marks · Multiple choice

Consider the following Syntax Directed Translation Scheme (SDTS), with non-terminals $\{S, A\}$ and terminals $\{a, b\}$.

$S \rightarrow aA$ { print 1 }

$S \rightarrow a$ { print 2 }

$A \rightarrow Sb$ { print 3 }

Using the above SDTS, the output printed by a bottom-up parser, for the input $aab$ is:

  1. 1 3 2
  2. 2 2 3
  3. 2 3 1
  4. syntax error

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 2 3 1

Explanation

A bottom-up parser prints at each reduction. The first $a$ is shifted, and the next $a$ is reduced using $S \rightarrow a$, which prints 2. Then $b$ is read and $Sb$ is reduced to $A$, which prints 3. Finally the first $a$ and $A$ are reduced using $S \rightarrow aA$, which prints 1. The output is 2 3 1.