練習: 掛け算と割り算

足し算と引き算ができた．同じ要領で掛け算と割り算を追加しよう．

Token に Star と Slash を追加

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

Lexer

'*' => {
    tokens.push(Token::Star);
    self.pos += 1;
}
'/' => {
    tokens.push(Token::Slash);
    self.pos += 1;
}

もう慣れたはず．

Parser

parse のループに Star と Slash を追加:

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

    loop {
        match self.peek() {
            Some(Token::Plus)
            | Some(Token::Minus)
            | 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
}

eval

match op {
    Token::Plus => l + r,
    Token::Minus => l - r,
    Token::Star => l * r,    // ← 追加
    Token::Slash => l / r,   // ← 追加
    _ => panic!("unknown operator: {:?}", op),
}

動かしてみる

fn main() {
    let tests = vec![
        ("2 * 3", 6.0),
        ("10 / 3", 10.0 / 3.0),
        ("2 + 3 * 4", 20.0),     // ???
    ];

    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);
        println!("{} = {} (expected {})", input, result, expected);
    }
}

2 * 3 = 6 (expected 6)
10 / 3 = 3.3333333333333335 (expected 3.3333333333333335)
2 + 3 * 4 = 20 (expected 20)

ちょっと待った．2 + 3 * 4 の答えは 20？

算数では 3 * 4 が先に計算されて 2 + 12 = 14 になるはず．でも今の Parser は全ての演算子を左から順に同じ優先度で処理しているので，(2 + 3) * 4 = 20 になってしまう．

AST を見てみよう:

let mut lexer = Lexer::new("2 + 3 * 4".to_string());
let tokens = lexer.tokenize();
let mut parser = Parser::new(tokens);
let ast = parser.parse();
println!("{:?}", ast);

BinOp { op: Star, left: BinOp { op: Plus, left: Number(2.0), right: Number(3.0) }, right: Number(4.0) }

Plus が先にまとまってしまっている．本来は Star が先にまとまるべき．

これは次の章で直す．

この章の完成コード

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

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;
                }
                '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)
    }
}

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

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 {
        let mut left = self.parse_primary();

        loop {
            match self.peek() {
                Some(Token::Plus)
                | Some(Token::Minus)
                | 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),
            other => panic!("expected number, got {:?}", other),
        }
    }
}

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),
            }
        }
    }
}

fn main() {
    // 四則演算ができる！……が，優先順位が間違っている
    let input = String::from("2 + 3 * 4");

    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!("2 + 3 * 4 = {} (should be 14)", result); // 20 になってしまう
}