使用 Go 构建一个解释型语言

我目前正参与我们的一个大项目，Alloy。Alloy 是一种编译型的编程语言。我目前在计算机及编程领域最喜欢的一个爱好就是语言。事实上，我认为每个程序员都应该对编程语言是如何工作的有个基本的了解，这就是我写这个系列的原因。

这是系列文章中的第一篇文章。该系列将描述我已经写过的代码，来向你展示如何制作自己的编程语言。这里注意一下，本文假设你对编译器/解释器的理论/实践有已有很少或没有过往经验。还有要注意的是，这一系列的文章不是介绍编程或Go编程的。

什么是解释器（interpreter）？

解释器会直接执行或表现写在某特定脚本语言中的指令。这可以是一种已存在的脚本语言，像 Python或者 Ruby。它也可以是一种你自己创造的脚本语言，这将是我们在这里要做的。这一系列将从Go的基础开始指导你实现自己的脚本语言/解释器“玩具”。

为什么是“玩具”脚本语言/解释器？

解释器可以是极其复杂的。现代解释器（比如Ruby或Python）十分庞大，包括成百上千行，甚至多达百万的代码量。这对一个新手来说不太容易理解。玩具语言是个更为简化的版本，它们常常跳过或者省去一些短语（在这里我们将不考虑优化）。制造一种玩具语言是一个理解它们如何工作的有效方法，当开始使用它们时，它们将实实在在地帮助你理解，即使你不是在一个已经存在的解释器（如Rust）上工作。

编程语言

你可以用任意一种你喜欢的语言构建一个解释器。在这个案例中，我将使用Go。这之前我还没写过许多Go，所以对我来说这也是一个学习的经历！然而如果你不习惯用Go写，你可以用如下任一种语言制作你的解释器，可以是 C，Java，或者甚至是 JavaScript。

小结

由于在当今世界有如此多的解释器和编译器，因此有许多工具可以来帮助你制作它们。你需要决定是否考虑偷偷使用一个外部工具，或者你想要自己写所有的代码。我更喜欢后者，因为我觉得如果我使用某个外部工具来代劳，我就学不会它如何工作。不过这完全取决于你自己。在解释器环境中，你是否使用这些工具会在编译器/解释器社区引起非常强烈的争论。一些人会告诉你如果你不用ANTLR，BISON或者其它一些工具那么你会出错。另一些人会说完成它的唯一方法就是亲手写你自己的词汇分析器（lexer）和语法分析器（parser）。最后，这是你的选择，但在这一系列文章中，我会至少会涵盖如何构建词汇分析器（Lexer）和语法分析器（Parser）。

理论

在深入之前，我们需要讲解一下理论。

什么是词汇分析器和语法分析器

如果你看到这一段落，并困惑于我所指的词汇分析器和语法分析器，那么不用担心。典型做法是把这个分析过程分成不同的阶段。有些阶段是可选的，换句话叫做优化阶段。但是大部分现代解析器几乎处理所有阶段。让我们深入去看看这些阶段吧。

词法分析

第一阶段是语法分析，基本上就是一个分词器。词法分析、解析器或者语法分析把字符或者输入流分割成标记。这些标记以列表或者容器等数据结构存成标记流。解析器通过归类这些词（输入流中的符号字符串），给于特定的标记某种含义。例如，*，=，+等词可以归为操作符，tost 和bacon可以归为字符串常亮，而’a‘和’b‘则是字符。

解析

解析器是一个翻译组件，它用来接收数据的输入，一个词法分析器产生令牌列表，并产生一个表达式，通常是一种抽象的语法树，或其他结构。解释器遵循的规则被叫做语法，它是你定义的一种语言的方式，这些语法诸如Extended Backus- Naur Form (EBNF)和 BNF (Backus-Naur Form)，它们被用来描述一种语言的语法。下面是一个被写成EBNF语法的例子：

letter = "A" | "a" | ... "Z" | "z" | "_";
digit = { "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" };
identifier = letter { letter | digit };

这可能对你没有任何意义。你可能认识这些在编程语言中的符号，例如管道|，花括号{}。所有的符号都有特殊的含义：

{ }   - denotes repetition  
|     - denotes an option, similar to OR
[...] - optional terminal/nonterminal
;     - termination  
=     - definition  
...   - sequence
"..." - terminal string

我们在后面将着眼于更多的一些符号. 上面的示例定义了一个“生产规则”. 一个生产规则可能包含两个词汇元素: 非终端和终端. 终端是不能使用语法规则不能被改变的文字. 非终端则是可以被替换的符号, 可以把它看做是一个占位符或者一个变量. 它们有时会被称为“语法变量”. 在上面的示例中, 标识符，字母和数字都是非终端符号. 而 "Z", "0", "1", 都是终端符号的例子，它们是常量字符，也就是说它们不能被改变.

现在来看，上面的语法中所有的符号都意味着什么呢? 一个字母的定义是:

letter = "A" | "a" | ... "Z" | "z" | "_";

为了能够理解，要像读英语一样阅读它，例如，上面的语法被读作 “A” 或者 “a” 到 “Z” 或者 “z” 或者 “_”. 因此一个字母可以是任何从 a-Z 或者一个下划线的东西.

我们如此定义一个数字:

digit = { "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" };

这意味着一个数字可以是 “0” 或者 “1” 或者 “2” … 你理解到点子上了. 不过, 要注意这里的大括号. 如果你还记得我们在上面提供的列表, 括弧代表了重复, 指定重复 0 到 n 次, 这里的n可以是任何一个数字. 这就意味着一个数字可以是 0 - 9 总共重复 n 多次, 因此 123 是对的, 5123 也是对的.

最后是标识符:

identifier = letter { letter | digit };

目前我们理解了字母（letter)和数字（digit)的意思, 我们现在就能够理解这个小的生产规则. 基本上，一个标识符必须以一个字符开头，其后可以是0个或者更多个不同字母或者数字的重复. 例如，a_, a_a, a_1, a__, 等等都是正确的标识符.

这两个阶段的词法和语法解析通常指的是作为前端的编译器和解释器。现在，让我们开始写一些代码，我将使用GO来编写。所有的源代码将公布在我的 Github页面上。如果你接着使用GO来编写，首先为你的项目建立一个新的目录并且设置好你的main go文件。刚好，我编写了一个简单的hello world文件来进行测试。GO拥有一个神奇的工作空间系统，因此一开始，你就需要创建你的工作空间，我一直使用Linux来作为我的工作空间,因此我使用GO设置$HOME/go 的环境变量
。为方便起见，GO推荐我们增加这个设置到达我们的路径：

mkdir $HOME/go 
export PATH=$PATH:$GOPATH/bin

我的项目的基本路径是在 github.com/felixangell。

你可以找到你想要的，或者你的 github 用户名：

mkdir -p $GOPATH/src/github.com/yourusername

现在开始设置我们的解释器程序，我们在个人目录下创建一个文件夹，名字可以是你给这个解释器起的任何名字，我叫它 vident。我们进入这个目录。

mkdir $GOPATH/src/github.com/felixangell/vident
cd $GOPATH/src/github.com/felixangell/vident

然后我们创建一个简单的文件作为测试用，可以直接拷贝这一部分：

package main
 
import "fmt"
 
func main() {
  fmt.Printf("hello, world\n");
}

把他保存到我们刚刚建立的文件夹 vident 中，名字为 main.go。现在我们便以并运行它：

go install
vident

因为我们工程目录结构系统，我们需要添加 bin 目录到我们的目录，然后简单的运行上面的代码。当你运行时，你应该可以看到输出了“hello, world”。

那么接下来我们要定义我们的语言。Vident 是一门简单的语言，我们从一些小的特性入手，然后我们再转移到复杂的示例。下面是 Vident 的一个代码实例：

let x = 5 + 5
print: x, "hello", x

我需要把->改为:，否则熟悉 Tumblr 格式的人对它很多抱怨，抱歉！我们语言的 EBNF 语法：

letter = "A" | "a" | ... "Z" | "z" | "_";
digit = { "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" };
identifier = letter { letter | digit }; 
number_literal = digit | [ "." digit ];
string_literal = """ letter { letter } """;
char_literal = "'" letter "'";
literal = number_literal | string_literal | char_literal;
binaryOp = "+" | "-" | "/" | "*";
binary_expr = expression binaryOp expression;
expression = binary_expr | function_call | identifier | literal;
let_stat = "let" identifier [ "=" expression ];
arguments = { expression "," };
function_call = identifier [ ":" arguments ];
statement = let_stat | function_call;

目前我们已经为这门语言引入了一些东西，最明显的是方括号。方括号表示一个可选值，例如：

let_stat = "let" identifier [ "=" expression ];

这代表 let x 和 let x = 5 + 5 都是有效的，第一个是一个定义，比如定义变量，第二是显示的变量声明，即定义变量并声明值。

现在看上面的语法可能会有点复杂，但如果你一点点的靠近去理解它，它就会比你想象的更加简单. 注意，我们不会一下就全部实现它,而是按阶段分部分去着重于语法的每一个部分并进行实现!

不管怎么样，如上就是第一部分! 敬请关注接下来的章节，我们将会编写词法分析器，而我们也会讨论更多有关解释器后端的内容.