Chapter 1Concepts of compiler / 1

1.1The concept / 1

1.2Analysis of the source program / 2

1.2.1Lexical analysis / 2

1.2.2Syntax Analyzer / 3

1.2.3Semantic Analyzer / 4

1.2.4Intermediate Code Generator / 5

1.2.5Code Optimizer / 6

1.2.6Code Generator / 6

1.2.7Error handlers / 7

1.2.8Symbol table / 7

1.3Conclusion / 7

1.4The pass of compiler / 9

1.5Compiler example 1 / 9

1.5.1The lexical analysis / 10

1.5.2The Parser / 14

1.5.3Code generation / 17

1.6Compiler example 2 for using Flex tool / 20

Chapter 2Formal Language / 23

2.1String / 23

2.2Grammar and Formal language / 25

2.3Parsing tree and ambiguity / 31

2.4Extended Backus Naur Form / 34

2.5The type of grammar / 35

2.6Regular Expressions  /  38

Chapter 3Lexical analyzer / 41 

3.1Role of lexical analyzer /  41

3.2Design of lexical analyzer /  43

3.3Finite Automata /  45

3.3.1Deterministic Finite Automata—DFA / 45 

第1章编译程序概述 / 1

1.1概念 / 1

1.2源程序的分析 / 2

1.2.1词法分析器 / 2

1.2.2语法分析器 / 3

1.2.3语义分析 / 4

1.2.4中间代码生成器 / 5

1.2.5代码优化 / 6

1.2.6代码生成 / 6

1.2.7出错表 / 7

1.2.8符号表 / 7

1.3总结 / 7

1.4编译器的遍 / 9

1.5实例1——编译器程序 / 9

1.5.1词法分析器 / 10

1.5.2语法分析器 / 14

1.5.3代码生成器 / 17

1.6实例2——使用工具Flex / 20

第2章形式语言 / 23

2.1符号串 / 23

2.2文法和形式语言 / 25

2.3语法树和二义性 / 31

2.4扩充BNF范式 / 34

2.5文法的分类 / 35

2.6正则文法 /  38

第3章词法分析 / 41 

3.1词法分析器的作用 /  41

3.2词法分析器的设计 /  43

3.3有穷自动机 /  45

3.3.1确定有穷自动机 / 45

3.3.2Nondeterministic Finite Automata—NFA / 50

3.3.3Constructing DFA from NFA / 51 

3.3.4Minimum DFA /  53

3.3.5Constructing DFA from State Subset of CLOSURE /  54

3.3.6An example for constructing DFA from

regular expression / 56 

Chapter 4Topdown Syntax Analysis / 62 

4.1Practical limitation of grammar /  62

4.2FIRST(X) and FOLLOW(U)  / 65 

4.3Avoiding backtracking /  66

4.4Topdown parsing /  69

4.4.1Recursivedescent parsing /  69

4.4.2LL(1) method /  70

Chapter 5BottomUp Parsing /  75

5.1Operatorprecedence Parsing /  75

5.1.1Relation between pairs of operator 

precedence / 76 

5.1.2Constructing Operatorprecedence Relation/ 76 

5.1.3Operatorprecedence Grammar /78

5.1.4Leftmost Phrase /  79

5.1.5The Algorithm and Program of Operator 

Precedence Parsing /  80

5.2LR（0） Parser /  83

5.2.1Viable Prefix /  83

5.2.2Constructing FA by Viable Prefix /  84

5.2.3The Closure of set of items /  87

5.2.4LR(0) Parsing Table /  88

5.3SLR(1) Parser /  92

Chapter 6Symbol Table Manager and Type Checking / 98

6.1The Functions of Symbol Tables /  98

6.2The Attribute of Symbol Table /  99

6.3The Design of Symbol Table /  101

6.4The Structure of Symbol Table  /  103

6.4.1The operation of symbol table / 103

6.4.2The structure of symbol table / 104 

3.3.2非确定有穷自动机/ 50

3.3.3从非确定有穷自动机到确定有穷自动机的转换 / 51 

3.3.4最小化DFA / 53 

3.3.5有ε输入符号的状态子集的ε闭包 / 54 

3.3.6从正则表达式到DFA转换举例 /  56

第4章自顶向下语法分析 /  62

4.1文法的实用限制 /  62

4.2头符号集和后继符号集 / 65

4.3避免回溯 /  66

4.4自顶向下语法分析方法 / 69

4.4.1递归子程序法 / 69

4.4.2LL(1)方法 /  70

第5章自底向上语法分析 /  75

5.1算符优先分析法 /  75

5.1.1算符优先的关系 / 76

5.1.2构造算符优先关系 / 76

5.1.3算符优先关系文法/ 78

5.1.4最左素短语 / 79

5.1.5算符优先分析算法和程序 / 80 

5.2LR（0）分析法 /  83

5.2.1可归前缀 /  83

5.2.2构造识别可归前缀的有穷自动机 / 84

5.2.3项目集的闭包 / 87 

5.2.4LR(0)分析表 / 88

5.3SLR(1)分析法 /  92

第6章符号表和类型检查 / 98 

6.1符号表的作用 /  98

6.2符号表的属性 /  99

6.3符号表的设计 /  101

6.4符号表的结构 /  103

6.4.1符号表的操作 / 103

6.4.2符号表的结构 / 104

6.5Type checking /  107

Chapter 7Storage Organization and Register Allocation/ 109

7.1Static Storage Allocation /  109

7.2Dynamic Storage Allocation /  115

7.2.1Stack allocation /  115

7.2.2Allocation with nested procedure/ 117

7.2.3Heap Allocation /  119

Chapter 8Intermediate Code /  121

8.1Postfix Notation / 122 

8.1.1The definition of postfix notation / 122

8.1.2E.W.DIJKSTRA Method /  122

8.1.3Extended postfix notation /  124

8.2FourAddress Code /  125

6.5类型检查 /  107

第7章存储组织与分配 / 109 

7.1静态存储分配 /  109

7.2动态存储分配 /  115

7.2.1栈分配 /  115

7.2.2嵌套过程的存储分配/ 117

7.2.3堆存储分配 / 119

第8章中间语言 / 121 

8.1后缀表示 /  122

8.1.1后缀的定义 / 122

8.1.2E.W.DIJKSTRA方法/ 122 

8.1.3扩展后缀 / 124 

8.2四元组表示 /  125

8.3ThreeAddress Code /  127

8.4Comparison between three and fouraddress code /  127

8.5Portable Code /  128

8.6Assembly code /  130

Chapter 9Code Generation / 132 

9.1Structure of target program /  132

9.1.1Structure of “IF” sentence in program/ 133 

9.1.2Structure of “While” sentence in program/ 134

9.1.3Structure of “PROCEDURE” sentence in program / 135 

9.2An example /  137

9.2.1The algorithm of generating the target code /  137

9.2.2The function of symbol table in target code /  140

Chapter 10Code Optimization /  141

10.1Classifications of optimizations /  142

10.2Source program optimizations /  142

10.3Optimizations of threeaddress code /  147

10.4Optimizations of quadruples /  150

10.5Optimizations of target code /  151

8.3三元组表示 /  127

8.4三元组和四元组中间代码的比较 /  127

8.5伪代码 /  128

8.6汇编代码 /  130

第9章代码生成 /  132

9.1目标程序的结构 /  132

9.1.1条件语句目标程序/ 133

9.1.2循环语句目标程序/ 134

9.1.3过程语句目标程序/ 135 

9.2代码生成实例 /  137

9.2.1代码生成算法 / 137

9.2.2符号表的作用 / 140

第10章代码优化 /  141

10.1优化类型的分类 /  142

10.2源代码的优化 /  142

10.3三元组代码的优化 /  147

10.4四元组代码的优化 / 150

10.5目标代码的优化 / 151

参考文献 /  155