(SEM V) THEORY EXAMINATION 2023-24 COMPILER DESIGN

SECTION A — Short Answers (2 × 10 = 20 Marks)

(a) Explain cross compiler with example.

A cross compiler is a compiler that runs on one system (host) but generates executable code for another system (target).
Example:
A compiler that runs on a Windows machine but generates executable code for an ARM-based embedded device.
→ Used in embedded systems and IoT development.

(b) Regular Expression for a Valid Identifier

A valid identifier (starts with a letter or underscore, followed by letters, digits, or underscores):

RE=[A_a−zA−Z][A_a−zA−Z0−9]∗RE = [A\_a-zA-Z][A\_a-zA-Z0-9]^*RE=[A_a−zA−Z][A_a−zA−Z0−9]∗

Example valid identifiers: _count1, total_sum, x12.

(c) Bottom-up Parsing — Reduction Steps

Grammar:        S → aSB | d B → b            String: aaaadbbbb              Reductions:

d → S S → aSB → a(aSB)B → a(a(aSB)B)B → a(a(a(d)B)B)B → a(a(a(S)B)B)B 

Each B → b adds 1 reduction; total reductions = 9 (4 for ‘aS’ patterns, 4 for B→b, 1 for final S).

Answer: 9 reduction steps

(d) Remove Left Recursion          Given:         S → Aa | b | ε   A → Ac | SAd | ε

Step 1: Substitute S in A’s productions, then remove direct and indirect recursion.
Resulting grammar:

S → bS' | ε   S' → aS' | ε   A → bAd | ε

 Grammar is now free from left recursion.

(e) Syntax Directed Definition (SDD)

An SDD specifies how semantic rules are associated with grammar productions.
Example:

E → E1 + T   { E.val = E1.val + T.val } E → T        { E.val = T.val } T → num      { T.val = num.val }

It defines how semantic values (like computed results) are derived.

(f) Syntax Tree for (a*c)+b*((c*a)+d)

          +        /   \      *       *    /  \     /   \   a    c   b     +                 / \               *     d              / \             c   a 

 Root = +, left = (a*c), right = b*((c*a)+d).

(g) Static vs Dynamic Scope Rule

(h) Activation Record (AR)

A data structure that stores information about a function call.

Fields:

Return address                                                                Parameters

Local variables                                                                 Saved registers

Control link (previous AR)                                               Access link (for non-local variables)

(i) Design Issues in Code Generation                              Correctness of generated code

Machine dependency (instruction set, registers)            Efficiency (time & space)

Register allocation strategy                                             Handling control flow and data types

(j) DAG Nodes for Code Segment

a = b + c; e = a + 1; d = b + c; f = d + 1; g = e + f;

Common sub-expressions: (b+c) and (x+1) reused.
Nodes: {b, c, +, 1, a/e/d/f/g} → 7 nodes total

SECTION B — Short Descriptive (Any 3 × 10 = 30 Marks)

(a) Compilation Process (Example: c = a*b + 10)

Phases:

Lexical Analysis: tokens → id(a) id(b) op(*) num(10)    Syntax Analysis: builds parse tree

Semantic Analysis: type checking                              Intermediate Code: t1 = a*b; t2 = t1 + 10; c = t2

Code Optimization: reuse temp variables                  Code Generation: machine instructions

Linking & Loading

(b) Problems in Top-Down Parsing                              Left Recursion (e.g., A→Aα|β)

Ambiguity in grammar                                               Backtracking
Solutions: eliminate left recursion, use predictive (LL(1)) parsing.

(c) Syntax Directed Translation

Attaches semantic actions to grammar productions.
Example:

E → E1 + T  { print('+') } E → T T → id      { print(id.lexeme) }

Translates expression into postfix form.

(d) Symbol Table Data Structures                                   Hash Table: Fast lookup

Binary Search Tree: Ordered entries                             Linked List: Simple sequential
Fields: name, type, scope, memory location.

(e) Target Code for x := (a+b)*c + d/(a+b)

Intermediate Code:

t1 = a + b t2 = t1 * c t3 = d / t1 t4 = t2 + t3 x = t4     Optimized Code: Reuse t1 for (a+b) to avoid recomputation.

SECTION C — Long Questions (Any 1 from each)

3(a) Construct Minimized DFA

Perform state equivalence method:             Group final/non-final states.

Iteratively divide based on transitions.           Replace equivalent states.

Final DFA has minimal states (illustrated in paper image, page 2).

3(b) Phases of Compiler                                   Lexical Analysis

Syntax Analysis                                                 Semantic Analysis

Intermediate Code Generation                        Code Optimization

Code Generation                                              Error Handling

Example: Compilation of x = a + b * 5.

4(a) LALR Parsing Table

Grammar:                                                         S → CC   C → aC | b 

Construct LR(0) items → merge states with identical cores to form LALR(1) table (ACTION & GOTO).

5(a) Syntax Directed Definition Example

Grammar:

E → E + T | T   T → T * F | F   F → num

Input: 4*7+3*9
Compute step-by-step using semantic rules and build annotated parse tree.

5(b) Quadruples, Triples, Indirect Triples

Expression: (x+y)*(y+z)+(x+y+z)

Quadruples:

Use index references for triples/indirect triples.

6(a) Run-Time Storage Allocation

Static Allocation: Fixed memory before execution (e.g., global vars).  
Stack Allocation: LIFO for recursive calls.      Heap Allocation: Dynamic, uses free memory blocks.
Tradeoff: flexibility vs. management cost.

7(b) Data Flow Analysis — Flow Graph

C code:

for(i=1; i<=5; i++) { sum = sum + a[i]; }

Flow graph:

Start → Init (i=1) → Condition (i<=5?) → Body (sum+=a[i]) → Increment (i++) → Condition