(SEM VI) THEORY EXAMINATION 2024-25 COMPILAR DESIGN

BCS602 – COMPILER DESIGN

Time: 3 Hours | Max Marks: 70

SECTION A – Short Answer Questions

(2 × 7 = 14 marks | Attempt ALL)
 Write definition + 1–2 crisp points

a. Phases vs Passes of a Compiler

Phases: Logical stages like lexical, syntax, semantic, code generation

Passes: Number of times source program is read               One pass may contain multiple phases.

b. Top-Down vs Bottom-Up Parsing

c. Inherited vs Synthesized Attributes                  Synthesized: Flow bottom-up (from children to parent)

Inherited: Flow top-down (from parent to children)
Used in syntax-directed translation.

d. Role of Hash Table in Symbol Table                  Fast insertion & lookup

Stores identifiers, type, scope                               Reduces search time during compilation

e. Finite State Machine (FSM)                               FSM is a model with states, transitions, input alphabet.
Used in lexical analysis to recognize tokens.     (Design FSM with 4 states for even a’s & odd b’s in exam.)

f. Lexical vs Syntactic Structure

Lexical: Tokens, keywords, identifiers                   Syntactic: Grammar rules, parse trees
Lexical → Syntax analysis sequence.

g. Machine-Independent Code Optimization

Optimization that does not depend on target machine, e.g.:

Constant folding                                                    Common sub-expression elimination

Dead code elimination

SECTION B – Medium Answer Questions

(7 × 3 = 21 marks | Attempt ANY THREE)

Write stepwise explanation + diagram/example

a. Phases of Compilation (Very Important)              Lexical Analysis

Syntax Analysis                                                         Semantic Analysis

Intermediate Code Generation                                Code Optimization

Target Code Generation                                    

Explain outputs for:                                                   **a = (b + c)(b + c)2

b. Ambiguous Grammar Proof

Grammar:                                                                S → aSbS | bSaS | ε

Show two different parse trees / rightmost derivations
Confirms ambiguity.

c. Role of Symbol Table in Compiler Phases              Lexical: stores identifiers

Syntax: checks declarations                                       Semantic: type checking

Code generation: memory allocation

d. SLR Parsing Table Construction

Given grammar:                                                         S → Aa | bAc | Bc | bBa   A → d   B → d 

Steps:

Augmented grammar                                                LR(0) items

ACTION & GOTO table                                              Check conflicts (Shift/Reduce)

e. Semantic Errors & Detection

Examples:                                                                  Type mismatch

Undeclared variable                                                  Wrong number of arguments

Detected during semantic analysis using symbol table.

SECTION C – Attempt ANY ONE

(7 marks)

a. LL(1) Parsing Table Construction

Grammar:                                                                   S → aB | aC | Sd | Se   B → bBc | f   C → g 

Steps:                                                                         Remove left recursion

Compute FIRST & FOLLOW                                       Construct table

Check conflicts

b. Design Issues in Code Generation                        Instruction selection

Register allocation                                                    Memory addressing

Target machine architecture                                     Directly affects compiler performance.