8.3 N-tuple Notation

In this scheme of Intermediate code representation, we have a sequence of N-tuples, where N = 3 or 4. The first field of the N-tuple is an operator and the rest N – 1 fields are operands. If N = 3, it is called Triple notation and if N = 4, it is called Quadruple notation, these two being the most popular ones.

8.3.1 Triple notation

The triple notation is also called “two-address code” (TAC). An expression a + b is represented as An original expression a * b + c * d would be represented as a sequence of such triples:

Here, (1) denotes the result of triple 1 and (2) the result of triple 2.

A statement:

IF a > b THEN c = a ELSE c = b + 1 FI

is represented by a triple sequence:

Code optimization is difficult with the triple notation, because optimization usually involves movement of the triples within the sequence. This will require changes in the sequence reference numbers within the triples. If you have done machine language programming of microprocessors, you will readily see the difficulty. In fact, the triples are like instructions of some two-address virtual machine.

One way in which the problem with the triples can be solved is to use indirect triples. There we use an array of pointers to the actual triples, which are not moved. If need arises during the optimization phase to move any triples, only the corresponding pointers in the array are moved.

8.3.2 Quadruple Notation

A quadruple consists of four fields:

For example, an expression (a + b)* (c + d) – e can be represented by:

These schemes ease optimization. T1, etc. which represent temporary values, and are called temporary variables, can later be assigned to CPU registers or memory addresses, during the Code Generation phase.

8.3.3 Generation of N-tuple Code

We have already encountered the scheme for N-tuple generation while discussing the Intermediate code generation for the SIMPLE language in Section 2.2.3. We do not repeat it here.