About this previous year paper
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
| Top-Down | Bottom-Up |
|---|---|
| Starts from start symbol | Starts from input |
| LL parsing | LR parsing |
| Simple | More powerful |
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.