GATEverse — GATE CSE previous year questions

Consider the syntax directed translation scheme $\textsf{(SDTS)}$ given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction. $E\rightarrow E_{1} * T \qquad \{E.val = E_{1}.val * T.val\}$ $E\rightarrow T \qquad \qquad \{E.val = T.val\}$ $T\rightarrow F - T_{1}\qquad \{T.val = F.val - T_{1}.val\}$ $T\rightarrow F \qquad \qquad \{T.val = F.val\}$ $F\rightarrow 2 \qquad \qquad \{F.val = 2\}$ $F\rightarrow 4 \qquad \qquad \{F.val = 4\}$

(A)

Using this $\textsf{SDTS},$ construct a parse tree for the expression $4 - 2 - 4 * 2$ and also compute its $E.val$ .

(B)

It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the $\textsf{SDTS}$ given, without changing the grammar, to find $E.red$ , the number of reductions performed while reducing an input to $E$ .