elang/3. 简单的数值语言及其虚拟机

简单的数值语言及其虚拟机

上一节: https://bbs.125.la/forum.php?mod=viewthread&tid=14705938 源代码 git: http://gogs.mkyr.fun:99/myuan/elang

目标

本节的目标是给上一节的「语言」加上一个函数定义, 然后运行起来. 不过, 我打算在这里面玩一点花哨的, 不提供可变量, 让我们看看能走到哪一步吧.

最初函数空间中只给出 个函数:

• output(x, y, z...) 输出括号里的东西
• dir() 展示当前有哪些函数定义

允许输入的例子如下:

# 先热一下身

f(x) = x * x
output(f(15))

# 都是编程初学者的内容啦

fib(1) = 1
fib(2) = 1
fib(x) = fib(x - 1) + fib(x - 2)

output(fib(20))

factorial(0) = 1
factorial(x) = x * factorial(x-1)

output(factorial(15))

exp(x, 0) = 1
exp(x, y) = exp(x, y - 1) * x
square(x) = exp(x, 2)

output(exp(2, square(2, 2)))


sqrt(x) = sqrt(x, x / 2, 1, 10)
sqrt(x, s, y, 0) = s
sqrt(x, s, y, n) = sqrt(x, (s + y) / 2, x / ((s + y) / 2), n - 1)

output(sqrt(2), square(sqrt(2)))

新增的词法分析部分

本节引入了不可变变量和函数声明, 那个新的词法定义如下:

语句       ::= 函数定义 | 表达式                            # 新增了统筹的语句
函数定义   ::= 函数 "=" 表达式                              # 新增了函数定义
表达式     ::= 加后表达式 (("+" | "-") 加后表达式)*
加后表达式  ::= 因子 (("*" | "/") 因子)*
因子       ::= 左括号 表达式 右括号 | 函数 | 数字 | 标识符    # 之前的语法中最简因子只能是数字, 现在可以是标识符了
函数       ::= 标识符 左括号 (表达式 (逗号 表达式)*){0,1} 右括号

没什么新东西, 学会了上一节的东西之后, 就是体力活了. 唯一需要注意的是之前假设了标识符后面一点是左括号, 否则是语法错误, 现在不是了.

即时解释式虚拟机

第一个实现照例先做一个最朴素的, 就像第一节的四则运算器一样, 之后再用业界常用手段来做.

这样的一个虚拟机实现起来非常简单, 只需要记录当前已定义的函数. 由于没有可变量, 不必去记录状态, 一切都是纯的. 在常规命令式语言有点麻烦的函数作为参数也很容易做, 因为根本就没区分函数和量, 如下:

add_one(x) = x + 1
g(f, x) = f(f(x))
add_two(x) = g(add_one, x)

output(add_two(1)) # 2

在最大的环境里, 包含了前面说过的output和dir两个函数, 这两个函数是用易语言实现的, 默认的, 之后的其他函数都将在这门语言内部实现.

最复杂的部分大概是匹配函数调用, 调用时候要进行重载决议(从C++偷来的名词), 决议过程大致如下:

# 以如下举例

f(0)    = 0               # 1
f(x)    = x               # 2
f(0, 0) = 0               # 3
f(x, 0) = f(x)            # 4
f(x, y) = f(x + 1, y - 1) # 5

首先按函数参数数量匹配, 比如 f(2, 1) 应当只匹配到函数345, 如果匹配失败直接报错.
之后尝试按尽量多常量相容匹配, 比如 f(2, 1) 会匹配到函数5, 然后调用 f(3, 0), 这个时候就应该去匹配到公式4, 而不应该继续使用公式5, 因为公式4有一个常量相容, 公式5没有. f(3, 0) 则将转到 f(3), 然后求值到3.

数据结构

之前忘记在语法树节点上记录词类型了, 现在从函数名的40字节里分出来4个当做词类, 再分出来4字节用于语法结构类型, 当前语法类型为:

.版本 2

.常量 语类_未定义, "0"
.常量 语类_定义, "1"
.常量 语类_函数, "2"
.常量 语类_常量, "3"
.常量 语类_参数名, "4"

为了演示真正的在语法树上爬, 我没有额外定义什么数据结构来保存函数, 还是原来的那个抽象语法树上的函数节点. 至于函数环境, 应当用哈希表的, 但是手写一个哈希表在这个当下的易语言上有点傻, 就暴力数组查找了, 所以函数环境就是一个抽象语法树节点数组说, 没了.

鸣谢

感谢 e2txt 工具, 使得我可以按纯文本保存代码, 添入版本控制

其他闲聊

目前仍然没有合适的语法错误提示, 错了程序就挂掉, 以及保持了一个编译器界经典的操作, 内存只申请不释放, 等程序跑完一下子丢给操作系统处理, 很多编译原理书里都是这样做的!

上节写的「在JavaScript里实现的同样功能的解析器和虚拟机」先叉掉

上面的语言非常函数式, 以及同样有对应的几乎一比一等价的 C++ 模板表示, 当然现在有更简化的 constexpr 了, 这种奇技淫巧能用的地方减少了很多, 以前用起来模板, 起手一个递归式2333.

下节预告

• 基于栈或者基于寄存器的虚拟机
• 虚拟栈或者虚拟寄存器的监视器
• 将 AST 编译到 LLVM/CLI IR/WASM/binaryen IR

以上三者, 我可能会根据大家的兴趣和实现难度挑一个做.

可以从本节到达的其他方向

这一节我已经大量地在语法树上乱窜了, 并且在output时从树节点重新拼装了文本, 事实上这就是一个转换器了, 想想JavaScript混淆或者格式化, 都是基于这个原理完成的