JavaScript 实现 JSON 解析器

WecTeam

发布于 2019-12-30 16:13:30

3.5K0

发布于 2019-12-30 16:13:30

文章被收录于专栏：WecTeam

原文地址：https://lihautan.com/json-parser-with-javascript/ 原文作者：Tan Li Hau 译者：龚亮声明：本翻译仅做学习交流使用，转载请注明来源。

本周 Cassidoo 每周时事通讯[1]的面试问题是：编写一个函数，该函数接受一个有效的JSON字符串并将其转换为一个对象。编程语言不限，数据结构不限。输入示例：

fakeParseJSON('{ "data": { "fish": "cake", "array": [1,2,3], "children": [ { "something": "else" }, { "candy": "cane" }, { "sponge": "bob" } ] } } ')

有一次，我忍不住想写:

const fakeParseJSON = JSON.parse;

但是，我想，我已经写了不少关于 AST 的文章:

•使用Babel创建自定义JavaScript语法[2]•编写自定义babel转换的逐步指南[3]•用JavaScript操作AST[4]

其中包括编译器管道的概述，以及如何操作 AST，但是我还没有详细介绍如何实现解析器。

这是因为在一篇文章中实现JavaScript编译器对我来说是一项艰巨的任务。

好吧，不用担心。JSON 也是一种语言。它具有自己的语法，您可以从规范[5]中参考。编写 JSON 解析器所需的知识和技术可以转移到编写 JS 解析器中。

因此，让我们开始编写 JSON 解析器！

理解语法

如果您查看了规范页面，会发现有2个图。

•左侧的语法图（或者铁路图）：

图片来源：https://www.json.org/img/object.png

•右侧的 McKeeman形式[6] ，是 Backus-Naur形式（BNF）[7] 的变体。

json
  element

value
  object
  array
  string
  number
  "true"
  "false"
  "null"

object
  '{' ws '}'
  '{' members '}'

这两个图是等效的。

一个是可视化的，另一个是基于文本的。基于文本的语法（ Backus-Naur 形式）通常被提供给另一个解析器，该解析器解析该语法并为其生成一个解析器。?

在本文中，我们将重点关注铁路图，因为它是可视化的，而且似乎对我更友好。

让我们看看第一张铁路图：

图片来源：https://www.json.org/img/object.png

这是 JSON 中“对象”的语法。

我们从左边开始，沿着箭头走，然后在右边结束。

圆圈（例如：左花括号（{），英文逗号（,），英文冒号（:），右花括号（}））是字符，方框(例如:空格（whitespace）、字符串（string）和值（value）)是另一种语法的占位符。如果要解析“空格”，我们需要查看空格的语法。

因此，对于一个对象，从左边开始第一个字符必须是一个左花括号。然后我们有两个选择：

•空格 -> 右花括号 -> 结束，或者•空格 -> 字符串 -> 空格 -> 英文冒号 -> 值 -> 右花括号 -> 结束

当然，当您到达“值”时，您可以选择：

•-> 右花括号 -> 结束，或者•-> 英文逗号 -> 空格 -> ... -> 值

您可以继续保持循环，直到您决定执行以下操作：

•-> 右花括号 -> 结束。

我想我们现在已经熟悉铁路图，让我们继续下一节。

实现解析器

让我们从以下结构开始：

function fakeParseJSON(str) {
  let i = 0;
  // TODO
}

我们初始化i作为当前字符的索引，当i到达str结束时，我们将立即结束。

让我们实现“对象”的语法：

function fakeParseJSON(str) {
  let i = 0;
  function parseObject() {
    if (str[i] === '{') {
      i++;
      skipWhitespace();

      // if it is not '}',
      // we take the path of string -> whitespace -> ':' -> value -> ...
      while (str[i] !== '}') {
        const key = parseString();
        skipWhitespace();
        eatColon();
        const value = parseValue();
      }
    }
  }
}

在parseObject中，我们将调用其他语法的解析，例如“字符串”和”空格”，当我们实现它们时，一切都会起作用?。

我忘了加上一个英文逗号,，,只出现在我们开始第二次循环空格 -> 字符串 -> 空格 -> : -> ...之前。

基于此，我们添加了以下行，注意第8，12~15，20行（译者加）：

function fakeParseJSON(str) {
  let i = 0;
  function parseObject() {
    if (str[i] === '{') {
      i++;
      skipWhitespace();

      let initial = true;
      // if it is not '}',
      // we take the path of string -> whitespace -> ':' -> value -> ...
      while (str[i] !== '}') {
        if (!initial) {
          eatComma();
          skipWhitespace();
        }
        const key = parseString();
        skipWhitespace();
        eatColon();
        const value = parseValue();
        initial = false;
      }
      // move to the next character of '}'
      i++;
    }
  }
}

一些命名约定：

•当我们基于语法解析代码并使用返回值时，我们调用parseSomething•当我们期望字符在那里，但我们没有使用字符时，我们调用eatSomething•字符不在那里，但我们的程序是ok的，我们调用skipSomething

让我们来实现eatComma和eatColon：

function fakeParseJSON(str) {
  // ...
  function eatComma() {
    if (str[i] !== ',') {
      throw new Error('Expected ",".');
    }
    i++;
  }

  function eatColon() {
    if (str[i] !== ':') {
      throw new Error('Expected ":".');
    }
    i++;
  }
}

我们已经完成了parseObject语法的实现，但是这个解析函数的返回值是什么呢?

我们需要返回一个 JavaScript 对象，注意第8，22，28行（译者加）。

function fakeParseJSON(str) {
  let i = 0;
  function parseObject() {
    if (str[i] === '{') {
      i++;
      skipWhitespace();

      const result = {};

      let initial = true;
      // if it is not '}',
      // we take the path of string -> whitespace -> ':' -> value -> ...
      while (str[i] !== '}') {
        if (!initial) {
          eatComma();
          skipWhitespace();
        }
        const key = parseString();
        skipWhitespace();
        eatColon();
        const value = parseValue();
        result[key] = value;
        initial = false;
      }
      // move to the next character of '}'
      i++;

      return result;
    }
  }
}

既然您已经看到我实现了“对象”语法，现在轮到您尝试实现一下“数组”语法了:

图片来源：https://www.json.org/img/array.png

function fakeParseJSON(str) {
  // ...
  function parseArray() {
    if (str[i] === '[') {
      i++;
      skipWhitespace();

      const result = [];
      let initial = true;
      while (str[i] !== ']') {
        if (!initial) {
          eatComma();
        }
        const value = parseValue();
        result.push(value);
        initial = false;
      }
      // move to the next character of ']'
      i++;
      return result;
    }
  }
}

现在进入一个更有趣的语法“值”。

图片来源：https://www.json.org/img/value.png

值是以“空格”开始，然后是以下任意一种：“字符串”，“数字”，“对象”，“数组”，“真”，“假”或“空”，然后以“空格”结尾：

function fakeParseJSON(str) {
  // ...
  function parseValue() {
    skipWhitespace();
    const value =
      parseString() ??
      parseNumber() ??
      parseObject() ??
      parseArray() ??
      parseKeyword('true', true) ??
      parseKeyword('false', false) ??
      parseKeyword('null', null);
    skipWhitespace();
    return value;
  }
}

??是空值合并操作符[8]，它就像||，我们通常使用foo || default设置默认值。我们期望当foo是假值时||返回default。然而只有当foo是null或者undefined时空值合并操作符返回default。

parseKeyword 将检查当前的str.slice(i)是否与关键字字符串匹配，如果匹配，将返回关键字值:

function fakeParseJSON(str) {
  // ...
  function parseKeyword(name, value) {
    if (str.slice(i, i + name.length) === name) {
      i += name.length;
      return value;
    }
  }
}

parseValue就是这样！

我们还有3种语法，但是我将节省本文的篇幅，并在下面的 CodeSandbox 中实现它们：

<iframe src="https://codesandbox.io/embed/json-parser-k4c3w?expanddevtools=1&fontsize=14&hidenavigation=1&theme=dark&view=editor" style="width:100%; height:500px; border:0; border-radius: 4px; overflow:hidden;" title="JSON解析器" allow="geolocation; microphone; camera; midi; vr; accelerometer; gyroscope; payment; ambient-light-sensor; encrypted-media; usb" sandbox="allow-modals allow-forms allow-popups allow-scripts allow-same-origin"></iframe>

在我们完成所有语法实现之后，现在让我们返回json的值，它是由parseValue返回的:

function fakeParseJSON(str) {
  let i = 0;
  return parseValue();

  // ...
}

就是这样!

好吧，别急，我的朋友，我们刚刚完成了理想的情况，那异常的情况呢?

处理意外的输入

作为一名优秀的开发人员，我们还需要优雅地处理异常情况。对于解析器，这意味着使用适当的错误消息对开发人员进行提醒。

让我们处理两种最常见的错误情况：

•意外的标记•字符串意外结束

意外的标记

字符串意外结束

在所有的while循环中，比如parseObject中while循环：

function fakeParseJSON(str) {
  // ...
  function parseObject() {
    // ...
    while(str[i] !== '}') {

我们需要确保访问的字符不会超过字符串的长度。在这个例子中，这发生在字符串意外结束时，而我们仍然在等待一个结束字符“}”。

function fakeParseJSON(str) {
  // ...
  function parseObject() {
    // ...
    while (i < str.length && str[i] !== '}') {
      // ...
    }
    checkUnexpectedEndOfInput();

    // move to the next character of '}'
    i++;

    return result;
  }
}

加倍努力

您还记得您还是一名初级开发人员的时候，每当您遇到带有加密消息的语法错误时，您完全不知道出了什么问题吗？现在您有了更多经验，该停止这个良性循环并停止大喊大叫了。

Unexpected token "a"

并让用户呆呆地盯着屏幕。

有很多比大喊大叫来处理错误消息的更好的方法，您可以考虑将以下几点添加到解析器中：

错误代码和标准错误消息

这对于用户向 Google 寻求帮助作为标准关键字很有用。

// instead of
Unexpected token "a"
Unexpected end of input

// show
JSON_ERROR_001 Unexpected token "a"
JSON_ERROR_002 Unexpected end of input

更好地了解出了什么问题

像 Babel 这样的解析器，将向您显示一个代码框架，一个带有下划线、箭头或突出显示错误的代码片段：

// instead of
Unexpected token "a" at position 5

// show
{ "b"a
      ^
JSON_ERROR_001 Unexpected token "a"

有关如何打印代码段的示例：

function fakeParseJSON(str) {
  // ...
  function printCodeSnippet() {
    const from = Math.max(0, i - 10);
    const trimmed = from > 0;
    const padding = (trimmed ? 3 : 0) + (i - from);
    const snippet = [
      (trimmed ? '...' : '') + str.slice(from, i + 1),
      ' '.repeat(padding) + '^',
      ' '.repeat(padding) + message,
    ].join('\n');
    console.log(snippet);
  }
}

错误恢复建议

如果可能，请解释出了什么问题，并提供有关如何解决它们的建议：

// instead of
Unexpected token "a" at position 5

// show
{ "b"a
      ^
JSON_ERROR_001 Unexpected token "a".
Expecting a ":" over here, eg:
{ "b": "bar" }
      ^
You can learn more about valid JSON string in http://goo.gl/xxxxx

如果可能，请根据解析器到目前为止收集的上下文提供建议：

fakeParseJSON('"Lorem ipsum');

// instead of
Expecting a `"` over here, eg:
"Foo Bar"
        ^

// show
Expecting a `"` over here, eg:
"Lorem ipsum"
            ^

基于上下文的建议会让人感觉更有共鸣和可操作。

记住所有的建议，检查更新的 CodeSandbox。

•有意义的错误消息•带有错误指向失败点的代码段•提供错误恢复建议

<iframe src="https://codesandbox.io/embed/json-parser-hjwxk?expanddevtools=1&fontsize=14&hidenavigation=1&theme=dark&view=editor" style="width:100%; height:500px; border:0; border-radius: 4px; overflow:hidden;" title="JSON解析器（带有错误处理）" allow="geolocation; microphone; camera; midi; vr; accelerometer; gyroscope; payment; ambient-light-sensor; encrypted-media; usb" sandbox="allow-modals allow-forms allow-popups allow-scripts allow-same-origin"></iframe>

总结

要实现解析器，您需要从语法开始。

您可以使用铁路图或 Backus-Naur 形式语法。设计语法是最难的一步。

一旦掌握了语法，就可以开始基于语法来实现解析器。

错误处理很重要，更重要的是拥有有意义的错误消息，以便用户知道如何解决它。

现在您知道了如何实现简单的解析器，是时候着眼于更复杂的解析器了。

•Babel parser•Svelte parser

最后，请关注 @cassidoo[9] ，她的每周时事通讯棒极了!

感谢您花时间阅读本文。这对我意义重大。

如果你喜欢你刚刚读到的，请在 Tweet 转发[10]并评论它，我会写更多相关的文章；

如果你不同意或对这篇文章有意见，也请在 Tweet 转发[11]并评论它，我可以采纳你的建议并改进它。

References

[1] Cassidoo 每周时事通讯: https://cassidoo.co/newsletter/confirmed.html [2] 使用Babel创建自定义JavaScript语法: https://lihautan.com/creating-custom-javascript-syntax-with-babel/ [3] 编写自定义babel转换的逐步指南: https://lihautan.com/step-by-step-guide-for-writing-a-babel-transformation/ [4] 用JavaScript操作AST: https://lihautan.com/manipulating-ast-with-javascript/ [5] 规范: https://www.json.org/json-en.html [6] McKeeman形式: https://www.crockford.com/mckeeman.html [7] Backus-Naur形式（BNF）: https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form [8] 空值合并操作符: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Nullish_coalescing_operator [9] @cassidoo: https://twitter.com/cassidoo [10] 转发: https://twitter.com/intent/tweet?text=I%20disgree%20with%20%40lihautan's%20article&url=https://lihautan.com/json-parser-with-javascript/#unexpected-token" [11] 转发: https://twitter.com/intent/tweet?text=I%20disgree%20with%20%40lihautan's%20article&url=https://lihautan.com/json-parser-with-javascript/#unexpected-token"