JSON パーサーを一から作成する (1)

遞歩下降は直感的で強力な解析方法と言えます。

今日はJSONの解析から始めて、JSONパーサーの作り方を解説します。JSONの構造はシンプルなため、練習に適しています。解析構文はフロントエンドや通常の開発とは直接関係がないかもしれませんが、将来的にDSLを設計したり、特殊な要件でカスタム言語を作成する必要がある場合には、これらのテクニックが役立つでしょう。

なぜ遞歩下降を学ぶ必要があるのか？

JSON.parseがあるのに、なぜ遞歩下降を学ぶ必要があるのでしょうか？シンプルな構文解析を通じて、JSONデータを正常に解析するだけでなく、独自の構文を実装することもできます。また、このテクニックを他の場所にも応用することができます。

例えば、通常のJSONは次のようになります：

{
  "name": "kalan",
  "age": 20
}

今日は新しい構文を追加したいとします。テンプレートと呼ばれるもので、{}で囲まれた文字列は自動的に変数で置き換えられます。例えば：

{
  "name": "kalan",
  "age": 20,
	"job": $job$
}

カスタムのparse関数を使用して解析します：

parse(json, { job: 'engineer' });

// {
//   "name": kalan,
//   "age": 20,
//   "job": "engineer"
// }

または、新しい記号を使用したい場合：

{
  "name" @ "kalan"
  "age" @ 20
}

今日は、JSONを解析する再帰下降パーサーを作成し、上記の2つのカスタム機能に変更します。

遞歩下降（Recursive Descent）とは何ですか？

再帰下降について話すとき、LL、LR、トップダウン、非終端など、さまざまな恐ろしい用語や記号に陥りがちですが、最も直感的な方法で議論しましょう。まずは図を見てみましょう：

json-tree-2

JSONの形式を図で表してみました。JSONは主にkey + : + valueで構成され、valueは文字列、ブール値、数値、null、オブジェクトなどにさらに分割できます。

valueがオブジェクトの場合、同じルールを再度適用できることに気付くでしょう。つまり、図の最上位に戻り、同じルールで解析を続けることができます。

このように繰り返し処理することを再帰と呼び、マッチするルールを上から下にクエリすることをトップダウンと呼び、これらを組み合わせて再帰下降と呼んでいます。

各型および構文の詳細な定義については、JSON仕様を参照できます：

Screenshot_2020-05-10 JSON

まずは、最も単純な例を見てみましょう：1つのキーと値のみで構成され、値が文字列型である場合です。

{
  "name": "kalan"
}

json-simple

以下はプロセス（上記の図と比較してください）

{に出会い、オブジェクトの解析を開始
keyの解析に入る。文字列であることが予想されます
"に出会い、文字列を解析
n, a, m, eに出会い、nameをキーとして扱う
"に出会い、文字列のマッチングが終了し、次に:が必要です
:に出会い、valueの解析に入る
"に出会い、文字列の解析に入る
k, a, l, a, nに出会い、valueをkalanとして設定
"に出会い、文字列のマッチングが終了
}に出会い、オブジェクトのマッチングが終了
空の文字列（EOF）に出会い、解析が終了

このプロセスからわかるように、解析は一連の状態変化のようなものです。マッチする値に遭遇するたびに、上記の図のルールに従って次のボックスに移動するかどうかをテストします。各ボックスには受け入れられる値が異なる場合もあります。左から右にスムーズに進むことができれば、マッチが成功したことを意味します。

次に、実装を試してみましょう。

シンプルなパーサーの実装

シンプルなパーサーは、ポインタ、位置情報、現在の文字のいくつかの情報を使用して実現できます。

parse関数はプログラムのエントリーポイントとして使用され、特定の状態に一致する場合に対応する関数を実行します。

まず、使用する関数を定義します：

class Parser {
  constructor(raw) {
    this.raw = raw;
    this.index = 0;
  }

  // 現在の文字
  current() {
    return this.raw[this.index];
  }

  // マッチした後の文字列がstrであるかどうかを判定
  // 例: next('{')
  // 次の文字が'{'である場合、インデックスを移動し、trueを返す
  // 状態の判定に便利
  next(str) {
    if (this.raw.slice(this.index, this.index + str.length) === str) {
      this.index += str.length;
      return true;
    }

    return false;
  }

  // 空白を省略する、現時点ではスペースのみを考慮
  // タブなどの機能は実装されていません
  skip() {
    while (this.raw[this.index] <= " ") {
      this.index += 1;
    }
  }

  parse() {
    const value = object(this); // エントリーポイント
    return value;
  }
}

メインのエントリーポイントはparse関数です。また、skipやnextのような補助関数を定義して、現在の状態を確認するのに便利にします。次に、object関数の実装を見てみましょう：

function object(parser) {
  const obj = Object.create(null);
  let key = "";
  // もし先頭が { の場合、object関数で解析する必要がある
  if (parser.current() === "{") {
    parser.next("{");
    parser.skip();
    
    // もしすぐに } に出会った場合、空のオブジェクト {}
    if (parser.current() === "}") {
      parser.next("}");
      return obj;
    }
    
    // 現在の文字を読み取り、どの関数で解析するかを判断
    while (parser.current()) {
      key = string(parser); // keyは必ず文字列なので、文字列で解析する

      parser.skip(); // 空白文字を省略
      parser.next(":"); // : が現れることを予期
      obj[key] = string(parser); // 仮に値が文字列のみであると仮定し、文字列で解析する
      parser.skip();
      if (parser.current() === "}") { // } に出会った場合、オブジェクトの解析終了、objを返す
        parser.next("}");
        return obj;
      }
      parser.next(","); // カンマがある場合、次のkey-valueを解析し続ける
      parser.skip();
    }
  }
}

もし現在の文字が { である場合
- もし次の文字が } である場合、空のオブジェクトであり、戻り値として返す
whileループに入り、stringでキーを解析（JSONのキーは必ず文字列なので、文字列で解析します）。string関数の実装については後述します。
- 空白文字を省略（以下の例のように）
```
{ "name"         : "value" }
```
- :が現れることを予期
- stringで値を解析（ここでは一時的に文字列のみを想定し、他の型の処理は後で追加します）
- 空白文字を省略
- } に出会った場合、オブジェクトの終わりなので、objを返す
- , に出会った場合、次のkey-valueを解析するため、whileループを続ける
- 空白文字を省略

文字列の解析の実装：

function string(parser) {
  parser.next('"'); // もし次の文字が " である場合、文字列の解析方法を使用する
  if (parser.next('"')) {
    // { "": "value" } 空のキーをJSONとしては無効とします
    throw new Error("JSON key is empty.");
  }

  let key = "";
  let curr = "";
  // " が現れるまで次の文字を繰り返し読み取る
  while (((curr = parser.current()), curr)) {
    if (parser.next('"')) {
      parser.index += 1;
      return key;
    }
    key += curr;
    parser.index += 1;
  }
}

文字が " であることを予期
もし次の文字が " である場合、空の文字列であり、無効なキーとして警告を表示します
" が現れるまで、次の文字を繰り返し読み取ります

練習したい場合は、リポジトリを参照してください。

パーサーを手動で書くと、いくつかの小さな問題が見つかることがあります。テストを最初に書いておくことをお勧めします。手動でのテスト時間を節約できます。

まとめ

再帰下降パーサーを実装しましたが、AST（抽象構文木）に変換する必要はありませんでした。代わりに、直接JavaScriptオブジェクトに変換しました。これは、JSONのデータ構造が比較的単純であるためです。

また、パーサーの実装については、いくつかの観点を考えてみても良いでしょう：

エラーメッセージをよりフレンドリーにするために、情報を行と列の2次元形式で記録することができます。
よりフレンドリーなエラーメッセージの実装。例えば、}を忘れた場合に開発者に警告するか、構文エラーの場合にエラーの場所を明示的に指定するなど。

柔軟性を保つために、記号を変数（トークン）に置き換えることもできます。

part2では、数値、配列、ブール値、nullなどの他の型を実装し、より完全なJSONパーサーにする予定です。また、先ほど説明した2つのカスタム機能の実装を始めます：@を区切り文字として使用すること、および{}をテンプレートとして使用すること。

カランのブログ

JSON パーサーを一から作成する (1)

なぜ遞歩下降を学ぶ必要があるのか？

遞歩下降（Recursive Descent）とは何ですか？

シンプルなパーサーの実装

まとめ

作者

愷開 | Kalan