Fork me on GitHub

基于 LLVM 自制编译器——序

前言

最近一直在学习编译原理,为了加深对于理论的理解,期间参考 LLVM 官方的相关教程进行实践,设计并实现一款简易的编译器。

一开始,我使用 LLVM 官方的 《How to write your own compiler》 教程来进行尝试,该教程使用 JFlex 作为 词法分析器生成器(Lexical Analyzer Generator),CUP 作为 语法分析器生成器(Parser Generator),LLVM 2.7 作为编译后端。编译器整体采用 Java 编码实现,最终实现一门简易的面向对象编程语言 mjava。

一方面,由于年代久远,教程配套的源码其实还是存在挺多问题的,我花了很多时间用于解决工程问题,最终还是由于 LLVM 版本过低,LLVM IR 不兼容,放弃实践。另一方面,由于工业级编程语言几乎都是手工编码实现的编译前端,我意识到该教程与我的预期存在偏差,遂放弃。当然,如果有人感兴趣,可以在我的基础上继续实践——源码地址

最终,我重新找了另一份官方教程——《My First Language Frontend with LLVM Tutorial》。该教程基于 C++ 语言,手动实现编译前端,调用 LLVM API 生成中间代码,并加入了 LLVM 提供的各种优化通道(Optimization Pass)进行优化,同时支持 JIT 和 AOT 模式,最终实现一门简易的编程语言 Kaleidoscope。

出于笔记和深度理解的目的,我对该教程进行了翻译,各个章节中都或多或少加入了一些自己的理解,如有纰漏或错误,欢迎留言指正。

组织结构

在本系列教程中,我们将介绍并实现一门简单的编程语言——Kaleidoscope,教程的每一章都会逐步对其编译器进行完善。与此同时,我们会介绍编译原理相关的理论和知识,以及 LLVM 相关概念。在每一章中,我们会花费很大的篇幅对相关的代码实现进行解释。因此,强烈建议每一位读者亲自对代码进行实践。

教程总共分为十章,每一章包含不同的主题,各章之间属于循序渐进的关系,各章相关的代码,也是通过增量修改实现的。如下所示,为各章的主题与内容简介。

  • 第 1 章 - Kaleidoscope 与词法分析器。介绍了我们的目标,以及实现的基本功能。词法分析器是为一门编程语言构建解析器的基础,我们使用 C++ 实现一个简单的词法分析器。
  • 第 2 章 - AST 与解析器。介绍了解析器相关技术,以及抽象语法树的构造。关于解析技术,本教程使用的是递归下降分析法和算符优先级分析法。
  • 第 3 章 - LLVM IR 代码生成。介绍了如何基于 AST 生成 LLVM IR,通过一种简单的方法将 LLVM 引入到编译器实现中。
  • 第 4 章 - JIT 与优化器支持。基于 LLVM 为 Kaleidoscope 实现 JIT 编译功能,同时加入对于优化器的支持。
  • 第 5 章 - 语言扩展:控制流。对 Kaleidoscope 进行语言扩展,实现控制流能力(if 语句和 for 语句)。同时,简单介绍了 SSA 的构造。
  • 第 6 章 - 语言扩展:自定义运算符。对 Kaleidoscope 进行语言扩展,实现自定义运算符能力,允许用户自定义一元运算符和二元运算符(支持运算符优先级)。
  • 第 7 章 - 语言扩展:可变变量。对 Kaleidoscope 进行语言扩展,实现局部变量和赋值操作符。同时,介绍了一种隐式的方法让 LLVM 自动构造 SSA。
  • 第 8 章 - 目标文件编译。介绍了如何基于 LLVM IR 编译生成目标文件。
  • 第 9 章 - 调试信息。支持调试器,添加调试信息,允许在 Kaleidoscope 函数中设置断点,打印参数变量和调用函数。
  • 第 10 章 - 总结。主要讨论语言扩展的进阶内容,比如指针、垃圾回收、异常、调试等。

环境搭建

本文实践环境所使用的操作系统是 MacOS Monterey 12.5 版本,LLVM 14.0.0 版本。

下面,我们通过以下步骤生成工程,从而搭建调试环境。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 克隆 llvm 工程
$ git clone https://github.com/llvm/llvm-project

# 切换至 llvm 14.0.0 版本
$ git checkout llvmorg-14.0.0

# 创建构建目录
$ cd llvm-project/llvm/
$ mkdir build

# 生成 Xcode 工程
$ cd build
$ cmake -DCMAKE_BUILD_TYPE=Release -G Xcode ../llvm

通过上述步骤,我们会在 llvm-project/llvm/build/ 目录下生成一个 LLVM.xcodeproj 工程。使用 Xcode 打开该工程,我们可以看到项目中包含了非常多的 target,其中 Kaleidoscope 相关的 target 也在其中,如下图所示。

至此,环境搭建完毕!下面,让我们一起来跟着教程自制编译器吧!

参考

  1. How to write your own compiler
  2. JFlex
  3. CUP
  4. Building LLVM with CMake
欣赏此文?求鼓励,求支持!