【Rust】数式を「計算の木」へ：ASTと再帰下降構文解析で電卓エンジンの心臓部を作る #4

前回は、関数や定数の文字列を意味のある塊であると認識させるために、tomlに定義した関数を読み込むDefinitionsを実装してみました。

今回は、DefinitionsとLexerで部品として解析したものを、数式として構造として解析するParserの実装をしていきます。

1. Parserの概要：バラバラの単語を「計算の設計図」へ

作る前に、Parserについておさらいします。

前回実装したLexerによって、数式は「意味のある単語（トークン）」に分解されました。しかし、これらはまだ横一列に並んでいるだけの状態です。

例えば、1 + 2 * 3 という入力を考えてみましょう。 人間なら直感的に「2 * 3 を先にやって、その結果に 1 を足す」と判断できますが、計算機にとっては単なる [1, +, 2, *, 3] というリストでしかありません。これを、演算子の優先順位を守りながら、正しく計算できる「構造」に組み立てるのが Parser（構文解析器¹） の役割です。

1.1. 「計算の木」を作る（抽象構文木：AST）

Parserは、トークンの列を読み進めながら、抽象構文木（Abstract Syntax Tree, AST） と呼ばれるツリー構造を構築します。

この木構造のポイントは、「優先順位が高い計算ほど、木の下の方（葉に近い方）に配置される」 という点です。 計算を実行するときは、この木を末端から順番に解いていくことで、自然と正しい順序で答えが導き出されます。

1.2. Rustで立ちはだかる「再帰」の壁

Parserを実装する際、プログラム的には「式の中に式が含まれる」という再帰的な定義が必要になります。

• 式 ＝ 数値
• 式 ＝ 式 ＋ 式
• 式 ＝ 関数(引数1, 引数2, …)

ここでRust学習者が最初に突き当たるのが、「列挙型（enum）のサイズが計算できない」 というコンパイルエラーです。

// これだとエラーになる
enum Expr {
    Number(f64),
    Binary(Expr, Op, Expr), // Exprの中に自分自身(Expr)を入れると、サイズが無限になってしまう
}

Rustはコンパイル時にデータのサイズを確定させる必要があるため、自分自身を中に持つ構造はそのままでは定義できません。そこで、Box<T> を使ってデータをヒープ領域に逃がし、「実体ではなく、実体へのポインタ（固定サイズ）」を持たせることで、この無限再帰の構造を実現します。

関連記事 ヒープって何？： ヒープソート前座　ヒープとは？【ソートアルゴリズム入門】#10

1.3. どうやって木を作るのか？（再帰下降構文解析）

今回の実装では、「再帰下降構文解析（Recursive Descent Parsing）」 という手法を採用します。

これは、

1. まずは「足し算・引き算」を探す
2. その中で「掛け算・割り算」を探す
3. さらにその中で「数値や括弧」を探す ……といった具合に、優先順位が低いものから高いものへと順番に掘り下げていく方法です。

この仕組みを作ることで、複雑な 1 + 2 * (3 + 4) といった式も、数学的なルール通りに解釈できるようになります。

調べてみると歴史背景や現代のプログラミング言語の源流とかに触れられて結構面白かったです。

2. 実装の要件定義をしてみる

2.1. 演算子の優先順位を「階層化」

1.3節で説明した、優先順位を以下のように定義しました。

このように関数を分けることで、後から「モジュロ演算（%）を追加したい」となった時も、term() 関数の中に処理を一行足すだけで済み、全体の構造を壊さずに拡張できます。

2.2 三つの「辞書」を束ねる：Environment（環境）

ここは、今回の実装だけの話ではないですが、電卓の拡張性を持たせるために、次の評価(Evaluation)をスムーズに行うための設計です。パースするときに必要な要素は3つの環境です。

Parserは、計算の瞬間に以下の3つの辞書（HashMap）にアクセスできる必要があります。

1. Global Constants: TOMLで定義された pi や e など。
2. Local Scope: 関数 conv(W, K) を計算する際の W や K といった、その場限りの引数。
3. History: $1, $2 のような、アプリが保持する過去の計算結果。

これらを Context 構造体として一つにまとめておくことで、評価関数（eval）をスッキリとした設計に保てます。

3. 実装

パースのコア部分の抜粋です。

let expr = self.parse_expression()?;で一番優先度の低いものの解析を呼び出し、その中で次に優先度が高いものparse_termを呼び出していくという感じです。

    pub fn parse(&mut self) -> Result<Expr, String> {
        let expr = self.parse_expression()?;
        if let Some(Token::EOF) = self.tokens.peek() {
            Ok(expr)
        } else {
            Err(format!("Unexpected token: {:?}", self.tokens.peek()))
        }
    }

    // 1. 足し算・引き算 (優先順位：低)
    fn parse_expression(&mut self) -> Result<Expr, String> {
        let mut left = self.parse_term()?;

        while let Some(token) = self.tokens.peek() {
            let op = match token {
                Token::Plus => BinOp::Add,
                Token::Minus => BinOp::Sub,
                _ => break,
            };
            self.tokens.next(); // 演算子を消費
            let right = self.parse_term()?;
            left = Expr::BinaryOp {
                left: Box::new(left),
                op,
                right: Box::new(right),
            };
        }
        Ok(left)
    }
    // 2. 乗除算
    fn parse_term(&mut self) -> Result<Expr, String> { ... }

パサーの出力をそのまま出してもよかったですが、視づらいので、簡易的に、四則演算と累乗のみの評価と計算をする簡易版Evaleterを作り、計算させてみました。

// 簡易版評価機（関数は放置）
match expr {
    Expr::Number(n) => Ok(*n),
    Expr::Variable(name) => constants.get(name).copied().ok_or_else(|| format!("Unknown variable: {}", name)),
    Expr::BinaryOp { left, op, right } => {
        let l = evaluate(left, constants)?;
        let r = evaluate(right, constants)?;
        match op {
            BinOp::Add => Ok(l + r),
            BinOp::Sub => Ok(l - r),
            BinOp::Mul => Ok(l * r),
            BinOp::Div => {
                if r == 0.0 { Err("Division by zero".into()) } else { Ok(l / r) }
            }
            BinOp::Pow => Ok(l.powf(r)),
        }
    }
    Expr::UnaryOp { op, expr } => {
        let val = evaluate(expr, constants)?;
        match op {
            UnOp::Neg => Ok(-val),
        }
    }
    _ => Err("Function calls and History references are not yet implemented in evaluator".into()),
}

動作結果。

出力結果を見れば、通常の四則演算と、符号(-5)の計算、および、カッコつきとカッコ無しでの累乗の計算ができていることが確認できます。

(2 ^3) ^2 = 64
2 ^3 ^2 = 512 // こっちは右結合

なぜ標準は右結合なのかをまとめてみました：　なぜ電卓プログラムのべき乗は 2^3^2 = 512 でなければならないのか？【右結合・計算機】

さいごに

今回は、数式として構造として解析するParserの実装をしてみました。今の実装はとりあえずの仮組なので、次回は関数を読み込む時点で自動的に構造を作っておき、高速化するなど関数と基本計算を組み合わせて使えるように作り込んでいこうと思います。

次回　関数の構造解析 : 関連記事は、2026年4月30日に公開予定 (あと8時間)

1. 参考 : wiki 再帰構文解析(EN) ↩︎

関連記事

第１回　構想編 ：【Rustで作る】ターミナル関数電卓を設計する（アーキテクチャ編） #1
第２回　Lexer実装：【Rust】自作計算機エンジンへの道：Lexer（字句解析）で数式をトークンに分解する #2
第３回　tomlの読み込み：【Rust】TOMLで関数を自由に追加！自作電卓に設定読み込みとホットリロードを実装する #3