INTERMEDIATE CODE GENERATION
❏ Intermediate code eliminates the need of a new full compiler for every unique machine
by keeping the analysis portion same for all the compilers.
❏ The second part of compiler, synthesis,
is changed according to the target machine.
❏ It becomes easier to apply the source
code modifications to improve code
performance by applying code
optimization techniques on the intermediate code.
❏ The commonly used intermediate code representations are:
1. Postfix notation
2. Syntax Tree
3. Three Address code
1. Postfix notation
❏ The ordinary(infix) way of writing the sum of a and b is the operator in
the middle: a+b
❏ The postfix notation: ab+
❏ In general,if e1 and e2 are any postfix expressions and X is any binary
operator, then the result of applying X to the values denoted by e1 and
e2 is indicated in postfix notation by e1e2X.
❏ No parentheses are needed in postfix notation.
Example:
1. (a-b)*(c+d)+(a-b) -> ab-cd+*ab-+
2. If e then x else y -> infix: e?x:y
Postfix: exy?
SDD for infix-postfix translation:
Production Semantic Rule
E -> E + T E.lval = E.lval || T.lval || ‘+’
E -> T E.val = T.lval
T -> T * F T.lval = T.lval || F.lval || ‘*’
T -> F T.lval = F.lval
F -> num F.lval = num.lval
SDT for infix-postfix translation:
E -> E + T {printf(“ + ”); }
E -> T { }
T -> T * F {printf(“ * “); }
T -> F { }
F -> num {printf(“num.lval”); }
2. Syntax Trees
❏ The Syntax tree is nothing more than the condensed form of the parse tree,useful
for language constructs.
❏ In syntax tree, internal nodes are operators and child nodes are operands.
❏ To form syntax tree put parentheses in the expression, this way it’s easy to
recognize which operand comes first.
❏ example:
x = (a+b*c) / (a-b*c)
Direct Acyclic Graph for Expressions:
❏ The DAG is used to represent the structure of basic blocks, to visualize the flow between basic blocks, and to
provide optimization techniques in the basic block.
❏ DAG can be understood here:
❏ Leaf nodes represent identifiers, names and constants.
❏ Interior nodes represent operators also represent the results of expressions or the identifiers where the
values to be stored or assigned.
❏ A DAG for an expression identifies the common sub-expressions (more than once) in the
expression.
❏ Example:
DAG for expression a+a*(b-c)+(b-c)*d
SDD for DAG:
❏ A DAG is obtained if the function constructing a node first checks to see
whether an identical node already exists. If a previously created identical
node exists, the existing node is returned.
❏ For example,
before constructing a new node with label op and fields with pointers to
left and right, Node(op,left,right) can check whether such a node has
already been constructed. If so, Node(op,left,right) can return a pointer to
the existing node otherwise it creates a new node.
Example:
SDD to produce syntax tree for assignment statement
Production Semantic Rules
S -> id := E S.node = Node(‘assign’,Leaf(id,id.entry), E.node)
E -> E1 + E2 E.node = Node(‘+’,E1.node,E2.node)
E -> E1 * E2 E.node = Node(‘*’,E1.node,E2.node)
E -> -E1 E.node = Unode(‘unmins’,E1.node)
E -> (E) E.node = E.node
E -> id E.node = Leaf(id,id.entry)
3. Three-Address code:
❏ A statement involving no more than three references (two for operands
and one for result) is known as three address statement.
❏ A sequence of three address statements is known as three address code.
Three address statement is of the form x= y op z, here x,y,z will have
address (memory location).
❏ Sometimes a statement might contain less than three references but it is
still called three address statement.
❏ Example: a source language expression X+Y*Z might be translated into
sequence of three address statements:
t1 = Y * Z
t2 = X + t1 where t1,t2 are temporary variables.
Example:
❏ Three address code is a linearized representation of a syntax tree or a DAG in which explicit names
correspond to the interior nodes of the graph
