Skip to content
GATEiit

GATE CSE 2022 Q65: Evaluating an expression with a syntax-directed translation

Question

Consider the following grammar along with translation rules.

S→S1#T{S.val=S1.val∗T.val}S→T{S.val=T.val}T→T1%R{T.val=T1.val÷R.val}T→R{T.val=R.val}R→id{R.val=id.val}\begin{aligned} 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 id && \{R.val = id.val\} \end{aligned}

Here #\# and %\% are operators and idid is a token that represents an integer and id.valid.val represents the corresponding integer value. The set of non-terminals is {S,T,R,P}\{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.valS.val for root of the parse tree for the expression 20#10%5#8%2%220 \# 10 \% 5 \# 8 \% 2 \% 2 is _____________.

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 80 (official GATE 2022 final answer key)

Concept used: The grammar fixes precedence and associativity: % (division) binds tighter than # (multiplication), and both are left-associative.

First step: Group as 20#(10%5)#((8%2)%2)20 \# (10 \% 5) \# ((8 \% 2) \% 2), i.e. 20×(10÷5)×((8÷2)÷2)20 \times (10 \div 5) \times ((8 \div 2) \div 2).

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key