GATE CS 2022 Q.65: Syntax-Directed Translation

Consider the following grammar along with translation rules.

S \to S_1 \,\#\, T \quad \{S.val = S_1.val * T.val\}

S \to T \quad \{S.val = T.val\}

T \to T_1 \,\%\, R \quad \{T.val = T_1.val \div R.val\}

T \to R \quad \{T.val = R.val\}

R \to \text{id} \quad \{R.val = \text{id}.val\}

Here # and % are operators and id is a token that represents an integer and id.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 _____________.

Your answer

Official answer and solution

Official answer: 80
From: Official GATE 2022 answer key

Solution

Construct the parse tree according to the grammar rules and compute synthesized attribute values bottom-up.

The grammar is:

S \to S_1 \,\#\, T \quad \{S.val = S_1.val * T.val\}

S \to T \quad \{S.val = T.val\}

T \to T_1 \,\%\, R \quad \{T.val = T_1.val \div R.val\}

T \to R \quad \{T.val = R.val\}

R \to \text{id} \quad \{R.val = \text{id}.val\}

The grammar specifies that:

Operator # is left-associative at the $S$ -level, performing multiplication ( $*$ ).
Operator % is left-associative at the $T$ -level, performing division ( $\div$ ), with higher precedence than #.

The expression is $20 \,\#\, 10 \,\%\, 5 \,\#\, 8 \,\%\, 2 \,\%\, 2$ .

Evaluating each $T$ -term:

Term 1: $T_1 = 20 \implies T_1.val = 20$
Term 2: $T_2 = 10 \,\%\, 5 \implies 10 \div 5 = 2$
Term 3: $T_3 = 8 \,\%\, 2 \,\%\, 2$ $T_{3} = 8 % 2 % 2$ :
- By left-associativity: $(8 \div 2) \div 2 = 4 \div 2 = 2$

Evaluating the $S$ -level productions:

$S_0 \to T_1 \implies S_0.val = 20$
$S_1 \to S_0 \,\#\, T_2 \implies S_1.val = S_0.val * T_2.val = 20 * 2 = 40$
$S \to S_1 \,\#\, T_3 \implies S.val = S_1.val * T_3.val = 40 * 2 = 80$

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

Final answer

Common trap

Evaluating % from right to left as $8 \div (2 \div 2) = 8$ , violating the left-associative production $T \to T_1 \,\%\, R$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 65 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source