自己动手构建编程语言:如何设计编译器、解释器和DSL

Contents　目　录
前言
**部分　编程语言导论
第1章　为什么要构建另一种编程
　　　　语言2
1.1　编写自己的编程语言的动机2
1.1.1　编程语言实现的类型3
1.1.2　组织字节码语言实现4
1.1.3　示例中使用的语言4
1.2　编程语言与库的差别5
1.3　适用于其他软件工程任务6
1.4　建立语言需求6
1.5　案例研究：Unicon语言的创建需求8
1.5.1　Unicon需求#1—保留人们
　　　对Icon的喜爱8
1.5.2　Unicon需求#2—支持大型
　　　大数据项目9
1.5.3　Unicon需求#3—现代应用
　　　程序的高级输入/输出9
1.5.4　Unicon需求#4—提供可实
　　　现的通用系统接口9
1.6　本章小结10
1.7　思考题10
第2章　编程语言设计11
2.1　确定要编程语言提供的单词和
　　 标点符号的类型11
2.2　指定控制流13
2.3　决定支持哪种数据14
2.3.1　原子类型14
2.3.2　复合类型15
2.3.3　领域特定类型16
2.4　整体程序结构16
2.5　完成Jzero语言的定义17
2.6　案例研究：设计Unicon中的图形
　　 功能18
2.6.1　2D图形语言支持18
2.6.2　添加3D图形支持20
2.7　本章小结21
2.8　思考题21
第3章　扫描源代码22
3.1　技术需求22
3.2　词素、词类和标记23
3.3　正则表达式24
3.3.1　正则表达式规则24
3.3.2　正则表达式示例25
3.4　使用UFlex和JFlex26
3.4.1　头部分26
3.4.2　正则表达式部分27
3.4.3　编写一个简单的源代码扫
　　　描器27
3.4.4　运行扫描器30
3.4.5　标记和词法属性31
3.4.6　扩展示例以构造标记31
3.5　为Jzero编写扫描器34
3.5.1　Jzero Flex规范34
3.5.2　Unicon Jzero代码36
3.5.3　Java Jzero代码39
3.5.4　运行Jzero扫描器42
3.6　正则表达式并不总是足够的44
3.7　本章小结46
3.8　思考题47
第4章　解析48
4.1　技术需求48
4.2　语法分析49
4.3　理解上下文无关文法49
4.3.1　编写上下文无关文法规则50
4.3.2　编写编程构造规则51
4.4　使用iyacc和BYACC/J53
4.4.1　声明头部分中的符号53
4.4.2　组合yacc上下文无关文法
　　　部分54
4.4.3　理解yacc解析器55
4.4.4　修复yacc解析器中的冲突56
4.4.5　语法错误修复57
4.4.6　组合简单示例57
4.5　为Jzero编写解析器62
4.5.1　Jzero lex规范62
4.5.2　Jzero yacc规范62
4.5.3　Unicon Jzero代码66
4.5.4　Java Jzero解析器代码68
4.5.5　运行Jzero解析器69
4.6　改进语法错误消息70
4.6.1　向Unicon语法错误消息添加
　　　详细信息71
4.6.2　向Java语法错误消息添加详
　　　细信息71
4.6.3　使用Merr生成更好的语法错
　　　误消息72
4.7　本章小结72
4.8　思考题73
第5章　语法树74
5.1　技术需求74
5.2　GNU make的使用75
5.3　树77
5.3.1　定义语法树类型78
5.3.2　解析树与语法树79
5.4　从终结符创建叶子81
5.4.1　用叶子包装标记81
5.4.2　使用YACC的值栈82
5.4.3　为解析器的值栈包装叶子83
5.4.4　确定需要哪些叶子84
5.5　从产生式规则构建内部节点85
5.5.1　访问值栈上的树节点85
5.5.2　使用树节点工厂方法86
5.6　为Jzero语言形成语法树88
5.7　调试并测试语法树93
5.7.1　避免常见的语法树错误94
5.7.2　以文本格式输出语法树95
5.7.3　使用dot输出语法树96
5.8　本章小结101
5.9　思考题101
第二部分　语法树遍历
第6章　符号表104
6.1　技术需求104
6.2　建立符号表基础105
6.2.1　声明和作用域105
6.2.2　赋值和取消引用变量106
6.2.3　选择正确的树遍历106
6.3　为每个作用域创建和填充符号表107
6.3.1　向语法树添加语义属性108
6.3.2　定义符号表和符号表条目的类109
6.3.3　创建符号表110
6.3.4　填充符号表112
6.3.5　综合isConst属性114
6.4　检查未声明的变量115
6.4.1　识别方法体115
6.4.2　发现方法体中变量的使用116
6.5　查找重新声明的变量118
6.5.1　将符号插入符号表118
6.5.2　报告语义错误119
6.6　在Unicon中处理包和类作用域119
6.6.1　名称修饰120
6.6.2　为成员变量引用插入self120
6.6.3　在方法调用中插入self作为
　　　**个参数121
6.7　测试和调试符号表122
6.8　本章小结123
6.9　思考题124
第7章　基本类型检查125
7.1　技术需求125
7.2　编译器中的类型表示125
7.2.1　定义表示类型的基类126
7.2.2　子类化复杂类型的基类127
7.3　将类型信息分配给声明的变量129
7.3.1　从保留字合成类型130
7.3.2　将类型继承到变量列表中131
7.4　确定每个语法树节点的类型132
7.4.1　确定叶子的类型133
7.4.2　计算和检查内部节点的类型135
7.5　Unicon中的运行时类型检查和
　　　类型推断139
7.6　本章小结140
7.7　思考题140
第8章　检查数组、方法调用和结
　　　　构访问的类型142
8.1　技术需求142
8.2　检查数组类型的操作142
8.2.1　处理数组变量声明143
8.2.2　在数组创建期间检查类型143
8.2.3　在数组访问期间检查类型145
8.3　检查方法调用146
8.3.1　计算参数和返回类型信息147
8.3.2　检查每个方法调用站点的类型149
8.3.3　检查返回语句中的类型152
8.4　检查结构化类型访问153
8.4.1　处理实例变量声明154
8.4.2　在创建实例时检查类型154
8.4.3　在实例访问时检查类型157
8.5　本章小结159
8.6　思考题160
第9章　中间代码生成161
9.1　技术需求161
9.2　准备生成代码161
9.2.1　为什么要生成中间代码162
9.2.2　了解生成程序的存储区域162
9.2.3　为中间代码引入数据类型163
9.2.4　将中间代码属性添加到树中165
9.2.5　生成标签和临时变量165
9.3　中间代码指令集168
9.3.1　指令168
9.3.2　声明168
9.4　用标签为控制流注释语法树 169
9.5　为表达式生成代码171
9.6　为控制流生成代码173
9.6.1　为条件表达式生成标签目标174
9.6.2　生成循环代码177
9.6.3　为方法调用生成中间代码178
9.6.4　检查生成的中间代码179
9.7　本章小结180
第10章　IDE中的语法着色182
10.1　下载本章中使用的示例IDE183
10.2　将编译器集成到程序员的编辑
　　　器中184
10.2.1　从IDE中分析源代码185
10.2.2　将编译器输出发送到IDE185
10.3　避免在每次更改时重新解析
　　　整个文件186
10.4　使用词法信息为标记着色189
10.4.1　扩展EditableTextList组件以
　　　支持颜色189
10.4.2　在绘制单个标记时对其
　　　　进行着色190
10.5　使用解析结果突出显示错误191
10.6　添加Java支持192
10.7　本章小结194
第三部分　代码生成与运行时系统
第11章　字节码解释器196
11.1　技术需求196
11.2　什么是字节码196
11.3　比较字节码和中间码198
11.4　为Jzero构建字节码指令集200
11.4.1　定义Jzero字节码文件格式200
11.4.2　了解栈机操作的基础知识202
11.5　实现字节码解释器203
11.5.1　将字节码加载到内存中203
11.5.2　初始化解释器状态205
11.5.3　获取指令并推进指令指针206
11.5.4　指令解码207
11.5.5　执行指令208
11.5.6　启动Jzero解释器211
11.6　编写Jzero运行时系统212
11.7　运行Jzero程序213
11.8　检查Unicon字节码解释器iconx213
11.8.1　了解目标导向的字节码214
11.8.2　在运行时保留类型信息214
11.8.3　获取、解码和执行指令214
11.8.4　制作运行时系统的其余部分215
11.9　本章小结215
11.10　思考题215
第12章　生成字节码217
12.1　技术需求217
12.2　转换中间代码为Jzero字节码217
12.2.1　为字节码指令添加类218
12.2.2　将中间代码地址映射到
　　　　字节码地址219
12.2.3　实现字节码生成器方法220
12.2.4　为简单表达式生成字节码221
12.2.5　生成指针操作的代码223
12.2.6　为分支和条件分支生成
　　　　字节码224
12.2.7　为方法调用和返回生成代码225
12.2.8　处理中间代码中的标签和
　　　　其他伪指令226
12.3　比较字节码汇编程序与二进制
　　　格式227
12.3.1　以汇编格式输出字节码227
12.3.2　以二进制格式输出字节码229
12.4　链接、加载并包括运行时系统230
12.5　Unicon示例：icont中的字节码
　　　生成230
12.6　本章小结232
12.7　思考题232
第13章　生成本机代码233
13.1　技术需求233
13.2　决定是否生成本机代码233
13.3　x64指令集234
13.3.1　为x64指令添加类234
13.3.2　将内存区域映射到基于x64
　　　　寄存器的地址模式235
13.4　使用寄存器235
13.4.1　从空策略开始236
13.4.2　分配寄存器以加速本地
　　　　区域237
13.5　将中间代码转换为x64代码239
13.5.1　将中间代码地址映射到x64
　　　　内存地址240
13.5.2　实现x64代码生成器方法243
13.5.3　生成简单表达式的x64代码244
13.5.4　生成指针操作的代码245
13.5.5　为分支和条件分支生成
　　　　本机代码246
13.5.6　为方法调用和返回生成代码247
13.5.7　处理标签和伪指令249
13.6　生成x64输出250
13.6.1　以汇编语言格式编写x64
　　　　代码251
13.6.2　从本机汇编程序到目标文件251
13.6.3　链接、加载并包括运行时
　　　　系统252
13.7　本章小结253
13.8　思考题253
第14章　运算符和内置函数的实现254
14.1　实现运算符254
14.1.1　运算符是否需要硬件支持255
14.1.2　在中间代码生成中添加字符
　　　　串连接255
14.1.3　为字节码解释器添加字符
　　　　串连接257
14.1.4　将字符串连接添加到本机
　　　　运行时系统259
14.2　编写内置函数260
14.2.1　向字节码解释器添加内置
　　　　函数260
14.2.2　编写用于本机代码实现的
　　　　内置函数261
14.3　集成内置组件与控制结构262
14.4　为Unicon开发运算符和函数262
14.4.1　在Unicon中编写运算符263
14.4.2　开发Unicon的内置函数265
14.5　本章小结266
14.6　思考题266
第15章　域控制结构267
15.1　了解何时需要新的控制结构267
15.1.1　定义控制结构268
15.1.2　减少过多的冗余参数268
15.2　Icon和Unicon中的字符串扫描269
15.2.1　扫描环境及其基本操作270
15.2.2　通过控制结构消除过多参数271
15.3　Unicon中的渲染区域271
15.3.1　从显示列表渲染3D图形272
15.3.2　使用内置函数指定渲染区域272
15.3.3　使用嵌套渲染区域更改
　　　　图形细节层次273
15.3.4　创建渲染区域控制结构274
15.4　本章小结278
15.5　思考题278
第16章　垃圾收集279
16.1　认识垃圾收集的重要性279
16.2　对象的引用计数281
16.2.1　将引用计数添加到Jzero281
16.2.2　生成堆分配代码281
16.2.3　为赋值运算符修改生成的
　　　 代码283
16.2.4　引用计数的缺点和局限性283
16.3　标记实时数据并清理剩余数据284
16.3.1　组织堆内存区域285
16.3.2　遍历基本变量以标记实时
　　　 数据286
16.3.3　回收实时内存并将其放入
　　　 连续内存块290
16.4　本章小结293
16.5　思考题293
第17章　结语294
17.1　反思从编写这本书中学到的
　　　 东西294
17.2　决定何去何从295
17.2.1　学习编程语言设计295
17.2.2　学习如何实现解释器和字
　　　　节码机器296
17.2.3　获取代码优化方面的专业
　　　　知识297
17.2.4　监视和调试程序执行297
17.2.5　设计和实现IDE和GUI
　　　　构建器298
17.3　延伸阅读的参考资料298
17.4　本章小结301
第四部分　附录
附录A　Unicon基础304
附录B　部分章节要点324