Formula Sheets: Runtime Environment | Compiler Design - Computer Science Engineering (CSE) PDF Download

 Page 1


Runtime Environment F ormula Sheet
1. S ymbol T able
• Definition : Data structure storing information about identifiers (e.g., name,
type, scope, address).
• Oper ations :
– Insert : A dd identifier and attributes.
– Lookup : Retrieve attributes of an identifier .
– Delete : Remove identifier (e.g., when exiting scope).
• Organizations :
– Linear List : O(n) for lookup, insert, delete;n is number of entries.
– Hash T able : O(1) aver age case for lookup, insert, delete.
– Tree : O( logn) for balanced trees (e.g., BS T , A VL).
• Scope Management :
– Static Scope : Nested symbol tables for nested scopes.
– Dynamic Scope : Stack-based symbol table for runtime resolution.
2. Hash T ables and Hash Functions
• Definition : Maps k eys to indices via hash functionh(k) .
• Hash Function : h(k) =k mod m , wherem is table size (prefer ably prime).
• Collision Resolution :
– Chaining : Link ed list for entries with same hash value.
– Open A ddressing : Probe sequence, e.g., linear probingh(k,i) = (h(k)+i)
mod m .
• Time Complexity :
– A ver age case: O(1) for insert, lookup, delete (load factora =n/m< 1 ).
– W orst case: O(n) for chaining,O(m) for open addressing.
3. Runtime Stor age Organization
• Memory La yout :
– Code Area : Stores executable instructions.
– Static Area : Global variables, constants.
– Stack : A ctivation records for function calls.
1
Page 2


Runtime Environment F ormula Sheet
1. S ymbol T able
• Definition : Data structure storing information about identifiers (e.g., name,
type, scope, address).
• Oper ations :
– Insert : A dd identifier and attributes.
– Lookup : Retrieve attributes of an identifier .
– Delete : Remove identifier (e.g., when exiting scope).
• Organizations :
– Linear List : O(n) for lookup, insert, delete;n is number of entries.
– Hash T able : O(1) aver age case for lookup, insert, delete.
– Tree : O( logn) for balanced trees (e.g., BS T , A VL).
• Scope Management :
– Static Scope : Nested symbol tables for nested scopes.
– Dynamic Scope : Stack-based symbol table for runtime resolution.
2. Hash T ables and Hash Functions
• Definition : Maps k eys to indices via hash functionh(k) .
• Hash Function : h(k) =k mod m , wherem is table size (prefer ably prime).
• Collision Resolution :
– Chaining : Link ed list for entries with same hash value.
– Open A ddressing : Probe sequence, e.g., linear probingh(k,i) = (h(k)+i)
mod m .
• Time Complexity :
– A ver age case: O(1) for insert, lookup, delete (load factora =n/m< 1 ).
– W orst case: O(n) for chaining,O(m) for open addressing.
3. Runtime Stor age Organization
• Memory La yout :
– Code Area : Stores executable instructions.
– Static Area : Global variables, constants.
– Stack : A ctivation records for function calls.
1
– Heap : Dynamic memory allocation.
• A ctivation Record (Stack Fr ame) :
– Components: Return address, par ameters, local variables, tempor aries,
control link (to caller), access link (for static scope).
– Push/Pop : On function call/return.
• Stack vs. Heap :
– Stack: LIFO , fixed-size variables, fast allocation.
– Heap: Dynamic, variable-size objects, slower allocation.
4. Stor age Allocation
• Static Allocation :
– Fixed at compile time (e.g., global variables).
– Size known, no runtime overhead.
• Stack Allocation :
– F or local variables, par ameters in activation records.
– Offset Calculation : Relative to fr ame pointer .
– Time Complexity : O(1) for allocation/deallocation.
• Heap Allocation :
– F or dynamic objects (e.g., via malloc , new ).
– Free List : Tr acks available memory blocks.
– Allocation Str ategies : First-fit, best-fit, worst-fit.
– Time Complexity : O(k) for allocation, wherek is number of free blocks.
5. S ymbol T able Management
• Nested Scopes :
– Use stack of symbol tables; push new table on entering scope, pop on exit.
– A ccess link in activation record for static scoping.
• Type Information : Store type (e.g., int , array ) for type checking.
• Time Complexity :
– Insert/Lookup: O(1) aver age with hash table.
– Scope Entry/Exit: O(1) for stack oper ations.
2
Page 3


Runtime Environment F ormula Sheet
1. S ymbol T able
• Definition : Data structure storing information about identifiers (e.g., name,
type, scope, address).
• Oper ations :
– Insert : A dd identifier and attributes.
– Lookup : Retrieve attributes of an identifier .
– Delete : Remove identifier (e.g., when exiting scope).
• Organizations :
– Linear List : O(n) for lookup, insert, delete;n is number of entries.
– Hash T able : O(1) aver age case for lookup, insert, delete.
– Tree : O( logn) for balanced trees (e.g., BS T , A VL).
• Scope Management :
– Static Scope : Nested symbol tables for nested scopes.
– Dynamic Scope : Stack-based symbol table for runtime resolution.
2. Hash T ables and Hash Functions
• Definition : Maps k eys to indices via hash functionh(k) .
• Hash Function : h(k) =k mod m , wherem is table size (prefer ably prime).
• Collision Resolution :
– Chaining : Link ed list for entries with same hash value.
– Open A ddressing : Probe sequence, e.g., linear probingh(k,i) = (h(k)+i)
mod m .
• Time Complexity :
– A ver age case: O(1) for insert, lookup, delete (load factora =n/m< 1 ).
– W orst case: O(n) for chaining,O(m) for open addressing.
3. Runtime Stor age Organization
• Memory La yout :
– Code Area : Stores executable instructions.
– Static Area : Global variables, constants.
– Stack : A ctivation records for function calls.
1
– Heap : Dynamic memory allocation.
• A ctivation Record (Stack Fr ame) :
– Components: Return address, par ameters, local variables, tempor aries,
control link (to caller), access link (for static scope).
– Push/Pop : On function call/return.
• Stack vs. Heap :
– Stack: LIFO , fixed-size variables, fast allocation.
– Heap: Dynamic, variable-size objects, slower allocation.
4. Stor age Allocation
• Static Allocation :
– Fixed at compile time (e.g., global variables).
– Size known, no runtime overhead.
• Stack Allocation :
– F or local variables, par ameters in activation records.
– Offset Calculation : Relative to fr ame pointer .
– Time Complexity : O(1) for allocation/deallocation.
• Heap Allocation :
– F or dynamic objects (e.g., via malloc , new ).
– Free List : Tr acks available memory blocks.
– Allocation Str ategies : First-fit, best-fit, worst-fit.
– Time Complexity : O(k) for allocation, wherek is number of free blocks.
5. S ymbol T able Management
• Nested Scopes :
– Use stack of symbol tables; push new table on entering scope, pop on exit.
– A ccess link in activation record for static scoping.
• Type Information : Store type (e.g., int , array ) for type checking.
• Time Complexity :
– Insert/Lookup: O(1) aver age with hash table.
– Scope Entry/Exit: O(1) for stack oper ations.
2
6. Time Complexities
• S ymbol T able Oper ations :
– Linear List: O(n) .
– Hash T able: O(1) aver age,O(n) worst.
– Tree: O( logn) .
• Hash T able Oper ations : O(1) aver age,O(n) worst for chaining.
• Stack Allocation : O(1) per variable.
• Heap Allocation : O(k) for searching free list.
• A ctivation Record Management : O(1) for push/pop.
3