GATE 2022 CS – Question 65
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).$$
- $10\%5=10\div5=2$.
- $8\%2\%2$ is left associative: $(8\div2)\div2=4\div2=2$.
Then `#` left to right: $20*2*2=\mathbf{80}$.