4,456 views

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$.

$-$ is farthest from the start symbol, and $*$ is nearest to the start symbol, therefore, $-$ has higher precedence than $*$. $-$ is right associative as if an expression contains more than one $-$ then tree will grow towards right side, and $-$ present at the lower part of the tree towards right side will be evaluated before the $-$ present at the upper part of the tree towards left side, as Production T is right recursive.

So, expression will evaluate to 12.
Dont assume precedence of operator by yourself always take care of precedence and associativity given in question.

Subscribe to GO Classes for GATE CSE 2022

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)

1 comment

number of reductions is nothing but the number of non-leaves in the parse tree ...
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}
by

1 comment

@VS ,you can edit the selected answer to include this as part b answer.

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

by

how do we know that minus '-' is right to left?
second minus is at lower level than 1st minus so first 2-4=-2 then 4-(-2)=6 then 6*2 since is at higher level