通过 PEG.js 实现一个 JSON Parser

前言

最近想重拾编译原理，还记得编辑原理的基本流程：

词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成 -> 代码优化 -> 目标代码生成

对于几乎没有学过编译原理的人来说，充分理解并掌握这么多流程的确不现实，但可以从实现一个最简单的 JSON Parser 入手。

对于 Parser 来说，主要负责的是词法分析、语法分析和语义分析。

其中，词法分析将代码中的关键字、变量名、字符串、直接量和大括号等等转换成标记（token）并归类，这一步叫 tokenize。

对于语法分析和语义分析的定义如下：

语法分析是编译过程的一个逻辑阶段。 语法分析 的任务是在词法 分析 的基础上将单词序列组合成各类 语法 短语，如“程序”，“语句”，“表达式”等等. 语法分析 程序判断源程序在结构上是否正确. 源程序的结构由上下文无关文法描述.

语义分析是编译过程的一个逻辑阶段， 语义分析 的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。 语义分析 是审查源程序有无 语义 错误，为代码生成阶段收集类型信息。

通常经过源代码在经 Parser 处理过后，就能生成中间代码。中间代码是计算机处理程序的主要形式，一般使用 AST（Abstract Syntax Tree，抽象语法树）来存储和表示。因为 JSON 字符串在解析后就是一个JavaScript对象，且无需再另行处理，因此我们在这个简单的 JSON Parser 中可以跳过 AST 的生成，直接输出对象值。

PEG（Parsing Expression Grammar，解析表达式文法），是一种解析形式文法。这种文法用一个识别字符串的规则的集合来描述某种形式语言，以纯公式的形式的展现递归下降解析器的基础语法。 PEG 与 CFG（Context-Free Grammar，上下文无关文法）相比，最关键的不同就是 PEG 的选择操作符是有序的，且对应某个非终结符，必须且只能有一个的解析规则。

PEG.js 是 PEG 的 JavaScript 语言实现，并基于解析表达文法定义了一套自己的语法规则。最简单一个解析整数的示例如下：

Integer
  = [0-9]+ {
    return parseInt(text());
  }

其中，Integer 是一个非终结符， = 符号后面是对该非终结符的定义： [0-9]+ 表示需要由一个到多个 0 到 9 的整数组成（语义和正则表达式类似）。最后面由 {...} 包裹的块状语句是一个 JavaScript 函数片段，用以处理前面得到的解析结果。其中 text() 用来获取该文法解析到的文本，并将其通过 parseInt 这个 JavaScript 函数转换成 JavaScript 整数值，最终将处理过后的值作为该非终结符的值。

这段 PEG 规则代码不可直接由 JavaScript 执行，可以通过 PEG.js 将该格式编译生成可以由 JavaScript 直接执行的 Parser 代码，最终通过这段 Parser 代码执行代码的解析过程。

可以在 https://pegjs.org/online 这里进行在线演示。将上面的 Demo 代码复制到页面左边的文本框中，然后在右侧的文本框中数据一个整数，就可以看到在右侧下方的 output 一栏中正确输出结果。如果输入的不是一个整数，而是 abc ，就会报类似 Line 1, column 1: Expected [0-9] but "a" found. 错误，这是因为还没有对该字符进行文法定义。

JSON Parser 的实现

了解了 PEG.js 的基本原理之后，我们就可以开始着手写 JSON 的 PEG 规则了。首先来梳理一下 JSON 的基本结构。JSON 是一个嵌套的结构，其值可以是以下基本类型：

null

由此我们可以开始自顶向下定义 PEG 文法规则：

Value
  = Object
  / Array
  / String
  / Number
  / Boolean
  / Null

其中， Object 、 Array 等是我们自定义的非终结符（还未定义）， / 是选择操作符，在不满足前者的匹配条件时，会使用后面的匹配规则，类似于正则表达式中的 | 操作符。这样，最外层的 JSON 结构定义就完成了，接下来就是需要针对每个非终结符的文法进行定义。

Boolean 和 Null 的规则定义

鉴于 Object 、 Array 的定义稍显复杂，刚开始我们可以从简单的 Boolean 和 Null 下手，在 JSON 中分别对应的是 true ， false ， null 这一些字面值。

Boolean
  = "true" { return true; }
  / "false" { return false; }

Null
  = "null" { return null; }

引号内的表示终结符字符串，当匹配到该字符串时即表示匹配完成。这样，我们就写出了一个可以解析 true ， false ，和 null 的 JSON 解析器（由于 Object 等其它非终结符还没有进行定义，因此需要先将之前在 Value 中那些暂未定义的非终结符前面使用 // 注释掉才能进行在线演示）。

Number 的规则定义

在 JSON官网 中列出了 JSON 支持的整数定义：

JSON 中支持的数字可以是整数、小数、负数以及科学计数法，因此我们需要比较全面的考虑匹配规则。如果对正则表达式比较熟悉的话，根据上图不难写出这样的正则表达式：

/^-?(0|[1-9][0-9]*)(\.[0-9]+)?((e|E)(\+|-)?[0-9]+)?$/

但 PEG 是不支持正则表达式的，尽管语法与正则表达式类似，但还是有很多不一致的地方，因此我们写规则时需要将其翻译一下：

Number
  = "-"?("0"/([1-9][0-9]*))("."[0-9]+)?(("e"/"E")("+"/"-")?[0-9]+)? {
    return parseFloat(text());
  }

幸好 JavaScript 本身提供了浮点数字符串的解析能力，我们可以直接将匹配字符串传给 JavaScript 解析，节省了很大的工作量。这样，我们就完成了对数字的解析。

PEG支持空白字符的分隔，因此我们可以在匹配规则中加入一些空格，让规则看起来更加清晰：

Number
  = "-"? ("0" / ([1-9] [0-9]*)) ("." [0-9]+)? (("e" / "E") ("+" / "-")? [0-9]+)? {
    return parseFloat(text());
  }

String 的规则定义

JSON 官网对 String 的定义如下：

可以看到 String 的处理也并不简单，我们还需要特别注意转义符号 \ 的规则，一些控制字符比如 \n 代表换行符等都需要进行特殊处理，我们可以把这些转义规则使用 Escape 非终结符进行特殊定义

String
  = "\"" string:([^"\\] / Escape)* "\"" { // 这里的 string 是一个命名标识符
    return string.join('');           // 命名标识符可以在函数片段中作为参数使用
  }

Escape
  = "\\" character:["\\/bfnrt] {
    switch (character) {
      case '"':
      case '\\':
      case '/':
        return character;
      case 'b': return '\b';
      case 'f': return '\f';
      case 'n': return '\n';
      case 'r': return '\r';
      case 't': return '\t';
    }
  }
  / "\\u" codePoint:([0-9a-fA-F][0-9a-fA-F][0-9a-fA-F][0-9a-fA-F]) {
    return String.fromCodePoint(parseInt(codePoint.join(''), 16));
  }

上面对转义字符做了处理，其中对 \u 的处理比较啰嗦，因为 PEG.js 不支持范围匹配，所以如果需要匹配4个十六进制数字，就需要将匹配规则写4次。针对匹配到的 Unicode 码点，需要转换成对应的 Unicode 字符，比如汉子 '哈' 的 unicode 码点的十六进制表示可以通过 '哈'.codePointAt(0).toString(16) 得到，值为 0x54c8 ，因此针对 '\u54c8' 这样的字符串解析为 '哈' ，可以使用 String.fromCodePoint() 得到，这里需要注意进制转换。

Object 的规则定义

针对简单字面值的规则定义完成之后，我们可以开始 Object 的规则定义，Object 比较复杂，我们先从一个空对象 {} 开始定义：一个空对象内部不会有其它字符，但可以有空格之类的空白字符，因此我们还需要定义一个指定为空白字符的非终结符 _ 。

Object
  = "{" _ "}" {     // 每个符号规则之间需要用空格隔开
      return {};
  }

_ "whitespace"        // 可以为非终结符设定自定义别名
  = [ \t\r\n]*        // 与正则表达式不同的是，PEG 不支持 \s 符号

这样，我们就写出了一个可以解析空对象的JSON解析器。接下来继续完善 Object ，对象内部可以存在多条属性，属性之间用 , 分隔，最后一个属性后面不允许有 , ，属性两边可以存在空白字符。根据这条规则，我们还需要定义具有属性 Property 的对象及对应的 Property 规则：

Object
  ... // 接上面
  / "{" head:(_ Property _ ",")* tail:(_ Property _) "}" {
    return head.concat([tail])         // 将所有匹配的值组合成一个数组
      .map((element) => element[1])    // 每个匹配元素的第一项是空白字符，第二项才是 Property
      .reduce((result, [key, value]) => {
          result[key] = value;
          return result;
      })
  }

Property
  = key:Key _ ":" _ value:Value {    // key : value 之间也可以含有空白字符
    return [ key, value ];            // 将 Property 的值使用 Pair 的方式返回
  }

根据 PEG.js 的文档， * 操作符解析的得到的元素是一个 Array， ? 操作无解析得到的元素是一个值或 null ，因此需要注意处理匹配值。

Array 的规则定义

有了 Object 的规则定义，对 Array 的规则定义就很类似了：

Array
  = "[" _ "]" { return []; }         // 空数组
  / "[" head:(_ Value _ ",")* tail:(_ Value _) "]" {
    return head.concat([tail])
      .map((element) => element[1]);
  }

到这里，JSON Parser 的规则定义就完成了，可以尝试使用任何 JSON.stringify() 处理过的对象得到的 JSON 字符串，应当都能顺利完成解析。但还忽略了一点，就是 JSON.parse() 是能够解析类似 1 这样首位都有空格的元素的，因此我们还需要加入一条规则：

JSON
  = _ value:Value _ {
    return value
  }

现在这个满足 JSON 规范的 JSON Parser 就算正式完成了，在页面的右下角还可以将规则生成对应的 Parser 代码下载下来使用。

JSON AST Parser

下面再简单介绍实现一个可以解析出 AST 的 JSON Parser，以 ESTree Spec 的标准来生成一个 AST。与前面的 JSON Parser 相比解析规则一模一样，需要修改的只是其中解析函数片段的代码，需要返回一个 Tree Node 对象而不是非终结符的值。

在 ESTree Spec 中，字符串、布尔值、数字以及 null 的 AST 应该都是一个 Literal，其定义如下：

interface Literal <: Expression {
    type: "Literal";
    value: string | boolean | null | number | RegExp;
}

<: 意思是继承 Expression 的定义，这里我们可以忽略。

例如 true 的 AST 应该是这样的：

{
    type: "Literal",
    value: true
}

我们可以改写之前的解析规则成这样：

Boolean
  = "true" { return { type: 'Literal', value: true }; }
  / "false" { return { type: 'Literal', value: false }; }

Null
  = "null" { return { type: 'Literal', value: null }; }

Number
  = "-"? ("0" / ([1-9] [0-9]*)) ("." [0-9]+)? (("e" / "E") ("+" / "-")? [0-9]+)? {
    return {
      type: 'Literal',
      value: parseFloat(text())
    };
  }

根据 ESTree Spec 标准将剩下的 String 、 Object 、 Array 的 AST 解析函数写出来也不难了。

以上的全部代码可以在 https://github.com/DremyGit/peg-json-parser 中找到。