edited by
7,917 views
15 votes
15 votes

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\}$
  1. Using this $\textsf{SDTS},$ construct a parse tree for the expression $4 - 2 - 4 * 2$  and also compute its $E.val$.
  2. 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$.
edited by

3 Answers

Best answer
30 votes
30 votes

   Given expression $4-2-4*2$

Total reductions = 10

  1. Expression value, $E.val = 12$
  2. Total number of reductions performed, $E.red = 10$ (number of non-leaf nodes in the parse tree)
edited by
33 votes
33 votes
SDTS to find the number of reductions::

E→ E1 * T {E.red = E1.red+ T.red+1}

E→T {E.red = T.red+1}

T→F - T1 {T.red = F.red + T1.red+1}

T→F {T.red = F.red+1}

F→2 {F.red = 1}

F→4 {F.red = 1}
10 votes
10 votes

A. Given Expression is 4 - 2 - 4 * 2 , which can be rewritten as ((4 - (2 - 4))* 2) which is equal to 12.

Related questions

22 votes
22 votes
6 answers
1