Compiling Techniques

F. R. A. Hopgood

Macdonald, 1969

CONTENTS

• Contents
• Chapter 1 Introduction
  • 1.1 Definition of a compiler
  • 1.2 The structure of a compiler
  • 1.3 A brief history
• Chapter 2 Data Structures
  • 2.1 Introduction
  • 2.2 Abstract data structures
    • 2.2.1 String
    • 2.2.2 Array
    • 2.2.3 Queues and stacks
    • 2.2.4 Tables
    • 2.2.5 Trees
    • 2.2.6 Directed graphs
  • 2.3 Internal storage structures
    • 2.3.1 Vectors
    • 2.3.2 Lists
    • 2.3.3 Plexes
• Chapter 3 Data Structure Mappings
  • 3.1 Stacks and queues
  • 3.2 Strings
  • 3.3 Trees and directed graphs
  • 3.4 Arrays
    • 3.4.1 Array accessing using dope vectors
    • 3.4.2 Array accessing by Iliffe vectors
• Chapter 4 Tables
  • 4.1 Direct access tables
  • 4.2 Table look-up
  • 4.3 Search length
  • 4.4 Binary search
  • 4.5 Hash tables
    • 4.5.1 Open hash
    • 4.5.2 Overflow hash
    • 4.5.3 Overflow with chaining
    • 4.5.4 Overflow with internal chaining
    • 4.5.5 Deletion of entries
    • 4.5.6 Mapping functions
• Chapter 5 Language Description
  • 5.1 Introduction
  • 5.2 Notation
  • 5.3 Chomsky classification
  • 5.4 Parsing
  • 5.5 Recursion
• Chapter 6 Lexical Analysis
  • 6.1 Introduction
  • 6.2 Line reconstruction and input conversion
  • 6.3 Lexical conversion
  • 6.4 Number conversion
  • 6.5 A lexical analyser for Fortran
• Chapter 7 Syntax Analysis
  • 7.1 Introduction
  • 7.2 Precedence grammars
  • 7.3 Operator precedence grammars
  • 7.4 A parser for an operator precedence grammar
  • 7.5 Floyd productions
  • 7.6 Top-down analysis
    • 7.6.1 Selective top-down analysis
  • 7.7 Bottom-up analysis
  • 7.8 Comparison of parsers
  • 7.9 Implementation of operator precedence parsers
• Chapter 8 Code Generation for Arithmetic Expressions
  • 8.1 Introduction
  • 8.2 A hypothetical computer
  • 8.3 An elementary algorithm using an operator table
  • 8.4 An algorithm for generating code from a tree structure
  • 8.5 More complex algorithms
  • 8.6 Unary operators and transfer functions
    • 8.6.1 Defining code during stack combination
    • 8.6.2 Unary operators in the tree algorithm
  • 8.7 Coding simple common sub-expressions
  • 8.8 Coding sets of assignment statements
    • 8.8.1 Bogus common sub-expressions
    • 8.8.2 Statement rearrangement
  • 8.9 Global optimisation
• Chapter 9 Storage Allocation
  • 9.1 Introduction
  • 9.2 Allocating storage for temporary variables
  • 9.3 The Belady algorithm
  • 9.4 Index register allocation
• Chapter 10 Compiler-Compilers
  • 10.1 Introduction
  • 10.2 What is a Compiler-Compiler?
  • 10.3 Data structures
  • 10.4 Lexical analysis
  • 10.5 Syntax analysis
    • 10.5.1 Top-down analysers
    • 10.5.2 Floyd productions
  • 10.6 Semantic analysis
• Bibliography
• Index