概述
本书描述了将编程语言转换成可执行代码的技巧、数据结构以及运算法则。现代编译器是由很多阶段组成的，每一阶段对不同的语言进行操作。依据这样的结构，本的每章中都包含有一个相应的阶段。
为了说明编译语言的过程,本书将以一个简单但很重要的Java子集Mini Java为例。希望读者自己能够完成每一章中相应的阶段,那么在学习完第一部分后,就实现一个编译器。Mini Java很容易进行扩展以支持类扩展以及高级指令函数，第二部分中的习题就做了这样的工作，第二部分的其他章节还介绍了程序优化的高级术。附录A介绍了Mini Java语言。
编译器模块之间的接口几乎和模块内部的运算法则同等重要。为了具体描述这些接口，我们将把它们用真正的程序语言编写出来。本书使用了一种简单的、面向对象Java语言,Java是稳定的,它不能绕过类型系统从而违反抽象的原则； Java具有垃圾回收机制,在很大程度上简化了动态空间的处理。所有的这些属性对于实编译器都是很有好处的(几乎适用于编写任何软件)。
本书不是Java语言的教科书。不会使用Java语言的读者在使用这本书的同时,应该学会使用Java,并选择一本Java语言的书籍作为参考书。
Java是一种非常实用语言,它包含了一些简单的概念，但是这些对于很好地掌握了其他语言的学生来说并不算难。
1.1 模块及接口
任何大型的软件系统，只要设计者关注模块和接口的设计，那么这个系统就会变得容易理解和实现。
图1.1说明了一个典型编译器的各个阶段。每个阶段都由多个软件块实现。
将编译器分解成很多这样的阶段，是为了重复使用它们。例如，当改变计算机时，可以改变格式布局和指令选择模块。因为被编译的源语言改变时，只需改变翻译模就可以了。编译器直接与抽象语法接口的、面向语言的语法编辑器相连。
通过迭代法以得到正确的抽象是非常重要的一点。
然而，有些学生想在一个学期内实现一个编译器是不现实的。因此，我们在书中列出了工程框架，它的模块和接口是经过深思熟虑的，而且尽可能使之完美。
一些接口，比如抽象语法、IR树和汇编，都是数据结构的形式：例如，语法分析动作阶段设置了抽象语法数据结构，并将它放到了语义分析阶段中。
其他的接口都是象的数据类型：翻译接口是一个语义分析阶段能够调用的函数集；标记接口采用函数的形式，分析器调用它以得到输人程序的下一个标记。
阶段描述
| 2 | 词法分析 | 划分源文件为单独的单词或关键字 |
| 3 | 语法分析 | 分析程序的短语结构 |
| 4 | 语义动作 | 根据每个短语建立抽象语法树 |
| 5 | 语义分析 | 确定每个短语的含义、使变量和其声明关联，检查表达式的类型，翻译每个短语 |
| 6 | 格式布局 | 把变量、方法参数以该系统的操作方式存放，比如堆栈 |
| 7 | 翻译 | 生成中间表示树(In tem mediate Representation tree：IR tree),不依赖于任何确定的程序语言和目标机器的结构 |
| 8 | 规范化 | 从表达式中去除不明确的部分，整理条件语句的分支，以方便下一阶段的处理 |
| 9 | 指令选择 | 根据目标机器的指令体系，对IR树的节点进行划分 |
| 10 | 控制流分析 | 分析指令的顺序，画出控制流图，该图表述了程序执行时所有可能的流转, |
| 10 | 数据流分析 | 通过程序变量得到数据流的信息。例如，生存期分析将计算出每一个变量的生存区域 |
| 11 | 寄存器分配 | 为程序的变量和暂时的数据选择寄存器；各变量不能在同一时间使用同一个寄存器 |
| 12 | 代码生成 | 用寄存器代替在机器指令中出现的暂时变量名 |
这种模块化设计在编译器中是很典型的。
但是一些编译器把语法分析、语义分析、翻译以及规范化都放到了一个阶段中；
还有一些编译器把指令选择安排到最后进行，并且把它与代码生成结合到了一起。
简单的编译器将忽略控制流分析、数据流分析以及寄存器分配。
我们在本书中设计的编译器将尽可能简单。为了简化设计，编译器的结构将附带更多结构优化的语义，而不是抵触现存的接口
1.2 工具和软件
在现代编译器中，最有用的两条抽象规则为：便于语法分析的上下文无关文法和便于词法分析的正则表达式。
为了更好地利用这些抽象规则,借助一些特殊的工具是要的,例如Yacc(将语法转换成语法分析器),Lex(将具体说明转换成词法分析器) 。Java可以使用这些工具，本书中的编译器将用到它们。
本书中的程序可以用任何的Java编译器编译。语法分析生成器JavaCC和SableCC在Internet上是免费的：在以下网址可以查询到相关信息：
http//uk.cambridge.org/resources/052182060X(北美以外地区)
http//us.cambridge.org/titles/052182060X.html(北美地区)
Mini Java编译器中一些模块的源代码、一些编程习题的框架源代码和支持代码、Mini Java编程的例子以及其他相关的文件都可以从该网址中找到。
当提及到该地址中具体的某个子目录时,本书中的程序设计习题将把相应的目录设置为$MINI JAVA/。
1.3 树型语言的数据结构
编译器中使用的一些重要数据结构是进行编译程序的中间表示。这些中间表示都是用树和节点类型来表示的，它们都有不同的分工。
图1.1所示的阶段接口中就有很多这样的树。
树的中间表示可以用文法来描述，就像编程语言一样。
为了介绍这一概念，我们使用相应的语句和表达式编写了一个简单的程序，但是没有循环和if语句(称为直线程序语言)。
这种语言的语法规则如下所示：
执行如下程序：
a := 5+3; b := (print (a, a-1 ), 10*a); print(b)
输出
8 7
80
这段程序在编译器中是怎样被编译的呢?
一种表示方法就是源代码，即程序员所写的程序。
但程序很难被直接使用。
最方便的是树形数据结构,每条语句(Stm) 和表达式(Exp) 都对应一个节点。
图1.4是用树来表示的一个程序；节点都用语法1.3中的标记加以注明，每个节点的孩子数量等于相对应的语法右边的表达式数。
编码实现
我们可以创建代码，对应上述出现的信息
详情参见
语法规则
对每项语法规则，其左边的类都对应有一个构造函数。
对于这些语法规则，可以简单地把抽象的类扩展为具体的类。
构造函数的名字对应文法1.3括号中的部分。
每项语法规则都必须包含代表数据结构右边的部分。
例如,CompoundS tm在右边包含两条语句；
AssignStm包含一个标识符和一个表达式,等等。
在Java表示的数据结构中,它们变成了子类的域。
因此,CompoundStm有两个域(也叫做实例变量),分别是st ml和stm 2；AssignS tm包含域id和exp。
可以使用Binop类一它的子类分别是加、减、乘、除，它没有任何的子类需要域。
相应地,我们可以列举一些OpExp所包含的常量类型(Java中的整型) 。
编程风控
编程风格我们将遵循Java中表示树型数据结构的一些约定：
-
用文法来描述树。
-
用一个或多个抽象类来描述树，每个类对应语法中的一个符号。
-
每个抽象类可以用一个或多个子类来扩展，每个子类对应一个语法规则。
-
对于规则中右边的符号,相应的类中都有一个域(一些小的符号例外,诸如CompoundStm中的分号) 。
-
每个类中都有一个构造函数，可以初始化整个域。
-
数据结构在建立的时候就被初始化(由构造函数完成)，建立以后就不能被修改(直到最后被丢弃)，
Java 程序的模块规则
一个编译器可能是一个很大的程序，要尽量避免模块和接口的混乱.在用Java实现编译器的时候,我们使用了如下一些规则：
-
编译器的每个阶段或者每个模块都属于它自己的包。
-
“import ondemand”声明将不被使用。如果Java文件以如下方式开始：
import A.F.*;
import A.G.*;
import B.*;
import c.*;
那么对于表达式X.put(),需要从文件外部去寻找定义X时所使用的包。
- “单类型的import”声明是一个比较好的解决办法。如果模块以如下方式开始：
import A.F.W； import A.G.X；import B.Y； import C.z；
那么就能从A.G中找到X，而不必从文件外部寻找。
- java 是多线程系统。
我们希望能同时支持多个编译器线程,并能同时编译两个不同的程序，它们分别在不同的编译器线程中。
因此，静态变量应该尽量避免，除非它作为常量加以使用。同时不要让两个编译器线程更新相同的变量。
程序设计：直线程序解释器
为直线编程语言实现一个简单的程序分析器和解释器。
通过这一习题，大家可以熟悉环境(符号表指示了变量名和变量的信息)；熟悉抽象的语法(数据结构代表程序的短语结构)；熟悉树形数据结构的递归，这对于编译器中的很多部分都是很有用的；还可以熟悉无赋值语句的函数风格。
我们还提供了一个Java编程的热身习题。
对Java陌生而熟练使用其他语言的编程者可以完成这一习题，但是还需要其他资料的帮助。
解释过的程序已经分析为抽象语法，就像在程序1.5中描述的数据类型一样。
然而，我们并不希望在分析器方面费力，所以利用相应的数据构造函数编写了该程序：
ps: 这个代码感觉逻辑比较绕，不知道是否是语句不规范，本地写有报错。
没有副作用的解释器
标志语义和属性文法，它们都是描述程序语言的很好方法。
这也是编写编译器时很实用的技术，编译器也会在操作中指明编程语言可以做什么。
因此，在实现这些程序时，不要在非初始化时对任何变量或对象域赋新值。
对于局部变量,则可以使用初始化的形式进行声明(例如int i=j+3;)，而对于每个类，需要使用构造器进行相应的初始化(如程序1.5中的CompoundS tm构造器) 。
-
编写 Java 函数 int max args(St ms),对于给定语句的任意表达式,计算print语句中参数的最大值。例如,max args(prog) =2。
-
Java 函数 void interp(St ms) 解释了该语言编写的程序。为了使用函数编程风格，在声明局部变量的时候就要初始化它，而不要使用赋值语句。
用于检查每个Exp的函数都要使用instance of,由此决定这些表达式都属于哪个子类，然后将它们转换为相应的子类。
或者也可以在Exp和Stm中增加一些方法,以避免使用instance of。
在第一部分中，输出语句中可能包含有一些表达式，这些表达式又包含有其他的输出语句。
在第二部分中,将使用两个互相递归的函数interp Stm和interp Exp。
描述一个“表”并将标识符映射为赋值后的整型值,就像 id * int的列表。
package com.github.houbb.cp.learn.chap1.table;
/**
* @author binbin.hou
* @since 1.0.0
*/
public class Table {
private String id;
private int value;
private Table table;
public Table(String id, int value, Table table) {
this.id = id;
this.value = value;
this.table = table;
}
}
然后 interpStm 被声明为：
table interpStm(Stm s, table t)
假设链表中对c最初的操作优先于其他随后对c的操作。
因此， update函数很容易实现。相应的lookup函数为：
int lookup(Tablet，String key)
就是对链表的查询操作。
当然， 在面向对象的风格中， int lookup(String key) 应该是Table类中的一个操作
解释表达式比解释声明更为复杂。因为表达式返回整型值并有副作用。
我们希望模仿直线编程语言的赋值语句， 解释器本身没有任何副作用(然而， print语句是通过解释器的副作用完成的)解决的方法是将interp Exp声明为：
public class IntAndTable {
private int i;
private Table table;
public IntAndTable(int i, Table table) {
this.i = i;
this.table = table;
}
}
用表t和整型值i来解释表达式key，解释的结果就是新表t2。
当对有两个子表达式的表达式(例如Op Exp) 进行解释时， 解释第一个子表达式生成的表2可以继续用于解释第二个子表达式。
数据结构
课后习题都是关于二叉树的，很久不用都忘光了，需要重新学习。
拓展阅读
参考资料
《现代编译原理 java》
更多学习
更多实时资讯，前沿技术，生活趣事。尽在【老马啸西风】
交流社群：[交流群信息](https://mp.weixin.qq.com/s/rkSvXxiiLGjl3S-ZOZCr0Q)
