Scribd
Upload
14 views19 pages

Intermediate Code Generation in Compilers

The document discusses intermediate code generation in compilers. It covers: - Intermediate code acts as an interface between the front-end and back-end of a compiler. It allows separating source language details from target machine details. - Syntax trees can be represented as DAGs to share common subexpressions and optimize code generation. Three-address code is introduced to have at most one operator per instruction. - Code generation involves type checking, translating expressions and statements to three-address code incrementally, handling control flow and addressing memory. Backpatching updates symbolic labels to actual addresses.

Uploaded by

ipo ipo
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
14 views19 pages

Intermediate Code Generation in Compilers

The document discusses intermediate code generation in compilers. It covers: - Intermediate code acts as an interface between the front-end and back-end of a compiler. It allows separating source language details from target machine details. - Syntax trees can be represented as DAGs to share common subexpressions and optimize code generation. Three-address code is introduced to have at most one operator per instruction. - Code generation involves type checking, translating expressions and statements to three-address code incrementally, handling control flow and addressing memory. Backpatching updates symbolic labels to actual addresses.

Uploaded by

ipo ipo
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Intermediate Code Generation

Introduction
Intermediate code is the interface between front end
and back end in a compiler
Ideally the details of source language are confined to
the front end and the details of target machines to the
back end .

Static Intermediate Code


Parser
Checker Code Generator Generator
Variants of syntax trees
It is sometimes beneficial to crate a DAG instead of
tree for Expressions.
This way we can easily show the common sub-
expressions and then use that knowledge during code
generation
Example: a+a*(b-c)+(b-c)*d

+ *

*
d
a -

b c
creating DAG’s
Production Semantic Rules
1) E -> E1+T [Link]= new Node(‘+’, [Link],[Link])
2) E -> E1-T [Link]= new Node(‘-’, [Link],[Link])
3) E -> T [Link] = [Link]
4) T -> (E) [Link] = [Link]
5) T -> id [Link] = new Leaf(id, [Link])
6) T -> num [Link] = new Leaf(num, [Link])
Three address code
In a three address code there is at most one operator
at the right side of an instruction
Example:

+
t1 = b – c
+ * t2 = a * t1
t3 = a + t2
* t4 = t1 * d
d
t5 = t3 + t4
a -

b c
Forms of three address
instructions
 x = y op z
 x = op y
x = y
 goto L
 if x goto L and ifFalse x goto L
 if x relop y goto L
 Procedure calls using:
 call p,n
 y = call p,n
 x = y[i] and x[i] = y
 x = &y and x = *y and *x =y
Example
do i = i+1;
while (a[i] < v);
L: t1 = i + 1 100: t1 = i + 1
i = t1 101: i = t1
t2 = i * 8 102: t2 = i * 8
t3 = a[t2] 103: t3 = a[t2]
if t3 < v goto L 104: if t3 < v goto 100

Symbolic labels Position numbers


Data structures for three
address codes
Quadruples
Has four fields: op, arg1, arg2 and result
Triples
Temporaries are not used and instead references to
instructions are made
Indirect triples
In addition to triples we use a list of pointers to triples
Storage Layout for Local Names
Computing types and their widths
Translation of Expressions and
Statements
We discussed how to find the types and offset of
variables
We have therefore necessary preparations to discuss
about translation to intermediate code
We also discuss the type checking
Three-address code for expressions
Incremental Translation
Addressing Array Elements
Layouts for a two-dimensional array:
Abstract syntax tree for the
function definition
fun length(x) =
if null(x) then 0 else length(tl(x)+1)

This is a polymorphic function


Control Flow
boolean expressions are often used to:
Alter the flow of control.
Compute logical values.
Short-Circuit Code


Generating three-address code for booleans
Backpatching
 Previous codes for Boolean expressions insert symbolic labels for
jumps
 It therefore needs a separate pass to set them to appropriate addresses
 We can use a technique named backpatching to avoid this
 We assume we save instructions into an array and labels will be index
in the array
 For nonterminal B we use two attributes [Link] and [Link]
together with following functions:
 makelist(i): create a new list containing only I, an index into the array
of instructions
 Merge(p1,p2): concatenates the lists pointed by p1 and p2 and returns a
pointer to the concatenated list
 Backpatch(p,i): inserts i as the target label for each of the instruction
on the list pointed to by p
Translation of a switch-statement

You might also like