前言

通过开发一门类 Lisp 的编程语言来理解编程语言的设计思想，本实践来自著名的《Build Your Own Lisp》。

代码实现：https://github.com/JmilkFan/Lispy

前文列表

《用 C 语言开发一门编程语言 — 交互式解释器l》

使用 MPC 库来实现一个语法解析器

MPC（Micro Parser Combinators）是一个用于 C 的轻量且强大的解析器组合库。你可以使用这个库为任何语言编写语法解析器。

编写语法解析器的方法有很多，使用 MPC 的好处就在于，它极大地简化了原本枯燥无聊的工作，你只需要关注编写高层的抽象语法规则就可以了。

MPC 的功能特性：

词法分析器（基于正则表达式）的生成器；
语法分析器的生成器；
支持 Type-Generic（泛式类型）；
支持 Predictive（预测）；
支持 Recursive Descent（递归下降）；
易于集成到 C 语言项目（以一个源文件的形式存在）；
自动生成错误消息。

安装

MPC 库的安装非常简单，只需要将源码下载，把源文件 Copy 到我们的 C 语言项目中，然后在项目中包含 mpc 的头文件并链接 MPC 库即可。

$ git clone https://github.com/orangeduck/mpc.git

$ cd mpc
$ cp mpc.c mpc.h ../lispy

引入到 main.c：

#include "mpc.h"
1

编译：

gcc -std=c99 -Wall main.c mpc.c -lreadline -lm -o main
1

-lm：链接数学（Math）库。

快速入门

在这里插入图片描述

下面我们以编写一个 Doge（the language of Shiba Inu，柴犬语）语言的语法解析器为例，来快速熟悉 MPC 的用法。

首先解构一下 Doge 语言的语法结构：

Adjective（形容词）：wow、many、so、such。
Noun（名词）：lisp、language、c、book、build。
Phrase（短语）：由 Adjective 和 Noun 组成。
Doge（柴犬语）：由若干个 Phrase 组成；Phrase 又由 Adjective 和 Noun 组成。

然后，我们就可以尝试使用 MPC 来定义 Doge 语言的语法解析器了：

Step 1. 使用 MPC 定义 Adjective 和 Noun，为此我们创建两个 Parser（解析器）。
- mpc_or() 函数会返回一个 Parser 类型，该解析器表示 “取其一”，因为我们需要从 Adjective 和 Noun 中 “各取其一” 来组成 Phrase。

/* Build a parser 'Adjective' to recognize descriptions */
mpc_parser_t *Adjective = mpc_or(4, 
  mpc_sym("wow"), mpc_sym("many"),
  mpc_sym("so"),  mpc_sym("such")
);

/* Build a parser 'Noun' to recognize things */
mpc_parser_t *Noun = mpc_or(5,
  mpc_sym("lisp"), mpc_sym("language"),
  mpc_sym("book"),mpc_sym("build"), 
  mpc_sym("c")
);
56
7
8
9
10
11
12

Step 2. 使用已经定义好的 Adjective Parser 和 Noun Parser 来组成 Phrase Parser。
- mpc_and() 函数会返回一个 Parser 类型，该解析器只接受各 “子句” 按照顺序出现的语句。所以我们将先前定义的 Adjective Parser 和 Noun Parser 传递给它，表示：形容词后面紧跟着名词组成的短语。
- mpcf_strfold 和 free 函数，则指定了各个语句的 Fold（组织）及 Free（释放）方式。在 mpcf_strfold 和 free 函数的帮助下，我们不用担心什么时候加入和丢弃输入，它们将自动帮助我们完成。

mpc_parser_t *Phrase = mpc_and(2, mpcf_strfold, Adjective, Noun, free);
1

Step 3. 使用 Phrase Parser 来最终定义 Doge Parser，Doge 是由若干个 Phrase 组成的，mpc_many() 函数表达的正是这种逻辑关系。

mpc_parser_t *Doge = mpc_many(mpcf_strfold, Phrase);
1

上述语句表明 Doge 可以接受任意多条语句。这也意味着 Doge 语言是多样的。下面列出了一些符合 Doge 语法的例子：

/* 一条 Doge 语句由若干个 Phrase 组成，一个 Phrase 由一个 Adjective + 一个 Noun 构成。 */
"wow book such language many lisp"  
"so c such build such language"
"many build wow c"
""
"wow lisp wow c many language"
"so c"
56
7

通过上述步骤，我们简单的定义了一门 Doge 语言的描述自己实现了一门 Doge 语言的语法解析器。还可以继续使用 mpc 提供的其他函数，一步一步地编写能解析更加复杂的语法的解析器。

但是很显然的，上述的代码实现方式并不友好，随着语法的复杂度的增加，代码的可读性也会越来越差。所以 mpc 还提供了一系列的函数来帮助用户更加简单地完成常见的任务，使用这些函数能够更好更快地构建复杂语言的解析器，并能够提供更加精细地控制。具体的文档说明可以参见项目主页*（https://github.com/orangeduck/mpc）*。

更优雅的写法

下面，我们使用 MPC 提供的另一种更加简易的代码实现方式来编写 Doge 语法解析器 —— 将整个语言的语法规则写在一个长字符串中，而不是使用啰嗦难懂的 C 语句。

我们也不再需要关心如何使用 mpcf_strfold 或是 free 参数组织或删除各个语句。所有的这些工作都是都是自动完成的。

mpc_parser_t* Adjective = mpc_new("adjective");
mpc_parser_t* Noun      = mpc_new("noun");
mpc_parser_t* Phrase    = mpc_new("phrase");
mpc_parser_t* Doge      = mpc_new("doge");

mpca_lang(MPCA_LANG_DEFAULT,
  "                                           \
    adjective : \"wow\" | \"many\"            \
              |  \"so\" | \"such\";           \
    noun      : \"lisp\" | \"language\"       \
              | \"book\" | \"build\" | \"c\"; \
    phrase    : <adjective> <noun>;           \
    doge      : <phrase>*;                    \
  ",
  Adjective, Noun, Phrase, Doge);

/* Do some parsing here... */

mpc_cleanup(4, Adjective, Noun, Phrase, Doge);
56
7
8
9
10
11
12
13
14
15
16
17
18
19

使用 mpc_new() 函数定义 Parser 的名字。
使用 mpca_lang() 函数定义这些 Parser 的内容，以及多个 Parsers 之间的逻辑关系，从而最终构成一门语言的语法规则。
- 第一个参数是操作标记，在这里我们使用默认选项 MPCA_LANG_DEFAULT。
- 第二个参数是 C 语言的一个长字符串。这个字符串中定义了具体的语法规则。每个规则分为两部分，用冒号 : 隔开，使用 ; 表示规则结束：
  - 冒号左边：是语法规则的名字，e.g. adjective、noun、phrase、doge。
  - 冒号右边：是语法规则的定义，e.g. adjective：wow、many、so、such。

mpca_lang() 函数就是对 mpc_many()、mpc_and() 、 mpc_or() 这些函数的封装，自动地完成这些函数的工作，让 Parser 定义的代码变得干净利落，不拖泥带水。

定义语法规则的一些特殊符号的作用如下：
在这里插入图片描述