体系ガイド · 発展

式を解析してJavaScriptの構文木を作る

トークンの位置、演算子の優先順位、構文木の形を対応させ、実行前に式の意味とエラー位置を確定します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 到達目標:文字列から計算順序を取り出す
  2. トークンには値と元の位置を残す
  3. 優先順位をパーサの呼出し関係へ写す
  4. 括弧は構文木の形を変える
  5. 実装例:積を先にまとめる小さなパーサ
  6. 構文が正しくても実行できるとは限らない
  7. 演習:出力を固定せず木を修正する
  8. この記事をロゲイアに質問する理解を確かめる

到達目標:文字列から計算順序を取り出す

2 + 3 * 4を左から見える順に計算すると20ですが、JavaScriptでは乗算を先に結び付けるため結果は14です。この違いは、単に実行器が気を利かせることで生まれるのではありません。パーサが加算の右側に乗算の部分木を置けば、評価器は木の構造に従うだけで14を得られます。この章の到達点は、ソースのどの範囲が一つの式になり、どの演算がどの演算の子になったかを、数値の出力を見る前に説明できることです。前提は字句解析・構文解析のガイドと、木の親子関係です。

ここで作るのは、JavaScript全体のパーサではなく、数値・文字列・真偽値、束縛、分岐、関数などへ広げるための教材用処理系です。まず算術式に絞ると、空白、演算子、括弧、入力末尾という境界を一つずつ検査できます。デモのJavaScript実行では、ASTの各ノードと実行中の箇所を対応させてください。入力を自動で本物のJavaScriptへ渡す方式にはせず、対応しない文字や構文には位置を付けて停止します。

トークンには値と元の位置を残す

字句解析器の仕事は、文字を数字、名前、演算子、区切りへ分類することです。たとえば12 + valueなら、12は長さ2の数値トークン、+は演算子、valueは識別子です。トークンの配列だけでなく開始位置と終了位置も保存すると、閉じ括弧が足りない場所を元の入力に示せます。空白を読み飛ばしても、位置を詰め直してはいけません。文字列の内容に演算子と同じ記号があっても、引用符の内側なら加算記号として切り出さないという状態も必要です。

単項の-と二項の-は、同じ記号でも文脈で役割が変わります。-2 * 3の先頭では符号、7 - 2では減算です。字句段階で全部を負の数へまとめる設計では、式の境界を誤ることがあります。まず記号として渡し、構文段階で前置式か二項式かを決める方法なら責務が明確です。コメント、エスケープ、Unicode識別子などを後から加える場合も、黙って空白に置換するのでなく、位置と対応範囲を保つ試験を追加します。

優先順位をパーサの呼出し関係へ写す

足し算の式は積の式を読む、積の式は基本式を読む、という順に関数を分けます。sumが左側のproductを読んだ後に+を見つけると、右側にもproductを要求します。右側のproductは3 * 4を一つの部分木にして返すため、sumの結果は2 + (3 * 4)になります。同じ強さの左結合演算子なら、左側の木を更新しながら繰り返し読みます。8 - 3 - 1を8 - (3 - 1)へ変えないよう、木の形まで期待値に含めます。

段階読み取る範囲得られる構造
基本式2Number(2)
右側の積3 * 4Multiply(Number(3), Number(4))
全体の和2 + 3 * 4Add(Number(2), Multiply(...))

括弧は構文木の形を変える

(2 + 3) * 4なら、基本式が開き括弧を見つけた時点で内側の式を最後まで読み、閉じ括弧を確認します。その結果が乗算の左側となり、出力は20です。括弧の文字自体を計算するノードにする必要はありませんが、入力範囲は保持すると表示に役立ちます。括弧の位置だけを動かした比較では、トークンの数がほぼ同じでも木の根が変わることを観察してください。出力が変わった理由を、実行器の特別扱いに求める必要はありません。

境界例として単独の数値、空白だけの入力、閉じ括弧だけの入力を分けて扱います。単独の数値は有効な式ですが、空白だけなら式が存在しません。2 +では右辺を読む段階で失敗し、2 3では一つ目を読めても余ったトークンが残ります。部分的に解析できたことを、プログラム全体の成功として返さないのが不変条件です。位置付きエラーは失敗した試行の結果として表示し、前回の成功した出力を現在の結果に混ぜません。

実装例:積を先にまとめる小さなパーサ

次のコードは、字句解析済みの数値・+・*だけを受け取る独立した比較用プログラムです。デモの全機能を抜き出したものではありません。sumからproductへ進む構造と、読み取り位置posを全関数が共有する点に注目します。最後にposとトークン数を比べ、余りを拒否します。結果だけでなく、根が+で右の子が*であることも検査しています。実行すると14を出力します。

この実装へ減算や括弧を追加するときは、既存の14という一例が通ることだけで完了にしません。単独の値、連続する同種演算子、括弧の不足、余分な入力をそれぞれ試します。また、数字でないトークンをNumberへ渡した場合には、NaNを普通の数値ノードとして残さず拒否しています。構文エラーの種類と位置を返す型に変えることはできますが、空文字や0で失敗を代用すると、正常な値と区別できなくなります。

javascript
const tokens = ['2', '+', '3', '*', '4'];
let pos = 0;
function primary() {
  const value = Number(tokens[pos++]);
  if (!Number.isFinite(value)) throw new Error('number expected');
  return {type: 'Number', value};
}
function product() {
  let node = primary();
  while (tokens[pos] === '*') { pos++; node = {type: '*', left: node, right: primary()}; }
  return node;
}
function sum() {
  let node = product();
  while (tokens[pos] === '+') { pos++; node = {type: '+', left: node, right: product()}; }
  return node;
}
const tree = sum();
if (pos !== tokens.length) throw new Error('trailing token');
function run(n) {
  if (n.type === 'Number') return n.value;
  const left = run(n.left), right = run(n.right);
  return n.type === '+' ? left + right : left * right;
}
console.assert(tree.type === '+' && tree.right.type === '*');
console.assert(run(tree) === 14);
console.log(run(tree));

構文が正しくても実行できるとは限らない

name + 1は構文上の式にできても、nameの束縛が存在するかは環境を調べる段階の問題です。同様に関数呼出しの形が正しくても、その値が呼出し可能かは別に確認します。パーサへすべての実行条件を押し込むと、同じASTを異なる環境で評価できなくなります。構文木は入力の構造、実行環境は名前と値の対応、評価結果はその時点の出力として分けて保持します。次章では、この分離を使って同じ関数本文と異なる呼出し環境を追います。

評価器が木の子を訪れる順序も確認します。算術の優先順位は木を作る規則であり、左右の式の評価順序は言語の意味です。副作用を含む呼出しへ広げたとき、強く結び付く演算から適当に実行してよいわけではありません。まず左右を定めた順に評価し、その値へ演算を適用するという契約を、入力位置とイベント列へ残します。木の形が正しいのに出力が違う場合、解析と評価のどちらでずれたかを切り分けてください。

演習:出力を固定せず木を修正する

デモのJavaScript実行で、計算結果を20にしたいのに2 + 3 * 4と書かれた入力を、括弧を使って修正してください。出力関数へ20を直接書き込むのではなく、元の数値を用いた式の構造を直します。次に数値を5、2、6へ変え、同じ構造で42になることを確認します。修正した一例と、値を変えた回帰例の両方が成立すれば、偶然期待値へ合わせたのではなく、計算順序を表せたと判断できます。

最後に閉じ括弧を一つ削除し、どの段階で解析が止まるかを記録してください。エラーの後に有効な入力へ戻し、最初から実行した場合と同じASTと出力へ戻ることも確認します。ノートには「どの文字を変えたか」「根と子の関係がどう変わったか」「別の値でも成立したか」を一行ずつ残します。構文木のノード数や呼出し深さに上限がある場合、上限到達は処理未完了です。途中まで得られた値を正常終了として採点しない点も、処理系の実装条件です。

デモで動作を確かめる

JavaScriptの構文木と実行環境

デモの途中状態を読み込んでいます…

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 19

学習コースから次を選ぶ