Compilers : principles and practice

Cover Contents List of Figures List of Tables List of Algorithms Preface Acknowledgements Chapter 1: Introduction 1.1 Languages 1.1.1 Machine Language 1.1.2 Hex AbsoluteLoaderLanguage 1.1.3 Assembly Language 1.1.4 Macro Assembly Language 1.1.5 Intermediate or ByteCode 1.1.6 High Level Language 1.1.7 Very High Level Language 1.1.8 Why High Level Language? 1.2 Translation Process 1.3 Translation Schemes 1.3.1 T-diagram 1.3.2 Assembler 1.3.3 Macro Assembler 1.3.4 Interpreter 1.3.5 Load-and-Go Scheme 1.3.6 Compiler 1.3.7 What Does a Compiler Do? 1.4 Theoretical Viewpoint 1.4.1 Acceptor and Compiler 1.5 Phases of a Compiler 1.6 A More Detailed Look at Phases of a Compiler 1.6.1 Lexical Analyzer – Scanner 1.6.2 SyntaxAnalyzer – Parser 1.6.3 Semantic Analyzer – Mapper 1.6.4 Code Generation and Machine-dependent Optimization 1.6.5 Optimization 1.6.6 How to Develop Optimized Code? 1.7 A Real-life Compiler–gcc 1.8 What Do We Mean by “Meaning”? Looking Forward Historical Notes Exercises Web Resources Glossary Chapter 2: A Simple Translator 2.1 A Simple Language 2.1.1 Grammar of simple 2.1.2 Target Language 2.1.3 Example Program in Machine Code 2.2 Compiler for Simple 2.2.1 Scanner 2.2.2 Parser 2.2.3 Intermediate Form and Semantic Phase 2.2.4 Code Generation 2.2.5 Comments on the Compiled Code 2.3 A Virtual Machine for Simple Looking Forward Exercises Web Resources Glossary Chapter 3: Lexical Analyzer 3.1 Scanner 3.1.1 Examples: RE, FSM and Implementation 3.2 Symbol Tables and a Scanner 3.3 Compiler Writing Tools 3.3.1 Lex – A Scanner Generator 3.3.2 Flex 3.3.3 Debugging lex and flex 3.4 Error Handling in a Scanner Exercises Web Resources Glossary Chapter 4: Syntax Analyzer 4.1 Top-down and Bottom-up Parsing 4.2 Top-down Parsing 4.2.1 Recursive-descent Parser (RDP) 4.2.2 Exercises 4.2.3 Parser for Simple LL(1) Grammars 4.2.4 LL(1) Grammar Without ε-rules 4.2.5 LL(1) Grammars with ε-rules 4.3 Bottom-up Parsing 4.3.1 Shift/Reduce Parsing 4.3.2 Operator Precedence Parsing 4.3.3 LR Grammars 4.3.4 FSM for an LR(0) Parser 4.3.5 Design of the FSM for an LR(0) Parser 4.3.6 Table-driven LR(0) Parser 4.3.7 Parsing Decision Conflicts 4.3.8 Canonical LR(1) Parser 4.3.9 SLR(1) Parser 4.3.10 Conflict Situations 4.3.11 Look-ahead (LA) Sets 4.3.12 LALR(1) Parser 4.4 Yacc – A Parser Generator 4.4.1 YACC – A Compiler Writing Tool 4.4.2 Working of the Parser Generated by YACC 4.4.3 Input Specification 4.4.4 Recursion in Grammar Specification 4.4.5 Actions 4.4.6 Ambiguity and Conflict Resolution 4.4.7 Error Handling 4.4.8 Arbitrary Value Types 4.4.9 Debugging yacc 4.4.10 Working Examples 4.5 Other Parser Generators 4.5.1 Bison 4.5.2 Parse::Yapp 4.5.3 ANTLR 4.6 Grammar for miniC 4.7 Symbol Table and Parser 4.7.1 Pre-defined Entities 4.8 Real-life – GCC: GNU Compiler Collection Exercises Web Resources Further Reading Glossary Chapter 5: Syntax-directed Translation 5.1 Implicit Stacking in RDP 5.2 Synchronized Semantic Stacks 5.2.1 Semantic Stack in yacc 5.3 Action Symbols 5.3.1 Action Symbols in yacc 5.4 Attribute Grammars 5.4.1 Syntax-directed Techniques 5.4.2 Definition of Attribute Grammar 5.4.3 Dependency Graphs 5.4.4 Definitions: Inherited and Synthesized Attributes 5.4.5 S-Type Definitions and Grammars 5.4.6 L-Type Definitions and Grammars 5.4.7 Synthesized and Inherited Attributes in yacc 5.4.8 More on Inherited Attributes in yacc 5.5 Symbol Table Handling 5.5.1 Symbol Table in miniC 5.6 Intermediate Representation Output for miniC Exercises Web Resources Further Reading Glossary Chapter 6: Type Checking 6.1 Data Types and Type Checking 6.2 Type Expressions and Type Constructors 6.3 Type Equivalence 6.4 Type Names, Declarations and Recursive Types 6.4.1 Recursive Types 6.5 Type Inference 6.5.1 Formal Semantics 6.6 Type Conversion and Coercion 6.7 Overloading of Operators and Functions 6.8 Example: Type Checking in an Interpreter Exercises Web Resources Further Reading Glossary Chapter 7: Run-Time Environment 7.1 Run-Time Storage Allocation 7.1.1 Static Allocation 7.1.2 Typical Function Calls Interface for C 7.1.3 Dynamic Allocation 7.1.4 Nested Functions in GCC Extension 7.1.5 On-demand or Heap Allocation 7.1.6 Parameter Passing and Calling Conventions 7.1.7 C Variables 7.1.8 Block-structured Languages 7.2 Operating System 7.2.1 A Running Program – A Process 7.2.2 Linux System Calls 7.3 Libraries 7.3.1 Language Library 7.3.2 Special Purpose Libraries 7.4 System Environmental Variables 7.5 Invocation Command-line Parameters Exercises Web Resources Further Reading Glossary Chapter 8: Intermediate Code 8.1 Building a Parse Tree 8.1.1 Generating Parse Tree in Memory 8.2 Polish Notation 8.2.1 Generating RPN 8.3 N-tuple Notation 8.3.1 Triple notation 8.3.2 Quadruple Notation 8.3.3 Generation of N-tuple Code 8.4 Abstract Syntax Tree 8.4.1 Generating Abstract Syntax Tree 8.5 Abstract or Virtual Machine Code 8.5.1 P-code for a PASCAL Machine 8.5.2 Java Bytecode 8.6 Threaded Code 8.6.1 Subroutine Threaded Code 8.6.2 Direct Threaded Code 8.6.3 Indirect Threaded Code 8.6.4 Token Threaded Code 8.6.5 Implementation of Threaded Code on Motorola 68000 8.6.6 Implementation of Threaded Code on Intel x86 Machines 8.7 SECD and WAM 8.8 Grammar and IR Generation for miniC 8.8.1 Expressions 8.8.2 Assignments 8.8.3 Statements 8.8.4 IF-THEN and IF-THEN-ELSE 8.8.5 WHILE-DO 8.8.6 Variable Declarations 8.8.7 Function Definitions 8.8.8 Function Calls 8.8.9 Utility Functions Used 8.9 Real-life: Intermediate Codes of GNU gcc 8.9.1 Example GCC Intermediate Code Exercises Further Reading Glossary Chapter 9: Code Generation and Machine-dependent Optimization 9.1 Our Concerns in Code Generation 9.1.1 Input Intermediate Representation (IR) 9.1.2 Nature of Target Language 9.1.3 Selection of Alternatives from Instruction Set 9.1.4 Allocation of CPU Registers 9.1.5 Order of Evaluation Sequence 9.2 The Target Language 9.2.1 x86 Assembly Language in GAS Syntax 9.3 Data Structures 9.3.1 Vectors and Arrays 9.3.2 Vectors 9.3.3 Arrays 9.4 Control Constructs 9.5 Procedures and Function Calls 9.5.1 Function Prologue and Epilogue 9.5.2 Saving Registers 9.5.3 A Test for C Linkage 9.6 The Target Operating Environment 9.6.1 Memory Management 9.6.2 CPU Register Usage 9.6.3 Activation Record (AR) 9.7 Code Optimization 9.8 Machine-dependent Optimization 9.8.1 Register Allocation 9.8.2 Instruction Rescheduling: Use of Parallelism in Instruction Execution 9.9 Converting the 4-Tuple and RPN into Assembly Code 9.9.1 Conversion of 4-Tuple to Assembly Code 9.9.2 Conversion of RPN to Assembly Code Exercises Further Reading Glossary Chapter 10: Code Optimization 10.1 Basic Blocks 10.1.1 Formal Algorithm to Delineate BBs 10.1.2 Reference and Define Information 10.1.3 Loops in Flow-graphs 10.1.4 Example Implementation – miniC 10.2 Value Numbering Scheme 10.3 Peep-hole Optimization 10.3.1 Strength Reduction 10.3.2 Constant Folding 10.3.3 Constant Propagation 10.3.4 Dead Variable and Dead Code Elimination 10.4 Structural Optimization 10.4.1 Redundant Sub-expressions 10.4.2 Loop Unwinding 10.4.3 Replace Index by Pointers 10.4.4 Code Motion 10.4.5 Variable Folding 10.4.6 In-line Function 10.4.7 Register Allocation 10.5 Global Data-flow Analysis 10.6 Super-optimizers 10.6.1 Massalin’s Super-optimizer 10.6.2 GNU GCC Super-optimizer – GSO 10.7 Epilogue Exercises Further Reading Glossary Chapter 11: Overview of Processing of Some Languages 11.1 Java 11.1.1 Brief History 11.1.2 Overview 11.1.3 Characteristics of Java 11.1.4 Development with Java 11.1.5 The First Java Program 11.1.6 Type Conversion 11.2 Perl 11.2.1 Perl Internals 11.3 PROLOG 11.3.1 A Short Introduction to PROLOG 11.4 FORTH 11.4.1 Hello World in Forth 11.4.2 A Quick Introduction to FORTH 11.4.3 Summary 11.4.4 Vmgen Exercises Web Resources Chapter 12: Project: Compiler for a MiniC 12.1 MiniC Language 12.1.1 What is HOC6? 12.1.2 Objectives of miniC 12.2 Architecture of miniC Compiler 12.3 MiniC Grammar for yacc 12.4 Target Language 12.4.1 x86 Instructions 12.4.2 Assembler Directives 12.4.3 Floating-point Instructions 12.5 Symbol Table 12.6 Scanner 12.7 Parser 12.8 Code Generation 12.8.1 Arithmetic Expression 12.8.2 Assignment 12.8.3 Comparison with Logical Result 12.8.4 Integer Increment and Decrement 12.8.5 IF-THEN-ELSE Construct 12.8.6 Function Definition and Call 12.8.7 Assembly Language Macros 12.8.8 Built-in Functions Library 12.8.9 A Few Example miniC Programs 12.8.10 Assembly Language Idioms 12.8.11 Linux System Calls 12.9 Testing 12.10 Use of gdb to Debug the FPU Operations 12.10.1 An Example miniC Program 12.11 Difference Between AT&T and Intel Assembly Syntax Exercises Further Reading and Web Resources Appendix A: Formal Languages and Automata A.1 Essential Mathematical Background A.1.1 Formal Logic: A Language for Mathematics A.1.2 Assertions and Propositions A.1.3 Logical Connectives A.1.4 Sets A.1.5 Relations A.1.6 Inductive Definitions A.1.7 Proof Techniques A.1.8 Proof by Induction A.1.9 Cantor’s Theory of Counting and Infinite Sets A.2 Formal Language Theory Review A.2.1 Strings A.2.2 Binary Operation on Strings A.2.3 Relationships Between Strings A.2.4 Languages A.2.5 Binary Operation on Languages A.2.6 Power Xi of a Language X A.2.7 Closure of a Language A.3 Grammars A.3.1 Methods of Grammar Specification A.3.2 Chomsky Classification A.4 Regular Languages, Regular Expressions and Finite-state Machine A.4.1 Regular Languages A.4.2 Finite Automaton or Finite-state Machine A.4.3 Non-deterministic FSM A.4.4 Conversion of a Regular Grammar to FSM A.4.5 Languages Not in the Class Regular A.4.6 Implementation Notes A.5 Context-free Languages, CFG and Push-down Automata A.5.1 Context-free Language A.5.2 Context-free Grammars A.5.3 Push-down Automata A.5.4 Pumping Lemma for Context-free Languages Exercises Glossary Appendix B: Assemblers and Macro Processors B.1 Assembly Languages B.1.1 Example Assembly Language B.2 Assemblers B.2.1 One-pass Assembler B.2.2 Two-pass Assembler B.2.3 Symbol Table Handling B.2.4 Macro Assembler B.3 Macro Processors B.3.1 Real-world: M4 Macro Processor B.3.2 Real-world: Pre-processing (cpp) Exercises Appendix C: Linkers and Loaders C.1 Linkers C.1.1 Relocation and Linking C.1.2 Tasks Performed by a Linker C.1.3 An Object Module C.1.4 Logical View of Process Memory C.1.5 Actual Process Memory C.1.6 Static Linking C.1.7 Dynamic Linking C.2 A Typical Linking Loader C.2.1 Data from Object Modules C.2.2 Database Used or Created During Linking C.3 In Linux World C.3.1 ld – GNU Linking Loader C.4 Loaders C.4.1 Absolute Loader C.4.2 Relocating Loader C.4.3 Virtual Memory and Loader Appendix D: Worked-out Problems D.1 Problems for Chapter 4: Parsers D.1.1 Top-down Parsing D.1.2 Bottom-up Parsing D.2 Problems for Chapter 5: Syntax-directed Translation D.2.1 Syntax-directed Definition (SDD) D.2.2 Syntax-directed Translation (SDT) D.3 Problems for Chapter 6: Type Checking D.3.1 Type as Attribute D.4 Problems for Chapter 7: Run-Time Environment D.4.1 Storage Allocation D.4.2 Call Graph D.4.3 Function Storage and Activation Record Bibliography Index