JSON解析器的简单实现

前言

不管多么复杂庞大的数据,它的基本组成其实是很简单的,从结构上看所有的数据都可以分解成三种类型:

  1. scalar 标量,比如所有的名词。
  2. sequence序列,即标量的合集,编程语言中的数组。
  3. mapping映射,键值对,比如JS中的对象,python中的dict。

因此,在编程语言中,只要有了数组和对象,就可以表示一切数据了。在 JavaScript 中虽然没有栈,链表,二叉树之类的数据结构,但都可以简单模拟出来。而为了储存数据,JSON这种目前应用极广的非常轻量的数据交换格式终于诞生了,它的规则极其简单:

  1. 并列的数据之间用逗号(”, “)分隔。
  2. 映射用冒号(”: “)表示。
  3. 并列数据的集合(数组)用方括号(“[]”)表示。
  4. 映射的集合(对象)用大括号(”{}”)表示。

我们可以看出来,一组JSON数据它其实要么就是数组,要不就是一个键值对合集的对象。

解析

JSON格式结构清晰简单,因此解析起来也非常方便,在解析文本的过程中,遇到一个左大括号({)时,表示需要从当前字符开始,解析出一个对象,而解析对象的过程则是解析出多对 key/value,每解析完一对,如果遇到了右大括号(}),则对这个对象的解析就结束了,而如果遇到的不是右大括号,就解析下一对 key/value,直到遇见右大括号。而解析出一对 key/value,则是必须先解析出一个字符串,然后一个冒号(:),然后是这个 key 对应的值。

同理,当遇到一个左方括号([)时,需要从这个字符开始解析出一个数组;而解析数组,则是解析出多个由逗号分隔的值,直到解析完一个值后遇到的不是逗号而是右方括号(]),则这个数组解析完毕。

遇到一个双引号(”)时,需要从当前位置开始解析出一个字符串。

遇到字母 “n” 的话,则是从当前位置开始往后读 4 个字符,且读到的 4 个字符组成的字符串必须是“null”,否则就应该报错。

遇到字母 “t” 的话,则是从当前位置开始往后读 4 个字符,且读到的 4 个字符组成的字符串必须是“true”,否则就应该报错。

遇到字母 “f” 的话,则是从当前位置开始往后读 5 个字符,且读到的 5 个字符组成的字符串必须是“false”,否则就应该报错。

剩下的就是数值了。

// 声明一个测试用的字符串,暂时不考虑特殊的情况,完成功能后再增强鲁棒性
const jsonStr = '{"a":1,"b":true,"c":false,"foo":null,"bar":[1,2,3]}'
function parse(jsonstr) {
  let i = 0
  // 使用一个全局变量 i 来保存我们解析到哪里了,或者说下一步要从哪里开始解析

  str = jsonStr
  return parseValue()

  // 然后先实现一个解析出一个值的函数,名为 parseValue,同时,它解析完一个“值”后,会把 i 移动到下一个即将开始解析的位置,我们所有的函数都依赖这个变量i
  function parseValue() {
    if (str[i] === '{') {
      return parseObject()
    } else if (str[i] === '[') {
      return parseArray()
    } else if (str[i] === 'n') {
      return parseNull()
    } else if (str[i] === 't') {
      return parseTrue()
    } else if (str[i] === 'f') {
      return parseFalse()
    } else if (str[i] === '"') {
      return parseString()
    } else {
      //如果不考虑出错的话,不是以上所有的情况即
      return parseNumber()
    }
  }
}

接下来,我们只需要一步步实现 parseValue 函数所调用到的这几个函数就行了:

function parseString() {
  var result = ''
  i++ // 开始解析之前,i是指向双引号的,但字符的内容是不包含这个双引号的
  while(str[i] != '"') {
    result += str[i++]
  }
  i++// 移动i到解析完成后的下一个位置
  return result
}

function parseNull() {
  // 简单粗暴,直接往后读出一个长度为4的个字符串出来
  // 如果不是null,则直接报错
  var content = str.substr(i, 4)

  if (content === 'null') {
    i += 4
    return null
  } else {
    throw new Error('Unexpected char at pos: ' + i)
  }
}

function parseFalse() {
  // 基本同上
  var content = str.substr(i, 5)

  if (content === 'false') {
    i += 5
    return false
  } else {
    throw new Error('Unexpected char at pos: ' + i)
  }
}

function parseTrue() {
  // 基本同上
  var content = str.substr(i, 4)

  if (content === 'true') {
    i += 4
    return true
  } else {
    throw new Error('Unexpected char at pos: ' + i)
  }
}

function parseNumber() {
  // 本函数的实现并没有考虑内容格式的问题,实际上JSON中的数值需要满足一个格式
  // 不过好在这个格式基本可以用正则表达出来,不过这里就不写了
  // 想写的话对着官网的铁路图写一个出来就行了
  // 并且由于最后调用了parseFloat,所以如果格式不对,还是会报错的
  var numStr = ''//-2e+8
  // 此处只要判断i位置还是数字字符,就继续读
  // 为了方便,写了另一个helper函数
  while (isNumberChar(str[i])) {
    numStr += str[i++]
  }
  return parseFloat(numStr)
}

// 判断字符c是否为组成JSON中数值的符号
function isNumberChar(c) {
  var chars = {
    '-': true,
    '+': true,
    'e': true,
    'E': true,
    '.': true
  }
  if (chars[c]) {
    return true
  }
  if (c >= '0' && c <= '9') {
    return true
  }
  return false
}

// 解析数组,就很容易了
// 掐头去尾
// 然后一个值一个逗号
// 如果解析完一个值后没遇到逗号,说明解析完了
// 现在你知道没有多余的逗号有多好解析了吧~
function parseArray() {
  i++
  var result = []//[1234,"lsdf",true,false]
  while(str[i] !== ']') {
    result.push(parseValue())
    if (str[i] === ',') {
      i++
    }
  }
  i++
  return result
}

// 解析对象,一如既往的简单
// 掐头去尾
// 然后一个key,是字符串
// 一个冒号
// 一个值,可能是任意类型,所以调用parseValue
// 最后,如果解析完一组k/v对,遇到了逗号,则解析下一组,没遇到逗号,则解析完毕
function parseObject() {
  i++
  var result = {}//{"a":1,"b":2}
  while(str[i] !== '}') {
    var key = parseString()
    i++//由于只考虑合法且无多余空白的JSON,所以这里就不判断是不是逗号了,正常应该是发现不是逗号就报错的
    var value = parseValue()
    result[key] = value
    if (str[i] === ',') {
      i++
    }
  }
  i++
  return result
}

最后打开 node 跑一次就可以看到最后的结果了:

{ a: 1, b: true, c: false, foo: null, bar: [ 1, 2, 3 ] }

ref: