基于状态机的JSON解析

在 json.org/json-zh.htm… 中介绍了JSON各类语法的状态机。本文根据这些状态机给出解析JSON的typescript实现方法。

JSON 是一种非常简单的语言。有以下几个特点：

null[

parseValueparseObjectparseArrayparseNumberparseStringskipWhitespacepospeek=s[pos]Parse

class Parse {
  private pos = 0;
  private get peek() {
    return this.s[this.pos];
  }
  constructor(private s: string) {}
}

Deno.test

skipWhitespace: 跳过空白符

spacelinefeedcarriage feedhorizontal tab

class Parse {
  skipWhitespace() {
    while (Parse.isWhitespace(this.peek)) {
      this.pos++;
    }
  }
  static isWhitespace(char: string) {
    switch (char.charCodeAt(0)) {
      case 32: // 空格 space
      case 10: // 换行 linefeed
      case 13: // 回车 carriage feed
      case 9: // 水平符号 horizontal tab
        return true;
      default:
        return false;
    }
  }
}

Deno.test("isWhitespace", () => {
  assertEquals(Parse.isWhitespace(" "), true);
  assertEquals(
    Parse.isWhitespace(`
  `),
    true,
  );
  assertEquals(Parse.isWhitespace("  "), true);
  assertEquals(Parse.isWhitespace("12"), false);
});

parseValue: 解析一个值

[{-"tnftruenullfalse

class Parse {
  parseValue() {
    this.skipWhitespace();
    switch (this.peek) {
      case "n":
        this.pos += 4;
        return null;
      case "t":
        this.pos += 4;
        return true;
      case "f":
        this.pos += 5;
        return false;
      case "{":
        return this.parseObject();
      case "[":
        return this.parseArray();
      case '"':
        return this.parseString();
      case "-":
        this.pos++;
        return -this.parseNumber();
      case "0":
      case "1":
      case "2":
      case "3":
      case "4":
      case "5":
      case "6":
      case "7":
      case "8":
      case "9":
        return this.parseNumber();
      default:
        throw "解析错误";
    }
  }
}

Deno.test("测试基础类型", () => {
  assertEquals(new Parse("true").parseValue(), true);
  assertEquals(new Parse("false").parseValue(), false);
  assertEquals(new Parse('"123"').parseValue(), "123");
  assertEquals(new Parse("1").parseValue(), 1);
  assertEquals(new Parse("1.2").parseValue(), 1.2);
});

parseArray: 解析一个数组

上图是数组类型状态机。对应的代码如下。

class Parse {
  parseArray() {
    this.pos++; // 跳过 '['
    this.skipWhitespace();
    const list: unknown[] = [];
    if (this.peek == "]") {
      this.pos++;
      return list;
    }
    while (true) {
      this.skipWhitespace();
      list.push(this.parseValue());
      this.skipWhitespace();
      if (this.peek == "]") {
        this.pos++;
        break;
      }
      if (this.peek == ",") {
        this.pos++;
      }
    }
    return list;
  }
}

Deno.test("测试数组", () => {
  assertEquals(new Parse("[1,2]").parseArray(), [1, 2]);
  assertEquals(new Parse("[1,[2,3]]").parseArray(), [1, [2, 3]]);
  assertEquals(new Parse("[1,[2,3,[1]]]").parseArray(), [1, [2, 3, [1]]]);
  assertEquals(new Parse("[1,[2,3,[1],4,[5]]]").parseArray(), [1, [
    2,
    3,
    [1],
    4,
    [5],
  ]]);
});

parseObject: 解析一个对象

上图是对象类型状态机。对应的代码如下。

class Parse {
  parseObject() {
    this.pos++; // skip '{'
    this.skipWhitespace();
    const values: any = {};
    if (this.peek == "}") {
      this.pos++;
      return values;
    }
    while (true) {
      this.skipWhitespace();
      const key = this.parseString();
      this.skipWhitespace();
      if (this.peek != ":") {
        throw "FormatException";
      }
      this.pos++;
      this.skipWhitespace();
      const value = this.parseValue();
      this.skipWhitespace();
      values[key] = value;
      // @ts-ignore
      if (this.peek === "}") {
        this.pos++;
        break;
      }
      // @ts-ignore
      if (this.peek === ",") {
        this.pos++;
      }
    }
    return values;
  }
}

parseString: 解析一个字符串

上图是字符串对应的状态机。为了简单表达，下面的代码没有解析特殊字符。如果读者感兴趣，可以自己实现。

class Parse {
  parseString(): string {
    this.pos++; //skip '"'
    if (this.peek == '"') {
      this.pos++;
      return "";
    }
    var str = "";
    while (true) {
      if (this.peek == '"') {
        break;
      }
      str += this.peek;
      this.pos++;
    }
    this.pos++; //skip '"'
    return str;
  }
}

parseNumber: 解析一个数字

上图是数字对应的状态机。为了简单表达，下面的代码只解析了简单的整数和小数。如果读者感兴趣，可以自己实现。

class Parse {
  parseNumber() {
    let num = "";
    while (Parse.isNumber(this.peek)) {
      num += this.peek;
      this.pos++;
    }
    if (this.peek === ".") {
      this.pos++;
      const decimal = this.parseNumber();
      num += "." + decimal;
    }

    return parseFloat(num);
  }
  static isNumber(char: string) {
    return char >= "0" && char <= "9";
  }
}

parse: 解析一个JSON字符串

class Parse {
  parse() {
    this.skipWhitespace();
    let json: any = this.s;
    switch (this.peek) {
      case "{":
        json = this.parseObject();
        break;
      case "[":
        json = this.parseArray();
        break;
      default:
        json = this.parseValue();
    }
    this.skipWhitespace();
    return json;
  }
}

Deno.test("测试完整的一个JSON", () => {
  const obj = {
    "level": 2,
    "tid": 73753,
    "classId": 82,
    "gameType": 6,
    "uids": [
      103136,
      100113,
      100778,
    ],
    "info": [
      {
        "uid": 103136,
        "winChips": 455700,
        "userChips": 100372300,
        "fee": -135000,
        "blind": 300000,
      },
      {
        "uid": 100113,
        "winChips": -300000,
        "userChips": 93139748,
        "fee": 0,
        "blind": 300.45,
      },
      {
        "uid": 100778,
        "winChips": -300000,
        "userChips": 99100000,
        "fee": 0,
        "blind": 300000,
      },
    ],
  };
  assertEquals(new Parse(JSON.stringify(obj)).parseObject(), obj);
});

参考