零基础构建语言解释器

简介:

在编写Interpreter之前,我们需要先了解Lexer(词法分析器),Parser(语法解析器),AST(抽象语法树)。

一般情况下,Interpreter在解释执行程序时,一般会经过如下步骤。

  1. Lexer读入程序代码,把代码转换token序列。
  2. Parser把读到的token序列转换为AST(大部分情况下,Lexer内嵌为Parser的一部分)。
  3. 对AST进行Lowering(化简AST)或者desugar(把语法糖的AST节点转换为标准等价AST节点)处理。
  4. Interpreter递归执行AST,AST决定了代码的执行顺序。

alternative text

介绍完了基本的一些概念,我们现在开始来实现语言解释器。

首先,我们需要先定制文法规则,一般情况下,我们只要制定好了文法规则,就可以找一些工具来帮我们生成AST,对于复杂的文法规则,手写Parser是非常麻烦并且乏味的。 这里,为了简单,我们选用S-Expression来作为我们的文法规则来实现Lambda Calculus(Lambda演算)的解释器。 通过该Interpreter的实现,大家可以很容易就搞明白程序设计语言中耳熟能详却又未必深刻了解的一些概念,比如:类型,Lexical Scope(词法作用域),Dynamic Scope(动态作用域),闭包等概念。

Lambda Calculus

虽然规则简单,Lambda演算却是一门强大的语言。它的三个元素分别是是:变量,函数,调用。用传统的表达法,它们看起来就是:
    变量:x
    函数:λx.t
    调用:t1 t2

每个程序语言里面都有这三个元素,只不过具体的语法不同,所以你其实每天都在使用 lambda calculus。换成S-Expression就是:
    变量:x
    函数:(lambda (x) e)
    调用:(e1 e2)

Parser的实现

在parse处理token序列之前,我们先对tokens序列做一下预处理,其转换规则如下例所示,详细源码可以在此查看

"(((lambda (x) (lambda (y) (+ x y))) 2) 3)" => [[[lambda [x] [lambda [y] [+ x y]]] 2] 3]     
function doParse(node) {
    var head;
    if (isArray(node)) {
        if (node.length == 0) {
            throw new SyntaxError("syntax error: " + node);
        } else {
            head = node[0];
            switch(head) {
                case 'def':
                    return parseDef(node);
                case 'lambda':
                    return parseLambda(node);
                default:
                    return parseApply(node);
            }
        }
    } else {
        return node;
    }
}

为了演示方便,除了变量,函数,调用Node之外,我这里还额外实现了一个节点def,它的主要功能是方便给变量及函数定制别名。

解析Lambda节点

function parseLambda(node) {
    var params, paramNames;
    if (node.length !== 3) {
        throw new SyntaxError("syntax error in function definition" + node);
    }
    params = node[1];
    if (!isArray(params)) {
        throw new SyntaxError("incorrect format of parameters: " + params);
    }
    paramNames = params.map(function(param, _){
        if (isArray(param)) {
            throw new SyntaxError("illegal argument name : " + param);
        }
        return param;
    });
    return {type: 'lambda', params: paramNames, body: doParse(node[2])};
}

解析Apply节点

function parseApply(node) {
    return {type: 'apply', func: doParse(node[0]), args: doParseList(aps.call(node, 1))};
}

解析Def节点

function parseDef(node) {
    if (node.length != 3) {
        throw new SyntaxError("incorrect format of definition " + node);
    }
    return {type: 'def', pattern: doParse(node[1]), value: doParse(node[2])}
}

(def if (lambda (p) (lambda (x) (lambda (y) ((p x) y))))) 转化的AST如下: alternative text

Interpreter的实现

function interpret(node, scope) {
    switch (node.type) {
        case 'def':
            return scope.define(node.pattern, interpret(node.value, scope));
        case 'apply':
            var closure = interpret(node.func, scope),
                args = node.args.map(function(arg) { return interpret(arg, scope); }),
                newScope;
            if (closure.type === 'closure') { // Lambda Closure
                newScope = closure.fn.params.reduce(function(ctx, param, i) {
                    ctx.define(param, args[i]);
                    return ctx;
                }, closure.env.copy()); // scope.copy() static scope vs. dynamic scope
                return interpret(closure.fn.body, newScope);
            } else { // BuiltIn Function
                return closure.apply(scope, args);
            }
        case 'lambda':
            return {type: 'closure', fn: node, env: scope};
        default:
            if (scope.defined(node)) {
                return scope.lookup(node);
            } else {
                throw new EvalError("Unknown variable " + JSON.stringify(node));
            }
    }
}

如果你想支持原生的数据类型,比如字符串和数字,default部分可以改为:

default:
    if (node[0] === '"' && node.slice(-1) === '"') {
        return node.slice(1, -1);
    } else if (!isNaN(parseFloat(node))) {
        return parseFloat(node);
    } else {
        if (scope.defined(node)) {
            return scope.lookup(node);
        } else {
            throw new EvalError("Unknown variable " + node);
        }
    }

程序设计语言中的一些概念

Closure(闭包)

在计算机科学中,闭包(Closure)是词法闭包(Lexical Closure)的简称,是引用了自由变量的表达式(通常是函数)。这些被引用的自由变量将和这个函数一同存在,即使已经离开了创造它的环境也不例外。 词法作用域(lexical scope)等同于静态作用域(static scope)。所谓的词法作用域其实是指作用域在词法解析阶段既确定了,不会改变。

在这里很容易看出,闭包的数据结构可以定义为,包含一个函数定义 f 和它定义时所在的环境 (struct Closure (f env))

(def add (lambda (x) (lambda (y) (+ x y)))) ;; add是一个全局函数,它是没有绑定任何自由变量的闭包,它的env就是全局的scope。
(def add5 (add 5)) ;; add5是一个全局函数,它是有捕获自由变量的闭包。
(add5 10) ;; Output: 15

动态作用域 vs. 词法作用域

本例中,以下代码决定语言程序语言使用的是词法作用域还是动态作用域。

newScope = closure.fn.params.reduce(function(ctx, param, i) {
    ctx.define(param, args[i]);
    return ctx;
}, closure.env.copy()); 
return interpret(closure.fn.body, newScope);

closure.env.copy()替换为scope.copy()就可以把当前的词法作用域替换为动态作用域。词法作用域总是关联定义该Closure的Scope环境,动态作用域则是使用执行该Closure的Scope环境。

类型

类型的本质在于它所定义的操作以及操作之间的关系和不变式。类型的实现关键在于满足类型规范的要求,而具体实现是可以变化的,使用者和测试用例都应该只依赖于类型规范而不依赖于具体实现。函数式的类型实现往往和类型规范是直接对应的,简单通用,但可能有性能问题,而命令式的类型实现往往会引入复杂的内部数据结构,但是其优点是高效。这两种实现并不是完全互斥的,有时候可以将二者相结合达到简单与高效的结合。下面我们就使用函数式的方式来实现数据类型。

自然数

下面的代码定义了0~9几个自然数(这种方式定义的自然数也称为Church数),并定义了+,*(幂)三种操作。

(def 0 (lambda (f) (lambda (x) x)))
(def succ (lambda (n) (lambda (f) (lambda (x) (f ((n f) x))))))
(def 1 (succ 0))
(def 2 (succ 1))
(def 3 (succ 2))
(def 4 (succ 3))
(def 5 (succ 4))
(def 6 (succ 5))
(def 7 (succ 6))
(def 8 (succ 7))
(def 9 (succ 8))
(def + (lambda (m) (lambda (n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))))
(def * (lambda (m) (lambda (n) (lambda (f) (n (m f))))))
(def ** (lambda (a) (lambda (n) (n a)))) // exp

为了方便直观演示,我们这里还定义了几个辅助的内建函数。

env.define('inc', function(v){
    return v ? v + 1 : 1;
});
env.define('println', function(){
    console.log.apply(this, arguments);
});
env.define('nil', null);

我们再定义一个方法,用于把Church数转为普通的数字。

(def church->int (lambda (n) ((n (lambda (x) (inc x))) nil)))
((3 (lambda (x) (println (church->int 5))))
;; output:
;; 5
;; 5
;; 5

(church->int 0) ;; => undefined
(church->int 6) ;; => 6

(church->int ((+ 1) 2)) ;; => 3 
(church->int ((* 2) 3)) ;; => 6
(church->int ((** 2) 3)) ;; => 8
布尔类型

布尔值及其操作定义

(def true (lambda (x) (lambda (y) x)))');
(def false (lambda (x) (lambda (y) y)))');
(def and (lambda (p) (lambda (q) ((p q) false))))');
(def or (lambda (p) (lambda (q) ((p true) q))))');
(def not (lambda (p) ((p false) true)))))');
(def if (lambda (p) (lambda (x) (lambda (y) ((p x) y)))))');

为了方便测试并查看效果,我们新增一个内建函数。

env.define('assert-equals', function(n1, n2){
    if (n1 !== n2) {
        throw new EvalError(n1 + " must equals " + n2);
    } else {
        return true;
    }
});

测试布尔类型上的操作。

(assert-equals ((and true) true) true) 
(assert-equals ((and true) false) false) 
(assert-equals ((and false) true) false) 
(assert-equals ((and false) false) false) 

(assert-equals ((or true) true) true) 
(assert-equals ((or true) false) true)
(assert-equals ((or false) true) true)
(assert-equals ((or false) false) false)

(assert-equals (not false) true) 
(assert-equals (not true) false) 

(assert-equals (((if true) 3) 5) 3)
(assert-equals (((if false) 3) 5) 5)
LISP中常用的数据类型cons(有序对)
(def cons (lambda (x y) (lambda (p) (((if p) x) y)))))
(def car (lambda (cons) (cons true)))
(def cdr (lambda (cons) (cons false)))

验证cons类型及其操作。

(def c (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 0))))))

(assert-equals (car c) 1)
(assert-equals (car (cdr c)) 2) 
(assert-equals (car (cdr (cdr c))) 3) 
目录
相关文章
|
敏捷开发 测试技术 项目管理
【软件设计师备考 专题 】准备软件设计师资格考试:复习指南和策略
【软件设计师备考 专题 】准备软件设计师资格考试:复习指南和策略
541 0
|
11月前
Seata框架在AT模式下是如何保证数据一致性的?
通过以上这些机制的协同作用,Seata 在 AT 模式下能够有效地保证数据的一致性,确保分布式事务的可靠执行。你还可以进一步深入研究 Seata 的具体实现细节,以更好地理解其数据一致性保障的原理。
360 50
|
11月前
|
负载均衡 Oracle 网络协议
Oracle中TAF与SCANIP全面解析
通过本文的解析,读者可以清晰地理解Oracle中TAF与SCAN IP的概念、工作原理及其在实际应用中的优势和局限性。TAF通过自动故障转移提升了会话的高可用性,而SCAN则通过简化客户端连接和负载均衡提升了集群的可管理性和扩展性。这两种技术在现代企业数据库架构中扮演着重要角色,能够显著提高系统的稳定性和可用性。
434 6
|
12月前
|
算法 数据可视化 计算机视觉
Python中医学图像处理常用的库
在Python中,医学图像处理常用的库包括:ITK(及其简化版SimpleITK)、3D Slicer、Pydicom、Nibabel、MedPy、OpenCV、Pillow和Scikit-Image。这些库分别擅长图像分割、配准、处理DICOM和NIfTI格式文件、图像增强及基础图像处理等任务。选择合适的库需根据具体需求和项目要求。
445 0
|
12月前
|
JSON Java 数据格式
Java Jackson-jr库使用介绍
Jackson-jr是专为资源受限环境设计的轻量级JSON处理库,适用于微服务、移动应用及嵌入式系统。它通过牺牲部分高级功能实现了更小体积和更快启动速度,非常适合对库大小敏感的项目。本文将介绍如何使用Jackson-jr进行JSON序列化与反序列化,并演示处理嵌套对象与数组的方法。此外,还介绍了自定义序列化与反序列化的技巧以及性能与功能的权衡。通过示例代码,展示了Jackson-jr在常见任务中的高效与灵活性。
175 0
|
监控 Cloud Native 安全
[云原生] 破局微服务通信:探索MegaEase服务网格的创新之路
[云原生] 破局微服务通信:探索MegaEase服务网格的创新之路
388 0
|
存储 JSON 前端开发
QT Http协议
QT Http协议
271 0
|
SQL 运维 DataWorks
EMR Serverless StarRocks + DataWorks 开启极速分析新体验
EMR Serverless StarRocks + DataWorks ,开启极速分析体验
1435 0
EMR Serverless StarRocks + DataWorks 开启极速分析新体验
|
otter 数据库连接 数据库
Otter支持同步整个实例
Otter支持同步整个实例
797 2
|
Web App开发 Rust JavaScript
认识 WebAssembly 与 Rust 实践
作者基于 WebAssembly 的兴趣写下本文,提供了一种未来在业务中遇到性能问题时的优化手段和思路。
654 0
认识 WebAssembly 与 Rust 实践