Yui的编译过程分为以下几个阶段:

  • 预处理
  • 词法分析
  • 语法分析
  • 语义分析
  • 将指令列表序列化为字节码

下面我们详细的了解一下每一个步骤的具体工作

预处理

预处理主要完成以下几个工作:

  • 移除源代码中所有的注释信息
  • 获取源代码中所有的define代码,解析出define的key和value并把它们的映射关系保存在内存中
  • 移除所有的define代码
  • 移除所有的停用词
  • 根据之前已经获取到的映射关系,把源代码中所有的被定义关键字替换为其相应的值
  • 从源代码中解析出所有的表达式(多个表达式的情况下每个表达式用 {} 进行包裹)

更多详细的信息可以查看预处理过程的源码进行进一步的了解。同时需要注意的是,预处理过程可能会生成多个表达式,而词法分析、语法分析、语义分析都是只针对单个表达式进行的。

词法分析

词法分析比较简单,只需要把表达式解析为token的列表,token包括以下几种类型:

  • (
  • )
  • +
  • -
  • *
  • /
  • 浮点数
  • 整数

token的解析使用正则表达式而不是手动的创建DFA和NFA,经过词法分析之后原始的字符串被分割为一个token列表,词法分析的源码在这里

语法分析

语法分析的目的是把词法分析所得到的token列表转化为一棵抽象语法树(Abstract Syntax Tree,AST)。例如对于表达式

(1 + 2) * (3 - 4)

由于我们使用的是中缀表达式,所以应该生成一棵如下的AST

这里生成AST的难点在于运算规则的优先级,表达式运算有如下的三个优先级

  1. 括号:最高的优先级
  2. 乘除法:中等的优先级
  3. 加减法:最低的优先级

我们分别使用了不同的方法对应不同的优先级计算,计算加减法的方法在最外层,计算乘除法的方法在中间一层,最内部的方法解析括号内的表达式和负数。通过不断地读入token,这三个方法递归的执行,最终生成一棵AST。语法分析的源码在这里

语义分析

在上一步我们已经得到了一棵AST,在语义分析中我们将遍历这棵树并且生成指令列表。我们使用递归的方式来遍历整棵树,在遍历的过程中我们把访问到的每个节点都创建为一条指令,然后把这条指令添加到指令列表中。

指令分为两类,一类是数值指令,一类是计算指令。所有的叶子节点都是数值指令,所有的内部节点都是计算指令。例如,对于上面那棵语法树,它可以生成如下的指令列表

PUSH 1
PUSH 2
PLUS
PUSH 3
PUSH 4
MINUS
MULTIPLY

语义分析的源码在这里

将指令列表序列化为字节码

在上一步的语义分析中我们已经得到了最终的指令列表,但是指令本身需要经过序列化才可以进行保存和传输,下面我们看看如何把指令列表进行序列化。

由于在源码中可能有多个表达式,所以最终我们在语法分析结束后,得到的可能是包含多个表达式的指令列表。对于每一个表达式的指令列表,我们使用如下方式进行序列化

  • 首先我们对指令进行编码,每一个指令都使用一个字节进行编码,具体编码如下:

    PUSH       0x00
    PLUS       0x01
    MINUS      0x02
    MULTIPLY   0x03
    DIVIDE     0x04
    
  • 如果是操作指令,直接把这个指令的编码添加到字节数组中

  • 如果是数值指令,除了把PUSH指令添加到字节数组之外,还要把对应的数值也序列化添加到字节数组中
    • 首先判断数值是整数还是浮点数,在添加数值之前先使用一个字节表示接下来的数值类型(整型或浮点型)
    • 整数和浮点数使用各自的编码方式进行序列化,再把数字序列化的结果添加到字节数组中

针对每一个表达式进行序列化的源码在这里

在对每一个表达式进行了序列化之后,我们得到了一个字节数组的数组,接下来我们再把所有表达式的序列化结果整合起来

  1. 首先我们把MagicNumber放到字节数组的首部
  2. 取出一个表达式的序列化值,计算出这个字节数组的长度,然后将这个整型的长度转化为字节数组
  3. 把长度的值添加到字节数组中
  4. 把表达式本身添加到字节数组中
  5. 重复步骤 2 ~ 5 直到所有的表达式处理完毕

通过上面的方式我们生成一个大的字节数组,这就是我们最终生成的结果。

例如我们有两个表达式A和B,它们生成了两个字节数组A1和B1,那么我们可以构建如下的序列化结果

[MagicNumber][A1 Length Byte Array][A1][B1 Length Byte Array][B1]

在经过了上面这些步骤之后,我们最终把源码编译成了字节码。现在只需要把字节码写入到一个文件中,整个编译就完成了。

注:Yui还实现了从字节码到指令的转化过程,这是为了让目标文件中的指令更易读。此操作对应的命令为 dec,源码位于这里