Lecture 1
Compiler Design
Awanish Pandey
Department of Computer Science and Engineering
Indian Institute of Technology
Roorkee
January 21, 2025
January 21, 2025 1/9
Introduction
Instructor
Awanish Pandey
January 21, 2025 2/9
Introduction
Instructor
Awanish Pandey
Office: MFS building, 1st floor
January 21, 2025 2/9
Introduction
Instructor
Awanish Pandey
Office: MFS building, 1st floor
Please use teams for any communication related to the course.
January 21, 2025 2/9
Introduction
Instructor
Awanish Pandey
Office: MFS building, 1st floor
Please use teams for any communication related to the course.
E-Mail: ap@cs.iitr.ac.in
January 21, 2025 2/9
Introduction
Instructor
Awanish Pandey
Office: MFS building, 1st floor
Please use teams for any communication related to the course.
E-Mail: ap@cs.iitr.ac.in
Subject must start from [CSN-352] Email not complying with this rule will NOT
be entertained.
January 21, 2025 2/9
Introduction
Instructor
Awanish Pandey
Office: MFS building, 1st floor
Please use teams for any communication related to the course.
E-Mail: ap@cs.iitr.ac.in
Subject must start from [CSN-352] Email not complying with this rule will NOT
be entertained.
TA
To be added
January 21, 2025 2/9
Acknowledgments
The course structure is based on Compilers: Principles, Techniques, and Tools by Aho, Sethi,
Ullman and Lam (2nd Edition).
January 21, 2025 3/9
Acknowledgments
The course structure is based on Compilers: Principles, Techniques, and Tools by Aho, Sethi,
Ullman and Lam (2nd Edition).
Slides are based on the slides of the late Prof Sanjeev K Aggarwal.
January 21, 2025 3/9
Learning from this course
Course has theoretical and practical components. Both are needed in implementing
programming languages. The focus will be on the practical application of the theory.
January 21, 2025 4/9
Learning from this course
Course has theoretical and practical components. Both are needed in implementing
programming languages. The focus will be on the practical application of the theory.
Emphasis will be on algorithms and data structures rather than proofs of correctness of
algorithms.
January 21, 2025 4/9
Learning from this course
Course has theoretical and practical components. Both are needed in implementing
programming languages. The focus will be on the practical application of the theory.
Emphasis will be on algorithms and data structures rather than proofs of correctness of
algorithms.
Theory of lexical analysis, parsing, type checking, runtime system, code generation,
optimization
January 21, 2025 4/9
Learning from this course
Course has theoretical and practical components. Both are needed in implementing
programming languages. The focus will be on the practical application of the theory.
Emphasis will be on algorithms and data structures rather than proofs of correctness of
algorithms.
Theory of lexical analysis, parsing, type checking, runtime system, code generation,
optimization
Techniques for developing lexical analyzers, parsers, type checkers, run-time systems, code
generators, and optimization.
January 21, 2025 4/9
Learning from this course
Course has theoretical and practical components. Both are needed in implementing
programming languages. The focus will be on the practical application of the theory.
Emphasis will be on algorithms and data structures rather than proofs of correctness of
algorithms.
Theory of lexical analysis, parsing, type checking, runtime system, code generation,
optimization
Techniques for developing lexical analyzers, parsers, type checkers, run-time systems, code
generators, and optimization.
Students will be confident that they can design, develop, understand, modify, enhance,
and maintain compilers for (even complex!) programming languages
January 21, 2025 4/9
Course Structure
Relative Weight
Project 25
Mid-Term Evaluation 25
End-Term Evaluation 50
January 21, 2025 5/9
Course Structure
Relative Weight
Project 25
Mid-Term Evaluation 25
End-Term Evaluation 50
General Instructions
Please give feedback throughout the course, either personally or over the mail.
January 21, 2025 5/9
Course Structure
Relative Weight
Project 25
Mid-Term Evaluation 25
End-Term Evaluation 50
General Instructions
Please give feedback throughout the course, either personally or over the mail.
Feel free to discuss anything with me.
January 21, 2025 5/9
Course Structure
Relative Weight
Project 25
Mid-Term Evaluation 25
End-Term Evaluation 50
General Instructions
Please give feedback throughout the course, either personally or over the mail.
Feel free to discuss anything with me.
Please be on time. Respect your own time and my/TAs time.
January 21, 2025 5/9
Course Structure
Relative Weight
Project 25
Mid-Term Evaluation 25
End-Term Evaluation 50
General Instructions
Please give feedback throughout the course, either personally or over the mail.
Feel free to discuss anything with me.
Please be on time. Respect your own time and my/TAs time.
Keep your electronic devices in silent mode.
January 21, 2025 5/9
Course Structure
Relative Weight
Project 25
Mid-Term Evaluation 25
End-Term Evaluation 50
General Instructions
Please give feedback throughout the course, either personally or over the mail.
Feel free to discuss anything with me.
Please be on time. Respect your own time and my/TAs time.
Keep your electronic devices in silent mode.
DO NOT CHEAT
January 21, 2025 5/9
Project Detail
Group of 4
January 21, 2025 6/9
Project Detail
Group of 4
Implement end-to-end toy compiler
January 21, 2025 6/9
Project Detail
Group of 4
Implement end-to-end toy compiler
Each group has to choose a source, intermediate, target, and implementation language.
January 21, 2025 6/9
Project Detail
Group of 4
Implement end-to-end toy compiler
Each group has to choose a source, intermediate, target, and implementation language.
Project form
January 21, 2025 6/9
Project Detail
Group of 4
Implement end-to-end toy compiler
Each group has to choose a source, intermediate, target, and implementation language.
Project form
Assignment 1 (Lexical Analysis) 10%
Assignment 2 (Syntax Analysis) 20%
Assignment 3 (Intermediate Code generation) 30%
Assignment 4 (Optimization and Target code generation) 40%
January 21, 2025 6/9
History
Two major ways of implementing Programming Languages
January 21, 2025 7/9
History
Two major ways of implementing Programming Languages
Interpreter
January 21, 2025 7/9
History
Two major ways of implementing Programming Languages
Interpreter
Compiler
January 21, 2025 7/9
History
Two major ways of implementing Programming Languages
Interpreter
Compiler
Early Machines
IBM developed 704 in 1954. All programming was done in assembly language. The cost
of software development far exceeded the cost of hardware. Low productivity.
January 21, 2025 7/9
History
Two major ways of implementing Programming Languages
Interpreter
Compiler
Early Machines
IBM developed 704 in 1954. All programming was done in assembly language. The cost
of software development far exceeded the cost of hardware. Low productivity.
Speedcoding interpreter: programs ran about 10 times slower than hand written assembly
code
January 21, 2025 7/9
History
Two major ways of implementing Programming Languages
Interpreter
Compiler
Early Machines
IBM developed 704 in 1954. All programming was done in assembly language. The cost
of software development far exceeded the cost of hardware. Low productivity.
Speedcoding interpreter: programs ran about 10 times slower than hand written assembly
code
John Backus (in 1954): Proposed a program that translated high level expressions into
native machine code. Skeptism all around. Most people thought it was impossible
January 21, 2025 7/9
History
Two major ways of implementing Programming Languages
Interpreter
Compiler
Early Machines
IBM developed 704 in 1954. All programming was done in assembly language. The cost
of software development far exceeded the cost of hardware. Low productivity.
Speedcoding interpreter: programs ran about 10 times slower than hand written assembly
code
John Backus (in 1954): Proposed a program that translated high level expressions into
native machine code. Skeptism all around. Most people thought it was impossible
Fortran I project (1954-1957): The first compiler was released
January 21, 2025 7/9
Fortran 1
The whole new field of compiler design was started
January 21, 2025 8/9
Fortran 1
The whole new field of compiler design was started
More than half the programmers were using Fortran by 1958
January 21, 2025 8/9
Fortran 1
The whole new field of compiler design was started
More than half the programmers were using Fortran by 1958
The development time was cut down to half
January 21, 2025 8/9
Fortran 1
The whole new field of compiler design was started
More than half the programmers were using Fortran by 1958
The development time was cut down to half
Led to the enormous amount of theoretical work (lexical analysis, parsing, optimization,
structured programming, code generation, error recovery, etc.)
January 21, 2025 8/9
Fortran 1
The whole new field of compiler design was started
More than half the programmers were using Fortran by 1958
The development time was cut down to half
Led to the enormous amount of theoretical work (lexical analysis, parsing, optimization,
structured programming, code generation, error recovery, etc.)
Modern compilers preserve the basic structure of the Fortran I compiler !!!
January 21, 2025 8/9
What are Compilers
January 21, 2025 9/9
What are Compilers
Basics
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
Can the computer understand this?
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
Can the computer understand this?
Who will convert it?
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
Can the computer understand this?
Who will convert it?
Goals of translation
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
Can the computer understand this?
Who will convert it?
Goals of translation
▶ Good performance for the generated code
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
Can the computer understand this?
Who will convert it?
Goals of translation
▶ Good performance for the generated code
▶ Good compile-time performance
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
Can the computer understand this?
Who will convert it?
Goals of translation
▶ Good performance for the generated code
▶ Good compile-time performance
▶ Maintainable code
January 21, 2025 9/9
What are Compilers
Basics
What is High-Level Languages
▶ Expressive: matches our notion of languages (and application?!)
▶ Redundant to help avoid programming errors
Can the computer understand this?
Who will convert it?
Goals of translation
▶ Good performance for the generated code
▶ Good compile-time performance
▶ Maintainable code
▶ What about correctness?
January 21, 2025 9/9
