ゼロから作るJSONパーサー（1）

再帰下降構文解析（Recursive Descent Parsing）は、直感的かつ強力なパース手法と言える。

今日は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の構造を図で表してみると、JSONは基本的に key + : + value で構成されていることがわかる。さらに value は文字列、真偽値（boolean）、数値、null、objectなどに分解できる。

もし value が object である場合、同じルールをもう一度適用できることに気づいただろうか。つまり図の最上層に戻り、同じルールを使ってパースを続行できる。

このように延々と繰り返す処理を「再帰（Recursive）」と呼び、上から下へとマッチするルールを探していくアプローチを「トップダウン（Top-down / 自頂向下）」と呼ぶ。これらを組み合わせたものが「再帰下降（Recursive Descent）」だ。

各型や構文の詳細な定義については、JSONの仕様を参考にできる：

まずは最もシンプルな例から始めよう。key と value が1つだけで、value が文字列型の場合だ。

{
  "name": "kalan"
}

処理の流れは以下の通りだ（上の図と照らし合わせて参照してほしい）。

• { に遭遇、objectのパースを開始
• key のパースへ進む。文字列を期待
• " に遭遇、文字列のパースを開始