Introduction
The book systematically introduces the general construction principles, basic design methods and main implementation techniques of the compiler. The content includes: basic knowledge of grammar and language, design principles and construction methods of lexical analysis programs, various grammatical analysis technologies, grammar-guided translation technology and intermediate code generation, symbol table organization and management, code optimization, runtime storage space organization Basic knowledge of management, object code generation, parallel compilation technology, etc.
Book Catalog
Chapter 1 Compilation Overview
1.1 Translator and Compiler
1.2 Compiler Process and Basic Structure of Compiler
1.3 Generation method of compiler
1.4 Application of compilation technology in software development
Summary of this chapter
Extended reading
Self-test exercise 1
Exercise 1
Chapter 2 Basic knowledge of grammar and language
2.1 Overview
2.2 Basic concepts of alphabet and symbol string
2.2.1 Alphabet and symbol string
2.2.2 Symbol string operation
2.3 Grammar and language Formal definition
2.3.1 Formal language
2.3.2 Formal definition of grammar
2.3.3 Formal definition of language
2.3 .4 Normative Derivation and Normative Reduction
2.3.5 Recursive Rules and Recursiveness of Grammar
2.4 Phrases, Direct Phrases and Handle
2.4.1 Phrases And direct phrases
2.4.2 Handle
2.5 Ambiguity between syntax tree and grammar
2.5.1 Derivation and syntax tree
2.5.2 Ambiguity of grammar
2.5.3 Elimination of grammar ambiguity
2.6 Classification of grammar and language
2.7 The practicality of grammar Restrictions and transformations
Summary of this chapter
Extended reading
Self-test exercise 2
Exercise 2
Chapter 3 Lexical Analysis and Finite Automata
3.1 Function of Lexical Analysis Program
3.2 Word Symbols and Output Word Forms
3.2.1 Words in Language Symbols
3.2.2 The form of the output words of the lexical analysis program
3.3 Two definitions of language word symbols
3.3.1 Normal form and normal set< /p>
3.3.2 Normal grammar and normal form
3.4 Normal form and finite automata
3.4.1 Determined finite automata (DFA)
3.4.2 Non-deterministic finite automata (NFA)
3.4.3 Constructing NFA from regular expression R
3.4.4 Method of determinizing NFA into DFA< /p>
3.4.5 Simplification of DFA
3.4.6 Conversion from finite automata to normal form
3.5 Normal grammar and finite automata
3.5.1 Conversion method from right linear normal grammar to finite automata
3.5.2 Conversion method from left linear normal grammar to finite automata
3.5 .3 Conversion method from finite automaton to regular grammar
3.6 Method for writing lexical analysis program
Summary of this chapter
Extended reading
Self-test exercise 3
Exercise 3
Chapter 4 Syntax Analysis
4.1 Function of Syntax Analysis Program
4.2 From Above And down analysis method
4.2.1 The idea of non-deterministic top-down analysis method
4.2.2 Left recursion of grammar and elimination of backtracking
4.2.3 Rewriting some non-LL(1) grammar to LL(1) grammar
4.2.4 Recursive descent analysis method
4.2.5 Predictive analysis method and predictive analysis Table structure
4.3 General principles of bottom-up analysis
4.4 Operator priority analysis
4.4.1 Method overview
< p>4.4.2 Definition of operator precedence grammar4.4.3 Construction of operator precedence relation table
4.4.4 Design of operator precedence analysis algorithm
< p>4.4.5 Construction of precedence function4.4.6 Limitations of operator precedence analysis
4.5LR analysis method
4.5.1LR analyzer The working principle and process of
4.5.2LR(0) analysis method
4.5.3SLR(1) analysis method
4.5.4LR(1) analysis method
4.5.5LALR(1) parsing method
4.5.6 Application of LR parsing method to ambiguous grammar
4.5.7 Error recovery in LR parsing Technique
4.6 Method of writing syntax analysis program
Summary of this chapter
Extended reading
Self-test exercise 4
< p>Exercise 4Chapter 5 Grammar-guided Translation Technology and Intermediate Code Generation
5.1 Overview
5.2 Attribute Grammar
5.3 Grammar Guided translation overview
5.4 Intermediate language
5.4.1 Reverse Polish style
5.4.2 Ternary and tree representation
5.4.3 Quaternary and three-address codes
5.5 Bottom-up syntax-guided translation
5.5.1 Translation of simple arithmetic expressions and assignment statements
5.5.2 Translation of Boolean expressions
5.5.3 Translation of control statements
5.5.4 Translation of loop statements
5.5.5 Brief description statements Translation of
5.5.6 Translation of assignment statements containing array elements
5.5.7 Translation of procedure and function call statements
5.6 Recursive descent syntax-guided Translation
Summary of this chapter
Extended reading
Self-test exercise 5
Exercise 5
Chapter 6 The organization and management of the symbol table
6.1 The role of the symbol table
6.2 The organization of the symbol table
6.3 The establishment and search of the symbol table
Summary of this chapter
Extended reading
Self-test exercise 6
Exercise 6
Chapter 7 Code Optimization
< p>7.1 Overview of optimization7.2 Partial optimization
7.2.1 Method of dividing basic blocks
7.2.2 DAG representation of basic blocks
< p>7.2.3 Use DAG to optimize basic blocks7.3 Loop optimization
7.3.1 Program flow diagram and loop
7.3.2 Loop search
7.3.3 Loop optimization
7.4 Peephole optimization
Summary of this chapter
Extended reading
Self-test Exercise 7
Exercise 7
Chapter 8 Storage Organization and Management at Runtime
8.1 Overview
8.2 Static Storage Allocation< /p>
8.3 Stacked Storage Allocation
8.3.1 Simple Stacked Storage Allocation
8.3.2 Stacked Storage Allocation for Nested Process
8.4 Heap storage allocation
8.5 Storage allocation of temporary variables
Summary of this chapter
Extended reading
Self-test exercise 8< /p>
Exercises 8
Chapter 9 Object Code Generation
9.1 Overview
9.2 Hypothetical Computer Model
9.3 Simple code generator
9.3.1 Standby information and active information
9.3.2 Code generation algorithm
9.3.3 Register allocation
The automatic generation technology of 9.4 code generator
Summary of this chapter
Extended reading
Self-test exercise 9
Exercise 9
Chapter 10 Basic knowledge of parallel compilation technology
10.1 Introduction of parallel compilation technology
10.2 Function and structure of parallel compilation system
10.2.1 Function of parallel compilation system
10.2.2 Structure of parallel compilation system
10.3 Vector language compilation technology
10.3.1 Vector syntax processing
p>10.3.2 Vector structure optimization
10.4 Shared memory parallel machine parallel compilation technology
10.4.1 pre-compilation
10.4.2 can be re Imported target code p>
Summary of this chapter
Exercise 10
Appendix A Lex lexical analyzer generator
A.1 Introduction to Lex lexical analyzer generator
p>A.2Lex input file format
A.3 Lex conventions for regular expressions
A.4Lex source program rules
A.5Flex command options
A.6Lex program example
Appendix B syntax analysis program generator YACC
B.1 Introduction to the syntax analysis program YACC< /p>
B.2 YACC input file format
B.3 YACC writing format
B.3.1 definition part
B.3.2 Rules section
B.3.3 Auxiliary program section
B.4YACC's built-in name and definition mechanism
The combined use of B.5Flex and Bison
Appendix C Compiler Experiments
C.1 Lexical Analysis
C.1.1 Experiment Objectives
C.1.2 Experiment Requirements
C.1.3 Algorithmic thoughts of lexical analysis program
C.1.4 C language program framework of lexical analysis program
C.2 Syntax analysis
C.2.1 The purpose of the experiment
C.2.2 Experimental requirements
C.2.3 The algorithm idea of the syntax analysis program
C.2.4 The C language program framework of the syntax analysis program
p>C.3 Semantic analysis
C.3.1 Experimental purpose
C.3.2 Experimental requirements
C.3.3 C language of semantic analysis program Program Framework
C.4 Operator Priority Analysis Method
C.5 Experimental Example
C.6 Formal Form Conversion into Graphical Representation of Automata
p>C.6.1 Experimental purpose
C.6.2 Experimental requirements
C.6.3 Reference design ideas
C.6.4 Reference algorithm
Appendix D self-test exercises and reference answers to exercises
References