Chapter 1 Introduction to Compiling 1
1．1 Compilers 1
1．2 Analysis of the source program 4
1．3 The phases of a compiler 10
1．4 Cousins of the compiler 16
1．5 The grouping of phases 20
1．6 Compiler-construction tools 22
Bibliographic notes 23
Chapter 2 A Simple One-Pass Compiler 25
2．1 Overview 25
2．2 Syntax definition 26
2．3 Syntax-directed translation 33
2．4 Parsing 40
2．5 A translator for simple expressions 48
2．6 Lexical analysis 54
2．7 Incorporating a symbol table 60
2．8 A bstract stack machines 62
2．9 Putting the techniques together 69
Exercises 78
Bibliographic notes 81
Chapter 3 Lexical Analysis 83
3．1 The role of the lexical analyzer 84
3．2 Input buffering 88
3．3 Specification of tokens 92
3．4 Recognition of tokens 98
3．5 A language for specifying lexical analyzers 105
3．6 Finite automata 113
3．7 From a regular expression to an NFA 121
3．8 Design of a lexical analyzer generator 128
3．9 Optimization of DFA-based pattern matchers 134
Exercises 146
Bibliographic notes 157
Chapter 4 Symtax Analysis 159
4．1 The role of the parser 160
4．2 Context-free grammars 165
4．3 Writing a grammar 172
4．4 Top-down parsing 181
4．5 Bottom-up parsing 195
4．6 Operator-precedence parsing 203
4．7 LR parsers 215
4．8 Using ambiguous grammars 247
4．9 Parser generators 257
Exercises 267
Bibliographic notes 277
Chapter 5 Syntax-Directed Translation 279
5．1 Syntax-directed definitions 280
5．2 Construction of syntax trees 287
5．3 Bottom-up evaluation of S-attributed definitions 293
5．4 L-attributed definitions 296
5．5 Top-down translation 302
5．6 Bottom-up evaluation of inherited attributes 308
5．7 Recursive evaluators 316
5．8 Space for attribute values at compile time 320
5．9 Assigning space at compiler-construction time 323
5．10 Analysis of syntax-directed definitions 329
Exercises 336
Bibliographic notes 340
Chapter 6 Type Checking 343
6．1 Type systems 344
6．2 Specification of a simple type checker 348
6．3 Equivalence of type expressions 352
6．4 Type conversions 359
6．5 Overloading of functions and operators 361
6．6 Polymorphic functions 364
6．7 An algorithm for unification 376
Exercises 381
Bibliographic notes 386
Chapter 7 Run-Time Environments 389
7．1 Source language issues 389
7．2 Storage organization 396
7．3 Storage-allocation strategies 401
7．4 Access to nonlocal names 411
7．5 Parameter Passing 424
7．6 Symbol tables 429
7．7 Language facilities for dynamic storage allocation 440
7．8 Dynamic storage allocation techniques 442
7．9 Storage allocation in Fortran 446
Exercises 455
Bibliographic notes 461
Chapter 8 Intermediate Code Generation 463
8．1 Intermediate Languages 464
8．2 Declarations 473
8．3 Assignment statements 478
8．4 Boolean expressions 488
8．5 Case Statements 497
8．6 Backpatching 500
8．7 Procedure calls 506
Exercises 508
Bibliographic notes 511
Chapter 9 Code Generation 513
9．1 Issues in the design of a code generator 514
9．2 The target machine 519
9．3 Run-time storage management 522
9．4 Basic blocks and flow graphs 528
9．5 Next-use in formation 534
9．6 A simple code generator 535
9．7 Register allocation and assignment 541
9．8 The dag representation of basic blocks 546
9．9 Peephole optimization 554
9．10 Generating code from dags 557
9．11 Dynamic programming code-generation algorithm 567
9．12 Code-generator generators 572
Exercises 580
Bibliographic notes 583
Chapter 10 Code Optimization 585
10．1 Introduction 586
10．2 The principal sources of optimization 592
10．3 Optimization of basic blocks 598
10．4 Loops in flow graphs 602
10．5 Introduction to global data-flow analysis 608
10．6 Iterative solution of data-flow equations 624
10．7 Code-improving transformations 633
10．8 Dealing with aliases 648
10．9 Data-flow analysis of structured flow graphs 660
10．10 Efficient data-flow algorithms 671
10．11 A tool for data-flow analysis 680
10．12 Estimation of types 694
10．13 Symbolic debugging of optimized code 703
Exercises 711
Bibliographic notes 718
Chapter 11 Want to Write a Compiler? 723
11．1 Planning a compiler 723
11．2 Approaches to compiler development 725
11．3 The compiler-development environment 729
11．4 Testing and maintenance 731
12．1 EQN, a preprocessor for typesetting mathematics 733
Chapter 12 A Look at Some Compilers 733
12．2 Compilers for pascal 734
12．3 The C compilers 735
12．4 The Fortran H compilers 737
12．5 The Bliss/11 compiler 740
12．6 Modula-2 optimizing compiler 742
A．2 A Pascal subset 745
A．3 Program structure 745
A．1 Introduction 745
Appendix A Compiler Project 745
A．4 Lexical conventions 748
A．5 Suggested exercises 749
A．6 Evolution of the interpreter 750
A．7 Extensions 751
Bibliography 752
Index 780