構文解析¶

前章の字句解析は、文字の並びをトークン(識別子・数値リテラル・演算子・キーワードなど)の列に変換しました。構文解析(parsing)は、そのトークン列を言語の文法規則に照らして木構造 — 抽象構文木(abstract syntax tree、AST)— に組み立てる段階です。ここでは、平坦なトークンの列がどのように入れ子の木になるのか、文と式で解析手法が分かれる理由、そして「後になるまで意味が確定しない構文(カバー文法)」という JavaScript 特有の難所を扱います。あわせて、深い入れ子によるスタック溢れへの備え、AST をメモリ上でどう表すか、そして手書きの再帰下降とパーサジェネレータによる表駆動という二つの流儀のトレードオフを整理します。

トークンから AST へ¶

字句解析の出力は一次元のトークン列です。しかしプログラムの構造は本質的に入れ子です。a + b * c では乗算が加算より内側にあり、if (x) { ... } では条件と本体が if 文に従属します。この入れ子関係を明示的に表すのが AST です。

AST は、言語の各構文要素を一つの「ノード」で表し、従属する要素を子ノードとしてぶら下げた木です。たとえば a + b * c は次のような木になります。

flowchart TD
  add["+ (加算)"] --> a["a"]
  add --> mul["* (乗算)"]
  mul --> b["b"]
  mul --> c["c"]

重要なのは、AST が「構文」を表すのであって、ソースの文字通りの姿(括弧・空白・セミコロンの有無)をそのまま保持するわけではないことです。a + b * c と a + (b * c) は同じ木になります。演算の優先順位や結合の向きは、木の形そのものに畳み込まれています。後段のコンパイラは、この木を深さ優先でたどれば、括弧や優先順位を再解釈することなく正しい順序でコードを生成できます。

ノードは種類(node kind)ごとに持つ情報が異なります。二項演算ノードは演算子と左右の部分式を、if 文ノードは条件式・then 節・else 節を、識別子ノードは名前を持ちます。多くのエンジンは、各ノードにソース上の位置(開始・終了オフセット)も持たせます。これは構文エラーの報告や、実行時エラーのスタックトレース、デバッガの行番号対応に使われます。

文の解析 — 再帰下降¶

JavaScript の文法は、文(statement)と式(expression)という二つの大きなカテゴリに分かれます。文は「実行される単位」(if 文、for 文、変数宣言、return 文など)、式は「値を生む単位」(算術演算、関数呼び出し、リテラルなど)です。

文の解析には再帰下降(recursive descent)が広く使われます。これは、文法上の各構文要素に対して一つの解析関数を用意し、それらが互いを呼び合う手法です。関数の呼び出し構造が、そのまま文法の入れ子構造に対応します。

parseStatement():
    現在のトークンを見て分岐する
    "if"    なら parseIfStatement()
    "for"   なら parseForStatement()
    "{"     なら parseBlock()
    "return" なら parseReturnStatement()
    それ以外 なら parseExpressionStatement()

parseIfStatement():
    "if" を読み飛ばす
    "(" を期待
    cond = parseExpression()
    ")" を期待
    then = parseStatement()   // ここで再帰する
    "else" があれば else = parseStatement()
    return IfNode{cond, then, else}

この方式の魅力は、コードが文法をほぼそのまま書き写した姿になることです。if 文の本体がまた文であること(if の中に for を書けること)は、parseIfStatement が parseStatement を呼び戻すという再帰で自然に表現されます。人間が読み書きしやすく、後述するようにエラーメッセージも作り込みやすいため、実用的な JavaScript エンジンの多くが手書きの再帰下降を採用します。

式の解析 — 演算子の優先順位¶

式の解析には、文とは別の工夫が要ります。1 + 2 * 3 - 4 を正しく解釈するには、* が + や - より強く結合すること(優先順位)と、同じ強さの + と - が左から右へ結合すること(結合性)を、木の形に反映しなければなりません。

これを素朴な再帰下降で書くと、優先順位の各段(加減算の段、乗除算の段、単項演算の段…)ごとに関数を積み重ねることになります。JavaScript には二項演算子だけでも十数段の優先順位があり、これを段ごとの関数として書くと関数が増え、優先順位表の変更も面倒です。

そこで式には、優先順位をデータ(表)として持ち、一つのループで処理する手法が使われます。代表的なのが優先順位登り法(precedence climbing)と、それを一般化したPratt 構文解析(Pratt parsing)です。考え方は共通で、「各演算子に結合力(binding power)という数値を割り当て、より強く結びつく演算子を先に木の内側に取り込む」というものです。

parseExpression(minBP):        // minBP: これ以上弱い演算子では止まる
    left = parseUnary()        // まず左オペランド(単項式)を読む
    loop:
        op = 現在のトークン
        if op が二項演算子でない: break
        bp = 優先順位表[op]
        if bp < minBP: break   // 呼び出し側に委ねるべき弱さなら抜ける
        次のトークンへ進む
        right = parseExpression(bp + 結合性による補正)
        left = BinaryNode{op, left, right}
    return left

parseExpression は、自分より強い演算子を再帰でまとめ上げてから左辺に畳み込みます。minBP という「これより弱い演算子には手を出さない」しきい値を再帰に渡すことで、優先順位と結合性の両方を一つのループで扱えます。左結合か右結合か(たとえば代入 = や指数 ** は右結合)は、再帰に渡すしきい値を bp にするか bp + 1 にするかで切り替えられます。

Pratt 構文解析は、これをさらに一般化し、各トークンに「前置としての振る舞い」(単項マイナス、括弧、リテラルなど)と「中置・後置としての振る舞い」(二項演算子、関数呼び出しの (、プロパティアクセスの .、添字の [)を関連づけます。関数呼び出しや添字アクセスも「非常に強い後置演算子」として同じ枠組みで扱えるのが利点です。優先順位を表として一元管理できるため、演算子の追加・変更が容易で、式の解析コードが平坦に保たれます。

カバー文法 — 後で意味が決まる構文¶

JavaScript の構文解析で最大の難所は、同じトークン列が、後続を読むまでどの構文か確定しない場面が数多くあることです。人間が左から右へ一度だけトークンを読む(先読みは限定的)という前提を保ちつつ、こうした曖昧さをどう捌くかが設計の核心になります。代表例を挙げます。

• アロー関数の引数か、括弧付きの式か: (a, b) まで読んだ時点では、これが (a, b) => a + b のアロー関数の引数リストなのか、カンマ演算子で連結した括弧付きの式 (a, b) なのか判別できません。決着がつくのは、閉じ括弧の次に => が現れるかどうかを見た瞬間です。
• ブロックかオブジェクトリテラルか: 文が置ける位置での { はブロック文の始まりですが、式が置ける位置での { はオブジェクトリテラルです。{ x } はブロック内のラベル・式文にも、プロパティ短縮記法のオブジェクトにも読めます。
• 分割代入パターンか、通常の式か: [a, b] = c の左辺 [a, b] は配列の分割代入パターンですが、単独の [a, b] は配列リテラル(式)です。{ a, b } = c も同様に、左辺はオブジェクト分割代入パターンです。同じ [...] や {...} が、後に = が続くかどうかで意味を変えます。
• async は識別子かキーワードか: async は予約語ではありません。async 単体なら変数名として有効ですが、async function や async (x) => の文脈では非同期関数を導きます。async を読んだだけでは、ただの識別子なのか非同期関数の先頭なのか決まりません。

これらは仕様上、カバー文法(cover grammar)として定式化されています。カバー文法とは、複数の構文を包み込む「一段ゆるい上位の文法」で解析しておき、後で文脈が確定した時点で正しい構文として再解釈(reinterpret)する仕組みです。たとえば括弧内は、アロー引数と括弧式の両方を許す CoverParenthesizedExpressionAndArrowParameterList という緩い規則で受理し、=> が続けば引数リストとして、続かなければ式として、それぞれ確定させます。オブジェクト・配列リテラルとその分割代入パターンも、両方を包む緩い規則で受理してから、代入の左辺に来たときにパターンとして再解釈します。

エンジンの実装では、この「緩く受理してから確定させる」を主に二つの方法で実現します。

• 後から再解釈する(reinterpret): いったん式として AST を組み立て、確定した時点でその部分木をパターンやアロー引数リストへ変換する。すでに作った木を作り直す必要がない一方、「式としては正しいがパターンとしては不正」(たとえばアロー引数に来られない要素)を後から検出できるよう、緩く受理した箇所を記録しておく必要があります。
• やり直す(reparse): 曖昧な地点の位置を控えておき、確定後にそこへ戻って正しい規則で読み直す。実装は単純になりますが、最悪の場合、入れ子の括弧ごとに読み直しが重なって解析時間が入力長に対して二次的に膨らむ恐れがあり、先読みや上限を設けて抑える必要があります。

いずれにせよ鍵は、確定を遅らせつつ、後で不正と分かる可能性のある箇所(early error の候補)を取りこぼさず覚えておくことです。緩く受理した結果、本来エラーであるべき入力を通してしまっては仕様適合を損ないます。カバー文法の箇所では「どこを緩めたか」を記録し、確定時にその制約を検査するのが定石です。

エラーの検出と報告¶

構文解析は、文法に合わない入力を検出して報告する最初の関門でもあります。良い構文エラーは、「何が」「どこで」期待に反したかを具体的に伝えます。位置情報(行・列、またはソースオフセット)を各ノードとトークンに持たせておくと、")" が必要ですが "}" が見つかりました(3 行 12 列) のように、原因箇所を指したメッセージを出せます。

再帰下降が好まれる理由の一つがここにあります。各解析関数は「いま何を期待しているか」を文脈として持っているため、その文脈に応じた具体的なメッセージを、その場で書けます。パーサジェネレータが生成する表駆動パーサでは、エラーが「この状態でこのトークンは受理不能」という機械的な形になりがちで、人間向けの説明に翻訳する追加の作りこみが要ります。

エラー回復(error recovery)は任意の発展要素です。一つ目のエラーで解析を止めず、ある程度読み飛ばして解析を続け、一度の実行でできるだけ多くのエラーを報告する仕組みです。文の区切り(; や })まで読み飛ばして次の文から再開する「同期(synchronization)」がよく使われます。回復は、対話的なエディタや言語サーバのように「一度になるべく多くの誤りを示したい」用途で価値があります。一方、スクリプトを実行するエンジン本体では、最初のエラーで停止して報告すれば十分なことが多く、回復の複雑さを持ち込まない判断も妥当です。

実装上の罠: カバー文法の early error 取りこぼし¶

カバー文法を「緩く受理」した結果、本来ならその場で構文エラー(仕様のいう early error)にすべき入力を、うっかり通してしまう罠があります。たとえば、アロー関数の引数には既定値付きの分割代入は書けても、ある種の式は書けません。括弧内を「式としては何でも受理」で読み流し、=> を見てからアロー引数へ再解釈する際に、「式としては合法だがアロー引数としては不正」なケースの検査を忘れると、不正なプログラムを受理してしまいます。

逆に、確定を焦って早まると別の誤りが起きます。{ を式文の位置で見た瞬間にブロックと決めつけると、オブジェクトリテラルを含む式文を誤って弾きます。async を見た瞬間にキーワード扱いすると、async という変数名の正当な使用を壊します。

対策は、カバー文法の各箇所で「どの制約を保留したか」を明示的に記録し、構文が確定した時点でまとめて検査する設計にすることです。「緩く受理する範囲」と「確定時に検査すべき制約」を対にして持ち、どちらも取りこぼさないことが、仕様適合と実用の両立につながります。差分テスト(第VI部)で他実装との受理・不受理の食い違いを突き合わせると、この種の取りこぼしを効率よく炙り出せます。

実装上の罠: 再帰深度とスタック溢れ¶

手書きの再帰下降は、文法の入れ子をネイティブの関数呼び出しの入れ子で表します。これは自然で読みやすい反面、入力の入れ子が深いほどネイティブのコールスタックを深く消費することを意味します。((((((...)))))) のように括弧を数万段重ねた式、あるいは深くネストした配列リテラルや二項演算を与えると、解析関数の再帰がコールスタックを食い尽くし、スタックオーバーフローでプロセスが異常終了しかねません。これは外部から与えられた入力でエンジンを落とせるという、現実的な堅牢性・セキュリティ上の問題です。

素朴に見えて厄介なのは、これがクラッシュ(制御不能な終了)であって、JavaScript 側で捕捉できる例外ではない点です。ユーザコードは try/catch でスタック溢れを防げません。

対策は、解析中に入れ子の深さを自前で数え、あらかじめ決めた上限を超えたら、クラッシュする前に捕捉可能なエラー(RangeError)を送出することです。深くネストした式そのものは構文としては正しく、失敗の本質は資源の枯渇なので、多くのエンジンはこれを RangeError として報告します。

parseExpression(minBP, depth):
    if depth > 最大許容深度:
        throw RangeError("入れ子が深すぎます")    // クラッシュ前に止める
    ...
    right = parseExpression(bp + 1, depth + 1)     // 深さを引き継ぐ

上限値は、実際に使えるコールスタックの大きさと、1 段あたりの消費量から安全側に見積もります。この防御は式・文・パターンなど再帰が深くなりうるすべての経路に一貫して入れる必要があり、一箇所でも抜けるとそこから溢れます。ツリーウォーク型の実行(第I部「エンジンの全体像」)でも同じ木を再帰でたどるため、実行側にも同種の深度制限が要ります。深い入れ子は解析・実行の両方で危険だと捉えておくのが安全です。

なお、再帰を明示的なスタック(ヒープ上のデータ構造)を使った反復に書き換えれば、原理的にはネイティブスタックを消費しません。ただし読みやすさが大きく損なわれるため、実用上は「深度を数えて上限で止める」防御を選ぶのが一般的です。

AST の表現とメモリ¶

AST はプログラム全体を表す大きなデータ構造で、大規模なソースでは数十万から数百万のノードになりえます。ノードをメモリ上でどう配置するかは、割り付けの速さ・メモリ使用量・後段の走査速度に効きます。大きく二つの方式があります。

• ポインタベース: 各ノードを個別にヒープに割り付け、子ノードへの参照をポインタで持つ。もっとも素直で、ノードごとに型を持つオブジェクトとして扱いやすい。一方、ノードごとの割り付け費用がかさみ、メモリ上に散らばるためキャッシュ効率が悪く、ノードを個別に解放・管理する手間がかかります。
• アリーナ/インデックスベース: ノードを一つの連続した配列(アリーナ)にまとめて格納し、子は配列の添字(インデックス)で指す。割り付けは配列末尾への追記で済み高速、メモリが密に並ぶためキャッシュ効率が良く、解析が終われば配列ごと一括で破棄できます。ポインタの代わりに 32 ビット添字を使えば、64 ビットポインタより 1 参照あたりのメモリも小さくできます。半面、添字経由の間接参照はポインタより記述がやや煩雑で、異なる種類のノードを一様な要素として詰めるためのレイアウト設計(共用体やタグ付き表現)が要ります。

多くの性能志向のエンジンは、AST を「作っては一括で捨てる」寿命の短いデータと捉え、アリーナ方式を採ります。解析からコンパイルまでの間だけ生きていればよく、コンパイルが済めば AST 全体を一度に解放できるからです。この「フェーズごとに一括確保・一括解放する」考え方は、汎用の GC(第III部)に載せるより単純で速く、AST のように寿命が揃ったデータに向いています。

ノードの種類判別には、各ノード先頭に種類タグ(node kind)を持たせるのが基本です。共通フィールド(種類・ソース位置)を全ノードで揃え、種類ごとに固有のフィールドを続ける設計にすると、走査側は種類タグで分岐して固有部を読めます。

単一パスと多重パス¶

構文解析を一度の走査で済ませるか(単一パス)、複数回に分けるか(多重パス)も設計上の分岐です。

JavaScript には、後で判明する情報が前の解釈に影響する箇所があります。関数内での変数宣言の巻き上げ(hoisting)、use strict によるモードの切り替え(strict モードは一部の構文を追加でエラーにする)などです。厳密には、関数を最後まで読まないと確定しない制約もあります。

多くのエンジンは、初回に関数の本体を軽く読み飛ばして(pre-parse)構文の妥当性と巻き上げ対象だけを把握し、実際に呼び出されたときに本体を本格的に解析する遅延解析を採ります(第I部で触れた遅延コンパイルと同じ発想)。起動時にすべての関数本体を完全に解析する無駄を省けるためです。この場合、pre-parse と本解析で同じ制約(early error 検査など)を二度、齟齬なく適用する必要があり、両者の食い違いは受理・不受理のバグの温床になります。単一パスは実装が単純ですが、後から確定する制約の扱いに注意が要り、多重パスは無駄を減らせる代わりに一貫性の維持という別の負担を負います。

再帰下降と表駆動の比較¶

構文解析器の作り方には、大きく手書きの再帰下降(トップダウン)と、パーサジェネレータによる表駆動(ボトムアップ、LR/LALR など)の二つの流儀があります。表駆動は、文法定義から解析表を機械的に生成し、その表に従ってトークンを還元(reduce)していく方式で、yacc/bison のようなパーサジェネレータが代表です。

JavaScript は、カバー文法・ASI(自動セミコロン挿入)・文脈依存キーワードなど、素朴な文脈自由文法の枠に収まりにくい要素を多く含みます。これらを表駆動の枠組みに乗せるには回避策の積み重ねが必要になりがちで、かつエラーメッセージや遅延解析といった実用上の要求も手書きの方が満たしやすいため、実用的な JavaScript エンジンの多くは手書きの再帰下降(式には Pratt/優先順位登り法)を採用します。表駆動は、文法が安定していて自動生成の恩恵が大きい言語処理系で強みを発揮しますが、JavaScript の構文解析では手書きの柔軟さが優先される傾向にあります。

まとめ¶

• 構文解析は、平坦なトークン列を入れ子の AST に組み立てる段階で、優先順位や結合の向きは木の形そのものに畳み込まれる。
• 文は再帰下降(文法をそのまま関数の呼び合いに写す)で、式は優先順位を表として扱う Pratt/優先順位登り法で解くのが定石。式に別手法が要るのは優先順位と結合性を平坦に扱うためである。
• カバー文法は「後で意味が決まる構文」(アロー引数か括弧式か、ブロックかオブジェクトか、パターンか式か、async の扱い)を、緩く受理してから再解釈・再解析で確定させる。確定を遅らせつつ early error を取りこぼさないことが要。
• 深い入れ子は再帰下降でネイティブスタックを溢れさせうる。深度を数えて上限で捕捉可能なエラーに変え、クラッシュを防ぐ。
• AST はアリーナ/インデックス方式で密に置き一括で捨てると、割り付け・キャッシュ効率で有利。ポインタ方式は素直だが割り付けと局所性で劣る。
• JavaScript の文脈依存性とエラー報告・遅延解析の要求から、実用エンジンは手書きの再帰下降を採ることが多い。

参考文献¶

• ECMA-262: ECMAScript Language: Expressions — 演算子優先順位と式文法の一次資料。
• ECMA-262: Supplemental Syntax(カバー文法) — カバー文法と early error の定式化。
• ECMA-262: Automatic Semicolon Insertion — 構文解析が扱う ASI 規則。