编译技术

最初只是我学习编译原理过程中的一些记录，后来加入了一些编程语言的内容。

摘录

来自王垠的经典博文《对Parser的误解》，观点甚合吾心：

会写Parser并不了不起，没必要过度高估写Parser的难度，更不用对会写Parser的人顶礼膜拜；
最近看到《Crafting Interpreters》的作者也表达了类似的观点：https://craftinginterpreters.com/compiling-expressions.html#design-note。
Parser技术只占了PL领域的很小一部分，PL和OS、AI等一样是一个很大的范畴。得到AST得到IR甚至只是“万里长征的第0步”，后面还有各种分析和优化技术；
龙书害人不浅。

工程实践中的技巧：

尽量复用别人的Parser，必要时定义一套自己的AST然后做一下两种数据结构之间的转换就行。这个转换的意义在于“适配”、“防腐”；
注重单一职责原则，没必要非去追求在一遍扫描过程之后就获取源码的全部信息。提防“过早优化”；
还是单一职责，Parser就只做Parser的事情，分析和优化在后面的阶段再做；
不建议学习各类“Parser generator”；
曾经也短暂接触过flex和bison这类东西，但很快就放弃了。一者是因为懒惰，同时我也觉得为了解析一种DSL去学习另一种DSL是一件非常蠢的事情，本质还是调API。
递归下降yyds，能够解决日常生活中99%的Parser需求。

这里也有一些前人的总结。

个人学习路径

我的学习路径，感觉还不错。加粗的是当前状态：

《计算理论导论》自动机有关内容
《SICP》求值器有关内容
尝试实现Lisp子集，使用求值器执行
深入理解延续、CPS风格
将实现的小语言翻译为某种形式的IR及ISA，如LLVM IR/RISCV/WASM等（龙虎鲸……）
软件分析/优化（系统性的课程）
……

个人记录

兴趣很重要。我对编译技术感兴趣也是因为喜欢造轮子，喜欢DIY，以及在初学者阶段接触过c++模板元编程和函数式程序设计，留下了深刻印象。因此当你说想学编译的时候，应该搞清楚自己是喜欢折腾各种高效的编译算法、优化算法、还是想要DIY自己想要的语法、深入各种语言范式背后的理论（例如类型系统、延续、生命周期、函数式等）、亦或是想要设计自己的语言虚拟机等等。
我曾经也认为写编译器前端或者ISA模拟器很高大上，自己上手了才意识到，这其实是一件苦差事，因为我们处在下游，在实现别人设计好的东西，做的是那些边角料工作与粗活重活。对我个人来说，更想要的是发挥自己的创造欲望，发明自己的语法比解析别人定义的语法要有趣，设计自己的指令集比读又臭又长的ISA Spec要有趣，编写自己的语言虚拟机也比复刻已有的设计要有趣。这并不意味着我们不需要学习已有的知识，也不是鼓励重复造轮子，而是一种保持兴趣的行之有效的学习方式。
我们并不总是需要将AST转换为IR再转换为机器码什么的，如果只是自己在语法上整活的话在宿主语言里对AST写个求值器就够了。由于和词法分析、语法分析是相对独立的模块，AST相当于接口层，可以分开进行并做单元测试；
正如龙书4.3节所述，用正则表达式来辅助完成词法分析足矣，不需要也不应该在词法分析阶段做分析程序结构的工作。我作为新手曾犯的一个错误就是拎不清词法分析和语法分析的界限，经常在词法分析阶段想识别一些结构化的语法，最后就是一团乱麻。其实词法分析器只要能读token就行了。甚至用于识别token的正则式随便找一些编译器源码都能套用；
以前在别处学来的正则表达式的小技巧：有时我们需要识别一个由双引号包括的，但里面又允许带转义的双引号的结构：/^"([^"]|\\")*"$/；搞清楚贪婪、分组和环视很有帮助，推荐《深入理解正则表达式》；
自己编写的文法总是有BUG？这很正常，没人能一开始就设计出完美无缺的文法，能够消除左递归和提取公因子就够用了。虽然我不用ANTLR，但是这个仓库很有价值，搜罗了很多文法；
语法分析阶段，先从S-表达式起步，模仿一个Lisp的方言，不要一开始就想着实现各种花里胡哨的语法，应该编写简单清晰的代码以便随时重构；什么LL、LR、LK……，别问，问就是不知道，问就是递归下降加回溯🐶 。递归下降除了简单以外，代码结构和文法结构非常相似，因此重构起来会很轻松，也易于添加新的特性。同时每个非终结符都可以实现为一个小函数，方便测试；
虎书神图，盗了：
闭包是词法作用域（lexical scoping）的一个实现，对应的还有~~反人类的~~动态作用域（dynamic scoping）。出现动态作用域的原因据说是早期lisp的实现者将函数以代码（quote）的形式保存，直到调用的时候才进行求值。由于没有闭包捕获，函数体中的自由变元只能在被调用时所处的当前环境里去找，显然这会使程序产生各种奇怪的行为。只能说前辈们好天真……
在纯函数式与非纯函数式语言中，闭包的实现可以有很大的不同，因为彼此存在不同的分析优化机制。
近期遇到了一个理论与实践之间的gap，构造基本块和数据流图的时候，找到的资料都说是针对过程内IR的，但没有说清楚在真实工程中拿到整个程序的IR后如何处理call或ret。如果ret作为基本块的结束，它应该与所有调用的地方连线吗？如果语言支持嵌套函数，那call后面紧跟着的就不一定是固定的函数名，就很难在静态分析阶段确定基本块的范围了。虎书指出将函数变量表示为闭包，但也仅仅提了一嘴控制流图的计算要复杂一点。
在虎书上看到的段子：“有人可能会找借口说，‘但我使用的程序设计语言中有一种地址算术运算会导致无法知道数组维界’。是的，枪杀了父母的人只能依靠法官的怜悯，因为他已成了孤儿”。这里译者贴心地打了个圆场：“这句话的意思是，如果你用的程序设计语言使得编译器无法判断数组是否越界，那么用这个语言编写的程序的正确性也难以保证”。然而我觉得作者只是在吐嘈那样写编译器的人是孤儿而已哈哈。
call by value和call by reference的区别体现在寄存器分配上。call by name是实现懒惰计算的基础，我们在定义变量的地方将变量转换为可以计算出变量值的闭包函数var，每次使用变量调用var()拿到变量值。显然每次对var()的调用可以用缓存进行优化，这样不用每次都重新计算的laziness称为call by need。

以一个多态函数add<T>为例，多态语言必须解决的基本问题是编译器无法知道保存在多态变量中的数据的类型和大小，以便生成正确的机器代码，为此，有以下几种方法：

方法	介绍	优点	缺点
拓展	不生成通用的`add<T>`函数，而是为实例化`T`得到的每一个不同的类型生成专门的`add`函数。代表如C++的模板，Ada的泛型。	编译模式简单。	函数复制会导致代码膨胀，我们常常希望在声明函数的地方编译该函数，而不是在它的每一个调用点重新编译一个实例；无法处理多态递归，例如`add<T>`中还调用了`add<sub<T>>`，那么`add<int>`会生成`add<sub<int>>`类型，进而生成`add<sub<sub<int>>>`，无限展开。
完全装箱、贴标签	用数据结构包裹（算上类型信息）大于字长的值，记录有一个描述字用于描述类型信息；对于小于字长的值，例如在一个按字节编址的机器上所有记录指针都按4的倍数边界对齐，则可以认为最后一位是1的字不是指针，于是可以这样来表示字符值：将它们左移1位然后加1。	克服了一部分拓展的缺点，贴标签的代价通常小于装箱，是许多多态语言的实现方式。	完全装箱的代价高昂；贴标签的缺点是必须为标签保留专门的一位，导致整数不能使用一个机器字的所有位。C 语言标准甚至不保证指针是一个整体，因此没有对指针进行位操作的标准方法。
基于强制的表示分析	对完全装箱的改进：单态变量保存的值使用没有装箱也不贴标签的表示；多态变量保存的值使用装箱或贴标签。	单态部分高效。	需要额外的分析过程。
将类型作为运行时参数传递	改写多态函数，将类型信息当作是一个运行时的值来对待	使得typecase（`instanceof`, `typeof`，`typeid`……）机制成为可能	类型描述必须在运行时构建，构建的代价不能太大。改写后的多态函数需要根据类型参数的不同采用不同的方法处理它的变量，这样做的代价也可能很大。

对称协程和非对称协程：前者通常提供一种叫做transfer的语义，作用与goto类似；后者则提供yield和resume一对语义。yield 函数暂停执行中的协程 B，并将其控制权返还给之前调用resume 使 B 得以执行的协程 A。对称的含义是彼此的地位对等，因此控制权转移到同地位其他协程，而非对称则转移到调用者，前者往往导致程序执行流变得难以理解。
The transfer primitive of symmetric coroutines corresponds to replacing the entire call stack of the running coroutine by the call stack of the transfer target. On the other hand, the resume primitive adds the target stack on top of the current one.
A symmetric coroutine is simpler than an asymmetric one but poses a big problem for an embeddable language such as Lua. Any active C function in a script must have a corresponding activation register in the C stack. At any point during the execution of a script, the call stack may have a mix of C functions and Lua functions. (In particular, the bottom of the call stack always has a C function, which is the host program that initiated the script.) A program cannot remove these C entries from the call stack, however, because C does not offer any mechanism for manipulating its call stack. Therefore, the program cannot make any transfer.
有个相似的概念是Fiber，区别是Fiber协程一般有个调度者，Fiber阻塞（block，和Coroutine的挂起yield类似）后将控制权交给调度者，而Coroutine交给caller或对称协程。
有栈协程和无栈协程：有栈协程和无栈协程的区别主要在于协程是否拥有自己的堆栈。这将决定协程函数内部能否进行任意深度的 yield 操作。有栈协程在挂起时会保存其完整的调用栈，包括所有的局部变量和函数调用信息，因此可以在任意深度的函数调用中进行挂起和恢复。而无栈协程在挂起时只保存顶层函数的状态，因此只能在顶层函数中进行挂起和恢复。无栈协程在挂起时不保留调用栈状态，它和内部调用的普通函数“并列”地存在于主程序堆栈上，挂起操作仅站在协程函数视角而丢失了所有后续调用信息，故再恢复时将缺乏足够的信息来恢复到挂起时函数调用的深度。这有点类似于通常我们无法在内层循环中 break 掉外层循环。而有栈协程自己持有一个独立的堆栈，内部调用函数运行在协程自己的堆栈上，这个堆栈通常由协程库分配和管理，站在主程序的角度，那只是一块协程函数所使用的应用级内存。这也意味着如果有栈协程的堆栈非常小，在协程内部可调用的函数深度将非常有限，即使主程序的堆栈无限大。
典型的无栈协程如JS中的协程，典型的有栈协程如Lua中的协程。下面Lua代码在协程函数中调用了普通函数normalFn，并在普通函数中挂起协程的行为，在JS中无法实现，JS压根就不能在普通函数中使用yield，但你可以在 async 函数中使用 await 来实现类似的功能：
lua
```
local normalFn = function()
  print("normal fn")
  coroutine.yield()
end

local genFn = coroutine.create(function()
  print("before")
  normalFn()
  print("after")
end)

coroutine.resume(genFn)
coroutine.resume(genFn)
```
Q: 有栈协程内部任意深度处，如果要使用协程函数外部的局部变量，是如何捕获的？
A: 对于Lua来说，它采用了一种叫 upvalue 的机制，在创建闭包时遍历外层函数被引用的变量并创建 upvalue 链表，存放于闭包关联的数据结构以组成被捕获的“环境”，在合适的时候还会将被捕获变量拷贝到堆中（例如被捕获变量所在栈帧将被销毁）。细节可参考《Coroutines in Lua》。
Q: 是否有可能以某种方式记录下无栈协程函数到挂起点之间的调用信息，以实现和有栈协程一样的效果呢？
A: 理论上可以，但那几乎意味着需要把协程函数所在帧和挂起位置之间的所有信息保存下来，这在实践中可能会非常复杂和低效。因此，通常我们会选择使用有栈协程来实现这种功能。

编译技术 ​

摘录 ​

个人学习路径 ​

个人记录 ​

编译技术

摘录

个人学习路径

个人记录