Compiler Construction Course Outline - University of Sargodha

Course Title: Compiler Construction

Course Code: CS-4141

Course Structure: Lectures: 3 / Labs: 0

Credit Hours: 3

Prerequisites: CS-3131 (Theory of Automata and Formal Languages)

Course Objectives:

At the end of the course students will understand the overall structure of a compiler, and will
know significant details of a number of important techniques commonly used. They will be
aware of the way in which language features raise challenges for compiler builders.

Course Syllabus:

Principles of Compilation, Compiler Structure, High-Level View of Translation, Desirable
Properties of a Compiler.Scanners.Parsers.Context-Sensitive Analysis.Intermediate
Representations.The Procedure Abstraction.Code Shape.Code Optimization.Data-Flow
Analysis.Scalar Optimizations.Instruction Selection.Instruction Scheduling. Register Allocation.
Implementation of a prototype compiler(Lab Assignment for the Semester)

Course Outline:

1.      Overview of Compilation: Principles of Compilation, Compiler Structure, High-Level
View of Translation, Desirable Properties of a Compiler. [TB: Ch.1]

2.      Scanners: Recognizing Words, Regular Expressions, Implementing Scanners. [TB: Ch.2]

3.      Parsers: Expressing Syntax, Top-Down Parsing, Bottom-Up Parsing. [TB: Ch.3]

4.      Context-Sensitive Analysis: Type Systems, Attribute-Grammar Framework, Ad Hoc
Syntax-Directed Translation. [TB: Ch.4]

5.      Intermediate Representations: Graphical IRs, Linear IRs, Mapping Values to Names,
Symbol Tables. [TB: Ch.5]

6.      The Procedure Abstraction: Procedure Calls, Name Spaces, Communicating Values
Between Procedures, Standardized Linkages. [TB: Ch.6]

7.      Code Shape: Assigning Storage Locations, Arithmetic Operators, Boolean and Relational
Operators, Storing and Accessing Arrays, Character Strings, Structure References,
Control-Flow Constructs, Procedure Calls. [TB: Ch.7]

8.      Code Optimization: Scope of Optimization, Local Optimization, Regional Optimization,
Global Optimization, Interprocedural Optimization. [TB: Ch.8]

9.      Data-Flow Analysis: Iterative Data-Flow Analysis, Static Single-Assignment Form,
Inter-procedural Analysis. [TB: Ch.9]

10.  Scalar Optimizations: Taxonomy for Transformations, Example Optimizations. [TB:
Ch.10]

11. Instruction Selection: Code Generation, Extending the Simple Tree-Walk Scheme,
Instruction Selection via Tree-Pattern Matching, Instruction Selection via Peephole
Optimization. [TB: Ch.11]

12. Instruction Scheduling: The Instruction-Scheduling Problem, Local List Scheduling,
Regional Scheduling. [TB: Ch.12]

13. Register Allocation: Background Issues, Local Register Allocation and Assignment,
Moving Beyond Single Blocks, Global Register Allocation and Assignment.

14. Implementation of a prototype compiler (Class Assignment for the Semester)

Textbook(s):

•          Engineering a Compiler, Second Edition by Keith Cooper and Linda Torczon, Morgan
Kaufmann; 2^ndEdition (February 21, 2011). ISBN-10: 012088478X

Reference Material:

•          Compilers: Principles, Techniques, and Tools By Alfred V. Aho, Ravi Sethi, Jeffrey D.
Ullman, Contributor Jeffrey D. Ullman , Prentice Hall; 2^ndEdition (2006). ISBN-10:0321486811

•          Modern Compiler Design, By Dick Grune, Henri E. Bal, Ceriel J. H. Jacobs, Koen G.
Langendoen, Springer; 2^ndEdition. (2012). ISBN-10: 1461446988

•          Modern Compiler Implementation in C, By Andrew W. Appel, Maia Ginsburg,
Contributor Maia Ginsburg, Cambridge University Press, (2004). ISBN-10: 0521607655

Note: This content is obtained from official documents of University of Sargodha and applied on BS Computer Science for Main Campus, Sub Campuses, and Affiliated Colleges.