1.1k views

Consider the syntax directed translation scheme (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 {E.val = E$_{1}$.val * T.val}

E$\rightarrow$ T {E.val = T.val}

T$\rightarrow$ F - T$_{1}$ {T.val = F.val - T$_{1}$.val}

T$\rightarrow$ F {T.val = F.val}

F$\rightarrow$2 {F.val = 2}

F$\rightarrow$4 {F.val = 4}

1. Using this 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 SDTS given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$.
edited | 1.1k views

Given expression $4-2-4*2$

Total reduction $=10$

1. expression value =12
2. a total number of reductions performed =10

answered by Loyal (7.7k points)
edited by
+2
number of reductions is nothing but the number of non-leaves in the parse tree ...

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

answered by Active (3k points)
0
how do we know that minus '-' is right to left?
+1
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
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}
answered by Loyal (8.7k points)
0
@VS ,you can edit the selected answer to include this as part b answer.