JavaScript实现JSON解析器

WecTeam
3,985 阅读9分钟

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

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

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

有一次，我忍不住想写:

const fakeParseJSON = JSON.parse;

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

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

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

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

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

理解语法

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

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

图1

图片来源：www.json.org/img/object.…

json
  element

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

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

这两个图是等效的。

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

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

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

图1

图片来源：www.json.org/img/object.…

这是 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;
    }
  }
}

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

图1

图片来源：www.json.org/img/array.p…

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;
    }
  }
}

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

图1

图片来源：www.json.org/img/value.p…

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

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

??是 空值合并操作符，它就像||，我们通常使用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&amp;fontsize=14&amp;hidenavigation=1&amp;theme=dark&amp;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&amp;fontsize=14&amp;hidenavigation=1&amp;theme=dark&amp;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

如果你觉得这篇内容对你有价值，请点赞，并关注我们的官网和我们的微信公众号(WecTeam)，每周都有优质文章推送：

WecTeam

avatar
文章
阅读
粉丝