Official PYQ · 2006Q59Parsing (LL, LR)MCQ1 mark

GATE CS 2006 Q59 — Parsing (LL, LR)

Consider the following translation scheme.

$S\rightarrow ER$
$R\rightarrow *E\left \{ \text{print}(\text{‘}*\text{’}); \right \} R\mid \varepsilon$
$E\rightarrow F+E\left \{ \text{print}(\text{‘}+\text{’}); \right \}\mid F$
$F\rightarrow (S)\mid id \left \{ \text{print}(id.value); \right \}$

Here $id$ is a token that represents an integer and $id.value$ represents the corresponding integer value. For an input $\text{‘}2 * 3 + 4\text{’},$ this translation scheme prints

View worked solution

Answer: D

To find the output of the translation scheme for the input $2 * 3 + 4$ , we construct the parse tree and execute the semantic actions during a depth-first (post-order) traversal.

The parse tree for the input string $id_2 * id_3 + id_4$ is structured as follows:

$S \rightarrow E \; R$ $S \to E R$
- $E \rightarrow F \rightarrow id_2 \; \{\text{print}(2);\}$
- $R \rightarrow * \; E_1 \; \{\text{print}(‘*’);\} \; R_1$ $R \to * E_{1} {print (‘ * ’);} R_{1}$
  - $E_1 \rightarrow F_1 + E_2 \; \{\text{print}(‘+’);\}$ $E_{1} \to F_{1} + E_{2} {print (‘ + ’);}$
    - $F_1 \rightarrow id_3 \; \{\text{print}(3);\}$
    - $E_2 \rightarrow F_2 \rightarrow id_4 \; \{\text{print}(4);\}$
  - $R_1 \rightarrow \varepsilon$

Performing a depth-first traversal, the semantic actions are executed in the following order:

Under $E$ , the token $id_2$ is matched: prints 2
Under $E_1$ , the token $id_3$ is matched: prints 3
Under $E_2$ , the token $id_4$ is matched: prints 4
The action in $E_1 \rightarrow F_1 + E_2 \{\text{print}(‘+’);\}$ is executed: prints +
The action in $R \rightarrow * E_1 \{\text{print}(‘*’);\} R_1$ is executed: prints *

Combining the printed values in order of execution gives: 2 3 4 + *.

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

Published 10 Oct 2026

Report a correction

More Parsing (LL, LR) questions

GATE CS 2006 Q59 — Parsing (LL, LR)

Related questions