Compiler Design, Analysis, & Optimization

Curriculum

Module 1: Introduction, History, and Motivation

• Motivation
• History
• The Big Picture

Module 2: Linking and Multifile Compilation

• Linking – I
• Linking – II
• Linking – III
• Linking – IV
• Linking – V
• Linking – VI
• Preprocessor and Multifile Compilation

Module 3: An Overview of Compilers

• What are Compilers
• Goals of Translation
• How to Translate?
• Steps in Translation – I
• Steps in Translation – II
• Semantic Analysis
• Front End Phases
• Back End Phases
• Example of Code Optimizations
• Code Generation
• Post Translation Optimizations – I
• Post Translation Optimizations – II
• Advantage of Analysis Synthesis Model
• Issues in Compiler Design
• Tool-based Compiler Development
• Bootstrapping Example
• Bootstrapping a Compiler

Module 4: Lexical Analysis Phase

• Lexical Analysis
• Implementing Lexical Analysis
• The Role of Symbol Table
• Lexical Analysis: Challenges
• How to Specify Tokens
• Regular Expressions and Definitions
• Transition Diagrams
• Lexical Analyzer Generators

Module 5: Lex and Yacc Tutorial

• Lex and Yacc: Tutorial – I
• Lex and Yacc: Tutorial – II
• Lex and Yacc: Tutorial – III
• Lex and Yacc: Tutorial – IV
• Lex and Yacc: Tutorial – V
• Lex and Yacc: Tutorial – VI
• Lex and Yacc: Tutorial – VII
• Lex and Yacc: Tutorial – VIII
• Lex and Yacc: Tutorial – IX
• Lex and Yacc: Tutorial – X
• Lex and Yacc: Tutorial – XI
• Lex and Yacc: Tutorial – XII
• Lex and Yacc: Tutorial – XIII
• Lex and Yacc: Tutorial – XIV

Module 6: Syntax Analysis Phase

• Syntax Analysis
• Syntax Analyzer Issues
• Ambiguity
• Resolving Ambiguities
• Parsing
• Bottom-up Parsing
• Shift Reduce Parsing
• Example of Shift Reduce Parsing
• Parser Stack and Handle
• Handle Properties
• Handle Pruning
• Conflicts
• LR Parse Table
• Using the Parse Table
• Example of Parsing
• Parser Configuration and Viable Prefixes
• LR(0) Items and Closure
• Goto Operation
• Parse Table Creation Example
• Example of Parse Table
• When to Shift and When to Reduce
• Computing Follow Set
• SLR Parse Table
• SLR Parser Limitation
• Parse Table Discussion
• CLR Parser
• CLR Parser Example
• CLR and LALR Parse Table
• Notes on LALR Parsers

Module 7: Abstract Syntax Tree

• Abstract Syntax Tree (AST)
• Computing AST
• Constructing AST using YACC
• AST for Various Statements

Module 8: Semantic Analysis Phase

• Semantic Analysis
• Why Semantic Analysis
• Attribute Grammar Framework
• Example of Semantic Analysis
• Synthesized and Inherited Attributes
• Synthesized Attributes

Module 9: Attribute Evaluation

• Inherited Attributes
• Example of Inherited Attribute
• Dependence Graph
• Attribute Evaluation
• Example of Attribute Evaluation
• L-attributed Grammar
• Example of Translation Scheme
• Evaluation of Translation Scheme
• Another Example
• Evaluating Inherited Attributes
• Inherited Attributes on Parser Stack
• Simulating the Evaluation of Inherited Attributes
• Algorithm for Inherited Attribute Evaluation
• Space for Attributes
• Attribute Storage

Module 10: Type Systems

• Introduction to Type Systems
• Type Systems
• Type Checking
• Type Constructors
• Types and Symbol Table
• Type Checking of Functions
• Type Checking of Expressions
• Type Checking of Statements
• Equivalence of Types
• Name-based Equivalence of Types
• Cycles in Types
• Type Conversion
• Type Checking with Conversion
• Overloading
• Overloading Resolution
• Narrowing the Possible Types
• Polymorphic Functions
• Type Variables

Module 11: Intermediate Representation (IR) and Symbol Tables

• IR and Symbol Tables
• Issues in IR Design
• Levels of IRs
• Three Address Code
• IR Demos

Module 12: Symbol Table Creation

• Populating Symbol Table
• Handling Scopes
• Structure of Symbol Table
• Global Symbol Table as a Tree
• Storage Binding and Symbolic Registers
• Local Variables in Frames
• Storing Large Local Data
• Symbol Table Creation
• Declarations Processing
• Nested Scopes
• Records/structs in Symbol Table
• Arrays in Symbol Table

Module 13: Intermediate Code Generation

• Intermediate Code Generation
• Three Address Code (3AC) for Expressions
• Example of 3AC
• 3AC for Flow of Control Statements
• 3AC for Type Conversion
• 3AC for Boolean (No Short-circuit)
• 3AC for Boolean (Short Circuit)
• Short Circuit and If-then
• Short Circuit and If-then-else
• Short Circuit for Boolean Expressions
• 3AC for Case Statement

Module 14: Backpatching

• Backpatching
• Boolean
• Expression Backpatching
• Syntax Directed Translation for Backpatching
• Example of Backpatching
• Flow of Control Backpatching
• Scheme to Implement Backpatching – I
• Scheme to Implement Backpatching – II

Module 15: Procedures and Runtime Systems

• Procedure Calls
• Runtime Systems
• Activation Tree
• Declarations and Scope
• Storage Organisation
• Activation Records (AR)
• AR Examples – I
• AR Examples – II
• AR Examples – III
• AR Examples – IV
• AR Examples – V
• AR Examples – VI
• AR Examples – VII
• Issues Related to Runtime systems
• Storage Allocation Strategies
• Calling Sequence
• Long/Unknown Length Data
• Heap Allocation
• Accessing Non-locals
• Lexical Scoping
• Using Access Links
• Setting up Access Links
• Access Link Scenarios
• Procedures as Parameters
• Displays
• Dynamic Scoping
• Parameter Passing

Module 16: Code Generation (CG)

• CG Issues
• Instruction Selection
• Flow Graph
• Register Allocation
• Code Generation Algorithm
• CG Example
• CG Using DAG
• CG using Instruction Reordering
• Code Generator Generator
• Sethi Ullman Algorithm: Introduction
• Labeling
• Algorithm
• Example
• Optimality