折腾一个编译器（中间表示翻译篇）

在MyLang的实现中，语法分析器MyParser和语义分析器libBlock都是独立的单元，因此需要一个“对接”的过程。

语法分析篇中我们提到，MyParser提供了Pass模块用于遍历AST。本文即描述了一个Pass模块的实例。

libblock中间表示

libblock中间表示由一些被称为block（块）的单元组成。每个block是一个作用域。在MyLang中的一个function、program或class对应一个block。有一个全局的根block，主program所在的block是它的一个成员（而不是它本身）。

每个block中包含一些名称及绑定在名称上的代码树，包含一个调用接口（函数的调用、类的构造）。名称又可以根据性质分为type、expr、var、static、fast，和MyLang对应。

block这个概念在作者之前做的某几个语言里也出现过。

libblock的代码树比MyParser生成的AST简单一些，大致包含：

Get节点：从当前作用域获取某个名称对应的内容；
With节点：访问另一个作用域，用于obj.field这样的形式；
Call节点：函数调用或类的构造；
Literal节点：字面量，包括整数、浮点数、字符等（需要注意，libblock没有“字符串节点”，字符串由连续的字符节点表示）；
Label节点：标签的标识符，用于跳转，同一个Block里，每个标签有一个唯一的标识符；
Block节点：引用其它block，通常出现在编译时执行的代码树里（例如类型定义）。

libblock中间表示直接以C++对象的形式存在于内存中，但也可以用文本表示出来。

例子

下面看例子——

源码：

1 program example()
2 is
3   var a is integer;
4   var b is integer;
5 begin
6   input a;
7   input b;
8   print (a + b);
9 end

libblock中间表示，可以看到program是根block下的一个成员：

 1 {                                       # global
 2     type:
 3         "example" hidden: block {       # program
 4             expr:
 5                 "__code" hidden: (      # program body
 6                     __locate (@0)
 7                     input (a)
 8                     input (b)
 9                     print (__add (
10                         a
11                         b
12                     ))
13                     __locate (@1)
14                 )
15             var:
16                 "a": integer            # variable "a"
17                 "b": integer            # variable "b"
18         }
19 }

函数体在__code，它以expr成员的形式存放在block结构中。在MyLang中，不写函数体而直接声明expr __code is ...;也是可行的（注：这一细节暂未定型）。

实现细节

出于简化编译过程、减少和语言的耦合性等考虑，libblock代码树的节点被设计得尽可能简单，因此它不直接包含控制流结构。那么控制流结构是如何翻译的呢？

回到之前的例子，可以看到其中出现了__locate，这是一个函数，它的参数@0（或@1）是Label节点。libblock的Label本身只代表一个标识符（一个数字），而标签的位置是通过__locate函数确定的（__locate @XXX表示“使XXX标识符表示当前的位置”）。

很自然，__goto和__branch函数分别表示无条件、有条件跳转。其中__branch表示“若条件不成立则跳转到标签”。

将__locate、__goto和__branch组合使用，就可以实现循环、分支等结构：

 1 begin
 2   while a < 10 do
 3     LOOP_BODY_IS_HERE;
 4   end while
 5 
 6   if a == b then
 7     THEN_BRANCH;
 8   else
 9     ELSE_BRANCH;
10   end if
11 end

 1 "__code" hidden: (
 2     __locate (@0)
 3     __locate (@2)           # loop begin
 4     __branch (
 5         @3
 6         __less (
 7             a
 8             10
 9         )
10     )
11     LOOP_BODY_IS_HERE
12     __goto (@2)
13     __locate (@3)           # loop end
14     __branch (              # branch begin
15         @4
16         __equal (
17             a
18             b
19         )
20     )
21     THEN_BRANCH
22     __goto (@5)
23     __locate (@4)
24     ELSE_BRANCH
25     __locate (@5)           # branch end
26     __locate (@1)
27 )

另一方面，libblock的中间表示也不包含运算符。我们可以看到，运算符被理解为了有两个参数的函数，例如上面出现过的__add、__equal。

由于MyParser是一个LL分析器，它接受的语法是不包含左递归的。我们会发现，A-B+C可以自然地被解析成(A-(B+C))，但是无法直接得到((A-B)+C)。

 1 Bad    -
 2      /   \
 3     A     +
 4          / \
 5         B   C
 6 
 7 Good     +
 8        /   \
 9       -     C
10      / \
11     A   B

这就需要在将AST变换为libblock中间表示的过程中，完成一组“旋转”操作。

“旋转”的实现并不复杂。继续以A-B+C为例，完成A的处理之后，将得到的树传入负责处理-B的函数，组合成A-B，然后再将A-B传入负责处理+C的函数，就能得到正确的表达式结构了。

写博客结尾真是一件麻烦的事……总之，MyLang的中间表示翻译大致如上文所述。在MyLang项目中，对应的代码在一个名为mylang_analysis_pass.hpp的文件里。

MyLang的语义分析、代码生成还没有开发完成，后续博客的话题可能暂时切换到MyLang之外。