体系ガイド · 発展

RustでJavaScriptを読む:トークンから構文木へ

小さなJavaScript処理系の字句解析、演算子の優先順位、構文木、失敗位置を、Rustの実装と対応づけます。

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

更新日

この記事の目次
  1. 到達目標:実行前に文の形を確定する
  2. 扱う言語を文法として狭く定める
  3. バイト位置と最長一致を追う
  4. 手計算トレース:優先順位は木の形になる
  5. 構文の失敗と実行時の失敗を分ける
  6. 実行できるRust:二つの木を比較する
  7. 変更点を局所化して調べる
  8. 演習:解析結果を予測してから動かす
  9. この記事をロゲイアに質問する理解を確かめる

到達目標:実行前に文の形を確定する

第4弾では、HTMLとCSSを扱うRustの処理系に、小さなJavaScript処理系をつなぎます。この章の対象は、ソースを実行する直前までです。文字列を読み、トークンへ分割し、宣言、式、分岐、関数という構造を取り出します。画面にJavaScriptらしい文字列が表示できても、処理系がその意味を理解した証拠にはなりません。Rustが作る構文木と、入力のどこで処理を止めたかを確かめてください。

対応する配布ソースはexamples/rust-browser-wave4です。lex_jsとparse_programを起点に、字句解析と構文解析の責任を分けて読みます。ホスト側のJavaScriptエンジンへ教材の入力を渡して実行する構成ではありません。CLIとWASMは同じRustの解析器を使います。両方で同じ入力から同じ解析結果が出ることを調べると、画面の見た目と処理系そのものの正しさを切り分けられます。

扱う言語を文法として狭く定める

対象には数値、文字列、真偽値、null、letとconst、代入、算術と比較、if、トップレベルの名前付き関数、引数とreturnがあります。この列挙は学習上の契約です。ECMAScript全体の実装や、既存のサイトをそのまま動かす互換性を意味しません。ループ、クロージャ、非同期処理などを入力した場合は、対応していない構文として扱う必要があります。見た目が似た機能を推測で補わないことが重要です。

文法を読むときは、文と式を分けます。let n = 2 + 3;は宣言文であり、右辺の2 + 3は値を作る式です。関数宣言には名前、仮引数列、本体があり、関数呼び出しには呼び出す対象と実引数列があります。同じ丸括弧があっても、文脈によって役割は違います。対応範囲の表を手元に作り、サンプルに登場しない構文を自動的に許可したと思い込まないようにします。

バイト位置と最長一致を追う

字句解析器は、入力のカーソルを進めながら識別子、リテラル、演算子、区切りを区別します。比較演算子には=、==、===のような共通の接頭辞があるため、一文字ずつ確定すると別の意味になります。候補の長さと並びを確認し、最長の有効な演算子を先に認識する必要があります。一方、文字列の内部にある記号を演算子として分解してはいけません。文字列を読む状態と通常の状態を区別して追います。

ソース位置をRustの文字列の添字として使う場合は、UTF-8のバイト境界を守ります。日本語が入った文字列リテラルを一文字と一バイトで混同すると、診断の範囲がずれたり、不正な切り出しになったりします。この教材のソース上限は各HTML、CSS、JavaScriptで8192バイトです。入力全体のJSONにも上限があります。文字数で上限内に見えても、送信されるバイト数で境界を確かめてください。

手計算トレース:優先順位は木の形になる

2 + 3 * 4を読む場合、乗算のまとまりを加算の右側へ置きます。左から現れた演算子をそのまま計算する方法では、誤って20になります。構文解析器は実行結果の14を先に知る必要はありません。必要なのは、乗算の方が強く結びつくという構文の規則です。括弧を付けた(2 + 3) * 4では、加算のまとまりが乗算の左側に移ります。二つの木を書いてから実行結果と比較します。

表は教材の解析段階を手で追うための例です。個別のログ行を転載したものではありません。最初にトークン列を確認し、次に右辺の木を描き、最後に評価器へ渡すという順番を保ちます。式を変えたとき、字句解析だけが変わるのか、木の形も変わるのかを説明してください。正しい数値が偶然出た場合でも、括弧を入れた対になる入力で構造の誤りを発見できます。

段階入力または構造確認すること
字句2 / + / 3 / * / 4演算子と数値を区別
構文Add(2, Mul(3, 4))乗算が右部分木
評価2 + 12 = 14構造から計算
対照Mul(Add(2, 3), 4)括弧で20へ変化

構文の失敗と実行時の失敗を分ける

let n = ;には右辺がありません。この失敗は値の計算より前に確定できます。一方、存在しない名前を式の中で読む問題は、文の形が正しくても実行時に現れます。診断を調べるときは、入力が解析器を通過したかどうかを先に確認します。すべてを「JavaScriptエラー」とまとめると、修正すべきトークンと、修正すべき束縛やDOM参照の違いが見えなくなります。

正常系では宣言を含む短い入力を使い、境界では空入力、深い括弧、上限付近のソースを使います。失敗系には閉じ忘れた括弧と未対応のループを用意します。いずれも無限に読み続けず、成功または診断として終わることが必要です。深さや入力長の制限は、文法の意味とは別の実行資源の契約です。上限を増やす前に、再帰や確保量がどう増えるかを説明できるようにします。

実行できるRust:二つの木を比較する

次のコードは構文木の形と計算結果の関係を確かめる、独立したホスト用の契約テストです。rustcで単一ファイルとして実行できます。配布プロジェクトのJavaScript字句解析器をこの短いコードへ置き換えるものではなく、入力文字列を構文解析する機能も含みません。木を明示的に構築することで、構文解析器が評価器へ渡すべき情報を最小限に取り出しています。

Exprの列挙型を読むと、数値と二項演算を別の形で表しています。Boxは再帰的な木の大きさを確定させるために使います。evalは木の形だけに従って再帰し、文字列の中から演算子を探しません。14と20の両方を検証した後、同じ二つの式を配布CLIとWASMへ入力してください。実際の解析結果とこの契約の関係を説明できれば、図と実装を結びつけられています。

rust
#[derive(Debug, PartialEq)]
enum Expr { Num(i64), Add(Box<Expr>, Box<Expr>), Mul(Box<Expr>, Box<Expr>) }
fn eval(e: &Expr) -> i64 {
    match e { Expr::Num(n) => *n, Expr::Add(a,b) => eval(a)+eval(b),
        Expr::Mul(a,b) => eval(a)*eval(b) }
}
fn main() {
    let tree = Expr::Add(Box::new(Expr::Num(2)), Box::new(Expr::Mul(
        Box::new(Expr::Num(3)), Box::new(Expr::Num(4)))));
    assert_eq!(eval(&tree), 14);
    let grouped = Expr::Mul(Box::new(Expr::Add(Box::new(Expr::Num(2)),
        Box::new(Expr::Num(3)))), Box::new(Expr::Num(4)));
    assert_eq!(eval(&grouped), 20);
    println!("precedence=14 grouped=20");
}

変更点を局所化して調べる

新しい演算子を加えるときは、字句解析だけの変更で済むと考えないでください。トークン、優先順位、構文木、評価、診断、入力例がつながります。例えば比較演算を加算と同じ強さで読むと、個々の演算は実装できていても条件式全体が誤ります。既存の正常例を残し、追加した演算子が左右のどの式を取り込むかを確認する、小さな対照入力を先に作ります。

ソースの関数名を覚えることより、境界を言葉で説明することを重視します。lex_jsの出力にはどの段階まで意味があるか、parse_programは何を保証して評価器へ渡すかを説明してください。Rustの型とエラーの戻り値を追うと、どの関数が入力を消費し、どの関数が位置情報を保つかを読み取れます。画面のトレースの一行を、関連するRustの分岐へ戻して確認します。

演習:解析結果を予測してから動かす

演習では、let score = 2 + 3 * 4;とlet score = (2 + 3) * 4;を用意し、それぞれの右辺を木に描きます。次に掛け算の右辺を削除した入力を作り、最初に不足が確定するトークン位置を予測してください。正常な二例と失敗例を同じ環境で動かし、数値、構造、診断を別々に記録します。解析に失敗した入力でDOMの更新が進んだと解釈しないよう注意します。

発展課題では、日本語を含む文字列を条件分岐の中へ移し、バイト位置と文字の見え方を比べます。提出物には、対応する構文の一覧、予測した木、実測した結果、予測と異なった理由を書いてください。最後に未対応の構文を一つ選び、どの段階で拒否されるべきかを説明します。正しく動く例を増やすだけでなく、受け付けない入力の境界まで示すと、処理系の契約が明確になります。

RustでJavaScriptを解析して実行する

実験の途中状態を読み込み中…

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

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

CS基礎を固める · STEP 20

学習コースから次を選ぶ