インタプリタを自作する演習 — 字句解析と構文解析から実行まで

インタプリタを自作する。コードのカード、組み合わせたパズルと電卓。

1 + 2 * 3 を計算するプログラムを、文字列の左から順に処理して書くと 9 になります。正解は 7 です。

この「掛け算が先」という、誰でも知っているはずの規則をプログラムに教えるところで、言語処理系の話の8割が終わります。 変数も if も関数も、そのあとに足す部品にすぎません。

この記事は、四則演算の電卓から始めて、変数と if と while と関数が動く小さな言語まで、200行くらいで作る回です。正規表現エンジンを自作した回と同じで、「木にしてから辿る」という同じ形がまた出てきます。

対象レベル: 中級 / 区分: 必要に応じて読む

目次

この記事でわかること

  • 言語処理系が3つの部品(字句解析・構文解析・評価)でできていること
  • 演算子の優先順位が、関数の呼び出しの深さで表せること(ここが山場)
  • 式と文の違い。なぜ if は値を返さない言語が多いのか
  • 変数の有効範囲(スコープ)が、ただの親子関係であること
  • インタプリタとコンパイラがどこまで同じで、どこから違うのか

この記事でやること

  1. まず、素朴に書いて 9 という間違った答えを出す
  2. 文字の列を「語」の列にする(字句解析)
  3. 語の列を木にする(構文解析・山場①)
  4. 木を辿って計算する(評価)
  5. 変数・if・while・関数を足す(山場②)
  6. エラーに行番号を付ける(山場③)

先に知る言葉

この記事で初めて出てくる言葉です。 詳しくは用語集にもまとめてあります。

言葉意味
字句解析(トークナイズ)文字の列を「語」に切る。1+23 → 1 + 23
構文解析(パース)語の列を、意味のつながった木にする
ASTその木のこと。抽象構文木。ただの入れ子のオブジェクト
再帰下降文法の階層をそのまま関数の呼び出しにする書き方。手で書ける構文解析
環境変数名 → 値の対応表。関数を呼ぶたびに新しく作る

準備

mkdir -p ~/mylang
cd ~/mylang
node -v
v22.14.0

① まず、間違える

先に間違った答えを見ておきます。 ここを飛ばすと、このあとの面倒くささが何のためなのか分からなくなります。

cat > naive.js <<'EOF'
// 左から順に計算する(素朴だが間違い)
const src = "1 + 2 * 3";
const tokens = src.split(/\s+/);
let acc = Number(tokens[0]);
for (let i = 1; i < tokens.length; i += 2) {
  const op = tokens[i], n = Number(tokens[i + 1]);
  acc = op === "+" ? acc + n : op === "-" ? acc - n : op === "*" ? acc * n : acc / n;
}
console.log(acc);
EOF
node naive.js
9

9 です。 1 + 2 を先にやってしまっています。優先順位は「後回しにする仕組み」が無いと表現できません。

② 字句解析 —— 文字を語に切る

まず、文字の列を扱いやすい単位に切ります。ここは難しくありません。

cat > lexer.js <<'EOF'
export function tokenize(src) {
  const tokens = [];
  let i = 0, line = 1;
  const KEYWORDS = new Set(["let", "if", "else", "while", "fn", "return", "print"]);

  while (i < src.length) {
    const c = src[i];
    if (c === "\n") { line++; i++; continue; }
    if (/\s/.test(c)) { i++; continue; }
    if (c === "#") { while (i < src.length && src[i] !== "\n") i++; continue; }

    if (/[0-9]/.test(c)) {                       // 数
      let s = i;
      while (i < src.length && /[0-9.]/.test(src[i])) i++;
      tokens.push({ type: "num", value: Number(src.slice(s, i)), line });
      continue;
    }
    if (/[A-Za-z_]/.test(c)) {                   // 名前かキーワード
      let s = i;
      while (i < src.length && /[A-Za-z0-9_]/.test(src[i])) i++;
      const word = src.slice(s, i);
      tokens.push({ type: KEYWORDS.has(word) ? word : "name", value: word, line });
      continue;
    }
    const two = src.slice(i, i + 2);             // 2文字の記号を先に見る
    if (["==", "!=", "<=", ">="].includes(two)) {
      tokens.push({ type: two, line }); i += 2; continue;
    }
    if ("+-*/()<>={},;".includes(c)) {
      tokens.push({ type: c, line }); i++; continue;
    }
    throw new Error(`${line}行目: 読めない文字 '${c}'`);
  }
  tokens.push({ type: "eof", line });
  return tokens;
}
EOF

2文字の記号を先に見るのが要点です。 1文字ずつ見ると <= が < と = に割れて、そのあと絶対に直せません。長いものから試すのは、字句解析の鉄則です。

③ 優先順位を、関数の深さで表す

ここがこの記事の中心です。 「掛け算が先」を、条件分岐ではなく関数の呼び出し順で表します。

式        := 比較
比較      := 足し算 ( ("=="|"!="|"<"|">"|"<="|">=") 足し算 )*
足し算    := 掛け算 ( ("+"|"-") 掛け算 )*
掛け算    := 単項   ( ("*"|"/") 単項 )*
単項      := "-" 単項 | 基本
基本      := 数 | 名前 | 名前"(" 引数 ")" | "(" 式 ")"

下にあるものほど先に計算されます。 「足し算」は、自分の仕事を始める前に必ず「掛け算」を呼びます。だから掛け算のほうが先にまとまります。優先順位という概念を、呼び出しの深さに置き換えているわけです。

cat > parser.js <<'EOF'
export function parse(tokens) {
  let p = 0;
  const peek = () => tokens[p];
  const eat = (type) => {
    if (tokens[p].type !== type)
      throw new Error(`${tokens[p].line}行目: ${type} が必要ですが ${tokens[p].type} が来ました`);
    return tokens[p++];
  };

  function expr()  { return comparison(); }

  function comparison() {
    let node = addsub();
    while (["==", "!=", "<", ">", "<=", ">="].includes(peek().type)) {
      const op = tokens[p++].type;
      node = { kind: "binary", op, left: node, right: addsub() };
    }
    return node;
  }
  function addsub() {
    let node = muldiv();
    while (peek().type === "+" || peek().type === "-") {
      const op = tokens[p++].type;
      node = { kind: "binary", op, left: node, right: muldiv() };
    }
    return node;
  }
  function muldiv() {
    let node = unary();
    while (peek().type === "*" || peek().type === "/") {
      const op = tokens[p++].type;
      node = { kind: "binary", op, left: node, right: unary() };
    }
    return node;
  }
  function unary() {
    if (peek().type === "-") { p++; return { kind: "neg", value: unary() }; }
    return primary();
  }
  function primary() {
    const t = tokens[p];
    if (t.type === "num")  { p++; return { kind: "num", value: t.value }; }
    if (t.type === "(")    { p++; const e = expr(); eat(")"); return e; }
    if (t.type === "name") {
      p++;
      if (peek().type === "(") {                 // 関数呼び出し
        p++;
        const args = [];
        while (peek().type !== ")") {
          args.push(expr());
          if (peek().type === ",") p++;
        }
        eat(")");
        return { kind: "call", name: t.value, args, line: t.line };
      }
      return { kind: "var", name: t.value, line: t.line };
    }
    throw new Error(`${t.line}行目: 式が来るはずの場所に ${t.type} があります`);
  }
  // ここから下は文の解析(文法は⑥で説明します)
  function block() {
    eat("{");
    const stmts = [];
    while (peek().type !== "}" && peek().type !== "eof") stmts.push(statement());
    eat("}");
    return stmts;
  }
  function statement() {
    const t = peek();
    if (t.type === "let") {
      p++; const name = eat("name").value; eat("=");
      const value = expr(); eat(";");
      return { kind: "let", name, value };
    }
    if (t.type === "print")  { p++; const value = expr(); eat(";"); return { kind: "print", value }; }
    if (t.type === "return") { p++; const value = expr(); eat(";"); return { kind: "return", value }; }
    if (t.type === "if") {
      p++; eat("("); const cond = expr(); eat(")");
      const then = block();
      let els = null;
      if (peek().type === "else") { p++; els = block(); }
      return { kind: "if", cond, then, else: els };
    }
    if (t.type === "while") {
      p++; eat("("); const cond = expr(); eat(")");
      return { kind: "while", cond, body: block() };
    }
    if (t.type === "fn") {
      p++; const name = eat("name").value; eat("(");
      const params = [];
      while (peek().type !== ")" && peek().type !== "eof") {
        params.push(eat("name").value);
        if (peek().type === ",") p++;
      }
      eat(")");
      return { kind: "fn", name, params, body: block() };
    }
    if (t.type === "name" && tokens[p + 1].type === "=") {   // 代入(== は字句解析で別の語になっている)
      p += 2; const value = expr(); eat(";");
      return { kind: "assign", name: t.value, value };
    }
    const value = expr(); eat(";");                          // 式だけの文
    return { kind: "expr", value };
  }
  function program() {                                       // ファイル全体 = 文の並び
    const stmts = [];
    while (peek().type !== "eof") stmts.push(statement());
    return stmts;
  }
  return { expr, program, eat, peek, at: () => p, set: (v) => (p = v), tokens };
}
EOF

木になったことを、目で見る

node --input-type=module -e '
import { tokenize } from "./lexer.js";
import { parse } from "./parser.js";
const api = parse(tokenize("1 + 2 * 3"));
console.log(JSON.stringify(api.expr(), null, 1));
'
{
 "kind": "binary",
 "op": "+",
 "left":  { "kind": "num", "value": 1 },
 "right": {
  "kind": "binary",
  "op": "*",
  "left":  { "kind": "num", "value": 2 },
  "right": { "kind": "num", "value": 3 }
 }
}

掛け算が、足し算の内側に入っています。 この時点で優先順位は解決済みで、あとはこの木を辿るだけです。「難しいことは、計算の前に終わらせておく」という形が、ここでもそのまま出てきます。

④ 評価 —— 木を辿るだけ

cat > eval.js <<'EOF'
export const hooks = {};             // 関数呼び出しの中身は⑥で run.js が入れる

export function evaluate(node, env) {
  switch (node.kind) {
    case "num": return node.value;
    case "call": return hooks.call(node, env);
    case "neg": return -evaluate(node.value, env);
    case "var": {
      const scope = env.find(node.name);
      if (!scope) throw new Error(`${node.line}行目: ${node.name} は定義されていません`);
      return scope.vars.get(node.name);
    }
    case "binary": {
      const a = evaluate(node.left, env), b = evaluate(node.right, env);
      switch (node.op) {
        case "+": return a + b;
        case "-": return a - b;
        case "*": return a * b;
        case "/":
          if (b === 0) throw new Error("0 では割れません");
          return a / b;
        case "==": return a === b ? 1 : 0;
        case "!=": return a !== b ? 1 : 0;
        case "<":  return a < b ? 1 : 0;
        case ">":  return a > b ? 1 : 0;
        case "<=": return a <= b ? 1 : 0;
        case ">=": return a >= b ? 1 : 0;
      }
    }
  }
  throw new Error(`評価できない節: ${node.kind}`);
}
EOF

20 行しかありません。 難しい仕事は構文解析が終わらせているので、評価は木の形どおりに再帰するだけです。

⑤ 変数を足す —— 環境は、ただの Map

cat > env.js <<'EOF'
export class Env {
  constructor(parent = null) { this.vars = new Map(); this.parent = parent; }
  find(name) {                      // 自分に無ければ親へ聞きに行く
    if (this.vars.has(name)) return this;
    return this.parent ? this.parent.find(name) : null;
  }
  define(name, value) { this.vars.set(name, value); }
  assign(name, value) {
    const scope = this.find(name);
    if (!scope) throw new Error(`${name} は定義されていません`);
    scope.vars.set(name, value);
  }
}
EOF

スコープの正体は、この parent の1本の線です。 「関数の中から外の変数が見える」「外から中の変数は見えない」——どちらも find が親にしか登らない、というだけで説明が付きます。

⑥ 式と文を分ける

1 + 2 は値になります。while は値になりません。この違いを、木の種類として分けます。

文 := "let" 名前 "=" 式 ";"
    | "print" 式 ";"
    | "if" "(" 式 ")" ブロック ( "else" ブロック )?
    | "while" "(" 式 ")" ブロック
    | "fn" 名前 "(" 引数 ")" ブロック
    | "return" 式 ";"
    | 名前 "=" 式 ";"
    | 式 ";"
cat > run.js <<'EOF'
import { readFileSync } from "node:fs";
import { tokenize } from "./lexer.js";
import { parse } from "./parser.js";
import { evaluate, hooks } from "./eval.js";
import { Env } from "./env.js";

function execBlock(stmts, env) {
  for (const s of stmts) {
    const r = exec(s, env);
    if (r && r.return) return r;      // return を上へ伝える
  }
  return null;
}

function exec(node, env) {
  switch (node.kind) {
    case "let":    env.define(node.name, evaluate(node.value, env)); return null;
    case "assign": env.assign(node.name, evaluate(node.value, env)); return null;
    case "print":  console.log(evaluate(node.value, env)); return null;
    case "if":
      return evaluate(node.cond, env)
        ? execBlock(node.then, new Env(env))
        : (node.else ? execBlock(node.else, new Env(env)) : null);
    case "while": {
      let guard = 0;
      while (evaluate(node.cond, env)) {
        const r = execBlock(node.body, new Env(env));
        if (r && r.return) return r;
        if (++guard > 1_000_000) throw new Error("ループが100万回を超えました");
      }
      return null;
    }
    case "fn":     env.define(node.name, { params: node.params, body: node.body, env }); return null;
    case "return": return { return: true, value: evaluate(node.value, env) };
    case "expr":   evaluate(node.value, env); return null;   // 式だけの文
  }
}
EOF

while に上限を入れているのは、わざとです。 自作の言語で while (1) {} を書くと、端末ごと固まります。止められない仕組みを作るときは、止める仕掛けを先に入れる——正規表現エンジンを書いたときに、暴走する入力で学んだのと同じことです。

関数呼び出し —— 新しい環境を作る

cat >> run.js <<'EOF'
hooks.call = (node, env) => {          // eval.js の case "call" から呼ばれる
  const f = env.find(node.name)?.vars.get(node.name);
  if (!f) throw new Error(`${node.line}行目: 関数 ${node.name} がありません`);
  if (f.params.length !== node.args.length)
    throw new Error(`${node.line}行目: ${node.name} は引数 ${f.params.length} 個です`);
  const local = new Env(f.env);          // ⚠️ 呼び出し元ではなく、定義された場所の環境を親にする
  f.params.forEach((p, i) => local.define(p, evaluate(node.args[i], env)));
  const r = execBlock(f.body, local);
  return r ? r.value : 0;
};

// ファイルを読んで、字句解析 → 構文解析 → 実行
const src = readFileSync(process.argv[2], "utf8");
execBlock(parse(tokenize(src)).program(), new Env());
EOF

評価器(eval.js)は関数の中身を実行する execBlock を知らないので、case "call" は run.js が入れた hooks.call に任せています。これで run.js がそろいました。

new Env(f.env) の1行が、クロージャの正体です。 呼び出し元の環境を親にすると、関数の中身が「どこから呼ばれたか」で変わってしまいます。定義された場所を覚えているから、JavaScript の関数は外側の変数を見られます。

⑦ 動かす

cat > sample.ml <<'EOF'
# 階乗を出す
fn fact(n) {
  if (n <= 1) { return 1; }
  return n * fact(n - 1);
}

let i = 1;
while (i <= 5) {
  print fact(i);
  i = i + 1;
}
EOF
node run.js sample.ml
1
2
6
24
120

自分で決めた文法で書いたファイルが、自分で書いたプログラムで動きました。

⑧ エラーに行番号を付ける

ここを省くと、自作言語は使えません。 どこで間違えたか分からないからです。

let x = ;
1行目: 式が来るはずの場所に ; があります

行番号は字句解析のときにしか分かりません。 構文解析の段階では、もう文字の位置が失われているからです。だから tokenize で全トークンに line を付けておき、以降はそれを運びます。

エラーの読み方の回で「下から読む」と書いたのは、この構造の裏返しです。 処理系は、起きた場所から呼び出し元へ向かってメッセージを積み上げます。一番下(一番内側)が、実際に落ちた場所です。

⑨ インタプリタとコンパイラは、どこから違うのか

工程インタプリタコンパイラ
字句解析同じ
構文解析同じ
木ができたあとその場で辿って実行する機械語やバイトコードに書き出す
実行の速さ遅い(毎回木を辿る)速い(変換は1回)
エラーに気づく時期そこへ到達したとき変換のとき

前半は完全に同じです。 違うのは「木をどうするか」だけ。TypeScript が「実行時には消える」のも、同じ話で、型の検査は木ができた時点で終わっていて、出力する JavaScript には型が残りません。

作らなかったもの

省いたものなぜ
文字列型・配列評価器に型の判定が増えるだけで、新しい理解が増えない
バイトコード木を辿る形が見えなくなる。速さは目的ではない
ガベージコレクションJavaScript が持っているものに任せる
エラーからの復帰最初の1つで止める。複数まとめて報告するのは別の設計

完成の判定

#確かめること合格の形
1優先順位print 1 + 2 * 3; が 7
2括弧print (1 + 2) * 3; が 9
3再帰fact(5) が 120
4スコープ関数の中で let した変数が、外から見えない
5エラー未定義の変数で行番号付きで止まる

4 と 5 が本番です。 1〜3 は電卓でも通ります。

つまずいたところ

1 + 2 * 3 が 9 のまま

addsub が muldiv を呼んでいません。文法の階層と、関数の呼び出しの階層は同じ形でなければいけません。片方だけ直しても合いません。

括弧を閉じ忘れると、無限ループになる

while (peek().type !== ")") のような判定は、eof を考えていないと止まりません。終端を必ず条件に入れます。

while (peek().type !== ")" && peek().type !== "eof") { … }

関数の中から外の変数が見えない

new Env(f.env) ではなく new Env() にしています。親を渡さないと、find が登れません。

再帰が深いと落ちる

RangeError: Maximum call stack size exceeded

これは自作言語ではなく、下で動いている JavaScript のスタックが尽きています。 評価器が再帰で書かれているので、対象言語の再帰の深さが、そのままホスト言語のスタックの深さになります。スタックとキューの回で見たエラーが、ここでそのまま出ます。

後片づけ

cd ~
rm -rf mylang

よくある質問

なぜ再帰下降で書くのですか。構文解析器の生成ツールは使わないのですか
手で書けて、文法の形がそのままコードの形になるからです。生成ツールを使うと、文法ファイルは短くなりますが、生成されたコードは読めないので「なぜ掛け算が先になるのか」が見えません。実際、多くの本番の処理系も手書きの再帰下降を採用しています。エラーメッセージを自分で作り込めることが大きな理由です。
この言語は実用になりますか
なりません。文字列も配列もなく、数値だけを扱う言語だからです。目的は実用ではなく、言語処理系が3つの部品でできていることを手で確かめることにあります。ここまで作ってあれば、文字列型を足す作業が字句解析と評価の2か所で済むこと、それが設計として自然であることも見えるようになります。
優先順位を変えたいときは何を直しますか
関数の呼び出し順を変えます。たとえば累乗を掛け算より優先させたいなら、掛け算の関数が呼ぶ相手を、単項ではなく新しい累乗の関数にします。条件分岐や優先順位の表を書き換えるのではなく、階層そのものを組み替えるのがこの書き方の特徴です。
while に回数の上限を入れるのは邪道ではありませんか
学習用としては入れたほうが安全です。無限ループを書いたときに端末ごと固まると、原因が分からないまま強制終了することになり、何も学べません。上限に当たったときに明示的なエラーを出せば、自分が無限ループを書いたことがその場で分かります。本番の処理系では入れませんが、その場合は実行を外から止められる仕組みが別にあります。
コンパイラを作るなら、どこから変えればよいですか
評価器を置き換えます。字句解析と構文解析はそのまま使えるので、木を辿って計算する代わりに、木を辿って命令列を出力する関数を書きます。最初は自分で決めたバイトコードにして、それを実行する小さな仮想機械を書くのが分かりやすい順番です。いきなり機械語を出そうとすると、レジスタの割り当てという別の難問が同時に来ます。

まとめ — 理解できたこと

  • 言語処理系は3つの部品でできている。 字句解析・構文解析・評価
  • 優先順位は、関数の呼び出しの深さで表す。 深いほど先にまとまる
  • 難しい仕事は構文解析で終わる。 評価は木のとおりに再帰するだけで 20 行
  • スコープの正体は parent の1本の線。 関数が「定義された場所」を覚えているのがクロージャ
  • 行番号は字句解析でしか取れない。 あとから足せないものは、最初に持たせる
  • インタプリタとコンパイラは、木ができるまで同じ。 違うのはその後だけ

参考リンク

次に読む

この記事は 【番外編】roadmap.sh の外 の 30 / 35 本目です。

記事
← 前の記事正規表現が固まる理由 — エンジンを100行で自作する
→ 次の記事512バイトに入らなくなる — メモリ管理とマルチタスク

上から順に読めば積み上がるように並べています。 飛ばしても構いませんが、詰まったら前の回に戻ってください。

全体の順路は はじめに にあります。

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次