Official PYQ · 2016Set 1 · Q46Syntax-directed TranslationMCQ1 mark

GATE CS 2016 Set 1 Q46 — Syntax-directed Translation

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

$S \to aA \quad \{\text{print }1\}$

$S \to a \quad \{\text{print }2\}$

$A \to Sb \quad \{\text{print }3\}$

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

View worked solution

Answer: C

A bottom-up parser performs reductions in the reverse order of a rightmost derivation.

First, let's find the rightmost derivation for the input string $aab$ using the given grammar:

\begin{aligned} S &\Rightarrow aA && \text{(using } S \to aA\text{)}\\ &\Rightarrow aSb && \text{(using } A \to Sb\text{)}\\ &\Rightarrow aab && \text{(using } S \to a\text{)} \end{aligned}

The sequence of reductions performed by the bottom-up parser is the exact reverse of this rightmost derivation:

First reduction: $a \to S$ (reducing the second $a$ in $aab$ to $S$ )
Associated action: {print 2}
Second reduction: $Sb \to A$ (reducing $Sb$ to $A$ )
Associated action: {print 3}
Third reduction: $aA \to S$ (reducing the entire string $aA$ to the start symbol $S$ )
Associated action: {print 1}

Thus, the output printed by the parser is: $2 \ 3 \ 1$ .

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions