蚊章汇 - Gil Mizrahi
type: channel
link: https://linuxcn.bwsl.wang/author/1108/
description: Gil Mizrahi
items: 用 350 行代码从零开始，将 Lisp 编译成 JavaScript

用 350 行代码从零开始，将 Lisp 编译成 JavaScript
type: item
date: 2018-10-31T18:18:10+08:00
description: 我们将会在本篇文章中看到从零开始实现的编译器，将简单的类 LISP 计算语言编译成 JavaScript。完整的源代码在 这里。我们将会：自定义语言，并用它编写一个简单的程序实现一个简单的解析器组合器为该语言实现一个解析器为该语言实现一个美观的打印器为我们的用途定义 JavaScript 的一个子集实现代码转译器，将代码转译成我们定义的 JavaScript 子集把所有东西整合在一起开始吧！1、定义语言Lisp 族语言最迷人的地方在于，它们的语法就是树状表示的，这就是这门语言很容易解析的原因。我们很快就能接触到它。但首先让我们把自己的语言定义好。关于我们语言的语法的范式（BNF）描述如下：program ::= expr expr ::= <integer> | <name> | ([<expr>])基本上，我们可以在该语言的最顶层定义表达式并对其进行运算。表达式由一个整数（比如 5）、一个变量（比如 x）或者一个表达式列表（比如 (add x 1)）组成。整数对应它本身的值，变量对应它在当前环境中绑定的值，表达式列表对应一个函数调用，该列表的第一个参数是相应的函数，剩下的表达式是传递给这个函数的参数。该语言中，我们保留一些内建的特殊形式，这样我们就能做一些更有意思的事情：let 表达式使我们可以在它的 body 环境中引入新的变量。语法如下：let ::= (let ([<letarg>]) ) letargs ::= (<name> <expr>) body ::= <expr>lambda 表达式：也就是匿名函数定义。语法如下：lambda ::= (lambda ([<name>]) )还有一些内建函数： add、mul、sub、div 和 print。让我们看看用我们这门语言编写的入门示例程序：(let ((compose (lambda (f g) (lambda (x) (f (g x))))) (square (lambda (x) (mul x x))) (add1 (lambda (x) (add x 1)))) (print ((compose square add1) 5)))这个程序定义了 3 个函数：compose、square 和 add1。然后将计算结果的值 ((compose square add1) 5) 输出出来。我相信了解这门语言，这些信息就足够了。开始实现它吧。在 Haskell 中，我们可以这样定义语言：type Name = String data Expr = ATOM Atom | LIST [Expr] deriving (Eq, Read, Show) data Atom = Int Int | Symbol Name deriving (Eq, Read, Show)我们可以解析用该语言用 Expr 定义的程序。而且，这里我们添加了新数据类型 Eq、Read 和 Show 等实例用于测试和调试。你能够在 REPL 中使用这些数据类型，验证它们确实有用。我们不在语法中定义 lambda、let 或其它的内建函数，原因在于，当前情况下我们没必要用到这些东西。这些函数仅仅是 LIST （表达式列表）的更加特殊的用例。所以我决定将它放到后面的部分。一般来说你想要在抽象语法中定义这些特殊用例 —— 用于改进错误信息、禁用静态分析和优化等等，但在这里我们不会这样做，对我们来说这些已经足够了。另一件你想做的事情可能是在语法中添加一些注释信息。比如定位：Expr 是来自哪个文件的，具体到这个文件的哪一行哪一列。你可以在后面的阶段中使用这一特性，打印出错误定位，即使它们不是处于解析阶段。练习 1：添加一个 Program 数据类型，可以按顺序包含多个 Expr练习 2：向语法树中添加一个定位注解。2、实现一个简单的解析器组合库我们要做的第一件事情是定义一个 嵌入式领域专用语言 Embedded Domain Specific Language （EDSL），我们会用它来定义我们的语言解析器。这常常被称为解析器组合库。我们做这件事完全是出于学习的目的，Haskell 里有很好的解析库，在实际构建软件或者进行实验时，你应该使用它们。megaparsec 就是这样的一个库。首先我们来谈谈解析库的实现的思路。本质上，我们的解析器就是一个函数，接受一些输入，可能会读取输入的一些或全部内容，然后返回解析出来的值和无法解析的输入部分，或者在解析失败时抛出异常。我们把它写出来。newtype Parser a = Parser (ParseString -> Either ParseError (a, ParseString)) data ParseString = ParseString Name (I…