Compiler Design: Principles, Techniques And Tools

Principles of Compiler Design

What you'll learn

Demonstrate the ability to design a compiler given a set of language features.

Demonstrate the the knowledge of patterns, tokens & regular expressions for lexical analysis.

Acquire skills in using lex tool & yacc tool for developing a scanner and parser.

Design and implement LL and LR parsers.

Design algorithms to do code optimization in order to improve the performance of a program in terms of space and time complexity.

Design algorithms to generate machine code.

Requirements

A course on “Formal Languages and Automata Theory”

A course on “Computer Organization and architecture”

A course on “Computer Programming and Data Structures”

Description

Course Objectives: Introduce the major concepts of language translation and compiler design and impart the knowledge of practical skills necessary for constructing a compiler. Topics include phases of compiler, parsing, syntax directed translation, type checking use of symbol tables, code optimization techniques, intermediate code generation, code generation and data flow analysis. Course Outcomes: Demonstrate the ability to design a compiler given a set of language features. Demonstrate the the knowledge of patterns, tokens & regular expressions for lexical analysis. Acquire skills in using lex tool & yacc tool for developing a scanner and parser. Design and implement LL and LR parsers Design algorithms to do code optimization in order to improve the performance of a program in terms of space and time complexity. Design algorithms to generate machine code. SYLLABUS: Module- I:Introduction: The structure of a compiler, the science of building a compiler, programming language basics.Lexical Analysis: The Role of the Lexical Analyzer, Input Buffering, Recognition of Tokens, The Lexical-Analyzer Generator Lex, Finite Automata, From Regular Expressions to Automata, Design of a Lexical-Analyzer Generator, Optimization of DFA-Based Pattern Matchers. Module- II:Syntax Analysis: Introduction, Context-Free Grammars, Writing a Grammar.Top-Down Parsing, Bottom-Up Parsing.Introduction to LR Parsing: Simple LR, More Powerful LR Parsers, Using Ambiguous Grammars and Parser Generators. Module- III: Syntax-Directed Translation: Syntax-Directed Definitions, Evaluation Orders for SDD's, Applications of Syntax-Directed Translation, Syntax-Directed Translation Schemes, Implementing L-Attributed SDD's.Intermediate-Code Generation: Variants of Syntax Trees, Three-Address Code, Types and Declarations, Type Checking, Control Flow, Switch-Statements, Intermediate Code for Procedures. Module- IV:  Run-Time Environments: Stack Allocation of Space, Access to Non-local Data on the Stack, Heap Management, Introduction to Garbage Collection, Introduction to Trace-Based Collection. Code Generation: Issues in the Design of a Code Generator, The Target Language, Addresses in the Target Code, Basic Blocks and Flow Graphs, Optimization of Basic Blocks, A Simple Code Generator, Peephole Optimization, Register Allocation and Assignment, Dynamic Programming Code-Generation. Module- V:  Machine-Independent Optimization: The Principal Sources of Optimization, Introduction to Data-Flow Analysis, Foundations of Data-Flow Analysis, Constant Propagation, Partial-Redundancy Elimination, Loops in Flow Graphs. Reference: Compilers: Principles, Techniques and Tools, Second Edition, Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffry D. Ullman.

Overview

Section 1: Introduction

Lecture 1 Introduction to Compilers

Lecture 2 The structure of a compiler: Phases of compilers

Lecture 3 The science of building a compiler

Lecture 4 Programming language basics

Section 2: Lexical Analysis or Scanner

Lecture 5 The Role of the Lexical Analyzer

Lecture 6 Input Buffering & Specification of Tokens

Lecture 7 Recognition of Tokens

Lecture 8 The Lexical-Analyzer Generator: Lex tool

Lecture 9 Finite Automata (FA)

Lecture 10 From Regular Expressions to Automata

Lecture 11 Design of a Lexical-Analyzer Generator

Lecture 12 Optimization of DFA-Based Pattern Matches

Section 3: Syntax Analysis or Parser

Lecture 13 Introduction to Syntax Analysis or Parser

Lecture 14 Context-Free Grammars (CFGs)

Lecture 15 Writing a Grammar

Section 4: Top-Down Parsing

Lecture 16 Recursive-Descent Parser

Lecture 17 Predictive Parser-Model, Working and Sequence of Moves

Lecture 18 Predictive Parser- Computing FIRST & FOLLOW values

Lecture 19 Predictive Parser - Predictive Parsing Table Construction & LL(1) Grammar

Section 5: Bottom-up Parsing

Lecture 20 Introduction to Bottom-up parsing | Shift-Reduce (SR) Parser

Lecture 21 Introduction to LR Parsing & LR(0) items

Lecture 22 The LR Parsing- Model, Working, Algorithm & Moves of LR parser

Lecture 23 Simple LR Parser (SLR Parser)

Lecture 24 Canonical LR Parser (CLR Parser) & LR(1) Items

Lecture 25 Constructing CLR Parsing Table

Lecture 26 Constructing LALR Parsing Table

Lecture 27 LR Parser using Ambiguous Grammars | Error Recovery in LR Parsing

Lecture 28 Parser Generators -YACC (Yet Another Compiler-Compiler)

Section 6: Syntax-Directed Translation (SDT)

Lecture 29 Syntax-Directed Definitions (SDD) | Inherited & Synthesized Attributes

Lecture 30 Evaluation Orders for SDD's

Lecture 31 Applications of Syntax-Directed Translation (SDT)

Lecture 32 Syntax-Directed Translation (SDT) Schemes

Lecture 33 Implementing L-Attributed SDD's

Section 7: Intermediate-Code Generation

Lecture 34 Variants of Syntax Trees

Lecture 35 Three-Address Code

Lecture 36 Types and Declarations

Lecture 37 Type Checking

Lecture 38 Control Flow | Switch-Statements | Intermediate Code for Procedures

Section 8: Run-Time Environments

Lecture 39 Storage Organization

Lecture 40 Stack Allocation of Space

Lecture 41 Access to Non-local Data on the Stack

Lecture 42 Heap Management

Lecture 43 Introduction to Garbage Collection & Introduction to Trace-Based Collection

Section 9: Code Generation

Lecture 44 Issues in the Design of a Code Generator

Lecture 45 Basic Blocks and Flow Graphs & Optimization of Basic Blocks

Lecture 46 A Simple Code Generator & Peephole Optimization

Lecture 47 Register Allocation & Assignment | Dynamic Programming Code Generation

Section 10: Machine-Independent Optimizations

Lecture 48 The Principal Sources of Optimization

Lecture 49 Loops in Flow Graphs | Constant Propagation | Partial Redundancy Elimination

Lecture 50 Introduction to Data-Flow Analysis

Lecture 51 Solving Data-Flow Equations

Section 11: Practice Test

Any Computer Science & Information Technology Under Graduates from India and Abroad Universities.,Any Computer Science & Information Technology Graduates for Graduate Aptitude Test in Engineering (GATE) examination in India that primarily tests the comprehensive understanding of various undergraduate subjects in engineering and science for admission into the Masters Program and Job in Public Sector Companies.,Any Computer Science & Information Technology Post Graduate Students for Ph.D entrance examination in India.,Any Computer Science & Information Technology Post Graduate Students for UGC NET or NTA-UGC-NET entrance examination in India.