練習: 演算子の優先順位と仕上げ

前の章で 2 + 3 * 4 = 20 という悲しい結果になった．本来は 14 であるべき．この章で直す．

なぜ間違うのか

今の parse は全ての演算子を左から順に同じ優先度で処理している:

2 + 3 * 4
→ (2 + 3) * 4
→ 20

本来は * が + より先に結合されるべき:

2 + 3 * 4
→ 2 + (3 * 4)
→ 14

解決策: パースを 2 段階に分ける

優先度の低い演算子ほど「上のレイヤー」で処理する:

parse（エントリーポイント）
  └→ parse_add_sub（+ と - を処理．優先度: 低）
       └→ parse_mul_div（* と / を処理．優先度: 高）
            └→ parse_primary（数値を処理）

parse_mul_div が先に呼ばれるので，* と / が先にまとまる．これが 再帰下降パーサー の基本的な考え方．

parse を分割する

今の parse を parse_add_sub と parse_mul_div に分ける:

fn parse(&mut self) -> Expr {
    self.parse_add_sub()
}

// + と - を処理（優先度: 低）
fn parse_add_sub(&mut self) -> Expr {
    let mut left = self.parse_mul_div(); // ← parse_primary ではなく parse_mul_div

    loop {
        match self.peek() {
            Some(Token::Plus) | Some(Token::Minus) => {
                let op = self.next_token().unwrap();
                let right = self.parse_mul_div(); // ← ここも
                left = Expr::BinOp {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                };
            }
            _ => break,
        }
    }

    left
}

// * と / を処理（優先度: 高）
fn parse_mul_div(&mut self) -> Expr {
    let mut left = self.parse_primary();

    loop {
        match self.peek() {
            Some(Token::Star) | Some(Token::Slash) => {
                let op = self.next_token().unwrap();
                let right = self.parse_primary();
                left = Expr::BinOp {
                    op,
                    left: Box::new(left),
                    right: Box::new(right),
                };
            }
            _ => break,
        }
    }

    left
}

構造は parse_add_sub と parse_mul_div でほぼ同じ．違いは:

• どの演算子を処理するか (+/- か */-)
• 部分式をどこからパースするか (parse_mul_div か parse_primary)

2 + 3 * 4 がどうパースされるか追ってみよう:

1. parse_add_sub 開始
2. parse_mul_div 呼び出し → parse_primary → Number(2) を left に
3. peek が Plus → * でも / でもないので parse_mul_div は Number(2) を返す
4. parse_add_sub に戻る．peek が Plus → ループに入る
5. Plus を消費，parse_mul_div 呼び出し
6. parse_primary → Number(3) を left に
7. peek が Star → ループに入る！Star を消費，parse_primary → Number(4)
8. left = BinOp { Star, 3, 4 } → parse_mul_div 終了
9. parse_add_sub に戻る．left = BinOp { Plus, 2, BinOp { Star, 3, 4 } }

Star が先にまとまった．

括弧を追加する

ついでに括弧も実装しよう．(1 + 2) * 3 のように優先順位を変えたいときに使う．

Token に追加:

#[derive(Debug, Clone, PartialEq)]
enum Token {
    Number(f64),
    Plus,
    Minus,
    Star,
    Slash,
    LParen,     // ← 追加
    RParen,     // ← 追加
}

Lexer に追加:

'(' => {
    tokens.push(Token::LParen);
    self.pos += 1;
}
')' => {
    tokens.push(Token::RParen);
    self.pos += 1;
}

parse_primary を拡張:

fn parse_primary(&mut self) -> Expr {
    match self.next_token() {
        Some(Token::Number(n)) => Expr::Number(n),
        Some(Token::LParen) => {
            // 括弧の中身は一番低い優先度からパースし直す
            let expr = self.parse_add_sub();
            // 閉じ括弧を消費
            match self.next_token() {
                Some(Token::RParen) => {}
                other => panic!("expected ')', got {:?}", other),
            }
            expr
        }
        other => panic!("expected number or '(', got {:?}", other),
    }
}

( を見つけたら parse_add_sub() をもう一度呼ぶ．括弧の中はまた一番優先度の低い演算子からパースし直すので，入れ子の括弧もちゃんと動く．

動かしてみる

fn main() {
    let tests = vec![
        ("2 + 3 * 4", 14.0),
        ("(2 + 3) * 4", 20.0),
        ("1 + 2 * 3", 7.0),
        ("10 - 2 - 3", 5.0),
        ("2 * 3 + 4 * 5", 26.0),
        ("100 / (5 + 5)", 10.0),
        ("(1 + 2) * (3 + 4)", 21.0),
        ("3.14 * 2", 6.28),
    ];

    for (input, expected) in tests {
        let mut lexer = Lexer::new(input.to_string());
        let tokens = lexer.tokenize();
        let mut parser = Parser::new(tokens);
        let ast = parser.parse();
        let result = eval(ast);

        let status = if (result - expected).abs() < 0.0001 { "OK" } else { "NG" };
        println!("[{}] {} = {}", status, input, result);
    }
}

[OK] 2 + 3 * 4 = 14
[OK] (2 + 3) * 4 = 20
[OK] 1 + 2 * 3 = 7
[OK] 10 - 2 - 3 = 5
[OK] 2 * 3 + 4 * 5 = 26
[OK] 100 / (5 + 5) = 10
[OK] (1 + 2) * (3 + 4) = 21
[OK] 3.14 * 2 = 6.28

全部 OK．

REPL を作る

せっかくなので対話的に使えるようにしよう:

use std::io;
use std::io::Write;

fn main() {
    println!("Bitterless Calc v0.1");
    println!("Type 'exit' to quit.");
    println!();

    loop {
        print!("> ");
        io::stdout().flush().unwrap();

        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let input = input.trim().to_string();

        if input == "exit" {
            break;
        }

        if input.is_empty() {
            continue;
        }

        let mut lexer = Lexer::new(input);
        let tokens = lexer.tokenize();
        let mut parser = Parser::new(tokens);
        let ast = parser.parse();
        let result = eval(ast);

        println!("{}", result);
    }
}

cargo run

Bitterless Calc v0.1
Type 'exit' to quit.

> 1 + 2 * 3
7
> (1 + 2) * 3
9
> 100 / 3
33.333333333333336
> exit

新しく出てきた要素:

• use std::io — 標準ライブラリの入出力モジュールを使う宣言
• io::stdout().flush().unwrap() — print! は改行しないので，表示を確実に出すために flush する
• io::stdin().read_line(&mut input) — キーボード入力を input に読み込む
• .trim() — 前後の空白や改行を除去

&mut input で &mut が出てきた．read_line は「この変数の中身を変更するよ」と宣言している．今は「おまじない」で OK．

最終完成コード

全 5 章をかけて作った電卓の完成形:

use std::io;
use std::io::Write;

// ---- Token ----

#[derive(Debug, Clone, PartialEq)]
enum Token {
    Number(f64),
    Plus,
    Minus,
    Star,
    Slash,
    LParen,
    RParen,
}

// ---- Lexer ----

struct Lexer {
    input: Vec<char>,
    pos: usize,
}

impl Lexer {
    fn new(input: String) -> Lexer {
        Lexer {
            input: input.chars().collect(),
            pos: 0,
        }
    }

    fn tokenize(&mut self) -> Vec<Token> {
        let mut tokens = Vec::new();

        while self.pos < self.input.len() {
            let ch = self.input[self.pos];

            match ch {
                ' ' | '\t' => {
                    self.pos += 1;
                }
                '+' => {
                    tokens.push(Token::Plus);
                    self.pos += 1;
                }
                '-' => {
                    tokens.push(Token::Minus);
                    self.pos += 1;
                }
                '*' => {
                    tokens.push(Token::Star);
                    self.pos += 1;
                }
                '/' => {
                    tokens.push(Token::Slash);
                    self.pos += 1;
                }
                '(' => {
                    tokens.push(Token::LParen);
                    self.pos += 1;
                }
                ')' => {
                    tokens.push(Token::RParen);
                    self.pos += 1;
                }
                '0'..='9' => {
                    let token = self.read_number();
                    tokens.push(token);
                }
                _ => {
                    self.pos += 1;
                }
            }
        }

        tokens
    }

    fn read_number(&mut self) -> Token {
        let start = self.pos;

        while self.pos < self.input.len()
            && (self.input[self.pos].is_ascii_digit() || self.input[self.pos] == '.')
        {
            self.pos += 1;
        }

        let num_str: String = self.input[start..self.pos].iter().collect();
        let num: f64 = num_str.parse().unwrap();

        Token::Number(num)
    }
}

// ---- AST ----

#[derive(Debug, Clone)]
enum Expr {
    Number(f64),
    BinOp {
        op: Token,
        left: Box<Expr>,
        right: Box<Expr>,
    },
}

// ---- Parser ----

struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}

impl Parser {
    fn new(tokens: Vec<Token>) -> Parser {
        Parser { tokens, pos: 0 }
    }

    fn peek(&self) -> Option<Token> {
        if self.pos < self.tokens.len() {
            Some(self.tokens[self.pos].clone())
        } else {
            None
        }
    }

    fn next_token(&mut self) -> Option<Token> {
        if self.pos < self.tokens.len() {
            let token = self.tokens[self.pos].clone();
            self.pos += 1;
            Some(token)
        } else {
            None
        }
    }

    fn parse(&mut self) -> Expr {
        self.parse_add_sub()
    }

    fn parse_add_sub(&mut self) -> Expr {
        let mut left = self.parse_mul_div();

        loop {
            match self.peek() {
                Some(Token::Plus) | Some(Token::Minus) => {
                    let op = self.next_token().unwrap();
                    let right = self.parse_mul_div();
                    left = Expr::BinOp {
                        op,
                        left: Box::new(left),
                        right: Box::new(right),
                    };
                }
                _ => break,
            }
        }

        left
    }

    fn parse_mul_div(&mut self) -> Expr {
        let mut left = self.parse_primary();

        loop {
            match self.peek() {
                Some(Token::Star) | Some(Token::Slash) => {
                    let op = self.next_token().unwrap();
                    let right = self.parse_primary();
                    left = Expr::BinOp {
                        op,
                        left: Box::new(left),
                        right: Box::new(right),
                    };
                }
                _ => break,
            }
        }

        left
    }

    fn parse_primary(&mut self) -> Expr {
        match self.next_token() {
            Some(Token::Number(n)) => Expr::Number(n),
            Some(Token::LParen) => {
                let expr = self.parse_add_sub();
                match self.next_token() {
                    Some(Token::RParen) => {}
                    other => panic!("expected ')', got {:?}", other),
                }
                expr
            }
            other => panic!("expected number or '(', got {:?}", other),
        }
    }
}

// ---- Eval ----

fn eval(expr: Expr) -> f64 {
    match expr {
        Expr::Number(n) => n,
        Expr::BinOp { op, left, right } => {
            let l = eval(*left);
            let r = eval(*right);
            match op {
                Token::Plus => l + r,
                Token::Minus => l - r,
                Token::Star => l * r,
                Token::Slash => l / r,
                _ => panic!("unknown operator: {:?}", op),
            }
        }
    }
}

// ---- main ----

fn main() {
    println!("Bitterless Calc v0.1");
    println!("Type 'exit' to quit.");
    println!();

    loop {
        print!("> ");
        io::stdout().flush().unwrap();

        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let input = input.trim().to_string();

        if input == "exit" {
            break;
        }

        if input.is_empty() {
            continue;
        }

        let mut lexer = Lexer::new(input);
        let tokens = lexer.tokenize();
        let mut parser = Parser::new(tokens);
        let ast = parser.parse();
        let result = eval(ast);

        println!("{}", result);
    }
}

おわりに

5 章かけて電卓を作った．振り返ると:

章	何を追加したか	学んだこと
8	数値のパース	enum, struct, impl, match, Vec
9	足し算	Box, Parser 構造体, 再帰
10	引き算	パターンの繰り返しに慣れる
11	掛け算・割り算	優先順位の問題に気づく
12	優先順位・括弧・REPL	再帰下降パーサー, 標準入出力

一歩ずつ，同じパターンを繰り返しながら拡張していくことで，自然と Rust のコードが書けるようになったはず．

次のステップ

ここからの発展として，例えばこんなことを試してみると面白い:

• 単項マイナス: -5 や -(1 + 2) を扱えるようにする
• 変数: x = 10 のように変数を定義して x + 5 で使えるようにする（HashMap を使う）
• エラーハンドリング: panic! の代わりに Result を使って，不正な入力を優雅に処理する
• モジュール分割: Token, Lexer, Parser, Eval をそれぞれ別ファイルに分割する

ここから先は The Book を読みながら，正確な所有権やライフタイムの知識を身につけていこう．

また，このチュートリアルの続編として Wonderfull Rust を用意している．Bitterless Rust で意図的に省略した「苦い」部分 — 所有権，ライフタイム，借用チェッカー，トレイト，マクロ，unsafe — これらがなぜ素晴らしいのかを，今度は語弊なしで正確に解説している．Rust の設計思想のどこが優れているのかを概念的に理解したい人は，ぜひ読んでみてほしい．

Bitterless に始めた Rust の旅が，ここから本格的なものになることを願っている．