Write the formula of Example 15.4 as an expression tree (a syntax tree in which each operator is represented by an internal node whose children are its operands). Convert your tree to an expression DAG by merging identical nodes. Comment on the redundancy in the tree and how it relates to Figure 15.4.

Figure 15.4:

Transcribed Image Text:

push a push b push c r2 := a r3:= b r4 := c add r1 := r2 + r3 add r1 := r1 + r4 push 2 r1 := r1/2 --S divide pop s push s push s r2 := r1 – r2 --S - a push a subtract push s push b r3:= r1 – r3 --s-b subtract push s push c r4:= r1 - r4 --S - C subtract r3:= r3 x r4 multiply multiply multiply push sqrt r2:= r2 x r3 r1:= r1 x r2 call sqrt call