Mumbai University > Computer Engineering > Sem6 > System Programming and Compiler Construction

Marks: 10M

Year: May 2015

• Intermediate code Generation phase takes as input parse tree representation and generates an intermediate representation.

• So that the translation process can be done faster.

• Program that performs ICG is called Intermediate code Generation.

• While translating a source program into a functionally equivalent object code representation, a parser may first generate an intermediate representation.

• This makes retargeting of the code possible and allows some optimizations to be carried out that would otherwise not be possible.

  The following are commonly used intermediate representations:

  • Postfix notation
  • Syntax tree
  • Three-address code

  1. Postfix notation

  • In postfix notation, the operator follows the operand. For example, in the expression ( a ˆ’ b ) * ( c + d ) + ( a ˆ’ b ), the postfix representation is:

  $$\text{Ab – Cd * Ab - +}$$

  2. Syntax tree

  • The syntax tree is nothing more than a condensed form of the parse tree. The operator and keyword nodes of the parse tree are moved to their parent, and a chain of single productions is replaced by single link.

3. Three-address code

• Three address code is a sequence of statements of the form x = y op z. Since a statement involves no more than three references, it is called a "three-address statement," and a sequence of such statements is referred to as three-address code.
• For example, the three-address code for the expression a + b * c + d is:

$$T1 = B * C \\ T2 = A + T2 \\ T3 = T3 + D$$

• Sometimes a statement might contain less than three references; but it is still called a three-address statement.

• The following are the three-address statements used to represent various programming language constructs:

• Used for representing arithmetic expressions:

$$ X = Y \ op \ Z \\ X = \ \ op \ Y \\ X = Y $$

• Used for representing Boolean expressions:

$$If A \gt B \ \ goto L \\ goto \ \ L \ \ $$

• Used for representing array references and dereferencing operations:

$$x = y[i] \\ x[i] = y \\ x = ^*y \\ ^* x = y$$

• Used for representing a procedure call:

$$Param \ \ T \\ Call \ \ p,n$$

• Representation of three address code

  • Records with fields for the operators and operands can be used to represent three-address statements.

  • It is possible to use a record structure with four fields: the first holds the operator, the next two hold the operand1 and operand2, respectively, and the last one holds the result.

  • This representation of a three-address statement is called a "quadruple representation".

2. Triple Representation

• The contents of the operand1, operand2, and result fields are therefore normally the pointers to the symbol records for the names represented by these fields.

• Hence, it becomes necessary to enter temporary names into the symbol table as they are created.

• This can be avoided by using the position of the statement to refer to a temporary value.

• If this is done, then a record structure with three fields is enough to represent the three-address statements:

• The first holds the operator value, and the next two holding values for the operand1 and operand2, respectively. Such a representation is called a "triple representation".

• The contents of the operand1 and operand2 fields are either pointers to the symbol table records, or they are pointers to records (for temporary names) within the triple representation itself.

• For example, a triple representation of the three-address code for the statement x = (a + b)* ˆ’ c/d.

3. Indirect Triple Representation

• Another representation uses an additional array to list the pointers to the triples in the desired order.

• This is called an indirect triple representation. For example, a triple representation of the three-address code for the statement x = ( a + b )* ˆ’ c/d

Comparison

• By using quadruples, we can move a statement that computes A without requiring any changes in the statements using A, because the result field is explicit.
• However, in a triple representation, if we want to move a statement that defines a temporary value, then we must change all of the pointers in the operand1 and operand2 fields of the records in which this temporary value is used.
• Thus, quadruple representation is easier to work with when using an optimizing compiler, which entails a lot of code movement.
• Indirect triple representation presents no such problems, because a separate list of pointers to the triple structure is maintained.
• When statements are moved, this list is reordered, and no change in the triple structure is necessary; hence, the utility of indirect triples is almost the same as that of quadruples.