Introduction
This book comprehensively and in-depth explores important topics in compiler design, including lexical analysis, grammatical analysis, grammar-guided definition and grammar-guided translation, runtime environment, Target code generation, code optimization technology, parallelism detection and inter-process analysis technology, and a large number of examples are given in the relevant chapters. Compared with the previous edition, this book has been fully revised to cover the latest developments in compiler development. A large number of examples and references are provided in each chapter.
Book Catalog
Publisher's Words
Translator's Preface
Foreword
Chapter 1 Introduction< /p>
1.1 Language Processor
1.2 The structure of a compiler
1.2.1 Lexical analysis
1.2.2 Syntax analysis
1.2.3 Semantic analysis
1.2.4 Intermediate code generation
1.2.5 Code optimization
1.2.6 Code generation
1.2.7 Symbol table management
1.2.8 Combine multiple steps into a trip
1.2.9 Compiler construction tool
1.3 Program design Language development process
1.3.1 Towards a high-level programming language
1.3.2 Impact on the compiler
1.3.3 Exercises in section 1.3
p>1.4 The related science of building a compiler
. 1.4.1 Modeling in compiler design and implementation
1.4.2 Science of code optimization
1.5 Application of Compilation Technology
1.5.1 Implementation of Advanced Programming Language
1.5.2 Optimization for Computer Architecture
1.5. 3 Design of New Computer Architecture
1.5.4 Program Translation
1.5.5 Software Productivity Tools
1.6 Basic Programming Language
1.6.1 The difference between static and dynamic
1.6.2 Environment and state
1.6.3 Static scope and block structure
1.6.4 Explicit Access control
1.6.5 Dynamic scope
1.6.6 Parameter transmission mechanism
1.6.7 Alias
1.6.8 1.6 Section exercises
1.7 Summary of Chapter 1
1.8 Bibliography of Chapter 1
Chapter 2 A Simple Grammar Guided Translator
2.1 Introduction
2.2 Grammar Definition
2.2.1 Grammar Definition
2.2.2 Derivation
2.2.3 Grammar Analysis tree
2.2.4 Ambiguity
2.2.5 Operator associativity
2.2.6 Operator precedence
< p>2.2.7 Exercises in section 2.22.3 Grammar-guided translation
2.3.1 Suffix representation
2.3.2 Comprehensive attributes
2.3.3 Definition of Simple Syntax Guidance p>
2.3.4 Tree traversal
2.3.5 Translation plan
2.3.6 Exercises in section 2.3
2.4 Syntax analysis
2.4.1 Top-down analysis method
2.4.2 Predictive analysis method
2.4.3 When to use production
2.4. 4 Design a predictive syntax analyzer
2.4.5 Left recursion
2.4.6 Section 2.4 exercises
2.5 Simple expression translator
2.5.1 Abstract and concrete grammar
2.5.2 Adjusting the translation plan
2.5.3 The process of non-terminal symbols
2.5.4 Simplification of the translator
2.5.5 Complete program
2.6 Lexical analysis
2.6.1 Eliminate blanks and comments
2.6. 2 Pre-reading
2.6.3 Constants
2.6.4 Identifying keywords and identifiers
2.6.5 Lexical analyzer
2.6.6 Exercises in Section 2.6
2.7 Symbol Table
2.7.1 Set up a symbol table for each scope
2.7.2 Use of the symbol table
2.8 Intermediate code generation
2.8.1 Two intermediate representations
2.8.2 Syntax tree construction
2.8.4 Three address code
2.8.5 Section 2.8 exercises
2.9 Summary of Chapter 2
Chapter 3 Lexical Analysis
3.1 The role of lexical analyzer
3.1.1 Lexical analysis and analysis
3.1.2 Lexical units, patterns, morphemes
3.1.3 Properties of lexical units< /p>
3.1.4 Lexical error
3.1.5 Exercises in section 3.1
3.2 Input buffer
3.2.1 Buffer pair
p>3.2.2 Sentinel tag
3.3 Specification of lexical unit
3.3.1 String and language
3.3.2 Operation on language< /p>
3.3.3 Regular expression
3.3.4 Regular definition
3.3.5 Regular expression extension
3.3.6 3.3 Section exercises
3.4 Recognition of lexical units
3.4.1 State transition diagram
3.4.2 Recognition of reserved words and identifiers
< p>3.4.3 Complete our continuity example3 .4.4 Architecture of lexical analyzer based on state transition diagram
3.4.5 Exercises in Section 3.4
3.5 Lexical analyzer generation tool lex
3.5. 1 The use of lex
3.5.2 The structure of the lex program
3.5.3 Conflict resolution in lex
3.5.4 Looking ahead operators
p>3.5.5 3.5 exercises
3.6 finite automata
3.6.1 uncertain finite automata
3.6.2 Conversion table
3.6.3 nfa accepts input string
3.6.4 determined finite automata
3.6.5 Section 3.6 exercise
3.7 From regular expressions to automata
3.7.1 Conversion from nfa to dfa
3.7.2 Simulation of nfa
3.7. 3 Nfa simulation efficiency
3.7.4 Constructing nfa from regular expressions
3.7.5 Efficiency of string processing algorithms
3.7.6 Exercises in section 3.7
3.8 Design of the lexical analyzer generation tool
3.8.1 The structure of the generated lexical analyzer
3.8.2 Pattern matching based on nfa
p>3.8.3 DFA used by the lexical analyzer
3.8.4 Implementing the forward-looking operator
3.8.5 3.8 exercises
3.9 Optimization of pattern matcher based on dfa
3.9.1 Important state of nfa
3.9.2 Function calculated according to abstract syntax tree
3.9. 3 Calculate nullable, firstpos and lastpos
3.9.4 Calculate followpos
3.9.5 Construct dfa based on regular expression
3.9.6 Minimize a dfa Number of states
3.9.7 Minimize the state of the lexical analyzer
3.9.8 Trade time for space in dfa simulation
3.9.9 Section 3.9 Exercises
3.9.10 Summary of Chapter 3
3.11 Chapter 3 References
Chapter 4 Syntax Analysis
4.1 Introduction On
4.1.1 The role of the parser
4.1.2 Representative grammar
4.1.3 The handling of grammatical errors
4.1.4 Error recovery strategy
4.2 Context-free grammar
4 .2.1 Formal definition of context-free grammar
4.2.2 Symbolic conventions
4.2.3 Derivation
4.2.4 Parse tree and derivation
p>4.2.5 Ambiguity
4.2.6 Verify the language generated by the grammar
4.2.7 Context-free grammar and regular expressions
4.2.8 Exercises in Section 4.2
4.3 Design Grammar
4.3.1 Lexical Analysis and Syntax Analysis
4.3.2 Elimination of Ambiguity
4.3.3 Elimination of left recursion
4.3.4 Extracting the left common factor
4.3.5 Non-context-free language construction
4.3.6 Exercises in Section 4.3
4.4 Top-down grammatical analysis
4.4.1 Recursively descending grammatical analysis
4.4.2 first and follow
4.4.3 ll(1) grammar
4.4.4 Non-recursive predictive analysis
4.4.5 Error recovery in predictive analysis
4.4.6 Exercises in Section 4.4
4.5 Bottom-up grammatical analysis
4.5.1 Reduction
4.5.2 Handle pruning
4.5.3 Shift-in-reduction syntax analysis technology
4.5.4 Conflicts in shift-in-reduction syntax analysis
4.5.5 Exercises in section 4.5
4.6 Introduction to lr syntax analysis technology: simple lr technology
4.6.1 Why use lr syntax analyzer?
4.6.2 item and lr(0) automata
4.6.3 lr-syntax analysis algorithm
4.6.4 construct slr- analysis table
p>4.6.5 Possible prefixes
4.6.6 Exercises in section 4.6
4.7 More powerful lr parser
4.7.1 Specification lr(1) item
4.7.2 Construction of lr(1) item set
4.7.3 Standard lr(1) analysis table
4.7.4 Construction Lalr syntax analysis table
4.7.5 The efficient construction method of lalr syntax analysis table
4.7.6 Compression of lr syntax analysis table
Section 4.7.7 4.7 Exercises
4.8 Using Ambiguous Grammar
4.8.1 Using Priority and Associativity to Resolve Conflicts
4.8.2 "Dangling-else" Ambiguity
4.8.3 Error recovery in lr syntax analysis
4.8.4 Exercises in section 4.8
4.9 Syntax parser generation tool
4.9.1 yacc, a grammatical analyzer generation tool
4.9.2 Using yacc to handle ambiguous grammar
4.9.3 Using lex to create a yacc lexical analyzer
p>4.9.4 Error recovery in yacc
4.9.5 Exercises in section 4.9
4.10: Summary of Chapter 4
4.11 References for Chapter 4
Chapter 5 Translation of Grammar Guidance
5.1 Definition of Grammar Guidance
5.1.1 Inheritance and Comprehensive Attributes
< p>5.1.2 Evaluate an sdd at the node of a parse tree5.1.3 Exercises in section 5.1
5.2 Evaluation order of sdd
5.2.1 Dependency graph
5.2.2 Order of attribute evaluation
5.2.3 s-attribute definition
5.2.4 l- Attribute definitions
5.2.5 Semantic rules with controlled side effects
5.2.6 Exercises in section 5.2
5.3 Application of grammar-guided translation
5.3.1 Construction of abstract syntax tree
5.3.2 Type structure
5.3.3 Section 5.3 exercises
5.4 Grammar-guided translation Scheme
5.4.1 Suffix translation scheme
5.4.2 The suffix sdt syntax analysis stack implementation
5.4.3 The production contains semantic verbs inside Sdt
5.4.4 Eliminate left recursion from sdt
5.4.5 l-attribute defined sdt
5.4.6 Exercises in section 5.4< /p>
5.5 Realize l-attribute sdd
5.5.1 Translate during recursive descent parsing
5.5.2 Generate code while scanning
>5.5.3 sdd and ll syntax analysis of l-attribute
5.5.4 bottom-up syntax analysis of sdd of l-attribute
5.5.5 section 5.5 Exercise
5.6 Summary of Chapter 5
5.7 References of Chapter 5
Chapter 6 Intermediate Code Generation
Chapter 7 Chapter Runtime Environment
Chapter 7 Summary
Chapter 8 Code Generation
Chapter 9 Machine Independent Optimization
Chapter 10 Instruction-level parallelism
Chapter 11 Optimization of Parallelism and Locality
Chapter 12 Interprocedural Analysis