Detailed Contents of "Compilers and Compiler Generators"
Pat Terry
p.terry@ru.ac.za
CONTENTS
1 INTRODUCTION
1.1 Objectives
1.2 Systems programs and translators
1.3 The relationship between high-level languages and translators
2 TRANSLATOR CLASSIFICATION AND STRUCTURE
2.1 T-diagrams
2.2 Classes of translator
2.3 Phases in translation
2.4 Multi-stage translators
2.5 Interpreters, interpretive compilers, and emulators
3 COMPILER CONSTRUCTION AND BOOTSTRAPPING
3.1 Using a high-level host language
3.2 Porting a high level translator
3.3 Bootstrapping
3.4 Self-compiling compilers
3.5 The half bootstrap
3.6 Bootstrapping from a portable interpretive compiler
3.7 A p-code assembler
4 MACHINE EMULATION
4.1 Simple machine architecture
4.2 Addressing modes
4.3 Case study 1 - a single-accumulator machine
4.3.1 Machine architecture
4.3.2 Instruction set
4.3.3 A specimen program
4.3.4 An emulator for the single-accumulator machine
4.3.5 A minimal assembler for the machine
4.4 Case study 2 - a stack-oriented computer
4.4.1 Machine architecture
4.4.2 Instruction set
4.4.3 Specimen programs
4.4.4 An emulator for the stack machine
4.4.5 A minimal assembler for the machine
5 LANGUAGE SPECIFICATION
5.1 Syntax, semantics, and pragmatics
5.2 Languages, symbols, alphabets and strings
5.3 Regular expressions
5.4 Grammars and productions
5.5 Classic BNF notation for productions
5.6 Simple examples
5.7 Phrase structure and lexical structure
5.8 e productions
5.9 Extensions to BNF
5.9.1 Wirth's EBNF notation
5.9.2 Semantic overtones
5.9.3 The British Standard for EBNF
5.9.4 Lexical and phrase structure emphasis
5.9.5 Cocol
5.10 Syntax diagrams
5.11 Formal treatment of semantics
6 SIMPLE ASSEMBLERS
6.1 A simple ASSEMBLER language
6.2 One and two pass assemblers, and symbol tables
6.3 Towards the construction of an assembler
6.3.1 Source handling
6.3.2 Lexical analysis
6.3.3 Syntax analysis
6.3.4 The symbol table interface
6.4 Two-pass assembly
6.4.1 Symbol table structures
6.4.2 The first pass - static semantic analysis
6.4.3 The second pass - code generation
6.5 One-pass assembly
6.5.1 Symbol table structures
6.5.2 The first pass - analysis and code generation
7 ADVANCED ASSEMBLER FEATURES
7.1 Error detection
7.2 Simple expressions as addresses
7.3 Improved symbol table handling - hash tables
7.4 Macro-processing facilities
7.5 Conditional assembly
7.6 Relocatable code
8 GRAMMARS AND THEIR CLASSIFICATION
8.1 Equivalent grammars
8.2 Case study - equivalent grammars for describing expressions
8.3 Some simple restrictions on grammars
8.3.1 Useless productions and reduced grammars
8.3.2 e-free grammars
8.3.3 Cycle-free grammars
8.4 Ambiguous grammars
8.5 Context sensitivity
8.6 The Chomsky hierarchy
8.6.1 Type 0 Grammars (Unrestricted)
8.6.2 Type 1 Grammars (Context-sensitive)
8.6.3 Type 2 Grammars (Context-free)
8.6.4 Type 3 Grammars (Regular, Right-linear or Left-linear)
8.6.5 The relationship between grammar type and language type
8.7 Case study - Clang
8.7.1 BNF Description of Clang
8.7.2 EBNF description of Clang
8.7.3 A sample program
9 DETERMINISTIC TOP DOWN PARSING
9.1 Deterministic top-down parsing
9.2 Restrictions on grammars so as to allow LL(1) parsing
9.2.1 Terminal start sets, the FIRST function and LL(1) conditions for e-free grammars
9.2.2 Terminal successors, the FOLLOW function, and LL(1) conditions for non e-free grammars
9.2.3 Further observations
9.2.4 Alternative formulations of the LL(1) conditions
9.3 The effect of the LL(1) conditions on language design
10 PARSER AND SCANNER CONSTRUCTION
10.1 Construction of simple recursive descent parsers
10.2 Case studies
10.3 Syntax error detection and recovery
10.4 Construction of simple scanners
10.5 Case studies
10.6 LR parsing
10.7 Automated construction of scanners and parsers
11 SYNTAX DIRECTED TRANSLATION
11.1 Embedding semantic actions into syntax rules
11.2 Attribute grammars
11.3 Synthesized and inherited attributes
11.4 Classes of attribute grammars
11.5 Case study - a small student database
12 USING COCO/R - OVERVIEW
12.1 Installing and running Coco/R
12.1.1 Installation
12.1.2 Input file preparation
12.1.3 Execution
12.1.4 Output from Coco/R
12.1.5 Assembling the generated system
12.2 Case study - a simple adding machine
12.3 Scanner specification
12.3.1 Character sets
12.3.2 Comments and ignorable characters
12.3.3 Tokens
12.3.4 Pragmas
12.3.5 User names
12.3.6 The scanner interface
12.4 Parser specification
12.4.1 Productions
12.4.2 Syntax error recovery
12.4.3 Grammar checks
12.4.4 Semantic errors
12.4.5 Interfacing to support modules
12.4.6 The parser interface
12.4.7 A complete example
12.5 The driver program
12.5.1 Essentials of the driver program
12.5.2 Customizing the driver frame file
13 USING COCO/R - CASE STUDIES
13.1 Case study - Understanding C declarations
13.2 Case study - Generating one-address code from expressions
13.3 Case study - Generating one-address code from an AST
13.4 Case study - How do parser generators work?
13.5 Project suggestions
14 A SIMPLE COMPILER - THE FRONT END
14.1 Overall compiler structure
14.2 Source handling
14.2.1 A hand-crafted source handler
14.2.2 Source handling in Coco/R generated systems
14.3 Error reporting
14.4 Lexical analysis
14.4.1 A hand-crafted scanner
14.4.2 A Coco/R generated scanner
14.4.3 Efficient keyword recognition
14.5 Syntax analysis
14.5.1 A hand-crafted parser
14.5.2 A Coco/R generated parser
14.6 Error handling and constraint analysis
14.6.1 Syntax error handling in hand-crafted parsers
14.6.2 Syntax error handling in Coco/R generated parsers
14.6.3 Constraint analysis and static semantic error handling
14.7 The symbol table handler
14.8 Other aspects of symbol table management - further types
15 A SIMPLE COMPILER - THE BACK END
15.1 The code generation interface
15.2 Code generation for a simple stack machine
15.3 Other aspects of code generation
15.3.1 Machine tyranny
15.3.2 Abstract syntax trees as intermediate representations
15.3.3 Simple optimizations - constant folding
15.3.4 Simple optimizations - removal of redundant code
15.3.5 Generation of assembler code
16 SIMPLE BLOCK STRUCTURE
16.1 Parameterless procedures
16.1.1 Source handling, lexical analysis and error reporting
16.1.2 Syntax
16.1.3 The scope and extent of identifiers
16.1.4 Symbol table support for the scope rules
16.1.5 Parsing declarations and procedure calls
16.2 Storage management
16.2.1 The stack frame concept
16.2.2 The static link chain
16.2.3 Hypothetical machine support for the static link model
16.2.4 Code generation for the static link model
16.2.5 The use of a "Display"
16.2.6 Hypothetical machine support for the display model
16.2.7 Code generation for the display model
16.2.8 Relative merits of the static link and display models
17 PARAMETERS AND FUNCTIONS
17.1 Syntax and semantics
17.2 Symbol table support for context sensitive features
17.3 Actual parameters and stack frames
17.4 Hypothetical stack machine support
17.5 Context sensitivity and LL(1) conflict resolution
17.6 Semantic analysis and code generation
17.6.1 Semantic analysis and code generation in a hand-crafted compiler
17.6.2 Semantic analysis and code generation in a Coco/R generated compiler
17.7 Language design issues
17.7.1 Scope rules
17.7.2 Function return mechanisms
18 CONCURRENT PROGRAMMING
18.1 Fundamental concepts
18.2 Parallel processes, exclusion and synchronization
18.3 A semaphore based system - syntax, semantics, and code generation
18.4 Run-time implementation
Appendix A Software resources for this book
Appendix B Source code for the Clang compiler/interpreter
Appendix C Cocol grammar for the Clang compiler/interpreter
Appendix D Source code for a macro assembler