目 录
译者序
前言
第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 进销存管理系统