Paper 2020 – 21

Designing Issues of a Code generator

Designing a code generator in a compiler involves several key issues that affect its
efficiency, correctness, and optimization capability. Here are some of the main
design considerations:

1. Intermediate Representation Selection: The choice of intermediate code

affects the ease of translation into machine code. Common representations
include three-address code, syntax trees, and directed acyclic graphs
(DAGs).
2. Target Machine Considerations: The generated code must be compatible
with the architecture of the target machine, considering aspects like register
allocation, instruction set, and memory management.
3. Optimization: The code generator should aim to minimize execution time
and memory usage by performing optimizations such as constant folding,
common subexpression elimination, and loop optimization.
4. Register Allocation and Assignment: Efficient usage of registers is crucial
to reduce memory access and enhance performance. Strategies like graph
coloring and usage of register descriptors help in effective register
allocation.
5. Handling of Control Statements: The translation of control statements
(loops, conditional statements, function calls) should be handled efficiently
to minimize unnecessary jumps and enhance execution flow.
 6. Error Handling and Debugging Support: The code generator should
produce code that supports debugging and error detection, including
meaningful error messages and runtime checks.

2021-22

Distinguish between statie scope and dynamic scope. Briefly explain access to non
local names in static scope

Static scope (also called lexical scope) and dynamic scope are fundamental
concepts in programming languages that define how variable names are resolved in
different contexts. These concepts play a crucial role in determining how functions
access variables that are not locally declared within them.

Distinguishing Static Scope and Dynamic Scope

Static Scope (Lexical Scope)

Static scope determines the visibility of variables based on where they are
written in the code. It follows a hierarchical structure, meaning:

 The location where a variable is declared determines its accessibility.

 The compiler or interpreter searches the enclosing scopes at compile time,
ensuring predictable behavior.
 Languages like Python, JavaScript, C, C++, and Java use static scope.

How Static Scope Works

When a function accesses a variable, the program looks for the variable in:
 1. The local scope (inside the function).
2. If the variable is not found, it checks the enclosing scope (parent function).
3. If still not found, it searches the global scope.
4. If absent everywhere, an error is thrown.

This ensures that variables are accessed in a well-defined and structured manner.

Dynamic Scope

Dynamic scope resolves variable names based on the calling sequence at

runtime. Instead of following the code’s structure, the program searches for
variables in the environment where the function was called.

How Dynamic Scope Works

 When a function accesses a variable, the interpreter searches the caller's

scope.
 The search continues up the chain of function calls.
 Since variable access depends on runtime behavior, debugging is more
difficult.

Languages like older versions of Lisp and Bash scripts use dynamic scope.

Access to Non-Local Names in Static Scope

In static scope, functions can access variables from outer (enclosing) functions,
following the scope chain.

Benefits of Static Scope

 Predictability: Variables always resolve based on their defined location.

  Maintainability: Code is easier to debug.
 Security: Prevents accidental overrides of variables from caller functions.

Differentiate between stack allocation and heap allocation

Stack allocation and heap allocation are two methods of memory management in
programming languages, each serving different purposes. Here’s how they differ:

Stack Allocation

 Memory is allocated in a fixed-size block within the call stack.

 Used for local variables inside functions.
 Memory is automatically managed—allocated when a function starts and
deallocated when it returns.
 Fast access since it follows a Last In, First Out (LIFO) structure.
 Limited in size, meaning large data structures cannot be stored in the stack.
 Variables stored in the stack have a short lifespan.

Heap Allocation

 Memory is allocated dynamically from the heap, which is a larger, flexible

pool of memory.
 Used for objects, data structures, or variables that need to persist beyond
a function’s execution.
 Requires manual management (in languages like C/C++) or automatic
garbage collection (in languages like Java and Python).
 Slower than stack allocation because memory is accessed via pointers.
 More flexible—can store large amounts of data without size restrictions.
  Variables stored in the heap have a long lifespan until explicitly freed.

Key Difference

 Stack allocation is fast and automatic, but limited in size and lifetime.
 Heap allocation is flexible and long-lasting, but requires manual memory
management or garbage collection.

Discuss the following terms:

i. Basic block

ii. Next use information

iii. Flow graph

1. Basic Block

A basic block is a sequence of consecutive instructions in a program that:

 Has only one entry point (execution begins at the first instruction).
 Has only one exit point (execution ends at the last instruction).
 Contains no jumps or branches except at the entry or exit.

Basic blocks are fundamental in compiler design and optimization, as they allow
for efficient analysis and transformation of code.

2. Next Use Information

Next use information refers to the next time a variable will be used after its
current assignment in a program. It helps in:

 Register allocation: Determines whether a value should be kept in a register

or stored in memory.
 Dead code elimination: Identifies variables whose values won’t be used
again.
 Optimization: Reduces unnecessary computations by tracking variable
usage.

3. Flow Graph

A flow graph (or control flow graph) is a directed graph representing the
control flow of a program. It consists of:

 Nodes (basic blocks)

 Edges (control flow relationships)

A flow graph helps visualize how execution moves through the program, making
it useful for optimizations like loop detection, unreachable code elimination, and
instruction reordering.

What are the two types of attributes that are associated with a grammar
symbol?

In the context of syntax-directed translation and attribute grammars, a

grammar symbol can have two types of attributes:

1. Synthesized Attributes
  A synthesized attribute is an attribute that is computed based on the
attributes of its children in a parse tree.
 These attributes flow bottom-up, meaning they are derived as information is
passed from lower-level nodes (children) to higher-level nodes (parents).
 Commonly used in semantic analysis and code generation in compilers.

2. Inherited Attributes

 An inherited attribute is an attribute that is determined by the attributes of

its parent or siblings.
 These attributes flow top-down (from parents to children) or horizontally
(from siblings to siblings).
 They are helpful in specifying context-sensitive information, such as
variable types in declarations.

Copy Prapogation

Copy Propagation is a compiler optimization technique that eliminates

unnecessary variable copies by replacing them with their original values.

How it Works:

1. If a variable x is assigned the value of another variable y (x = y), the

compiler tracks this copy.
2. Later in the code, wherever x is used, it replaces x with y (if safe to do so).
3. This helps eliminate redundant assignments and improves efficiency.

Example:
int a = b; // Copy propagation applies here int c = a + 5; // 'a' can be replaced with
'b'

After copy propagation, this changes to:

int c = b + 5; // Directly uses 'b'

Benefits of Copy Propagation:

 Reduces redundant memory operations.

 Simplifies code, making it easier for other optimizations (like dead code
elimination).
 Improves runtime efficiency.