目      录
译者序
前言
第1章   概论 1
1.1   为什么要用编译器 2
1.2   与编译器相关的程序 3
1.3   翻译步骤 5
1.4   编译器中的主要数据结构 8
1.5   编译器结构中的其他问题 10
1.6   自举与移植 12
1.7   TINY样本语言与编译器 14
1.7.1   TINY语言 15
1.7.2   TINY编译器 15
1.7.3   TM机 17
1.8   C-Minus：编译器项目的一种语言 18
练习 19
注意与参考 20
第2章   词法分析 21
2.1   扫描处理 21
2.2   正则表达式 23
2.2.1   正则表达式的定义 23
2.2.2   正则表达式的扩展 27
2.2.3   程序设计语言记号的正则表达式 29
2.3   有穷自动机 32
2.3.1   确定性有穷自动机的定义 32
2.3.2   先行、回溯和非确定性自动机 36
2.3.3   用代码实现有穷自动机 41
2.4   从正则表达式到DFA 45
2.4.1   从正则表达式到NFA 45
2.4.2   从NFA到DFA 48
2.4.3   利用子集构造模拟NFA 50
2.4.4   将DFA中的状态数最小化 51
2.5   TINY扫描程序的实现 52
2.5.1   为样本语言TINY实现一个扫描
程序 53
2.5.2   保留字与标识符 56
2.5.3   为标识符分配空间 57
2.6   利用Lex 自动生成扫描程序 57
2.6.1   正则表达式的Lex 约定 58
2.6.2   Lex输入文件的格式 59
2.6.3   使用Lex的TINY扫描程序 64
练习 65
编程练习 67
注意与参考 67
第3章   上下文无关文法及分析 69
3.1   分析过程 69
3.2   上下文无关文法 70
3.2.1   与正则表达式比较 70
3.2.2   上下文无关文法规则的说明 71
3.2.3   推导及由文法定义的语言 72
3.3   分析树与抽象语法树 77
3.3.1   分析树 77
3.3.2   抽象语法树 79
3.4   二义性 83
3.4.1   二义性文法 83
3.4.2   优先权和结合性 85
3.4.3   悬挂else问题 87
3.4.4   无关紧要的二义性 89
3.5   扩展的表示法：EBNF和语法图 89
3.5.1   EBNF表示法 89
3.5.2   语法图 91
3.6   上下文无关语言的形式特性 93
3.6.1   上下文无关语言的形式定义 93
3.6.2   文法规则和等式 94
3.6.3   乔姆斯基层次和作为上下文无关
规则的语法局限 95
3.7   TINY语言的语法 97
3.7.1   TINY的上下文无关文法 97
3.7.2   TINY编译器的语法树结构 98
练习 101
注意与参考 104
第4章   自顶向下的分析 105
4.1   使用递归下降分析算法进行自顶向下
的分析 105
4.1.1   递归下降分析的基本方法 105
4.1.2   重复和选择：使用EBNF 107
4.1.3   其他决定问题 112
4.2   LL(1)分析 113
4.2.1   LL(1)分析的基本方法 113
4.2.2   LL(1)分析与算法 114
4.2.3   消除左递归和提取左因子 117
4.2.4   在LL(1)分析中构造语法树 124
4.3   First集合和Follow集合 125
4.3.1   First 集合 125
4.3.2   Follow 集合 130
4.3.3   构造LL(1)分析表 134
4.3.4   再向前：LL(k)分析程序 135
4.4   TINY语言的递归下降分析程序 136
4.5   自顶向下分析程序中的错误校正 137
4.5.1   在递归下降分析程序中的错误
校正 138
4.5.2   在LL(1)分析程序中的错误校正 140
4.5.3   在TINY分析程序中的错误校正 141
练习 143
编程练习 146
注意与参考 148
第5章   自底向上的分析 150
5.1   自底向上分析概览 151
5.2   LR(0)项的有穷自动机与LR(0)分析 153
5.2.1   LR(0)项 153
5.2.2   项目的有穷自动机 154
5.2.3   LR(0)分析算法 157
5.3   SLR(1)分析 160
5.3.1   SLR(1)分析算法 160
5.3.2   用于分析冲突的消除二义性
规则 163
5.3.3   SLR(1)分析能力的局限性 164
5.3.4   SLR(k)文法 165
5.4   一般的LR(1)和LALR(1)分析 166
5.4.1   LR(1)项的有穷自动机 166
5.4.2   LR(1)分析算法 169
5.4.3   LALR(1)分析 171
5.5   Yacc：一个LALR(1)分析程序的
生成器 173
5.5.1   Yacc基础 173
5.5.2   Yacc选项 176
5.5.3   分析冲突与消除二义性的规则 180
5.5.4   描述Yacc分析程序的执行 183
5.5.5   Yacc中的任意值类型 184
5.5.6   Yacc中嵌入的动作 185
5.6   使用Yacc生成TINY分析程序 186
5.7   自底向上分析程序中的错误校正 188
5.7.1   自底向上分析中的错误检测 188
5.7.2   应急方式错误校正 188
5.7.3   Yacc中的错误校正 189
5.7.4   TINY中的错误校正 192
练习 192
编程练习 195
注意与参考 197
第6章   语义分析 198
6.1   属性和属性文法 199
6.1.1   属性文法 200
6.1.2   属性文法的简化和扩充 206
6.2   属性计算算法 207
6.2.1   相关图和赋值顺序 208
6.2.2   合成和继承属性 212
6.2.3   作为参数和返回值的属性 219
6.2.4   使用扩展数据结构存储属性值 221
6.2.5   语法分析时属性的计算 223
6.2.6   语法中属性计算的相关性 226
6.3   符号表 227
6.3.1   符号表的结构 228
6.3.2   说明 230
6.3.3   作用域规则和块结构 232
6.3.4   同层说明的相互作用 236
6.3.5   使用符号表的属性文法的一个
扩充例子 237
6.4   数据类型和类型检查 241
6.4.1   类型表达式和类型构造器 242
6.4.2   类型名、类型说明和递归类型 246
6.4.3   类型等价 248
6.4.4   类型推论和类型检查 253
6.4.5   类型检查的其他主题 255
6.5   TINY语言的语义分析 257
6.5.1   TINY的符号表 258
6.5.2   TINY语义分析程序 259
练习 260
编程练习 264
注意与参考 264
第7章   运行时环境 266
7.1   程序执行时的存储器组织 266
7.2   完全静态运行时环境 269
7.3   基于栈的运行时环境 271
7.3.1   没有局部过程的基于栈的环境 271
7.3.2  带有局部过程的基于栈的环境 281
7.3.3   带有过程参数的基于栈的环境 284
7.4   动态存储器 286
7.4.1   完全动态运行时环境 286
7.4.2   面向对象的语言中的动态存储器 287
7.4.3   堆管理 289
7.4.4   堆的自动管理 292
7.5   参数传递机制 292
7.5.1   值传递 293
7.5.2   引用传递 294
7.5.3   值结果传递 295
7.5.4   名字传递 295
7.6   TINY语言的运行时环境 296
练习 297
编程练习 303
注意与参考 304
第8章   代码生成 305
8.1   中间代码和用于代码生成的数据
结构 305
8.1.1   三地址码 306
8.1.2   用于实现三地址码的数据结构 308
8.1.3   P-代码 310
8.2   基本的代码生成技术 312
8.2.1   作为合成属性的中间代码或目标
代码 312
8.2.2   实际的代码生成 314
8.2.3   从中间代码生成目标代码 317
8.3   数据结构引用的代码生成 319
8.3.1   地址计算 319
8.3.2   数组引用 320
8.3.3   栈记录结构和指针引用 325
8.4   控制语句和逻辑表达式的代码生成 328
8.4.1   if 和while 语句的代码生成 328
8.4.2   标号的生成和回填 330
8.4.3   逻辑表达式的代码生成 330
8.4.4   if 和while 语句的代码生成过程
样例 331
8.5   过程和函数调用的代码生成 334
8.5.1   过程和函数的中间代码 334
8.5.2   函数定义和调用的代码生成过程 336
8.6   商用编译器中的代码生成：两个案
例研究 339
8.6.1   对于80×86的Borland 3.0版C编
译器 339
8.6.2   Sun SparcStation的Sun 2.0 C编
译器 343
8.7   TM：简单的目标机器 346
8.7.1   Tiny Machine的基本结构 347
8.7.2   TM模拟器 349
8.8   TINY语言的代码生成器 351
8.8.1   TINY代码生成器的TM接口 351
8.8.2   TINY代码生成器 352
8.8.3   用TINY编译器产生和使用TM
代码文件 354
8.8.4   TINY编译器生成的TM代码文
件示例 355
8.9   代码优化技术考察 357
8.9.1   代码优化的主要来源 358
8.9.2   优化分类 360
8.9.3   优化的数据结构和实现技术 362
8.10   TINY代码生成器的简单优化 366
8.10.1   将临时变量放入寄存器 366
8.10.2   在寄存器中保存变量 367
8.10.3   优化测试表达式 367
练习 368
编程练习 371
注意与参考 372
附录A   编译器设计方案 373
附录B   小型编译器列表 381
附录C   Tiny Machine模拟器列表 417

目录

第一部分  基础篇
 
001  第一个C程序 
002  运行多个源文件 
003  求整数之积 
004  比较实数大小 
005  字符的输出 
006  显示变量所占字节数 
007  自增/自减运算 
008  数列求和 
009  乘法口诀表 
010  猜数字游戏 
011  模拟ATM（自动柜员机）界面 
012  用一维数组统计学生成绩 
013  用二维数组实现矩阵转置 
014  求解二维数组的最大/最小元素 
015  利用数组求前n个质数 
016  编制万年历 
017  对数组元素排序 
018  任意进制数的转换 
019  判断回文数 
020  求数组前n元素之和 
021  求解钢材切割的最佳订单 
022  通过指针比较整数大小 
023  指向数组的指针 
024  寻找指定元素的指针 
025  寻找相同元素的指针 
026  阿拉伯数字转换为罗马数字 
027  字符替换 
028  从键盘读入实数 
029  字符行排版 
030  字符排列 
031  判断字符串是否回文 
032  通讯录的输入输出 
033  扑克牌的结构表示
034  用“结构”统计学生成绩 
035  报数游戏 
036  模拟社会关系 
037  统计文件的字符数 
038  同时显示两个文件的内容 
039  简单的文本编辑器 
040  文件的字数统计程序 
041  学生成绩管理程序 
 
第二部分  数据结构篇
 
042  插入排序 
043  希尔排序 
044  冒泡排序 
045  快速排序 
046  选择排序 
047  堆排序 
048  归并排序 
049  基数排序 
050  二叉搜索树操作 
051  二项式系数递归 
052  背包问题 
053  顺序表插入和删除 
054  链表操作（1） 
055  链表操作（2） 
056  单链表就地逆置 
057  运动会分数统计 
058  双链表 
059  约瑟夫环 
060  记录个人资料 
061  二叉树遍利 
062  浮点数转换为字符串 
063  汉诺塔问题 
064  哈夫曼编码 
065  图的深度优先遍利 
066  图的广度优先遍利
067  求解最优交通路径 
068  八皇后问题
069  骑士巡游 
070  用栈设置密码 
071  魔王语言翻译 
072  火车车厢重排 
073  队列实例 
074  K阶斐波那契序列 
 
第三部分  数值计算与趣味数学篇
 
075  绘制余弦曲线和直线的迭加
076  计算高次方数的尾数 
077  打鱼还是晒网 
078  怎样存钱以获取最大利息 
079  阿姆斯特朗数 
080  亲密数 
081  自守数 
082  具有abcd=(ab+cd)2性质的数 
083  验证歌德巴赫猜想
084  素数幻方 
085  百钱百鸡问题 
086  爱因斯坦的数学题 
087  三色球问题
088  马克思手稿中的数学题 
089  配对新郎和新娘 
090  约瑟夫问题
091  邮票组合 
092  分糖果 
093  波瓦松的分酒趣题 
094  求π的近似值 
095  奇数平方的有趣性质
096  角谷猜想 
097  四方定理 
098  卡布列克常数 
099  尼科彻斯定理 
100  扑克牌自动发牌 
101  常胜将军 
102  搬山游戏
103  兔子产子（菲波那契数列） 
104  数字移动 
105  多项式乘法 
106  产生随机数 
107  堆栈四则运算 
108  递归整数四则运算 
109  复平面作图 
110  绘制彩色抛物线 
111  绘制正态分布曲线 
112  求解非线性方程 
113  实矩阵乘法运算
114  求解线性方程 
115  n阶方阵求逆 
116  复矩阵乘法 
117  求定积分 
118  求满足特异条件的数列 
119  超长正整数的加法 
 
第四部分  图形篇
 
120  绘制直线 
121  绘制圆 
122  绘制圆弧 
123  绘制椭圆
124  设置背景色和前景色
125  设置线条类型 
126  设置填充类型和填充颜色 
127  图形文本的输出 
128  金刚石图案
129  飘带图案 
130  圆环图案 
131  肾形图案 
132  心脏形图案 
133  渔网图案 
134  沙丘图案
135  设置图形方式下的文本类型 
136  绘制正多边形 
137  正六边形螺旋图案 
138  正方形螺旋拼块图案
139  图形法绘制圆 
140  递归法绘制三角形图案 
141  图形法绘制椭圆 
142  抛物样条曲线 
143  Mandelbrot分形图案
144  绘制布朗运动曲线 
145  艺术清屏 
146  矩形区域的颜色填充 
147  VGA256色模式编程 
148  绘制蓝天图案 
149  屏幕检测程序 
150  运动的小车动画 
151  动态显示位图 
152  利用图形页实现动画
153  图形时钟 
154  音乐动画 
 
第五部分  系统篇
 
155  读取DOS系统中的国家信息 
156  修改环境变量 
157  显示系统文件表 
158  显示目录内容 
159  读取磁盘文件 
160  删除目录树 
161  定义文本模式 
162  设计立体窗口 
163  彩色弹出菜单 
164  读取CMOS信息 
165  获取BIOS设备列表 
166  锁住硬盘 
167  备份/恢复硬盘分区表 
168  设计口令程序 
169  程序自我保护
 
第六部分  常见试题解答篇
 
170  水果拼盘 
171  小孩吃梨 
172  删除字符串中的特定字符 
173  求解符号方程 
174  计算标准差 
175  求取符合特定要求的素数 
176  统计符合特定条件的数 
177  字符串倒置 
178  部分排序 
179  产品销售记录处理 
180  特定要求的字符编码 
181  求解三角方程 
182  新完全平方数 
183  三重回文数 
184  奇数方差 
185  统计选票 
186  同时整除 
187  字符左右排序 
188  符号算式求解 
189  数字移位 
190  统计最高成绩 
191  比较字符串长度 
192  合并整数 
193  矩阵逆置
194  删除指定的字符
195  括号匹配 
196  字符串逆置 
197  SIX/NINE问题 
198  单词个数统计 
199  方差运算 
200  级数运算 
201  输出素数 
202  素数题 
203  序列排序 
204  整数各位数字排序 
205  字符串字母移位 
206  Fibonacc数列 
 
第七部分  游戏篇
 
207  商人过河游戏 
208  吃数游戏 
209  解救人质游戏 
210  打字训练游戏 
211  双人竞走游戏 
212  迷宫探险游戏 
213  迷你撞球游戏
214  模拟扫雷游戏 
215  推箱子游戏 
216  五子棋游戏 
 
第八部分  综合实例篇
 
217  综合CAD系统 
218  功能强大的文本编辑器
219  图书管理系统
220  进销存管理系统
 

本书是Brian W. Kernighan和Rob Pike合著的最新力作。本书从排错、测试、性能、可移植性、设计、界面、风格和记法等方面，讨论了程序设计中实际的、又是非常深刻和具有广泛意义的思想、技术和方法，它的翻译出版将填补国内目前这方面书籍的空白。本书值得每个梦想并努力使自己成为优秀程序员的人参考，值得每个计算机专业的学生和计算机工作者阅读，也可作为程序设计高级课程的教材或参考书。

目      录

译者序

前言

第1章   风格 1

1.1   名字 2

1.2   表达式和语句 4

1.3   一致性和习惯用法 8

1.4   函数宏 14

1.5   神秘的数 15

1.6   注释 18

1.7   为何对此费心 22

第2章   算法与数据结构 23

2.1   检索 23

2.2   排序 25

2.3   库 27

2.4   一个Java快速排序 29

2.5   大O记法 31

2.6   可增长数组 33

2.7   表 35

2.8   树 39

2.9   散列表 43

2.10   小结 46

第3章   设计与实现 48

3.1   马尔可夫链算法 48

3.2   数据结构的选择 50

3.3   在C中构造数据结构 51

3.4   生成输出 54

3.5   Java 56

3.6   C++ 59

3.7   Awk和Perl 61

3.8   性能 63

3.9   经验教训 64

第4章   界面 67

4.1   逗号分隔的值 67

4.2   一个原型库 69

4.3   为别人用的库 72

4.4   C++实现 79

4.5   界面原则 82

4.6   资源管理 84

4.7   终止、重试或失败 86

4.8   用户界面 90

第5章   排错 93

5.1   排错系统 94

5.2   好线索，简单错误 95

5.3   无线索，难办的错误 98

5.4   最后的手段 101

5.5   不可重现的错误 103

5.6   排错工具 105

5.7   其他人的程序错误 107

5.8   小结 108

第6章   测试 110

6.1   在编码过程中测试 110

6.2   系统化测试 114

6.3   测试自动化 118

6.4   测试台 120

6.5   应力测试 123

6.6   测试秘诀 125

6.7   谁来测试 126

6.8   测试马尔可夫程序 127

6.9   小结 129

第7章   性能 130

7.1   瓶颈 130

7.2   计时和轮廓 135

7.3   加速策略 138

7.4   代码调整 140

7.5   空间效率 144

7.6   估计 145

7.7   小结 147

第8章   可移植性 149

8.1   语言 149

8.2   头文件和库 154

8.3   程序组织 156

8.4   隔离 159

8.5   数据交换 160

8.6   字节序 161

8.7   可移植性和升级 164

8.8   国际化 165

8.9   小结 167

第9章   记法 169

9.1   数据格式 169

9.2   正则表达式 174

9.3   可编程工具 180

9.4   解释器、编译器和虚拟机 182

9.5   写程序的程序 186

9.6   用宏生成代码 189

9.7   运行中编译 190

后记 195

附录：规则汇编 197

索引 200