编译器：增量式和可扩展的构建方法

Introduction

_Compilers_ 是一门实践性课程。其目标是构建一个真正的编译器，将高级语言编译成实际的 x86-64 机器代码，并生成可在学生笔记本电脑上运行的可执行文件。源语言是 'Tiger'：一种类似于 Pascal（或具有任意嵌套函数的 C）的过程式语言。编译器本身将使用 OCaml 开发。

该课程的另一个目标是让学生体验现代软件开发，特别是：测试驱动开发、版本控制，以及强调阅读、理解和扩展代码，而不是从头开始编写。

该课程的特点是迭代、增量式开发：我们从最简单的源语言开始，为其开发完整的编译器，然后逐步扩展源语言和编译器，尽可能地重用早期工作。在每次迭代中，我们都为源语言的一个（逐渐变大的）子集构建一个_完整_的端到端编译器，生成可运行和可测试的可执行文件。

另一个特点是广泛使用 tagless-final 风格，充分利用它提供的可扩展性。这里的可扩展性意味着_重用_——来自先前增量的类型检查和编译后的产物——而不是复制粘贴。因此，编译器被构建为领域特定语言的堆栈，底部是解析，顶部是汇编。通过在此处和彼处添加新操作来扩展语言（只有偶尔进行重定向）。

另一个特点是关注名称或“变量”，并将属性与它们关联。我们的方法可以随时添加属性并分析变量的使用情况，这可能会使一些人想起 algebraic effects。

我们涵盖了编译器课程的所有标准材料，从解析和类型检查到分析、优化、调用约定和汇编生成——但以一种非常规的方式。

该课程于 2022 年和 2023 年秋/冬季作为一门选修的 15 讲座的高年级本科课程教授。

版本 当前版本为 2024 年 11 月

参考资料 course-notes.pdf [1123K] 课程笔记（前几章） <tfintro/0README.dr> 代码部分：tagless-final 风格简介 Free Variable as Effect, in Practice 课程的一个大大简化的版本，但仍然希望能够让您体验到增量式、逐步式编译器开发的味道。本文还解释了编译中的可扩展 effects —— 本课程目前使用的技术。 emulator.ml [8K] 一个基本的 x86-64 模拟器，用于在引言中解释汇编。汇编知识_不是_先决条件。

Course Content

在预备知识和 tagless-final 风格的介绍之后，我们从最简单的语言开始开发编译器：
  1. 最简单的源语言：仅整数文字
  2. 一元表达式、布尔值、类型
  3. LL(1) 解析，词法分析
  4. 简单二元表达式
  5. 迁移到 ocamllex/ocamlyacc
  6. 局部变量，作用域
  7. 自由变量的含义：环境或 effect
  8. 变量使用情况分析和内存分配
  9. 完整表达式语言
  10. 虚拟表达式和序列
  11. 可变变量，赋值，函数调用
  12. 字符串和字符串操作
  13. 比较和条件
  14. 循环
  15. 函数声明，局部函数和过程
  16. 类型检查，更正式和实用
  17. 相互递归函数
  18. 嵌套函数
  19. 最终练习

Build tool

该课程使用一个专门的构建系统 —— 在某种意义上，是 `make` 的精简、专门和调整后的版本。它旨在支持增量式、逐步式开发，并且只包含所需的组件。它简单、快速，并且可在 MacOS、Linux 和 WSL 上移植。

构建工具实际上是一个名为 build.ml 的 OCaml 脚本。与 make 类似，该脚本接受要构建的目标列表，并按给定的顺序构建它们，并在出错时停止。该脚本是一个常规的 OCaml 文件，可以像这样进行编辑：请参见下面的示例。应特别注意 compiler_manifest，它列出了构建编译器所需的所有源文件，以及如何构建它们。

在 2022 年，该课程使用了 make。经验表明，自定义构建工具将更令人愉快和方便使用。首先，由于我们的编译器是通过扩展早期代码构建的，因此源代码分布在许多步骤中（每个步骤都在其自己的目录中）。 step23 上的代码可能会使用 step22/、step21/、step20/ 中的源代码文件。 make 的 VPATH 工具完全支持这种模式，使 make 查找所需的文件。但是，尚不清楚 make 到底找到了什么以及代码到底在哪里。最好有一个完整的代码文件列表。

必须在编译之前重命名先前步骤中的某些文件。例如，应将 step21/lang.mli 重命名为 lang_21.mli：它将以该名称包含在 step22/lang.mli 中。以前，我诉诸于符号链接，这会使目录混乱并且更难维护。

由于文件分布如此之广，因此很难维护自动依赖项。 Ocamldep 在这里没有帮助。另一方面，为了构建最终的可执行文件，我们必须明确地枚举所有需要的 .cmo 文件，以正确的顺序。必须手动维护该顺序。可以观察到，该顺序正是编译源代码文件的顺序。因此，我们不需要任何工具来发现依赖项，因为无论如何我们都必须列出 .cmo 文件。（我们还需要将 .cmi 文件添加到构建清单中）。因此，我们假设连续（单线程）构建，并失去并行性。根据我们的经验，编译非常快（包括完全重建），因此不需要并行性。

参考资料 step31-build.ml [2K] 一个完整的示例构建脚本 course-notes.pdf [1123K] 课程笔记的 4.1.1 节解释了如何使用构建工具 build.ml [9K] 规则的实现（包括时间戳检查等）和 main 函数

Utilities

目录 `util` 包含常用的代码，特别是构建工具和测试框架。

参考资料 common.ml [<1K] util.ml [2K] build.ml [9K] The Build tool expect.ml [5K] 测试框架：确认解析、生成的代码以及执行已编译代码的结果 Makefile [<1K] Makefile.common [<1K]

Last updated November 5, 2024

This site's top page is http://okmij.org/ftp/ oleg-at-okmij.org Your comments, problem reports, questions are very welcome! Generated by MarXere