怎样写一个解释器(雾)

栏目: Lisp · 发布时间: 6年前

内容简介:怎样写一个解释器(雾)

本文是王垠一篇 年代久远的文章 的笔记,我仿照其中的说明做了一个简单的 lisp “解释器”并记录了下来.

准确的来说并不算一个解释器,而更像是一个 DSL :在宿主语言中以多位数组(或列表)的形式存在,没有分词和解析的过程,也没有创建AST,而是直接解释运行。

如何用数组表示代码

lisp 中大量使用的 S-表达式 具有 '(+ 1 3) 的形式,在 python 中以列表表示,即 ["+", 1, 3] ,操作符放在最前面。

这个 S-表达式 就是我们解释器的输入

解析一个表达式

有了一个输入后要解析表达式,方便起见所有表达式都只有最多三个参数,而且除 if 外最多两个。实际上一个就行,在 HaskellF# 等语言中只有一元函数,多元函数是通过 Currying 实现的。

所以只需要判断第一个元素,然后进行运算即可。

["+", 1, 3] 为例,我们发现第一个元素是 "+" ,”+”需要两个参数(这里忽略了 一元+ 和错误处理)分别为 13 ,所以进行运算 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:


以上所述就是小编给大家介绍的《怎样写一个解释器(雾)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Usability for the Web

Usability for the Web

Tom Brinck、Darren Gergle、Scott D. Wood / Morgan Kaufmann / 2001-10-15 / USD 65.95

Every stage in the design of a new web site is an opportunity to meet or miss deadlines and budgetary goals. Every stage is an opportunity to boost or undercut the site's usability. Thi......一起来看看 《Usability for the Web》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

html转js在线工具
html转js在线工具

html转js在线工具