概述

本书描述了将编程语言转换成可执行代码的技巧、数据结构以及运算法则。现代编译器是由很多阶段组成的，每一阶段对不同的语言进行操作。依据这样的结构，本的每章中都包含有一个相应的阶段。

为了说明编译语言的过程,本书将以一个简单但很重要的Java子集Mini Java为例。希望读者自己能够完成每一章中相应的阶段,那么在学习完第一部分后,就实现一个编译器。Mini Java很容易进行扩展以支持类扩展以及高级指令函数，第二部分中的习题就做了这样的工作，第二部分的其他章节还介绍了程序优化的高级术。附录A介绍了Mini Java语言。

编译器模块之间的接口几乎和模块内部的运算法则同等重要。为了具体描述这些接口，我们将把它们用真正的程序语言编写出来。本书使用了一种简单的、面向对象Java语言,Java是稳定的,它不能绕过类型系统从而违反抽象的原则； Java具有垃圾回收机制,在很大程度上简化了动态空间的处理。所有的这些属性对于实编译器都是很有好处的(几乎适用于编写任何软件)。

本书不是Java语言的教科书。不会使用Java语言的读者在使用这本书的同时,应该学会使用Java,并选择一本Java语言的书籍作为参考书。

Java是一种非常实用语言,它包含了一些简单的概念，但是这些对于很好地掌握了其他语言的学生来说并不算难。

1.1 模块及接口

任何大型的软件系统，只要设计者关注模块和接口的设计，那么这个系统就会变得容易理解和实现。

图1.1说明了一个典型编译器的各个阶段。每个阶段都由多个软件块实现。

image

将编译器分解成很多这样的阶段，是为了重复使用它们。例如，当改变计算机时，可以改变格式布局和指令选择模块。因为被编译的源语言改变时，只需改变翻译模就可以了。编译器直接与抽象语法接口的、面向语言的语法编辑器相连。

通过迭代法以得到正确的抽象是非常重要的一点。

然而，有些学生想在一个学期内实现一个编译器是不现实的。因此，我们在书中列出了工程框架，它的模块和接口是经过深思熟虑的，而且尽可能使之完美。

一些接口，比如抽象语法、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语句(称为直线程序语言)。

这种语言的语法规则如下所示：

image

执行如下程序：

a := 5+3;   b := (print (a, a-1 ), 10*a); print(b)

输出

8 7
80

这段程序在编译器中是怎样被编译的呢?

一种表示方法就是源代码，即程序员所写的程序。

但程序很难被直接使用。

最方便的是树形数据结构,每条语句(Stm) 和表达式(Exp) 都对应一个节点。

图1.4是用树来表示的一个程序；节点都用语法1.3中的标记加以注明，每个节点的孩子数量等于相对应的语法右边的表达式数。

image

编码实现

我们可以创建代码，对应上述出现的信息

详情参见

语法规则

对每项语法规则，其左边的类都对应有一个构造函数。

对于这些语法规则，可以简单地把抽象的类扩展为具体的类。

构造函数的名字对应文法1.3括号中的部分。

每项语法规则都必须包含代表数据结构右边的部分。

例如,CompoundS tm在右边包含两条语句；

AssignStm包含一个标识符和一个表达式,等等。

在Java表示的数据结构中,它们变成了子类的域。

因此,CompoundStm有两个域(也叫做实例变量),分别是st ml和stm 2；AssignS tm包含域id和exp。

可以使用Binop类一它的子类分别是加、减、乘、除，它没有任何的子类需要域。

相应地,我们可以列举一些OpExp所包含的常量类型(Java中的整型) 。

编程风控

编程风格我们将遵循Java中表示树型数据结构的一些约定：

  1. 用文法来描述树。

  2. 用一个或多个抽象类来描述树，每个类对应语法中的一个符号。

  3. 每个抽象类可以用一个或多个子类来扩展，每个子类对应一个语法规则。

  4. 对于规则中右边的符号,相应的类中都有一个域(一些小的符号例外,诸如CompoundStm中的分号) 。

  5. 每个类中都有一个构造函数，可以初始化整个域。

  6. 数据结构在建立的时候就被初始化(由构造函数完成)，建立以后就不能被修改(直到最后被丢弃)，

Java 程序的模块规则

一个编译器可能是一个很大的程序，要尽量避免模块和接口的混乱.在用Java实现编译器的时候,我们使用了如下一些规则：

  1. 编译器的每个阶段或者每个模块都属于它自己的包。

  2. “import ondemand”声明将不被使用。如果Java文件以如下方式开始：

import A.F.*;
import A.G.*;
import B.*;
import c.*;

那么对于表达式X.put(),需要从文件外部去寻找定义X时所使用的包。

  1. “单类型的import”声明是一个比较好的解决办法。如果模块以如下方式开始：
import A.F.W； import A.G.X；import B.Y； import C.z；

那么就能从A.G中找到X，而不必从文件外部寻找。

  1. java 是多线程系统。

我们希望能同时支持多个编译器线程,并能同时编译两个不同的程序，它们分别在不同的编译器线程中。

因此，静态变量应该尽量避免，除非它作为常量加以使用。同时不要让两个编译器线程更新相同的变量。

程序设计：直线程序解释器

为直线编程语言实现一个简单的程序分析器和解释器。

通过这一习题，大家可以熟悉环境(符号表指示了变量名和变量的信息)；熟悉抽象的语法(数据结构代表程序的短语结构)；熟悉树形数据结构的递归，这对于编译器中的很多部分都是很有用的；还可以熟悉无赋值语句的函数风格。

我们还提供了一个Java编程的热身习题。

对Java陌生而熟练使用其他语言的编程者可以完成这一习题，但是还需要其他资料的帮助。

解释过的程序已经分析为抽象语法，就像在程序1.5中描述的数据类型一样。

然而，我们并不希望在分析器方面费力，所以利用相应的数据构造函数编写了该程序：

image

ps: 这个代码感觉逻辑比较绕，不知道是否是语句不规范，本地写有报错。

没有副作用的解释器

标志语义和属性文法，它们都是描述程序语言的很好方法。

这也是编写编译器时很实用的技术，编译器也会在操作中指明编程语言可以做什么。

因此，在实现这些程序时，不要在非初始化时对任何变量或对象域赋新值。

对于局部变量,则可以使用初始化的形式进行声明(例如int i=j+3;)，而对于每个类，需要使用构造器进行相应的初始化(如程序1.5中的CompoundS tm构造器) 。

  1. 编写 Java 函数 int max args(St ms),对于给定语句的任意表达式,计算print语句中参数的最大值。例如,max args(prog) =2。

  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)

image

假设链表中对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可以继续用于解释第二个子表达式。

数据结构

课后习题都是关于二叉树的，很久不用都忘光了，需要重新学习。

拓展阅读

mini java

参考资料

《现代编译原理 java》