编译器

引言

想做编译器很久了,大学期间留下了不少遗憾,没有实现自己的编译器,没有实现自己的JVM,没有实现自己的数据库,当然这其中有很多原因,比如学院的要求太松,比如自己也不够主动,这篇Blog将引导读者一步一步构建一个自己的编译器

学习重点

开发编译器我能学到什么?编译器本身吗?其实不对,我们设计编译器的时候,会遇到很多问题,解决这些问题的方法才是最终重要的东西。

编译器的流程

从头开发一个编译器是非常困难的,这涉及到很多知识点,这一部分主要介绍现代编译器的架构。

龙书上把编译器分为前端和后端两个部分,源代码首先经过前端转化为中间代码,中间代码经过后端转化为汇编文件。此后的工作就不是编译器的管理范围了,接下来由汇编器和链接器将汇编文件转化为可执行文件。

graph LR
  源代码 --编译器前端--> 中间代码 --编译器后端--> 汇编文件 --汇编器和链接器--> 可执行文件

为什么编译器要分为两个部分?为什么要分出前端和后端?实际上这样的架构做好以后,只要我们为\(m\)种源代码编写一个前端,为\(n\)种架构的机器编写后端,则我们可以组成\(n*m\)种编译器。当一个新类型的源代码或者新架构的机器出现时,我们可以以更快的速度对编译器进行更新,从而支持这些源代码或机器。另一方面,如果想要对源程序进行优化,编译器前端负责优化吗?还是编译器后端负责优化?这其实是优化器的工作,优化器的输入是中间代码,输出也是中间代码。

接下来读者最关心的问题,应该是中间代码是什么样的?中间代码并不只是一种形式,如果我们忽略优化器,就可以认为中间代码就是一个固定的形式。这个形式就是三地址形式或四元组形式,至于三地址形式和四元式形式究竟是什么,我们后面再做介绍。

编译器前端流程

从源代码到中间代码,编译器已经有了很成熟的架构,一般分为下面这几步。

graph LR
  源代码 --词法分析器--> token流 --语法分析器--> 语法树  --中间代码生成器--> 中间代码

词法分析

词法分析,如其名,只分析词语,即token,词是一个文法的最小单元。

文法

文法的种类有很多,正则文法,上下文无关文法,上下文有关文法。

正则文法

这一块内容就是我们平时所用到的正则表达式的文法,他的词是各个字符。

上下文无关文法

上下文无关文法涉及到4个定义

  • 终结符: 文法的基本单元,词
  • 非终结符: 文法的中间变量,一些词按顺序排列构成的符号
  • 产生式: 连接非终结符和终结符的等式,产生式表明了一些终结符和非终结符如何排列可以得到新的非终结符
  • 开始: 文法开始的非终结符,他表明了什么样的非终结符满足当前文法

例1

1
2
3
4
5
加法:
终结符: number +
非终结符: SUM
产生式: SUM -> number + number | SUM + number
开始: SUM

上诉文法可以接受 1+2, 我们只需要把1和2视为number,即可,此时的词法单元就是1,2,+

识别词法单元

编译器的第一步就是词法分析,他需要从待分析的文本中,逐字符读取,并分割词法单元。一种有效而有简单的方式就是使用正则表达式构建NFA模型,然后优化为DFA,此后对文本进行分割。

这里可能有一些抽象,突然来了这么多概念,下面一个一个来解释。

NFA

语法分析

由于高级程序设计语言基本可以被视为上下文无关文法,文法的语法分析有很多算法,下面依次对他们进行介绍。

递归下降

CYK算法

LL语法分析

LR语法分析

参考文献

一个项目

龙书