怎样写一个解释器(雾)

栏目: 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:


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

查看所有标签

猜你喜欢:

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

创业小败局

创业小败局

创业家、i黑马 / 时代华文书局 / 2014-8-1 / 42.00元

让别人的失败,成为你的成功之母! 《创业小败局》由徐小平、何伯权等六位经验丰富的业界大佬,从《创业家》五年来跟踪的数千个创业案例中,精心挑选而来。21个最具代表性的失败案例,每个案例都代表了一种最常见的失败规律,也基本上覆盖了当下中国创业浪潮中,最容易遭遇的创业陷阱。失 败是有规律的。有时候创业者的选择和 行为,必然会导致失败,但当事人却因为缺乏经验而没有察觉。比如在错误心态下引入错误的合伙......一起来看看 《创业小败局》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

随机密码生成器
随机密码生成器

多种字符组合密码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具