GATE 2022 CS Q.65: solution and answer

GATE 2022 · CSQ.65 · 2 marks · NAT

Consider the following grammar along with translation rules.

$S \to S_{1} # T {S . val = S_{1} . val * T . val}$
$S \to T {S . val = T . val}$
$T \to T_{1} % R {T . val = T_{1} . val \div R . val}$
$T \to R {T . val = R . val}$
$R \to i d {R . val = i d . val}$

Here # and % are operators and $i d$ is a token that represents an integer and $i d . val$ represents the corresponding integer value. The set of non-terminals is ${S, T, R, P}$ and a subscripted non-terminal indicates an instance of the non-terminal.

Using this translation scheme, the computed value of $S . val$ for root of the parse tree for the expression 20#10%5#8%2%2 is ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The computed value of $S . val$ at the root is $80$ .

Official answer: 80Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

The grammar is left-recursive in both $S \to S_{1} # T$ and $T \to T_{1} % R$ , so both # and % are left-associative. % is generated inside $T$ , which sits below $S$ , so % binds tighter than #.
Group the input by #: $20 # (10%5) # (8%2%2)$ .
First $T$ is $T \to R$ with $R \to i d$ , so $T . val = 20$ .
Second $T$ uses $T \to T_{1} % R$ : $T . val = 10 \div 5 = 2$ .
Third $T$ is left-associative, so it is $(8 \div 2) \div 2 = 4 \div 2 = 2$ .
$S$ is left-recursive, so $S . val = (20 * 2) * 2$ .
Hence $S . val = 40 * 2 = 80$ .

KEY IDEA

The grammar fixes the parse. A left-recursive rule makes its operator left-associative, and an operator generated lower in the grammar ( $%$ in $T$ ) binds tighter than one generated higher up ( $#$ in $S$ ). Parse the string first, then evaluate each node bottom-up.

WATCH OUT FOR

Using the usual meaning of # and %, or evaluating strictly left to right. That computes $((((20 \cdot 10) \div 5) \cdot 8) \div 2) \div 2 = 80$ here by coincidence, but the operations are not in that order. Another slip is grouping $8%2%2$ as $8 \div (2 \div 2) = 8$ instead of $(8 \div 2) \div 2 = 2$ .

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 7 Syntax-directed translation questions, with notes

GATE 2022 CS Q.65: solution and answer

Answer and solution

More Syntax-directed translation questions