Formula Sheets: Intermediate Code Generation | Compiler Design - Computer Science Engineering (CSE) PDF Download

 Page 1


Intermediate Code Gener ation F ormula Sheet
1. Intermediate Code F orms
• Three-A ddress Code : Instruction of form x = y op z , where x,y,z are vari-
ables, constants, or tempor aries.
– Examples : t
1
= a+b , t
2
= t
1
*c .
– At most one oper ator on right-hand side.
• Quadruples : (op,arg
1
,arg
2
,result) , e.g., (+,a,b,t
1
) .
• Triples : (op,arg
1
,arg
2
) , resu lt referenced b y index, e.g., (+,a,b) .
• Indirect Triples : List of pointers to triples for code reordering.
• Postfix Notation : Oper ator follows oper ands, e.g., ab+c* .
2. S yntax-Directed Tr anslation for Code Gener ation
• Definition : Uses SDD/SD T to tr anslate high-level code to intermediate code.
• Attributes :
– S ynthesized : E.code (code string), E.addr (address of result).
– Inherited : E.place (tempor ary variable for result).
• Example SDD for Expressions :
– E ? E
1
+T{E.code = E
1
.code||T.code|| gen(E.place = E
1
.place+T.place);E.place =
newtemp()}
– E ? T{E.code = T.code;E.place = T.place}
– T ? num{T.code = ?;T.place = num.lexval}
• Tr anslation Scheme : Embed actions, e.g.,E ? E
1
+T{ emit(+,E
1
.place,T.place,E.place)} .
3. Type Checking
• Type Expressions : Represent types, e.g., int, arr a y(n, int) .
• Type Rules :
– F or E ? E
1
+E
2
, E.type = int if E
1
.type = E
2
.type = int, else error .
– F or E ? arr a y(n,T) , E.type = arr a y(n,T.type) .
• Unification : Ensure type compatibility , e.g., E
1
.type = E
2
.type .
• Time Complexity : O(|E|) , where|E| is expression size.
1
Page 2


Intermediate Code Gener ation F ormula Sheet
1. Intermediate Code F orms
• Three-A ddress Code : Instruction of form x = y op z , where x,y,z are vari-
ables, constants, or tempor aries.
– Examples : t
1
= a+b , t
2
= t
1
*c .
– At most one oper ator on right-hand side.
• Quadruples : (op,arg
1
,arg
2
,result) , e.g., (+,a,b,t
1
) .
• Triples : (op,arg
1
,arg
2
) , resu lt referenced b y index, e.g., (+,a,b) .
• Indirect Triples : List of pointers to triples for code reordering.
• Postfix Notation : Oper ator follows oper ands, e.g., ab+c* .
2. S yntax-Directed Tr anslation for Code Gener ation
• Definition : Uses SDD/SD T to tr anslate high-level code to intermediate code.
• Attributes :
– S ynthesized : E.code (code string), E.addr (address of result).
– Inherited : E.place (tempor ary variable for result).
• Example SDD for Expressions :
– E ? E
1
+T{E.code = E
1
.code||T.code|| gen(E.place = E
1
.place+T.place);E.place =
newtemp()}
– E ? T{E.code = T.code;E.place = T.place}
– T ? num{T.code = ?;T.place = num.lexval}
• Tr anslation Scheme : Embed actions, e.g.,E ? E
1
+T{ emit(+,E
1
.place,T.place,E.place)} .
3. Type Checking
• Type Expressions : Represent types, e.g., int, arr a y(n, int) .
• Type Rules :
– F or E ? E
1
+E
2
, E.type = int if E
1
.type = E
2
.type = int, else error .
– F or E ? arr a y(n,T) , E.type = arr a y(n,T.type) .
• Unification : Ensure type compatibility , e.g., E
1
.type = E
2
.type .
• Time Complexity : O(|E|) , where|E| is expression size.
1
4. Directed A cyclic Gr aph (D A G)
• Definition : Gr aph representing expressions, nodes for oper ators/oper ands,
edges for dependencies.
• Construction :
– Leaf nodes: V ariables, constants.
– Internal nodes: Oper ators with children as oper ands.
– Reuse nodes for common subexpressions.
• Use : Eliminate redundant computations, optimize code.
• Time Complexity : O(|E|) for construction, wh ere|E| is expression size.
5. Basic Blocks and Flow Gr aphs
• Basic Block : Sequence of instructions with single entry and exit.
– Starts with leader (first instruction, target of jump, or follows jump).
– Ends before next leader .
• Flow Gr aph : Directed gr aph of basic blocks, edges represent control flow .
• Construction Algorithm :
– Identify leaders.
– Group instructions between leaders into blocks.
– A dd edges based on jumps/br anches.
• Time Complexity : O(n) , where n is number of instructions.
6. Peephole Optimization
• Definition : Local optimization over small code window (2-3 instructions).
• T echniques :
– Constant F olding : Evaluate t = 2+3 to t = 5 .
– Strength Reduction : Replace t = a*2 with t = a+a .
– Dead Code Elimination : Remove t = a+b if t unused.
– Redundant Load/Store Elimination : Remove x = y;y = x .
• Time Complexity : O(w) , where w is window size (constant).
7. Time Complexities
• Three-A ddress Code Gener ation : O(|w|) , where|w| is input length.
• Type Checking : O(|E|) .
2
Page 3


Intermediate Code Gener ation F ormula Sheet
1. Intermediate Code F orms
• Three-A ddress Code : Instruction of form x = y op z , where x,y,z are vari-
ables, constants, or tempor aries.
– Examples : t
1
= a+b , t
2
= t
1
*c .
– At most one oper ator on right-hand side.
• Quadruples : (op,arg
1
,arg
2
,result) , e.g., (+,a,b,t
1
) .
• Triples : (op,arg
1
,arg
2
) , resu lt referenced b y index, e.g., (+,a,b) .
• Indirect Triples : List of pointers to triples for code reordering.
• Postfix Notation : Oper ator follows oper ands, e.g., ab+c* .
2. S yntax-Directed Tr anslation for Code Gener ation
• Definition : Uses SDD/SD T to tr anslate high-level code to intermediate code.
• Attributes :
– S ynthesized : E.code (code string), E.addr (address of result).
– Inherited : E.place (tempor ary variable for result).
• Example SDD for Expressions :
– E ? E
1
+T{E.code = E
1
.code||T.code|| gen(E.place = E
1
.place+T.place);E.place =
newtemp()}
– E ? T{E.code = T.code;E.place = T.place}
– T ? num{T.code = ?;T.place = num.lexval}
• Tr anslation Scheme : Embed actions, e.g.,E ? E
1
+T{ emit(+,E
1
.place,T.place,E.place)} .
3. Type Checking
• Type Expressions : Represent types, e.g., int, arr a y(n, int) .
• Type Rules :
– F or E ? E
1
+E
2
, E.type = int if E
1
.type = E
2
.type = int, else error .
– F or E ? arr a y(n,T) , E.type = arr a y(n,T.type) .
• Unification : Ensure type compatibility , e.g., E
1
.type = E
2
.type .
• Time Complexity : O(|E|) , where|E| is expression size.
1
4. Directed A cyclic Gr aph (D A G)
• Definition : Gr aph representing expressions, nodes for oper ators/oper ands,
edges for dependencies.
• Construction :
– Leaf nodes: V ariables, constants.
– Internal nodes: Oper ators with children as oper ands.
– Reuse nodes for common subexpressions.
• Use : Eliminate redundant computations, optimize code.
• Time Complexity : O(|E|) for construction, wh ere|E| is expression size.
5. Basic Blocks and Flow Gr aphs
• Basic Block : Sequence of instructions with single entry and exit.
– Starts with leader (first instruction, target of jump, or follows jump).
– Ends before next leader .
• Flow Gr aph : Directed gr aph of basic blocks, edges represent control flow .
• Construction Algorithm :
– Identify leaders.
– Group instructions between leaders into blocks.
– A dd edges based on jumps/br anches.
• Time Complexity : O(n) , where n is number of instructions.
6. Peephole Optimization
• Definition : Local optimization over small code window (2-3 instructions).
• T echniques :
– Constant F olding : Evaluate t = 2+3 to t = 5 .
– Strength Reduction : Replace t = a*2 with t = a+a .
– Dead Code Elimination : Remove t = a+b if t unused.
– Redundant Load/Store Elimination : Remove x = y;y = x .
• Time Complexity : O(w) , where w is window size (constant).
7. Time Complexities
• Three-A ddress Code Gener ation : O(|w|) , where|w| is input length.
• Type Checking : O(|E|) .
2
• D A G Construction : O(|E|) .
• Basic Block/Flow Gr aph : O(n) .
• Peephole Optimization : O(1) per instruction.
3