The GATE Grind

GATE 2022 CS – Question 65

Compiler Design · Syntax-Directed Translation · 2 marks · Numerical answer

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 id\quad\{R.val=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 _____________.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 80

Explanation

Precedence and associativity: `%` has higher precedence than `#`; both are left-associative (from the productions $S\to S_1\#T$ and $T\to T_1\%R$, which are left-recursive). `#` means multiplication, `%` means division.

Expression `20#10%5#8%2%2`. Because `%` binds tighter, group `%` first:
$$20\ \#\ (10\%5)\ \#\ (8\%2\%2).$$

Then `#` left to right: $20*2*2=\mathbf{80}$.

More Syntax-Directed Translation questions

All Syntax-Directed Translation questions →