Compiler Construction (CS4623)

Pre-requisite(s)

Theory of Automata & Formal Languages (CS-3613)

Data Structures (CS-2143)

Recommended Book(s)

Alfred V. Aho, Monica S. Lam, RaviSethi And Jeffrey D. Ullman: Compilers: Principles, Techniques And Tools, Addison-Wesley Publishing Company, 2006, ISBN 978-0321486813.

Reference Book(s)

Kenneth C. Louden: Compiler Construction – Principles And Practice, Course Technology, 1997, ISBN 978-0534939724.

D. Grune, H. Bal, C. Jacobs, K. Langendoen: Modern Compiler Design, Wiley, 2000, ISBN 978-0471976974.

Course Objectives

Differentiate between different levels of programming languages. Understand the role of front-end and back-end of a compiler. Recognize different types of grammars. Understand and define grammars in BNF, syntax diagrams, regular expressions. Define tokens using the notation of regular expressions. Convert regular expressions into finite automata. Implement a lexical analyser. Define a programming language syntax using a CFG. Construct a parse tree for a given program. Differentiate between top-down and bottom-up parsing strategies. Understand LL (k) and LR (k) grammars. Write a top-down parser using recursive-descent and LL (1) parsing methods. Understand simple-precedence, operator precedence and SLR parsing methods. Understand semantic analysis (type checking, scope checking etc.) Understand various types of runtime environments. Understand code generation techniques. Understand code optimization techniques.

Course Learning Outcomes (CLO)

Course Objectives 

Course Contents

Overview of High-Level Languages and Translation

                        Levels of Programming Languages

                        Need for High-Level Languages

                        Advantages of High-Level Languages

                        Language Translation: Compilation and Interpretation

                        Phases of the Compilation Process

 Language Definition

                        Syntax Specification

                        Chomsky’s Classification of Grammars

                        Semantics Specification

  Lexical Analysis

                        Role of a Lexical Analyzer (Scanner)

                        Finite-State Automata

                        Notation of Regular Expressions

                        Conversion of Regular Expressions into DFAs

                        Writing a Lexical Analyzer using DFAs

                        Lexical Analysis tools

  Syntax and Semantic Analysis

                        Role of a Syntax Analyzer (Parser)
                        Classification of Grammars for Parsing
                        Top-Down Parsing
                        Bottom-Up Parsing
                        Parsing tools
                        Semantic Analysis

  Code Generation

            Runtime Environments

            Storage Allocation strategies

            Code Generation Techniques

   Code Optimization

 

            Eliminating Redundant Code

            Folding Constants

            Loop Optimization Techniques

            Expression/Statement Rewriting

            Peephole optimization

Mapping of CLOs to Assessment Modules

Final Exam

Assignments 

Surprise Tests/Quizzes

Project

Midterm Exam