编译原理及其习题解答PDF电子书下载

目录 1

第一章 引论 1

1.1 翻译程序 1

1.1.1　程序设计语言 1

1.1.2　翻译程序 2

1.2 为什么需要编译程序 3

1.3　编译程序的工作过程 5

1.3.1　分析 6

1.3.2　综合 7

1.4　编译程序的结构 8

1.5　编译程序的组织方式 10

1.6　编译程序的其他有关技术 10

1.6.1　编译程序的自展技术 10

1.6.2　编译程序的移植 11

1.6.3　编译程序的自动化 12

1.6.4　程序的可再入性 13

1.7　翻译程序编写系统 13

1.8　并行编译程序 14

习题一 16

1.9 小结 16

第二章　形式语言概论 18

2.1 语言成分 18

2.2　产生式文法和语言 20

2.2.1　产生式文法 20

2.2.2　上下文无关文法 21

2.2.3　上下文无关文法定义的语言 22

2.3.1　文法分类 23

2.3　文法的分类 23

2.3.2　文法分类的意义 26

2.3.3　文法举例 26

2.4　语言和语法 27

2.4.1 句型、句子和语言 27

2.4.2　语法树 28

2.4.3 产生式树 30

2.5.2　不可达文法符号 32

2.5.1　无用非终结符号 32

2.5 文法和语言的一些特性 32

2.5.3　可空非终结符 33

2.5.4　最左、最右推导和规范推导 34

2.5.5　二义性 36

2.6　分析方法简介 37

2.6.1 自上而下分析方法 38

2.6.2　确定的自上而下分析方法 40

2.6.3　自下而上分析方法 42

2.6.4　文法在内存中的表示 43

2.7 小结 45

习题二 45

第三章　有穷自动机 47

3.1 概述 47

3.2 有穷自动机的形式定义 49

3.2.1　状态转换表 50

3.2.2　状态转换图 51

3.2.3　构形和移动 52

3.2.5　非确定有穷自动机 53

3.2.4　自动机的等价性 53

3.3 NDFSA到DFSA的转换 55

3.3.1 空移环路的寻找和消除 55

3.3.2　消除空移 56

3.3.3　利用状态转换表消除空移 58

3.3.4　确定化——子集法 60

3.3.5　确定化——造表法 63

3.3.6　消除不可达状态 67

3.3.7　确定的有穷自动机的化简 68

3.3.8　从化简后的DFSA到程序表示 70

3.3.9　小结 72

3.4 正规文法与有穷自动机 72

3 4 1 从正规文法到FSA 72

3.4.2　从FSA到正规文法 74

3.5 正规表达式与FSA 74

3.5.1 正规表达式的定义 74

3.5.2 正规表达式的CFG 76

3.5.4　正规表达式到NDFSA的转换 77

3.5.3 正规表达式与FSA的对应性 77

3.5.5　NDFSA M到正规表达式的转换 81

3.5.6　从正规文法到正规表达式 82

3.6 DFSA在计算机中的表示 86

3.6.1　矩阵表示法 86

3 6.2　表结构 86

3.6.3　程序表示法 86

习题三 88

3.7 小结 88

第四章 词法分析 91

4.1 词法分析概述 91

4.2 单词符号 92

4.3　扫描程序的设计 93

4.4 标识符的处理 98

4 4.1 类型的机内表示 98

4 4.2　标识符的语义表示 102

4 4.3 符号表（标识符表） 105

4.5 设计词法分析程序的直接方法 106

4.4 4　标识符处理的基本思想 106

4.6 与设计扫描程序相关的几个问题 108

4.7 小结 108

习题四 109

第五章 自上而下语法分析 110

5.1 非确定的下推自动机 110

5.1.1　PDA的形式定义 111

5.1.2　PDA的构形和移动 112

5.1.3　上下文无关语言与PDA 114

5.2 消除左递归方法 117

5.2.1　文法的左递归性 117

5.2.2　用扩展的BNF表示法消除左递归 117

5.2.3　直接改写法 119

5.2.4　消除所有左递归的算法 120

5.3 LL（k）文法 121

5.3.1　LL（l）文法的判断条件 121

5.3.2　集合FIRST、FOLLOW与SELECT的构造 122

5.4.1　构造分析表M的算法 125

5.4　确定的LL（l）分析器的构造 125

5.4.2　LL（l）分析器的总控算法 127

5.5　LL（k）文法的几个结论 129

5.6　递归下降分析程序及其设计 130

5.6.1　框图设计 131

5.6.2　程序设计 131

5.7 带回溯的自上而下分析法 133

5.7.3　带回溯的自上而下分析算法 134

5.7.2　其他信息的存放 134

5.7.1 文法在内存中的存放形式 134

5.8 小结 139

习题五 139

第六章 自下而上分析和优先分析方法 142

6.1 短语和句柄 142

6.2　移进-归约方法 144

6.3 非确定的自下而上分析器 147

6.4　有关文法的一些关系 151

6.4.1　关系 151

6.4.2　布尔矩阵和关系 152

6.4.3　Warshall算法 153

6.4.4　关系FIRST与LAST 156

6.5 简单优先分析方法 158

6.5.1　优先关系 158

6.5.2　简单优先关系的形式化构造方法 160

6.5.3　简单优先文法及其分析算法 165

6.6　算符优先分析方法 169

6.6.1　算符优先文法 169

6.5.4　简单优先分析方法的局限性 169

6.6.2　OPG优先关系的构造 170

6.6.3　素短语及句型的分析 172

6.6.4　算符优先分析算法 174

6.7　优先函数及其构造 177

6.7.1　Bell方法 178

6.7.2　Floyd方法 179

6.7.3　两种方法的比较 181

6.8 两种优先分析方法的比较 182

6.9 小结 183

习题六 184

第七章 自下而上的LR（k）分析方法 186

7.1 LR（k）文法和LR（k）分析器 186

7.2　LR（O）分析表的构造 190

7.2.1　规范句型的活前缀 190

7.2.2　LR（O）项目 190

7.2.3　文法G的拓广文法 191

7.2.4　CLOSURE（I）函数 191

7.2.6　LR（O）项目集规范族 192

7.2.5　goto（I，X）函数 192

7.2.7　有效项目 195

7.2.8　举例 196

7.2.9　LR（O）文法 198

7.2.10　构造LR（O）分析表的算法 198

7.2.11 构造LR（O）分析表的步骤小结 200

7.3　SLR分析表的构造 200

7.4　规范LR（l）分析表的构造 204

7.5 LALR分析表的构造 210

7.6 无二义性规则的使用 213

7.7 小结 216

7.7.1 LR分析程序 216

7.7.2　LR分析表的自动构造 216

7.7.3　文法间的关系 217

7.7.4　LR文法举例 217

7.7.5　有关LR文法的几个结论 220

习题七 220

8.1.1 一般原理 222

8.1 一般原理和树变换 222

第八章　语法制导翻译法 222

8.1.2　树变换 224

8.2 简单SDTS和自上而下翻译器 227

8.3 简单后缀SDTS和自下而上翻译器 230

8.3.1　后缀翻译 230

8 3.2 IF-THEN-ELSE控制语句 231

8.3.3　函数调用 232

8.4　抽象语法树的构造 232

8.4.2　AST的拓广 235

8 4.1 自下而上构造AST 235

8.5 属性文法 236

8.5 L属性文法 237

8.5.2　S属性文法 237

8.6 中间代码形式 238

8.6.1　逆波兰表示法 238

8.6.2　逆波兰表示法的推广 238

8.6.3　四元式 240

8.6.4 三元式 241

8.7　属性翻译文法的应用 242

8.7.1 综合属性与自下而上定值 242

8.7.2 继承属性和自上而下定值 243

8.7.3　布尔表达式到四元式的翻译 244

8.7.4　条件语句的翻译 245

8.7.5　迭代语句的翻译 247

8.8　小结 249

习题八 249

9.1 数据区和属性字 252

第九章　运行时的存储组织与管理 252

9.2　基本数据类型的存储分配 254

9.3 数组的存储？ 254

9.3.1 单块存储方式 254

9.3.2　信息向量与数组分配程序 256

9.3.3　多块存储方式 257

9.4　记录结构的存储分配 258

9.5 参数传递方式及其实现 259

9.5.2　传值 260

9.5.1 换名 260

9.5.3　传地址 261

9.5.4　传结果 261

9.5.5　数组名用做实参 261

9.5 6　过程名用做实参 261

9.6 栈式存储分配方法 262

9.6.1 概述 262

9.6.2　现行DISPLAY和现行数据区 263

9.6.3　标识符的作用域 265

9.6.4　分程序的入口和出口工作 266

9.6.5　过程调用时的存储管理 267

9.7　堆式存储分配方法 270

9.8 临时工作单元的存储分配 271

9.9 小结 275

习题九 275

第十章　符号表的组织和查找 277

10.1 符号表的一般组织形式 277

10.2 符号表中的数据 278

10.3.1　线性查找 279

10.3 符号表的构造与查找 279

10.3.2　折半法 280

10.3.3　杂凑技术 281

10.4　分程序结构的符号表 284

10.5 小结 286

习题十 286

第十一章　优化 288

11.1　基本块及其求法 288

11.2　优化举例 290

11.3 利用变量的定义点进行优化 293

11.3.1　变量的定义点 293

11.3.2　循环中不变式的外提 294

11.3.3　运算强度削弱 294

11.3.4　公共表达式的消除 294

11.3.5　常量合并 295

11.4　循环优化 296

11.5 借助DAG进行优化 297

11.6　并行分支的优化 298

11.7　窥孔优化 300

11.8 小结 300

习题十一 300

第十二章　代码生成 302

12.1　假想的计算机模型 302

12.2　从四元式生成代码 303

12.3　从三元式生成代码 305

12.4　从树型表示生成代码 308

12.6　寄存器的分配 311

12.5　从逆波兰表示生成代码 311

12.7 小结 312

习题十二 312

第十三章 词法分析器生成工具LEX 314

13.1 LEX简介 314

13.2　LEX源文件的格式 316

13.2.1　模式 317

13.2.2　定义部分 319

13.2.3　规则部分 320

13.2.4　用户代码部分 321

13.3 LEX的工作原理 321

13.4　yylex（）函数的匹配原则 322

13.5　识别模式后处理 323

13.6　条件模式 326

13.7　FLEX的命令选项 327

13.8　举例 328

习题十三 329

14.1 YACC简介 330

第十四章 语法分析器生成工具YACC 330

14.2 YACC源文件的格式 334

14.2.1　单词和非终结符 334

14.2.2　定义部分 335

14.2.3　语法规则部分 342

14.3　语义定义 343

14.3.1　单词语义值的计算 343

14.3.2　非终结符语义值的计算 344

14.3.3　在规则中部的语义动作 346

14.4 归约-归约冲突和上下文相关性的处理 348

14.5　出错处理和恢复 350

14.6　输出分析器的调试 352

14.7 YACC和LEX的接口 353

14.8　BYACC的命令选项 354

14.9　举例 355

习题十四 361

习题解答 363

参考文献 440