Semester 5Year 3 · OddCore Subject★★★★★ Hard
CS 502

Compiler Design

Study of compiler phases, lexical analysis, parsing, syntax-directed translation, code generation, and optimization.

4Units
24Topics
4Credits
60hLecture hrs
100Max marks
Your Progress
0 / 24 topics
0% complete
Overview
🎯
Why it matters
Every line of code you write — C, Java, Python — gets compiled or interpreted. Understanding how compilers work reveals how high-level code becomes machine instructions. Essential for language design, optimizations, and performance.
💼
Placement relevance
Core systems roles at Google, Microsoft, Apple test compiler knowledge. Required for programming language teams. GATE weightage ~6-8 marks. Understanding parsing helps in all backend work (JSON, XML parsing).
🔗
Prerequisites for
Programming Language Design · Interpreter Development · Code Optimization · Static Analysis Tools · JIT Compilers
📚
Recommended books
Compilers: Principles, Techniques, and Tools by Aho, Lam, Sethi, Ullman (Dragon Book) · Modern Compiler Implementation in C by Andrew Appel · Compiler Design in C by Allen Holub
Curriculum — 4 Units
U1
Unit 1 · 6 Topics · 0% complete
Lexical Analysis
⚡ Key Formulae
Token:<token-name, attribute-value>
RE to NFA:Thompson's Construction
Role of Lexical Analyzer
Tokens, Patterns, Lexemes
Regular Expressions
Finite Automata (DFA, NFA)
LEX Tool
Symbol Table
U2
Unit 2 · 6 Topics · 0% complete
Syntax Analysis (Parsing)
⚡ Key Formulae
First & Follow:First(X): terminals that begin strings from X; Follow(A): terminals after A
LL(1) Condition:First(α) ∩ First(β) = ∅ for A→α|β
Context-Free Grammars
Parse Trees vs Syntax Trees
Top-Down Parsing (Recursive Descent, LL(1))
Bottom-Up Parsing (LR, SLR, LALR)
YACC Tool
Error Recovery
U3
Unit 3 · 6 Topics · 0% complete
Semantic Analysis & Intermediate Code
⚡ Key Formulae
Three-Address Code:x = y op z (at most 3 addresses)
Quadruple:(op, arg1, arg2, result)
Syntax-Directed Definitions
Type Checking
Three-Address Code
Quadruples, Triples
Symbol Table Management
Scope Resolution
U4
Unit 4 · 6 Topics · 0% complete
Code Generation & Optimization
⚡ Key Formulae
Basic Block:Sequence of consecutive statements with one entry, one exit
DAG:Directed Acyclic Graph for expression optimization
Code Generation
Instruction Selection
Register Allocation
Peephole Optimization
Loop Optimization
Data Flow Analysis
Previous Year Questions
Unit 22023 · End Semester10 marks
Construct LL(1) parsing table for the grammar: E→E+T|T, T→T*F|F, F→(E)|id. Show First and Follow sets for all non-terminals.
Unit 32022 · End Semester8 marks
Generate three-address code for: while (a < b) { if (c < d) x = y + z; else x = y - z; }
Exam Strategy
📊
First & Follow is always asked
Compute First and Follow sets for all grammar problems. LL(1) table construction needs these. Practice 10+ grammar examples.
🔄
Parsing table construction
LL(1), SLR, LALR table construction is 30% of exam. Show step-by-step: First/Follow, table entries, parse stack trace.
⚙️
Three-address code
Convert high-level code to 3AC format. Show temporaries (t1, t2...), labels (L1, L2...). Common for loops, conditionals, expressions.
Related Subjects
Semester 5
Theory of Computation
CS 503
Semester 2
Data Structures
CS 102