3 address code

Question

The minimum number of variables required in 3 address code of the given expression are:______

a * b * c + d - a + e * f - g + h

Order of precedence: * > + > - ; with * as left associative and +,- as right associative.

Comments

$7?$

---

The answer is 3.

---

How?

---

That's what I'm here to know man. XD

---

The solution is this. But I don't understand why the variables are being repeated on the L.H.S.

---

3 Address code aim to represent any production in terms of 3 variables and it does so by overriding value of a var with other result of other operations.

So, according to given Order of precedence: * > + > - ; with * as left associative and +,- as right associative, we got 

( ( ( ( a * b ) *  c ) + d )  - ( ( a + ( e * f ) ) - ( ( g + h  ) ) ) 

and it could be divided into 3 parts as 

t1 = a * b; t1 = t1*c; t1 = t1+d => this represents part 1. And thus final t2 => part 2, final t3 => part 3.

and in order to fit these many results into single variable, we need to keep overwrite the variable and that's why variables are being repeated on the L.H.S.

---

After rules of associativity and precedencce, if we think of last expression as E1 - E2, if we evaluate E1, then answer is 3, but if we evaluate E2 first, we would be getting 2 as the minimum answer. -> explained below.

t1 = e*f

t1 = t1+a

t2 = g+h

t2 = t1 - t2

t1 = a*b

t1 = t1*c

t1 = t1+d

t1= t1-t2

Shouldn't minimum answer be 2? Am i doing anything wrong here?

---

3 ?

---

Sambhrant Maurya because they r not asking for SSA

Answer 1

@Sambhrant Mayura

The question is asking only about the "MINIMUM number of variables for 3 Address Code". It is NOT asking the "Static Single Assignment" of 3 Address Code. Hence the variables on LHS can be repeated, which cannot be done in Static Single Assignment. You can refer this link.

I hope you doubt is clear by now.