N 倍效率神器，使用 PEG 生成自己的解析器

作者：Tony

在进行项目开发时，都会有一些定制化的工具，用来做各种提升工作效率的任务，期间不可避免总要去解析一些形形色色的文件。如果想要清晰、高效的完成这项工作，就会大量用到解析器技术。今天就带大家来实现一个解析器。

通过本文，你将可以了解到：

• 解析器的应用场景
• 写好解析器所需要了解的基础知识和
• 使用 PEG (Parsing expression grammar，解析表达文法）和 PEG.js 生成一个解析器

解析技术基础

什么是解析器

A parser is a software component that takes input data (frequently text) and builds a data structure – often some kind of parse tree, abstract syntax tree or other hierarchical structure, giving a structural representation of the input while checking for correct syntax.

上面是来自 Wikipedia 对解析器的解释。解析器是为了将一段文本，转换成一个另一种数据形式，比如抽象语法树。

为什么要有解析器
通常讲到编译器，都会讲到解析器：通常计算机要去分析语义、生成目标代码或者计算结果，都需要一个更容易分析、读取的数据形式，但往往人类自然的表达方式都与计算机容易理解的数据形式不同。比如以下的例子：

这是人类用来表达四则运算的方式。然而计算机却并不容易去处理这样的文本：不仅数字、操作符都混合在了一起，而且还有优先级的问题要考虑，对计算机程序来说，是一种“反直觉“的输入。计算机程序会更容易理解下面这种形式的输入：

计算机可以很快知道操作符、操作数之间的数据关系，所以可以很快计算出。

而解析器一般要解决的问题就是：把输入（通常是文本）转换成计算机容易处理的形式。

解析器解析一段文本一般都会分为词法分析和语法分析两个步骤。

词法分析
词法分析会将这段文本按照一定的规则，分割成一个一个的词，这里叫 token，它有点类似于中文文本分词技术（因为英文等拉丁语系的语言，它们可以直接使用空格来进行分词；中文则需要通过规则、匹配来分词，所以这里 token 分割更像中文分词）。这里切割下来的每个 token，要把它的类型(num, mul, add)、它本身的文本以及位置信息等存下来。

文本在这个时候就被切割了一串 token。但是这个过程和语法是没有一丁点关系的，也就是说这里只管把文本切成一个一个，而不用管它们是否合法。

而这串 token 是词法分析的输出，也是语法分析的输入。一般词法分析是通过有限状态自动机来消费字符串，最后将输入文本分解为一串 token。因为和本文主题有所偏差，这里就不展开讲，有兴趣的同学可以搜索关键字去学习。

语法分析
语法分析会分析这串 token，然后解析成计算机容易理解的形式，甚至是直接计算出结果。比如下图就是一种可能的语法分析的输出。而一般语法分析会依赖于一些规则条目来进行解析，也就是文法（Grammar）。

一般计算机语言使用的是一种叫做 CFG 的文法来描述的。CFG，中文「上下文无关文法」。下面是一个 CFG 的例子：

// 这里约定小写字母为不可再拆分的单位
S -> aSb | ab

这种文法里的每个规则会有两种组成元素：非终结符和终结符。非终结符意思是它还可以再展开，用其他元素来表示（比如上面的 S ）；而终结符则表明它已经是最小的单位，无法再展开（比如上面的 a 和 b，一般指词法分析中的 token)。

CFG 每个文法规则左边都只有一个非终结符，而右边可以由非终结符和终结符组成，意思是，只要出现左边的非终符，都可以等价替换成右边的那一串表达式。

而 CFG 规定左边有且只有一个非终结符，意味着这个非终结符出现在哪，前后都有啥并不重要，只要出现它都可以等价替换右边的式子，所以叫做上下文无关。上下文指的是左边这个非终结符的上下文。

不过这里要注意的是，CFG 是一种「生成型文法」，意思是 CFG 本身只描述了如何产生该文法对应的语言，而并未定义如何去解析它。同一个 CFG 文法规则，在不同的解析器或者不同的场景下，解析的结果可能是不同的，就如同我们的自然语言也会包含二义性一样。后面我们要提到的 PEG 则是另一种形式的文法。

解析器一般是怎么实现语法分析的
按照一个文法解析一串 token，一般有两种方向：自顶向下解析和自底向上解析。

自顶向下解析所用的方法一般是预测：根据文法制定的规则，预测下一个应该出现的 token 是什么，输入里的下一个 token 是否符合，然后再决定是否往下走；如果不可以往下走，是否要回到错误发生的地方。

而自底向上分析所用的方法则是归约（化简）：根据文法规则试图去化简已经消费的 token 序列的末端，有则化简，没有则继续消费下一个 token，直到化简成一个合法的结果。

有一种经常被用于手写解析器的自顶向下解析方法叫做「递归下降解析」，你可以把上面的每个非终结符定义成一个函数，在这个函数的实现里，根据该非终结符的文法，如果碰到非终结符就调用对应的函数，如果是终结符就试图消费字符。而最后你也可以成功消费完所有文本，完成这个文本的解析工作。

解析器生成器
其实从上面的介绍可以看出，解析器是一项可以直接用代码写出来的东西，只要掌握一定的技巧，就可以看着一个文法，写出一个解析器。至少递归下降解析可以很快的写出来。但我们为什么仍然需要一个解析器生成器？

一个可能的原因是手写解析器其实是相对枯燥的一件事情，需要很多重复的劳动（是不是有点写CURD 时的感觉）。所以这些繁琐重复的步骤，自然会有人用自动化的方式来解决掉；

另一个原因可能是高效率的解析器往往都需要预先对文法做很多分析工作，以在真正解析的过程中达到最好的性能。虽然你也可以用脑子和纸笔去分析，但是那也是很繁琐的事情。

而通过文法自动直接生成一个高效率的解析器，也更具有可维护性，毕竟维护一堆代码和维护一个文法，区别还是比较大的。

当然，解析器生成器比较大的缺点是在于，不是每个文法对应的解析器都适合被生成器生成。有时候可能因为某个生成器的局限，你需要去将某个文法改写，以至于适合生成器使用。

PEG 文法介绍

PEG 文法

In computer science, a parsing expression grammar (PEG), is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.

PEG —— 解析表达文法，顾名思义，是一种用于解析的文法。它是由 Bryan Ford 发明于 2004 年，它出现的大环境是业界都在使用生成型文法如 CFG 来解决解析相关的问题。而为了更好的完成解析工作，解析表达文法作为一个解析过程的抽象表示，明确地定义了解析的规则，不允许有二义性的存在，更加利于进行解析工作。它可以用于简单的文本匹配、查找（比如可以替代正则表达式），也可以用于构建解析器。Python 之父 Guido van Rossum 在 2019 年曾经发表过一系列博客，表示自己正在学习 PEG，并且试图使用 PEG 来替代 Python 原有的解析器 pgen。对他来说，PEG 解决 pgen 的局限性，可以让未来的 Python 拥有更灵活的语法（当然了，也有人说，是因为 pgen 的局限性，才让 Python 保持了语法的简单）。PEG 会将整个文本读入，可以进行无限回溯，使得 PEG 使用者可以更轻松的制定语法：带来的成本只不过是更多的内存罢了，而内存在近 30 年已经变得越来越廉价。「Guido 的系列博客」实现了一个手写的 PEG 解析器，感兴趣的朋友可以去找来学习一下。

在 PEG 中，文法中每一条解析规则的形式都是：

A <- e

左边的 A 指的是一个非终结符，而 e 则是解析表达式。意思是碰到非终结符A时，它需要消费形如表达式 e 才能解析成功。比如：

SingleNum <- [0-9]

当碰到非终结符 SingleNum，则需要消费 [0-9] 才能解析成功 ；如果下一个字符不是 0-9，则解析失败。

这里的文法其实有点类似于正则表达式，[0-9] 指的也是 0-9 的数字中的一个。这里也一样支持 +?* 这种符号，具体的定义在下文表格可以找到。比如 + 指的就是匹配 1 个以上，比如文法：

Num <- [0-9]+

则当遇到非终结符 Num 时，它需要消费 1 个或多个 [0-9] 来完成解析。
右边的解析表达式中也可以包含非终结符，比如 SingleNum，所以以下文法也是成立的：

Num <- SingleNum+

它还支持一种类似于 OR 的写法，假设我们需要一个解析器，这个解析器可以判断输入是否是一个合法的数字，它可以是单独的数字，也可以是字符串形式的数字。
此时就是这么写的：

ValidValue <- Num / NumInStr
NumInStr <- "'" Num "'"

而这个符号 / 与常见的 CFG 文法有区别的是，它是有优先级的，谁先写，谁先尝试；如果前面的规则被成功匹配了，它后面跟着的其它规则就不会被匹配到（即便本来也能成功匹配）。比如在上述文法中，一旦 Num被成功匹配，NumInStr 就不会被匹配到。

比如我们使用上述文法解析字符串 '123' ：

从解析器的角度，可以知道：

• 第一个期望消费的字符是 [0-9]（从 Num一路向下推断可以得知）；如果得不到，那就消费一个 '(从 NumInStr 一路向下推断可以得知）。此时解析器消费了一个 '
• 第二个期望得到的字符是 [0-9] (从Num一路向下推断可知）；如果得不到，那就是解析错误，此时解析器消费了一个 1
• 第三个期望得到的字符是 [0-9]；如果得不到，那就消费一个 ' (因为+是匹配一个以上，这里这两种可能都是可行的，但是 [0-9] 更靠前，优先级更高）此时消费了一个 2
• …
• 最后解析器如愿以偿得到一个 '，解析完成
  

我们可以看到，需要消费下一个字符的时候，基于前面解析的进度，都可以明确地、有优先级地确定接下来期望消费的字符。所以给定一个 PEG 文法和一段字符串，它解析的结果总是确定的。

具体的文法定义方法其实与正则表达式有点类似，但是 PEG 支持嵌套、递归。具体见下表：

生成型文法 vs 解析型文法
其实讲到解析型文法 PEG 的时候，总是避不开上面说到的生成式文法如 CFG。它们两个总是会被放到一起比较。

一个 PEG 的例子是长这样的：

S <- 'if' Conditions 'then' Statements 'else' Statements /
 'if' Conditions 'then' Statements

PEG 其实乍一看也挺像 CFG 的，但是实际上有所差别的是，CFG 是一种「生成型文法」，它表明了怎么生成符合某个文法规则的字符串，而没有定义如何去解析，没有定义如何去解决二义性。基于CFG 的解析方法，解析器需要自行去理解文法，确定是否需要解决冲突，如何解决冲突。

而 PEG 是一种「解析型文法」，它就是为解析而生的，它直接定义解析的行为，定义了如何去解析一个文本，其中最重要的是明确所有规则的优先级。基于 PEG 实现的解析器只要跟着这个规则走就可以了，没有其他选择。

所以用一个 CFG 文法来解释一段字符串，可能会出现不同的解析结果（与不同的解析器、不同的场景有关）；而一个 PEG 文法解析一段字符串，只可能出现一种解析的结果（因为文法本身就规定了解析的规则）。这可能是他们之间最大的区别了。

而体现到实际的文法上，最大的区别就在于，PEG 文法中常见的 / ，与 CFG 文法中常见的 | 之间的差异。PEG 文法中的 / 是一种自带优先级的符号，它表示这几个备选方案，按顺序逐个尝试，前面的成功匹配了，后面的就放弃了；而 CFG 中的 | 则是并列关系，表示这几个都是可以接受的，没有先后顺序。

另外，PEG 习惯在一个文法里同时定义了词法和语法，所以 PEG 的解析器一般也不会有词法分析这个步骤。

左递归问题
这里其实还有一个经典的问题，称为左递归，看以下例子：

Number <- Number? SingleNum
SingleNum <- [0-9]

是的这样看起来好像也合理，一个数字的解析表达式可以是递归的，Number + 一个数字，它还是 Number。但是如果解析器按照上面的解析方法试图去推断第一个期望的字符是什么时，就会发现，它陷入了一个无限递归「Number → Number → Number …」，它始终不知道下一个期望消费的字符是什么。

一般这种情况下就要自己改写文法，消除左递归，比如这么写：

Number <- SingleNum Number?
SingleNum <- [0-9]

这样则不会出现类似的问题，因为第一个期望的字符总是 [0-9]，然后第二个字符开始它可以是 [0-9]，也可以是 end ，当然也就等价于 [0-9]+ 。

当然了这里只是讲到了 PEG 文法的一些规则和解析的流程；而实际解析中，你想得到的结果不只是输入是否合法，而是一个解析结果，比如一棵 AST。

PEG.js 介绍
大部分的主流语言都有对应的 PEG 解析器生成器，比如 Go 的 pigeon，Java 的 parboiled，具体可以查看维基百科条目 Comparison of parser generators ，里面有 PEG 解析器生成器的详细列表。

这一节将介绍一个由 PEG 文法自动生成 JavaScript 版解析器的生成器：PEG.js。根据其项目主页的说法，目前还是在一个比较早期的阶段，尚且不太适合用于生产环境，但是对我们学习来说已经足够了。很遗憾的是，虽然已经有很多被证实的自动解决左递归问题的理论和具体实现，但是该库依然不直接支持左递归文法，如果文法中出现左递归，生成器将会抛出一个错误，由用户自行去改写，去掉左递归文法。

项目的具体细节可以查看其 repo: http://github.com/pegjs/pegjs。

有很多优秀的项目也在使用 PEG.js，官方在其 repo 中提供了一个列表，有兴趣可以前往查看。

PEG.js 一般使用方法
大部分情况下，PEG.js 的写法与 PEG 文法写法是一样的，不太一样的是这里使用 = 来代替 <-。在每个文法的后面也可以用花括号嵌入一些 JavaScript 代码，这些代码可以在该非操作符被成功解析时做一些操作，返回值也将被引用这个非操作符的表达式获得。

x:(Y) 的写法意思是，把解析表达式 Y 这部分，赋值给 x，在嵌入的代码里面可以直接使用。在默认情况下，因为我们的输入都是字符，所以解析器得到的也都是字符；类似 +* 这种匹配多个的情况时，解析器则将它们解析成数组。所以下方代码 s_num 会是一个数组，数组中都是SingleNum（也就是字符 [0-9] ）。

Num = s_num:(SingleNum+) {
    return parseInt(s_num.join(''))
}

SingleNum = [0-9]

嵌入的代码返回值将作为这个非终结符的值。比如下方代码， Num 赋值给 number ，这里的 number 根据上述代码可以得知，会是一个整型变量。

NumInStr = "'" number:(Num) "'" {
    return number
}

当写完这些文法规则、嵌入的代码后，执行：

cat example_parser.pegjs | pegjs > example_parser.js

即可得到生成好的解析器，然后在自己的项目里引入：

const parser = require('./example_parser.js');
const result = parser.parse(`'123'`);
console.log(result) // output: 123

这样就得到解析的结果了。

另外 PEG.js 官方还提供了一个在线尝试的网站
https://pegjs.org/online，也可以在上面直接试验。
下面给出一个实际的例子——如何写一个 Spanner DDL Parser。

例子：用 PEG.js 生成一个 Spanner DDL Parser
如果说上面只是小试牛刀，都是些几乎没啥用的例子，那么这里我们就给出一个稍微有用一点的例子。我们团队有时候会需要一些自动化的工具，比如我们需要从一个 CREATE TABLE 语句去生成一些 model 层的代码，这时我们得想办法去解析一个 DDL 语句。

当然了，用 Spanner 的DDL 作为例子还有另一个好处，官网提供了详细的语法描述：
Data Definition Language | Cloud Spanner | Google Cloud

这算是比较重要的参考资料，可以让你写出最正确的文法。这里大标题虽然写着 DDL Parser，不过我们目前只实现 CREATE TABLE 部分。

我们完成的目标是，当我们有这样的输入：

CREATE TABLE students (
 Id INT64 NOT NULL,
    FirstName STRING(0x46) NOT NULL,
    LastName STRING(MAX),
    CreatedAt timestamp NOT NULL OPTIONS (allow_commit_timestamp=true)
) PRIMARY KEY (Id DESC, FirstName ASC);

我们希望得到这样的输出：

{
 "table_name": "students",
 "column_defs": [
    {
 "name": "Id",
 "type": "int64",
 "not_null": true,
 "options": null
    },
    {
 "name": "FirstName",
 "type": "string(70)",
 "not_null": true,
 "options": null
    },
    {
 "name": "LastName",
 "type": "string(MAX)",
 "not_null": false,
 "options": null
    },
    {
 "name": "CreatedAt",
 "type": "timestamp",
 "not_null": true,
 "options": {
 "allow_commit_timestamp": true
      }
    }
  ],
 "primary_key": {
 "keys": [
      {
 "name": "Id",
 "seq": "desc"
      },
      {
 "name": "FirstName",
 "seq": "asc"
      }
    ]
  }
}

在 PEG 解析器中，是没有词法分析这一步的，所以解析器对字符串的消费是以字符为单位的。而我们的输入其实是以不定长的空格、换行符来分割成一个一个的词（关键词、变量名等）的。比如 CREATE 和 TABLE 之间事实上可以有换行符，有空格，所以我们需要自己做一个分词出来。一个比较简单的办法，先定义一个空白符的文法：

_ = [ \\r\\n]*

这里的 _ 只是一个缩写的形式，表示这里是一个或者多个空白符，你也可以写 WhiteSpaces 之类的。

这里写一个约定：下述文法里，除了空白符 _ ，非终结符统一用驼峰命名，JavaScript 变量统一用下划线命名。

为了让非终结符前后可以匹配一个或多个空格，并且让引用它的文法更简洁，我们统一在每个非终结符的解析式前后都加上 _。比如：

// 字符串后写上 i 表示它不区分大小写
Create = _ "create"i _Table = _ "table"i _

观察我们上面的输入语句（当然了更好是查看官方的文法定义），可以知道我们最顶层的语法应该是这样的：

DDL = Create Table TableName LeftPara ColumnDefs RightPara PrimaryKey? Semi?

而每个非终结符，都很可能需要嵌入一段 JavaScript 代码，来返回给上层对应的数据。最顶层的 DDL 的返回值则是最终的解析结果。所以应该是这样的（可以对照我们的期望输出）：

DDL = Create Table table_name:(TableName) LeftPara column_defs:(ColumnDefs) RightPara primary_key:(PrimaryKey?) Semi {
 return {
        table_name,
        column_defs,
        primary_key
    }
}

而其中 TableName (参照官方的规范）：

// 一个分组内的解析结果也是一个数组，这里需要把两部分的字符拼装起来
Identity = _ chars:([a-zA-Z][0-9a-zA-Z]+) _ {
 return [
      chars[0],
      ...(chars.length === 2 ? chars[1].join('') : [])
    ].join('')
  }

TableName = Identity

而 ColumnDefs 则稍显复杂，它的组成大概长这样，其中 ColumnDef 可以是任意多个：

ColumnDefs = ColumnDef,ColumnDef,ColumnDef(,)

最末尾的逗号可加可不加。现在假设我们已经有了 ColumnDef，第一个最符合直觉的写法可能是:

// 每个 ColumDef 里包含了一个逗号
ColumnDefs = _ ColumnDef+ _

但是我们好像忽略了逗号的感受，因为你无法知道你的 ColumnDef 是不是最后一个，也就不知道这个逗号能不能省。所以有了第二个符合直觉的想法：

ColumnDefs = _ ColumnDefs Comma ColumDef Comma? _

看起来是合理的。但是很遗憾，PEG.js 无法处理左递归语法。
所以最后我们决定这么写：

ColumnDefs = _ (ColumnDef Comma)* (ColumnDef?) _

如果输入中最后带了逗号，则它会在前半部分被匹配；如果不带逗号，则会在后半部分被匹配。而为了让它返回一个包含所有 columnDef 的数组，需要把这两部分拼装起来，比如：

ColumnDefs = 
  head:((ColumnDef _ ",")*) tail:(ColumnDef?) _ {
 return [
      ...head.map(item => item[0]),
      ...(tail ? [tail] : [])
    ]
  }

而 ColumnDef 又是这么定义的：

ColumnDef = 
  _ name:(Identity) type:(Type) not_null:(NotNull?) options:(Options?) _ {
 return {
      name,
 type,
      not_null: Boolean(not_null),
      options
    }
  }

剩下的代码也是大致类似，其实就是每一个非终结符都各司其职，将自己的结构化数据返回到上一层，最后会被汇总到 DDL 这个非终结符，得到最终结果。最后，写法随意、不易处理的 Spanner DDL 语句，被处理成适合计算机程序使用、分析的数据形式。



【关于AfterShip】

AfterShip 是一家成立于 2012 年的总部设立在香港的国际化公司，在深圳和香港拥有产品研发中心，为全球超过十万家 B 端客户提供包括营销推广服务、面单打印、物流跟踪和退货管理等的一系列电商 SaaS 服务，是国际物流查询领域里面的龙头企业，当前也推出了两款面向 C 端用户的 Mobile App 产品。

公司自 2014 年起已实现持续盈利，且每年 100% 增长。业务遍布全球，与全球 700 多家物流公司达成合作，涉及 30 多种主流语言，客户包括有 Amazon，Wish，eBay，Paypal，Groupon 和 Etsy 等。

我们以产品为驱动，技术为核心，从公司成立开始，便大量使用优秀开源软件，拥抱创新科技，公司有良好的 SaaS 付费习惯，浓厚的工具化和工程师文化。

同时注重人才培养，在这里工作，每个人都可参加从用户沟通、需求讨论、产品开发到上线部署的环节，团队国际化，公司业务快速发展，我们需要大量的人才加入我们，我们能提供成长为面向未来的国际化复合性人才的空间和机会。

也欢迎通过下面二维码内推朋友拿奖金哦～

https://app.mokahr.com/m/recommendation-apply/aftership/792 (二维码自动识别)