编译器构造—编译

第一章

2019年7月10日发布📑

编译

编译器

compiler

编译器就是将用高级语言编写的源程序编译成为对应的低级语言(例如机器语言)的程序。

编程语言

编程语言由三方面定义:

1.标记(token)或词位。例如关键字if,操作符+,常量如4'c',还有标识符。

2.语法描述和语言结构。例如类、方法、语句和表达式等。

3.语义描述。描述各种语言结构的意义。

机器语言

机器语言就是机器的指令集,面向机器,更适合被机器解析。机器的指令集及其运行方式通常称为机器的体系结构。那么常见的机器语言就是某些体系结构的机器的指令集了,例如Intel i386系列的,属于复杂指令集计算机(CISC)。另外还有MIPS和ARM等精简指令集计算机(RISC)。除了这些实在的处理器的机器语言之外,Java的虚拟机(JVM)体系结构也是一种机器语言,称为虚拟机并不是因为不存在,而是因为它是用软件实现的。在这个系列里面,我们主要关注JVM的机器语言。

为什么学习编译器

1.编译器是比较大型的程序,学习规模较大的程序开发有好处。

2.编译器应用到了很多已经学过的内容:数组、列表、队列、栈、树、图、maps、正则表达式、有限状态自动机、上下文无关语法还有解析器、递归以及模式。将这些知识都用起来是很有趣的。

3.会更加熟悉要编译的语言(也就是Java)

4.会学习到很多关于目标机器的知识,这里主要是关于JVM的。

5.可以将编译器的技术应用于处理XML文件。

编译器是如何工作的——编译的过程

how-it-works

前端

  • 分析源语言的输入程序的含义;

  • 源语言相关的(依赖于源语言);

  • 可以细分为一系列分析阶段,如下图:

    forntend

扫描器作用是将字符串分解成标记串:标识符、字面量、保留字、操作符和分隔符等。

解析器是按照一定的语法规则将标记串生成对应的抽象语法树,作用是让隐式语法(源程序)变成显式语法(抽象语法树)。

语义分析涉及到建立符号表(symbol table)、确定类型、类型检查,有时候还涉及一些存储分析,例如确定变量的地址和偏移量的时候。如果一门语义允许引用一个在后面才声明的变量,那么语义分析阶段至少要过两遍。

后端

  • 将中间表示转换成目标机器程序

  • 依赖于目标语言(与源语言无关)

  • 可以进一步划分成一些了综合阶段,如下图所示:

    backend

代码生成阶段负责选择生成哪些机器指令。

peephole即窥视孔,peephole optimizer是窥孔优化,是一种局部优化方式,编译器仅仅在一个基本块或者多个基本块中,针对已经生成的代码,结合CPU自己指令的特点,通过一些认为可能带来性能提升的转换规则,或者通过整体的分析,通过指令转换,提升代码性能。别看这些代码转换很局部,很小,但可能会带来很大的性能提升。

最后对象阶段将生成的模块链接起来称为可执行程序。

“中端”

有时候前端和后端之间会存在“优化器”,可理解为“中端”,如图:

middle-end

(勘误:上图左端文字应为“源语言程序”)

分离的好处

  1. 降低实现的复杂度。
  2. 前后端分离可以让分别独立的团队同时开发不同的部分,缩短整体实现耗时。
  3. 促进代码复用。

编译到虚拟机

Java编译器javac产生适用于JVM的“字节码”,字节码也属于一种中间表达形式(IR),在本书中,我们会编译一个Java语言的子集(j--)。学习在针对JVM的编译器的过程还缺少了一个方面的经验,那就是关于寄存器分配的学习,因为JVM是基于栈(Stack-based)的虚拟机,没有寄存器。

关于j--到JVM的编译器

j--编译器的组织

编译器的主入口是Main,它会读入一系列参数,然后创建一个扫描器对象用于扫描标记(Token),接着解析器对输入的源语言程序进行解析,并构造抽象语法树。

j-- compiler

抽象语法树的每个节点具有特定的类型,反映了背后的语法结构或支持的操作。例如类型JCompilationUnit在抽象语法树的根部,表示被编译的程序。它有子树,表示包名,导入的类型的列表,以及声明的类型。在抽象语法树中的一个类型为JMultiplyOp的对象,表示乘法操作。它的两棵子树分别表示两个操作数。在树的叶子可以发现有JVariable对象和表示字面常量的对象。

抽象语法树的每个节点定义了三个方法,每个方法在节点上执行某个任务,并递归地处理其子树。

  1. preAnalyze(Context context) 只在抽象语法树顶点附近的节点有定义,因为j--没有实现内部类。预分析主要处理导入的类型、定义的类名称、以及类成员头部(方法头和字段),这是很有必要的,因为方法体可能引用后面定义输入的名称。上下文参数是一连串Context(或其子类)对象,表示编译时符号表中声明的变量及其定义。
  2. analyze(Context context)在抽象语法树的所有节点都有定义。当在某个节点调用这个方法,它会声明在符号表中的名称,检查类型(在符号表中寻找名称的类型),并且将局部变量转化成一个方法的运行时本地栈帧,即局部变量存储的地方。
  3. codegen(CLEmitter output)用于生成该节点的Java虚拟机代码,并递归地调用生成其子树的代码。output参数是CLEmitter类型对象,它是生成的.class文件的一种抽象。

扫描器

解析器

syntax directed, recursive descent

compilationUnit ::= [package qualifiedIdentifier;]
{import qualifiedIdentifier;}
{typeDeclaration} EOF

认为不变吗? 测试一下,改变文件内容后,url是否更新。

抽象语法树

类型

符号表

preAnalyze()和analyze()

栈帧

codegen()

j--编译器代码

强化j--

编写测试

修改词法和语法

修改扫描器

修改解析器

语义分析和代码生成

测试更改

本书的组织形式