ブラウザで動く数式パーサを 250 行で書く — 再帰下降、右結合 `^`、`-2^2 = -4`、エラー位置レポート

Posted at 2026-05-20

「電卓に式を貼ったら トークン列と AST も一緒に見えたら勉強になるな」と思って書いた。Shunting-yard ではなく 再帰下降 で実装。^ を右結合、-2^2 = -4 (WolframAlpha / Python / Excel と一致)、関数呼び出し、変数、定数 (pi/e/tau)。約 250 行 + テスト 36 個。記事では文法の組み立てとよくある落とし穴 (右結合、unary 優先順位、エラー位置) を順番に追う。

🌐 デモ: https://sen.ltd/portfolio/expression-eval/
📦 GitHub: https://github.com/sen-ltd/expression-eval

なぜ shunting-yard ではなく再帰下降か

Dijkstra の shunting-yard アルゴリズムは中置式 → 後置式 (RPN) 変換のシンプルな手法で、電卓実装の定番。しかし 記事として読んで分かりやすいのは再帰下降:

文法と実装が 1:1 対応 — BNF を眺めながら関数のネスト構造を読める
デバッガで stack trace を見ると AST の構造がそのまま見える — operator stack の動きを追わなくていい
エラー位置のレポートが自然 — 「今読んでいるトークン」が常に明示的

実装ファイル expr.js は約 250 行。文法は次の通り:

expression     := additive
additive       := multiplicative (('+' | '-') multiplicative)*
multiplicative := unary (('*' | '/' | '%') unary)*
unary          := ('-' | '+')? power
power          := atom ('^' unary)?
atom           := number | identifier | identifier '(' args? ')' | '(' expression ')'
args           := expression (',' expression)*

演算子優先順位は文法のネストで自然に表現される。これが再帰下降の最大の利点。

ハマりどころ 1: `^` を右結合にする

2^3^2 は 2^(3^2) = 2^9 = 512 が正解 ((2^3)^2 = 64 ではない)。

左結合の + - * / % は 左の式に積み上げる ループで書く:

parseAdditive() {
  let left = this.parseMultiplicative();
  while (current is '+' or '-') {
    const right = this.parseMultiplicative();
    left = { type: "binop", op, left, right };       // ← 左に積む
  }
  return left;
}

右結合の ^ は 再帰で右に積む:

parsePower() {
  const base = this.parseAtom();
  if (current is '^') {
    consume();
    const exponent = this.parseUnary();              // ← 再帰
    return { type: "binop", op: "^", left: base, right: exponent };
  }
  return base;
}

ループではなく再帰なので、2^3^2 の AST は:

binop ^
  number 2
  binop ^
    number 3
    number 2

評価は深さ優先 → 内側の 3^2 = 9 → 外側の 2^9 = 512。

テストで両方の方向性を pin:

test("^ is right-associative", () => {
  assert.equal(evaluateExpression("2^3^2"), 512);    // 64 ではない
});

test("parse produces right-associative AST for '2^3^2'", () => {
  const ast = parse("2^3^2");
  assert.equal(ast.op, "^");
  assert.equal(ast.left.value, 2);
  assert.equal(ast.right.op, "^");                   // 右に階層がある
  assert.equal(ast.right.left.value, 3);
  assert.equal(ast.right.right.value, 2);
});

ハマりどころ 2: `-2^2 = -4` (unary minus は `^` より弱い)

これは多くの電卓実装で間違える。

言語 / ツール	`-2^2`	採用ルール
WolframAlpha	`-4`	`^` > unary `-`
Python (`**`)	`-4`	`**` > unary `-`
Excel	`4`	unary `-` > `^` ⚠
Google スプレッドシート	`4`	unary `-` > `^` ⚠
数学の慣習	`-4`	`^` > unary `-`

数学の慣習に従う = -2^2 = -(2^2) = -4。これが正しい。Excel が異端児。

これを実現するには ^ を unary より高い優先度 にする。文法の階層で:

unary  := ('-' | '+')? power      ← 最初に unary を見て、その下に power
power  := atom ('^' unary)?       ← power の右辺は unary に戻る

-2^2 をパースする流れ:

parseUnary() が - を見て consume、parsePower() を呼ぶ
parsePower() が parseAtom() を呼んで 2 を読む
次が ^ なので consume、再び parseUnary() を呼ぶ
ここで右辺の 2 を読む
parsePower() が { ^, 2, 2 } を返す
parseUnary() が { unary -, { ^, 2, 2 } } を返す → 評価すると -(2^2) = -4 ✓

ポイントは unary が power をくるむ こと。「unary の中で power」「power の右辺で unary」を組み合わせると、-2^-3 のような 右辺の負指数も自然に通る:

test("^ accepts unary minus on the exponent side", () => {
  assert.equal(evaluateExpression("2^-3"), 0.125);   // 2^(-3) = 1/8
});

test("^ binds tighter than * but unary minus binds looser than ^", () => {
  assert.equal(evaluateExpression("-2^2"), -4);      // -(2^2)
  assert.equal(evaluateExpression("(-2)^2"), 4);     // (-2)^2
  assert.equal(evaluateExpression("2 * 3^2"), 18);   // 2 * (3^2)
});

(-2)^2 を 4 にしたければ括弧で明示する。括弧があれば parseAtom() 内の '(' 分岐に入って正しく動く。

ハマりどころ 3: トークナイザの数値リテラル

数値リテラルは見た目簡単だが、エッジケースが多い:

42 — 整数
3.14 — 小数
.5 — 整数部省略
1e3 — 科学的記数法 (= 1000)
1.5e-2 — 負の指数 (= 0.015)
1e — エラー: 指数部に数字がない
1e+ — エラー: 符号だけで数字がない

ナイーブな実装:

while (i < source.length && /[0-9.eE+-]/.test(source[i])) i++;
const value = Number(source.slice(start, i));

これは間違い。1+2 を貼ったとき + まで読んでしまう。

正しくは 状態を順番に進める:

// 整数部
while (i < length && isDigit(source[i])) i++;

// 小数部 (任意)
if (source[i] === ".") {
  i++;
  while (i < length && isDigit(source[i])) i++;
}

// 指数部 (任意)
if (source[i] === "e" || source[i] === "E") {
  i++;
  if (source[i] === "+" || source[i] === "-") i++;
  const expStart = i;
  while (i < length && isDigit(source[i])) i++;
  if (i === expStart) throw new ExpressionError("exponent has no digits", start);
}

指数部 e の後に + や - が来てもよいが、その後に 必ず数字が必要。1e だけだと 1 * e ではなく エラーとして扱う (数値リテラルとして始めた以上、整合性を保つ)。

test("tokenize rejects exponent without digits", () => {
  assert.throws(() => tokenize("1e"), ExpressionError);
  assert.throws(() => tokenize("1e+"), ExpressionError);
});

ハマりどころ 4: エラー位置を caret つきで表示する

「Syntax error」だけでは不親切。エラーの列番号とソース + キャレットを返す:

export class ExpressionError extends Error {
  constructor(message, position) {
    super(message);
    this.name = "ExpressionError";
    this.position = position;     // 0-indexed column
  }
}

Parser.parseAtom() から不正なトークンを投げるとき:

throw new ExpressionError(`unexpected "${t.value}"`, t.position);

UI 側でキャレットを描画:

const caret = " ".repeat(Math.max(0, position)) + "^";
els.error.textContent = `${msg}\n${source}\n${caret}`;

ユーザーが見るのは:

parse: unexpected ")"
1 + + )
      ^

テストでも位置を pin できる:

test("error positions are reported", () => {
  try {
    parse("1 + + )");
  } catch (e) {
    assert.ok(e instanceof ExpressionError);
    assert.equal(e.position, 6);    // ")" の列
    return;
  }
  assert.fail("expected ExpressionError");
});

関数呼び出しは `atom` の中で分岐

atom レベルで識別子を読んだとき、次のトークンが ( なら関数呼び出し、そうでなければ変数参照:

parseAtom() {
  // ...
  if (t.type === "ident") {
    this.next();
    const lookahead = this.peek();
    if (lookahead && lookahead.value === "(") {
      this.next();
      const args = [];
      if (peek() is not ")") {
        args.push(this.parseAdditive());
        while (peek() is ",") {
          this.next();
          args.push(this.parseAdditive());
        }
      }
      consume ")";
      return { type: "call", name: t.value, args };
    }
    return { type: "ident", name: t.value };
  }
  // ...
}

min(3, 1, 2) のような 可変引数もこのループで自然に扱える。評価側で Math.min(...args) を呼ぶだけ:

const FUNCTIONS = {
  min: (...xs) => Math.min(...xs),
  max: (...xs) => Math.max(...xs),
  hypot: (...xs) => Math.hypot(...xs),
  // ...
};

変数は定数を上書きする

CONSTANTS = { pi, e, tau, ... } をハードコードしているが、ユーザーが e = 10 と渡したらそちらが優先される設計:

case "ident": {
  if (Object.prototype.hasOwnProperty.call(variables, node.name)) {
    return Number(variables[node.name]);              // ← 変数が勝つ
  }
  if (Object.prototype.hasOwnProperty.call(CONSTANTS, node.name)) {
    return CONSTANTS[node.name];
  }
  throw new ExpressionError(`undefined identifier "${node.name}"`, 0);
}

理由: ユーザーが明示的に渡した変数のほうが意図がはっきりしているから。Object.prototype.hasOwnProperty.call(variables, ...) を使うのは プロトタイプ汚染を避けるため (__proto__ などを引っかけない)。

test("variables override constants if same name", () => {
  assert.equal(evaluateExpression("e + 1", { e: 10 }), 11);   // pi/e/tau より変数が勝つ
});

エッジケース: 0 除算と sqrt(-1)

1 / 0 → Infinity (throw しない、JavaScript の挙動どおり)
sqrt(-1) → NaN
min(3, 1, 2) → 1

これらは formatResult() で表示用に変換:

export function formatResult(value) {
  if (Number.isNaN(value)) return "NaN";
  if (!Number.isFinite(value)) return value > 0 ? "∞" : "−∞";
  if (Number.isInteger(value) && Math.abs(value) < 1e15) return String(value);
  return String(Number(value.toPrecision(12)));
}

toPrecision(12) は浮動小数点の見栄えを良くするためのトリック。0.1 + 0.2 を 0.3 と表示できる (Number("0.30000000000000004").toPrecision(12) === "0.300000000000" → Number(...) で末尾 0 が落ちて "0.3")。

まとめ

再帰下降 で書くと文法 BNF と実装が 1:1 対応するので、記事に書きやすい
右結合 ^ はループではなく再帰で実装する
-2^2 = -4 は unary の中で power を呼ぶ階層で自然に実現できる (Excel は間違っている)
数値リテラルのトークナイズは状態順序に注意。1e 単体はエラー
エラー位置は position 属性 + caret 表示で見せる
関数引数は parseAdditive を再帰で呼ぶ。可変引数も自然に扱える
変数は定数を上書き する。hasOwnProperty.call で proto pollution を避ける

ソース: https://github.com/sen-ltd/expression-eval — MIT、約 250 行 + テスト 36 個、依存ゼロ、ビルドなし。

🛠 Built by SEN LLC as part of an ongoing series of small, focused developer tools. Browse the full portfolio for more.

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up