Compiler design
This useful study material lists 270 topics with detailed notes, diagrams, equations, formulas & course material, the topics are listed in 5 chapters. It is very useful for all the computer science engineering science students & professionals. Compiler Design is part of computer science & software engineering education courses and information technology degree programs of various universities.
Non-Deterministic Finite Automation
Basic Parsing Techniques
Syntax-directed Translation
Data Flow Analysis
Code Generation
- Introduction to Compiler
- The Structure of a Compiler
- Intermediate Code Generation
- Building a Compiler
- Applications of Compiler
- Optimizations for Computer Architectures
- Design of New Computer Architectures
- Program Translations
- Software Productivity Tools
- Programming Language Basics
- Explicit Access Control
- Parameter Passing Mechanisms
- Introduction to Lexical Analysis
- Regular expressions
- Short hands
- Nondeterministic finite automata
- Converting a regular expression to an NFA
- Deterministic finite automata
- Converting an NFA to a DFA
- The subset construction
- Minimisation of DFAs
- Dead states
- Lexers and lexer generators
- Splitting the input stream
- Lexical errors
- Properties of regular languages
- Limits to expressive power
- The Role of the Lexical Analyzer
- Input Buffering
- Specification of Tokens
- Operations on Languages
- Regular Definitions and Extensions
- Recognition of Tokens
- The Lexical-Analyzer Generator Lex
- Finite Automata
- Construction of an NFA from a Regular Expression
- Efficiency of String-Processing Algorithms
- The Structure of the Generated Analyzer
- Optimization of DFA-Based Pattern Matchers
- Introduction to Syntax analysis
- Context-free grammars
- Writing context free grammars
- Derivation
- Syntax trees and ambiguity
- Operator precedence
- Writing ambiguous expression grammars
- Other sources of ambiguity
- Syntax analysis and Predictive parsing
- Nullable and FIRST
- Predictive parsing revisited
- FOLLOW
- LL(1) parsing
- Methods for rewriting grammars for LL(1) parsing
- SLR parsing
- Constructions of SLR parse tables
- Conflicts in SLR parse-tables
- Using precedence rules in LR parse tables
- Using LR-parser generators
- Properties of context-free languages
- Introduction to Syntax-Directed Translator
- Evaluating an SDD at the Nodes of a Parse Tree
- Evaluation Orders for SDD\'s
- Ordering the Evaluation of Attributes
- A larger example of calculating FIRST and FOLLOW
- Syntax Definition
- Parse Trees
- Ambiguity
- Associativity of Operators
- Syntax-Directed Translation
- Synthesized Attributes
- Tree Traversals
- Parsing
- Predictive Parsing
- Use e-Productions
- Translator for Simple Expressions
- Semantic Rules with Controlled Side Effects
- Applications of Syntax-Directed Translation
- The Structure of a Type of syntax
- Syntax-Directed Translation Schemes
- Postfix Translation Schemes
- SDT\'s With Actions Inside Productions
- Eliminating Left Recursion from SDT\'s
- SDT\'s for L-Attributed Definitions
- Implementing L-Attributed SDD\'s
- On-The-Fly Code Generation
- L-Attributed SDD\'s and LL Parsing
- Bottom-Up Parsing of L-Attributed SDD\'s
- Switch-Statements
- Semantic Analysis
- Introduction to Intermediate Code Generation
- Variants of Syntax Trees
- Variants of Syntax Trees
- The Value-Number Method for Constructing DAG\'s
- Three-Address Code
- Quadruples
- Triples
- Static Single-Assignment Form
- Types and Declarations
- Type Equivalence
- Sequences of Declarations
- Translation of Expressions
- Incremental Translation
- Addressing Array Elements
- Translation of Array References
- Type Checking
- Type Conversions
- Overloading of Functions and Operators
- Type Inference and Polymorphic Functions
- Algorithm for Unification
- Control Flow
- Flow-of-Control Statements
- Control-Flow Translation of Boolean Expressions
- Boolean Values and Jumping Code
- Back patching
- Backpatching for Boolean Expressions
- Flow-of-Control Statements
- Break-, Continue-, and Goto-Statements
- Introduction to Run-Time Environments
- Stack Allocation of Space
- Activation Records
- Calling Sequences
- Variable-Length Data on the Stack
- Access to Nonlocal Data on the Stack
- Displays
- Heap Management
- Locality in Programs
- Reducing Fragmentation
- Managing and Coalescing Free Space
- Manual Deallocation Requests
- Introduction to Garbage Collection
- Reachability
- Reference Counting Garbage Collectors
- Introduction to Trace-Based Collection
- Basic Abstraction
- Optimizing Mark-and-Sweep
- Mark-and-Compact Garbage Collectors
- Copying collectors
- Short-Pause Garbage Collection
- Incremental Reachability Analysis
- Partial-Collection Basics
- The Train Algorithm
- Parallel and Concurrent Garbage Collection
- Partial Object Relocation
- Introduction Code Generation
- Issues in the Design of a Code Generator
- Instruction Selection
- Register Allocation
- The Target Language
- Addresses in the Target Code
- Stack Allocation
- Run-Time Addresses for Names
- Basic Blocks and Flow Graphs
- Basic Blocks
- Next-Use Information
- Representation of Flow Graphs
- Optimization of Basic Blocks
- Dead Code Elimination
- Representation of Array References
- Pointer Assignments and Procedure Calls
- A Simple Code Generator
- The Code-Generation Algorithm
- Design of the Function getReg
- Peephole Optimization
- Algebraic Simplification and Reduction in Strength
- Register Allocation and Assignment
- Register Assignment for Outer Loops
- Instruction Selection by Tree Rewriting
- Code Generation by Tiling an Input Tree
- Pattern Matching by Parsing
- General Tree Matching
- Optimal Code Generation for Expressions
- Evaluating Expressions with an Insufficient Supply of Registers
- Dynamic Programming Code-Generation
- The Dynamic Programming Algorithm
- Introduction to Machine-Independent Optimizations
- The Principal Sources of Optimization
- Semantics-Preserving Transformations
- Copy Propagation
- Induction Variables and Reduction in Strength
- Introduction to Data-Flow Analysis
- The Data-Flow Analysis Schema
- Reaching Definitions
- Live-Variable Analysis
- Available Expressions
- Foundations of Data-Flow Analysis
- Transfer Functions
- The Iterative Algorithm for General Frameworks
- Meaning of a Data-Flow Solution
- Constant Propagation
- Transfer Functions for the Constant-Propagation Framework
- Partial-Redundancy Elimination
- The Lazy-Code-Motion Problem
- The Lazy-Code-Motion Algorithm
- Loops in Flow Graphs
- Depth-First Ordering
- Back Edges and Reducibility
- Natural Loops
- Speed of Convergence of Iterative Data-Flow Algorithms
- Region-Based Analysis
- Necessary Assumptions About Transfer Functions
- An Algorithm for Region-Based Analysis
- Handling Non-reducible Flow Graphs
- Symbolic Analysis
- Data-Flow Problem Formulation
- Region-Based Symbolic Analysis
- Software Pipelining of Loops
- Introduction to Software Pipelining of Loops
- Introduction Instruction-Level Parallelism
- Multiple Instruction Issue
- A Basic Machine Model
- Code-Scheduling Constraints
- Finding Dependences Among Memory Accesses
- Phase Ordering Between Register Allocation and Code Scheduling
- Speculative Execution Support
- Basic-Block Scheduling
- List Scheduling of Basic Blocks
- Global Code Scheduling
- Upward Code Motion
- Updating Data Dependences
- Advanced Code Motion Techniques
- Software Pipelining
- Register Allocation and Code Generation
- A Software-Pipelining Algorithm
- Scheduling Cyclic Dependence Graphs
- Improvements to the Pipelining Algorithms
- Conditional Statements and Hardware Support for Software Pipelining
- Basic Concepts of Parallelism and Locality
- Parallelism in Applications
- Loop-Level Parallelism
- Introduction to Affine Transform Theory
- Matrix Multiply: An In-Depth Example
- Optimizations
- Iteration Spaces
- Controlling the Order of Execution
- Changing Axes
- Intermediate Code for Procedures
- Affine Array Indexes
- Data Reuse
- Self Reuse
- Self-Spatial Reuse
- Array Data-Dependence Analysis
- Integer Linear Programming
- Heuristics for Solving Integer Linear Programs
- Solving General Integer Linear Programs
- Finding Synchronization-Free Parallelism
- Affine Space Partitions
- Space-Partition Constraints
- Solving Space-Partition Constraints
- A Simple Code-Generation Algorithm
- Eliminating Empty Iterations
- Synchronization Between Parallel Loops
- The Parallelization Algorithm and Hierarchical Time
- Pipelining
- Solving Time-Partition Constraints by Farkas' Lemma
- Code Transformations
- Parallelism With Minimum Synchronization
- Locality Optimizations
- Partition Interleaving
- Putting it All Together
- Uses of Affine Transforms
- Interprocedural Analysis
- Context Sensitivity
- Cloning-Based Context-Sensitive Analysis
- Importance of Interprocedural Analysis
- SQL Injection
- A Logical Representation of Data Flow
- Execution of Datalog Programs
- Problematic Datalog Rules
- A Simple Pointer-Analysis Algorithm
- Flow Insensitivity
- Context-Insensitive Interprocedural Analysis
- Context-Sensitive Pointer Analysis
- Adding Context to Datalog Rules
- Datalog Implementation by BDD's
- Relational Operations as BDD Operations