UNIT - 3
Intermediate-Code Generation
Directed
(
using Syntax Translation)
Back-end and Front-end of A Compiler
Back-end and Front-end of A Compiler
Close to source language Close to machine language
(e.g. syntax tree)
m x n compilers can be built by writing just m front ends and nback ends
Back-end and Front-end of A Compiler
Includes:
• Type checking
•Any syntactic checks that remain after
parsing (e.g. ensure break statement is
enclosed within while-, for-, or switch
statements).
Intermediate Code
Data structure
data structure
£
data structure
Directed Acyclic
Graph
Postfix Code
②
②
⑧
Parse Tree too id , * id e tidy
Syntax Tree
• Similar to parse tree but
• Internal node represents operations
• Leaf node represents operands
• Semantic rules are only applied on reduction
Syntax Tree
Syntax Tree
+ *
a * - d
a - b c
b c
Syntax Tree
+ *
a * - d
a - b c
b c
Syntax Tree
+ *
a * - d
a - b c
b c
Syntax Tree
+
L 7
+ * - -
a * - d ✓
L ✓ L
a - b c L ✓
b c
Node can have more than
one parent
Directed Acyclic Graph (DAG):
• More compact representation
• Gives clues regarding generation of efficient code
Example
Construct the DAG for:
=L --_
-
# → *
← → ← →
Is it
^
,
Etty n
tatting atty syntan Correct
+
✓ →
5÷→
E'
nd Jg
-
y
How to Generate DAG from
Syntax-Directed Definition?
All what is needed is that functions such as Node and Leaf above
check whether a node already exists. If such a node exists, a pointer
is returned to that node.
How to Generate DAG from
Syntax-Directed Definition?
Data Structure for Syntax
i. it
Tree/DAG: Array
10
( Fn
symbol
table)
Data Structure for Syntax Tree/DAG:
Array
Leaves
Left and right children
Operation code of an intermediate node
Scanning the array each time a new node is needed, is not
an efficient thing to do.
Data Structure for Syntax Tree/DAG: Hash
Table
quite10
or
b t 10
Hash function = h(op, L, R)
Three-Address Code
• Another option for intermediate presentation
• Built from two concepts:
– addresses and instructions
• At most one operator apart from ’=’
• At most three operands (addresses)
at a * (b -
c ) t Cb -
c) Ad
Address
Can be one of the following:
• A name: source program name
• A constant
• Compiler-generated temporary
Instructions
Procedure call such as p(x1, x2, …,xn) is implemented as:
Example
OR
Choice of Operator Set
• Rich enough to implement the
operations of the source language
• Close enough to machine instructions to
simplify code generation
Data Structure
( three address code)
for
How to present these instructions in a
data structure?
– Quadruples
– Triples
– Indirect triples
Data Structure: Quadruples
• Has four fields: op, arg1, arg2, result
• Exceptions:
– Unary operators: no arg2
– Operators like param: no arg2, no result
– (Un)conditional jumps: target label is the
result
of
Data Structure: Triples
• Only three fields: no result field
• Results referred to by its position
Data Structure: Indirect
Triples
• When instructions are moving around
during optimizations: quadruples are
better than triples.
• Indirect triples solve this problem
Optimizing complier can reorder instruction
List of pointers to triples
list, instead of affecting the triplesthemselves
Single-Static-Assignment (SSA)
• Is an intermediate presentation
• Facilitates certain code optimizations
• All assignments are to variables with
distinct names
Single-Static-Assignment (SSA)
Example:
If we use different names forX in true part and false part, then which name
shall we use in the assignment of y = x * a ?
The answer is: Ø-function
Returns the value of its argument that corresponds to the control-flow
path that was taken to get to the assignment statement containing the
Ø-function
Example
