最近，我发了一条推特，我喜欢上 lambda 演算了，它简单、强大。

我当然听说过 lambda 演算，但直到我读了这本书 《类型和编程语言》（Types and Programming Languages） 我才体会到其中美妙。

已经有许多编译器/解析器/解释器（compiler / parser / interpreter）的教程，但大多数不会引导你完整实现一种语言，因为实现完全的语言语义，通常需要很多工作。不过在本文中， lambda 演算（译者注：又写作“λ 演算”，为统一行文，下文一律作 “lambda 演算”）是如此简单，我们可以搞定一切！

首先，什么是 lambda 演算呢？维基百科是这样描述的:

lambda 演算（又写作 “λ 演算”）是表达基于功能抽象和使用变量绑定和替代的应用计算数学逻辑形式系统。这是一个通用的计算模型，可以用来模拟单带图灵机，在 20 世纪 30 年代，由数学家奥隆索·乔奇第一次引入，作为数学基础的调查的一部分。

这是一个非常简单的 lambda 演算程序的模样：

lambda 演算中只有两个结构，函数抽象（也就是函数声明）和应用（即函数调用），然而可以拿它做任何计算。

1. 语法

编写解析器之前，我们需要知道的第一件事是我们将要解析的语言的语法是什么，这是 BNF（译者注：Backus–Naur Form，巴科斯范式， 上下文无关的语法的标记技术） 表达式：

语法告诉我们如何在分析过程中寻找 token 。但是等一下，token 是什么鬼？

2. Tokens

正如你可能已经知道的，解析器不会操作源代码。在开始解析之前，先通过 词法分析器（lexer）运行源码，这会将源码打散成 token（语法中全大写的部分）。我们可以从上面的语法中提取的如下的 token ：

我们来建一个可以包含 type （以上的任意一种）的 Token 类，以及一个可选的 value (比如LCID 的字符串)。

3. 词法分析器( Lexer )

现在我们可以拿上面定义的 token 来写 词法分析器（Lexer） 了， 为解析器解析程序提供一个很棒的 API 。

词法分析器的 token 生成的部分不是很好玩：这是一个大的 switch 语句，用来检查源代码中的下一个字符：

下面这些方法是处理 token 的辅助方法：

• next(Token): 返回下一个 token 是否匹配 Token
• skip(Token): 和 next 一样, 但如果匹配的话会跳过
• match(Token): 断言 next 方法返回 true 并 skip
• token(Token): 断言 next 方法返回 true 并返回 token

OK，现在来看 “解析器”！

4. 解析器

解析器基本上是语法的一个副本。我们基于每个 production 规则的名称（::= 的左侧）为其创建一个方法，再来看右侧内容 —— 如果是全大写的单词，说明它是一个 终止符 （即一个 token ），词法分析器会用到它。如果是一个大写字母开头的单词，这是另外一段，所以同样为其调用 production 规则的方法。遇到 “/” （读作 “或”）的时候，要决定使用那一侧，这取决于基于哪一侧匹配我们的 token。

这个语法有点棘手的地方是：手写的解析器通常是递归下降（recursive descent）的（我们的就是），它们无法处理左侧递归。你可能已经注意到了， Application 的右侧开头包含 Application 本身。所以如果我们只是遵循前面段落说到的流程，调用我们找到的所有 production，会导致无限递归。

幸运的是左递归可以用一个简单的技巧移除掉：

4.1. 抽象语法树 （AST）

进行分析时，需要以存储分析出的信息，为此要建立 抽象语法树 ( AST )on-h"> ε  # empty