编译一个表达式

Jun 25, 2022

今天天气不错，所以写一篇。

主要内容是介绍如何将一个表达式编译成机器能执行的汇编指令，不会涉及很细致的步骤，简单的描述下流程。另外，本文展示的流程只能让程序能够运行，不涉及如何优化。

1. 待编译的内容

文法

待编译的源码符合如下文法，由本人亲自随心所欲的定义。

expr : NUM OP expr
    | NUM
    | SYMBOL OP expr
    | SYMBOL
    | SYMBOL ASSGIN expr

以下是用来识别终结符的正则表达式

NUM = r'\d+'
OP = r'[\+\-\*\/]'
WS = r'\s+'
ASSIGN = r'\:\='
SYMBOL = r'[a-zA-Z]+'

源码

为更具体，我们假定需要编译的源码如下，目标是让其能正确的计算出330。

heigh := 10
width := 23

100 + heigh * width

2. 设计虚拟机

为了完成编译，首先设计一款简单的虚拟机，其特征如下：

寄存器

虚拟机运行程序的时候，需要存储一些资料在寄存器里。以X结尾的是通用寄存器，用来辅助指令的计算执行。PC是程序计数器，用来跟踪当前的指令位置，BP和SP用来控制栈。寄存器列出如下

AX
BX
CX
DX
PC
BP
SP

指令集

为了让虚拟机能够干活，需要给它定义些能够运行的指令。现将指令集定义如下

HALT    # 停机
LAX     # 加载立即数到AX
CALL    # 函数调用
ENT     # 用于函数进入时设置环境
RET     # 返回函数调用
PUSH
POP
JMP
RJZ     # 相对跳转
RJNZ
LD
SD
ADD     # 把栈顶的两个数相加
MUL
SUB
DIV
PRTMEM  # 打印栈顶的内容，地址由AX给出
SETM    # 设置AX内容到内存单元，地址由栈顶元素给出
GETM    # 获取指定内存单元的内容

至于如何实现，可以参考其他资料。

在虚拟机上运行指令

有了能执行上述指令的虚拟机，我们就可以给它编写程序了。现在给出一个例子。如果我们要计算 1 + 2，需要编写如下汇编程序

LAX 1  # 加载立即数1到寄存器AX
PUSH   # 将AX的内容放到栈顶
LAX 2  # 加载立即数2到寄存器AX
PUSH   # 将AX的内容放到栈顶
ADD    # 将栈顶的内容相加，放到栈顶
POP    # 将栈顶内容放到寄存器AX

运行后，结果就能在寄存器AX找到了。那么，我们如何利用一开始的源码来自动生成这样的指令呢？

3. 编译源码

由源码得到最终的汇编指令，我们需要经历如下步骤。

词法分析

首先需要将源码转换成Token序列，结果如下

TOKEN(type='WS', value='\n\n')
TOKEN(type='SYMBOL', value='heigh')
TOKEN(type='WS', value=' ')
TOKEN(type='ASSIGN', value=':=')
TOKEN(type='WS', value=' ')
TOKEN(type='NUM', value='10')
TOKEN(type='WS', value='\n')
TOKEN(type='SYMBOL', value='width')
TOKEN(type='WS', value=' ')
TOKEN(type='ASSIGN', value=':=')
TOKEN(type='WS', value=' ')
TOKEN(type='NUM', value='23')
TOKEN(type='WS', value='\n\n')
TOKEN(type='NUM', value='100')
TOKEN(type='WS', value=' ')
TOKEN(type='OP', value='+')
TOKEN(type='WS', value=' ')
TOKEN(type='SYMBOL', value='heigh')
TOKEN(type='WS', value=' ')
TOKEN(type='OP', value='*')
TOKEN(type='WS', value=' ')
TOKEN(type='SYMBOL', value='width')
TOKEN(type='WS', value='\n\n')

进行语法分析并生成虚拟机指令

然后，我们对上面得到的TOKEN序列进行分析，并生成虚拟机能够执行的指令序列如下：

JMP 3 
HALT
LAX 10
PUSH
PUSH 
CALL 13
LAX 20
PUSH 
HALT 
ENT 
LAX 0
PUSH
LAX 6
PUSH
LAX 10
SETM
LAX 7
PUSH
LAX 23
SETM
LAX 7
GETM
PUSH
LAX 6
GETM
PUSH
MUL
LAX 100
PUSH
ADD
POP
SD
LAX 0
PRTMEM 
RET 
HALT
HALT
HALT

分析采用的是递归下降，这样可以方便的写出分析源码的函数。

4. 运行

最后，将这些执行交给虚拟机，运行结果如下

5. 参考资料

如果你想了解更详细的过程，可以参考这些经典的资料

Compilers: Principles, Techniques, and Tools
Modern Compiler Implementation in Java/C/ML
Parsing Techniques