内容简介:怎样写一个解释器(雾)
本文是王垠一篇 年代久远的文章
的笔记,我仿照其中的说明做了一个简单的 lisp
“解释器”并记录了下来.
准确的来说并不算一个解释器,而更像是一个 DSL
:在宿主语言中以多位数组(或列表)的形式存在,没有分词和解析的过程,也没有创建AST,而是直接解释运行。
如何用数组表示代码
在 lisp
中大量使用的 S-表达式
具有 '(+ 1 3)
的形式,在 python
中以列表表示,即 ["+", 1, 3]
,操作符放在最前面。
这个 S-表达式
就是我们解释器的输入
解析一个表达式
有了一个输入后要解析表达式,方便起见所有表达式都只有最多三个参数,而且除 if
外最多两个。实际上一个就行,在 Haskell
, F#
等语言中只有一元函数,多元函数是通过 Currying
实现的。
所以只需要判断第一个元素,然后进行运算即可。
以 ["+", 1, 3]
为例,我们发现第一个元素是 "+"
,”+”需要两个参数(这里忽略了 一元+
和错误处理)分别为 1
和 3
,所以进行运算 1+3
,得到结果 4
变量和环境
完成了以上步骤的解释器只是一个普通的计算器,下面我们给它加上”变”量。由于我们对环境的操作,这里的”变”量实际上是不可变的,但我们可以重复绑定。
“环境”由一个单向列表实现,每个表达式都有自己的环境,这使得我们自然的使用了静态作用域。新的变量绑定被添加到源环境的后边形成新环境。由于每个表达式都会先从最内层的作用域开始查找变量,自然的实现了变量的遮蔽。
另外由于实现了变量,而函数也是变量( lambda
表达式),所以函数也是可用的了。
条件
但是我们的语言只能顺序执行,下面添加一个条件判断。
加入条件判断其实很简单,在解析的基础上加上判断表达式 if
即可。
结束
原文没有条件判断, if
是我诌的……不要加上 if
以后大概就是图灵完备的了233
原文的效果为
(r2 '(+ 1 2)) ;; => 3 (r2 '(* 2 3)) ;; => 6 (r2 '(* 2 (+ 3 4))) ;; => 14 (r2 '(* (+ 1 2) (+ 3 4))) ;; => 21 (r2 '((lambda (x) (* 2 x)) 3)) ;; => 6 (r2 '(let ([x 2]) (let ([f (lambda (y) (* x y))]) (f 3)))) ;; => 6 (r2 '(let ([x 2]) (let ([f (lambda (y) (* x y))]) (let ([x 4]) (f 3))))) ;; => 6
我做出来是
print(lisp(["+", 1, 2])) # => 3 print(lisp(["*", 2, 3])) # -> 6 print(lisp([["λ", "x", ["*", "x", 3]], 3])) # -> 9 print(lisp(["λ", "x", ["*", "x", 3]])) # -> Closure{x:x, exp:["*", "x", "3"], env:[]} print(lisp( ["let", ["x", 2], ["let", ["f", ["λ", "y", ["*", "x", "y"]]], ["f", 3]]] )) # => 6 print(lisp(["let", ["f", ["λ", "x", ["*", "x", 2]]], ["f", 4]])) # => 8 print(lisp( ["let", ["x", 2], ["let", ["f", ["λ", "y", ["*", "x", "y"]]], ["let", ["x", 4], ["f", 3]]]] )) # => 6
嗯,自我感觉还算可以:joy:
以上所述就是小编给大家介绍的《怎样写一个解释器(雾)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。