Contents

Preface

1 Introduction

• 1.1 The Art of Language Design
• 1.2 The Programming Language Spectrum
• 1.3 Why Study Programming Languages?
• 1.4 Compilation and Interpretation
• 1.5 Programming Environments
• 1.6 An Overview of Compilation
  • 1.6.1 Lexical and Syntax Analysis
  • 1.6.2 Semantic Analysis and Intermediate Code Generation
  • 1.6.3 Target Code Generation
  • 1.6.4 Code Improvement
• 1.7 Summary and Concluding Remarks
• 1.8 Review Questions
• 1.9 Exercises
• 1.10 Bibliographic Notes

2 Programming Language Syntax

• 2.1 Specifying Syntax
  • 2.1.1 Tokens and Regular Expressions
  • 2.1.2 Context-Free Grammars
  • 2.1.3 Derivations and Parse Trees
• 2.2 Recognizing Syntax
  • 2.2.1 Scanning
  • 2.2.2 Top-Down and Bottom-Up Parsing
  • 2.2.3 Recursive Descent
  • 2.2.4* Syntax Errors
  • 2.2.5 Table-Driven Top-Down Parsing
  • 2.2.6 Bottom-Up Parsing
• 2.3* Theoretical Foundations
  • 2.3.1 Finite Automata
  • 2.3.2 Push-down Automata
  • 2.3.3 Grammar and Language Classes
• 2.4 Summary and Concluding Remarks
• 2.5 Review Questions
• 2.6 Exercises
• 2.7 Bibliographic Notes

3 Names, Scopes, and Bindings

• 3.1 The Notion of Binding Time
• 3.2 Object Lifetime and Storage Management
  • 3.2.1 Stack-Based Allocation
  • 3.2.2 Heap-Based Allocation
  • 3.2.3 Garbage Collection
• 3.3 Scope Rules
  • 3.3.1 Static Scope
  • 3.3.2 Dynamic Scope
  • 3.3.3 Symbol Tables
  • 3.3.4 Association Lists and Central Reference Tables
• 3.4 The Binding of Referencing Environments
  • 3.4.1 Subroutine Closures
  • 3.4.2 First and Second-Class Subroutines
• 3.5 Overloading and Related Concepts
• 3.6 Naming-Related Pitfalls in Language Design
  • 3.6.1 Scope Rules
  • 3.6.2* Separate Compilation
• 3.7 Summary and Concluding Remarks
• 3.8 Review Questions
• 3.9 Exercises
• 3.10 Bibliographic Notes

4 Semantic Analysis

• 4.1 The Role of the Semantic Analyzer
• 4.2 Attribute Grammars
• 4.3 Attribute Flow
• 4.4 Action Routines
• 4.5 Writing Semantic Functions
• 4.6* Space Management for Attributes
  • 4.6.1 Bottom-Up Evaluation
  • 4.6.2 Top-Down Evaluation
• 4.7 Summary and Concluding Remarks
• 4.8 Review Questions
• 4.9 Exercises
• 4.10 Bibliographic Notes

5 Assembly-Level Computer Architecture

• 5.1 Workstation Macro-Architecture
• 5.2 The Memory Hierarchy
• 5.3 Data Representation
  • 5.3.1 Integer Arithmetic
  • 5.3.2 Floating-Point Arithmetic
• 5.4 Instruction Set Architecture
  • 5.4.1 Addressing Modes
  • 5.4.2 Conditional Branches
• 5.5 The Evolution of Processor Architecture
  • 5.5.1 Two Example Architectures: the 680x0 and MIPS
  • 5.5.2 Pseudo-Assembler Notation
• 5.6 Compiling for Modern Processors
  • 5.6.1 Keeping the Pipeline Full
  • 5.6.2 Register Allocation
• 5.7 Summary and Concluding Remarks
• 5.8 Review Questions
• 5.9 Exercises
• 5.10 Bibliographic Notes

6 Control Flow

• 6.1 Expression Evaluation
  • 6.1.1 Precedence and Associativity
  • 6.1.2 Assignments
  • 6.1.3 Ordering Within Expressions
  • 6.1.4 Short-Circuit Evaluation
• 6.2 Structured and Unstructured Flow
• 6.3 Sequencing
• 6.4 Selection
  • 6.4.1 Short-Circuited Conditions
  • 6.4.2 Case/Switch Statements
• 6.5 Iteration
  • 6.5.1 Enumeration-Controlled Loops
  • 6.5.2 Combination Loops
  • 6.5.3* Iterators
  • 6.5.4 Logically-Controlled Loops
• 6.6 Recursion
  • 6.6.1 Iteration and Recursion
  • 6.6.2 Applicative- and Normal-Order Evaluation
• 6.7* Non-Determinacy
• 6.8 Summary and Concluding Remarks
• 6.9 Review Questions
• 6.10 Exercises
• 6.11 Bibliographic Notes

7 Data Types

• 7.1 Type Systems
  • 7.1.1 The Definition of Types
  • 7.1.2 The Classification of Types
• 7.2 Type Checking
  • 7.2.1 Type Equivalence
  • 7.2.2 Type Conversion and Casts
  • 7.2.3 Type Compatibility and Coercion
  • 7.2.4 Type Inference
  • 7.2.5* The ML Type System
• 7.3 Records (Structures) and Variants (Unions)
  • 7.3.1 Syntax and Operations
  • 7.3.2 Memory Layout and its Impact
  • 7.3.3* With Statements
  • 7.3.4 Variant Records
• 7.4 Arrays
  • 7.4.1 Syntax and Operations
  • 7.4.2 Dimensions, Bounds, and Allocation
  • 7.4.3 Memory Layout
• 7.5 Strings
• 7.6 Sets
• 7.7 Pointers and Recursive Types
  • 7.7.1 Syntax and Operations
  • 7.7.2 Dangling References
  • 7.7.3 Garbage Collection
• 7.8 Lists
• 7.9* Files and Input/Output
  • 7.9.1 Interactive I/O
  • 7.9.2 File-based I/O
  • 7.9.3 Text I/O
• 7.10 Summary and Concluding Remarks
• 7.11 Review Questions
• 7.12 Exercises
• 7.13 Bibliographic Notes

8 Subroutines and Control Abstraction

• 8.1 Review of Stack Layout
• 8.2 Calling Sequences
  • 8.2.1 Case Study: C on the MIPS
  • 8.2.2 Case Study: Pascal on the 680x0
  • 8.2.3 In-Line Expansion
• 8.3 Parameter Passing
  • 8.3.1 Parameter Modes
  • 8.3.2 Special Parameter Mechanisms
  • 8.3.3 Function Returns
• 8.4 Generic Subroutines and Modules
• 8.5 Exception Handling
  • 8.5.1 Definition of Exceptions
  • 8.5.2 Exception Propagation
  • 8.5.3 Example: Phrase-Level Recovery in a Recursive Descent Parser
  • 8.5.4 Implementation of Exceptions
• 8.6 Coroutines
  • 8.6.1 Stack allocation
  • 8.6.2 Transfer
  • 8.6.3* Iterators
  • 8.6.4* Example: Discrete-Event Simulation
• 8.7 Summary and Concluding Remarks
• 8.8 Review Questions
• 8.9 Exercises
• 8.10 Bibliographic Notes

9 Building a Runnable Program

• 9.1 Back-End Compiler Structure
  • 9.1.1 An Example
  • 9.1.2 Phases and Passes
• 9.2 Intermediate Forms
  • 9.2.1* Diana
  • 9.2.2* GNU RTL
• 9.3 Code Generation
  • 9.3.1 An Attribute Grammar Example
  • 9.3.2 Register Allocation
• 9.4 Address Space Organization
• 9.5 Address Space Organization
  • 9.5.1 Emitting Instructions
  • 9.5.2 Assigning Addresses to Names
• 9.6 Linking
  • 9.5.1 Relocation and Name Resolution
  • 9.5.2 Type Checking
• 9.7* Dynamic Linking
  • 9.5.1 Position-Independent Code
  • 9.5.2 Fully-Dynamic (Lazy) Linking
• 9.8 Summary and Concluding Remarks
• 9.9 Review Questions
• 9.10 Exercises
• 9.11 Bibliographic Notes

10 Data Abstraction and Object Orientation

• 10.1 Object-Oriented Programming
• 10.2 Encapsulation
  • 10.2.1 Modules
  • 10.2.2 Classes
  • 10.2.3 Type extensions
• 10.3 Initialization and Finalization
  • 10.3.1 Choosing a Constructor
  • 10.3.2 References and Values
  • 10.3.3 Execution Order
  • 10.3.4 Garbage Collection
• 10.4 Dynamic Type Binding
  • 10.4.1 Virtual and Non-Virtual Methods
  • 10.4.2 Abstract Classes
  • 10.4.3 Member Lookup
  • 10.4.4 Related Concepts
• 10.5* Multiple Inheritance
  • 10.5.1 Semantic Ambiguities
  • 10.5.2 Replicated Inheritance
  • 10.5.3 Shared Inheritance
  • 10.5.4 Mix-in Inheritance
• 10.6 Object-Oriented Programming Revisited
  • 10.6.1* The Object Model of Smalltalk
• 10.7 Summary and Concluding Remarks
• 10.8 Review Questions
• 10.9 Exercises
• 10.10 Bibliographic Notes

11 Alternative Programming Models: Functional and Logic Languages

• 11.1 Historical Origins
• 11.2 Functional Programming
  • 11.2.1 A Review/Overview of Scheme
  • 11.2.2 Evaluation Order Revisited
  • 11.2.3 Higher-Order Functions
  • 11.2.4* Theoretical Foundations
  • 11.2.5 Problems with Functional Programming
• 11.3 Logic Programming
  • 11.3.1 Prolog
  • 11.3.2* Theoretical Foundations
  • 11.3.3 Problems with Logic Programming
• 11.4 Summary and Concluding Remarks
• 11.5 Review Questions
• Exercises
• Bibliographic Notes

12 Concurrency

• 12.1 Background and Motivation
  • 12.1.1 A Little History
  • 12.1.2 The Case for Multi-Threaded Programs
  • 12.1.3 Multiprocessor Architecture
• 12.2 Concurrent Programming Fundamentals
  • 12.2.1 Communication and Synchronization
  • 12.2.2 Languages and Libraries
  • 12.2.3 Implementation of Threads
  • 12.2.4 Thread Creation Syntax
• 12.3 Shared Memory
  • 12.3.1 Busy-Wait Synchronization
  • 12.3.2 Scheduler Implementation
  • 12.3.3 Scheduler-Based Synchronization
  • 12.3.4 Implicit Synchronization
• 12.4 Message Passing
  • 12.4.1 Naming Communication Partners
  • 12.4.2 Sending
  • 12.4.3 Receiving
  • 12.4.4 Remote Procedure Call
• 12.5 Summary and Concluding Remarks
• 12.6 Review Questions
• 12.7 Exercises
• 12.8 Bibliographic Notes

13 Code Improvement

• 13.1 Phases of Code Improvement
• 13.2 Peephole Optimization
• 13.3 Redundancy Elimination in Basic Blocks
• 13.4 Global Redundancy and Data Flow Analysis
  • 13.4.1 Static Single Assignment Form and Global Value Numbering
  • 13.4.2 Global Common Subexpression Elimination
• 13.5 Loop Improvement I
  • 13.5.1 Loop Invariants
  • 13.5.2 Induction Variables
• 13.6 Instruction Scheduling
• 13.7* Loop Improvement II
  • 13.7.1 Loop Unrolling and Software Pipelining
  • 13.7.2 Loop Reordering
• 13.8 Register allocation
• 13.9 Summary and Concluding Remarks
• 13.10 Review Questions
• 13.11 Exercises
• 13.12 Bibliographic Notes

Appendix A: Programming Languages Mentioned

Appendix B: Language Design and Language Implementation

Bibliography

Index

* Indicates advanced or optional material that may be skipped in the interest of time.

Back to the book home page

Last Change: 30 October 2005 /