wtrclred
Bitterless Rust

練習: 足し算

前の章で数値を 1 つパースできるようになった．この章では 足し算 を実装する．

"1 + 2" → [Lexer] → [Number(1), Plus, Number(2)] → [Parser] → AST → [Eval] → 3.0

Token に Plus を追加する

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

Lexer で + を認識する

tokenize の match に '+' を追加:

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;
            }
            '0'..='9' => {
                let token = self.read_number();
                tokens.push(token);
            }
            _ => {
                self.pos += 1;
            }
        }
    }

    tokens
}

これで "1 + 2" が [Number(1.0), Plus, Number(2.0)] になる．

AST に二項演算を追加する

数値だけでなく「左辺 + 右辺」という構造を表現する必要がある．Expr を拡張:

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

BinOp は Binary Operation（二項演算）の略．left と right にそれぞれ部分式が入る．

Box ってなに

Expr の中に Expr を持ちたいけど，Rust はデータのサイズをコンパイル時に知りたがる．Expr の中に Expr が直接入ると，サイズが無限になってしまう．

Box<Expr> は「Expr をヒープに置いて，そのポインタだけ持つ」仕組み．

語弊注意: Box は「再帰的なデータ構造を作るときに使うやつ」くらいの理解で OK．Box::new(値) で包む．使うときは自動で中身が見える．

Parser を構造体にする

前の章では parse 関数で済んだけど，複数のトークンを順に読み進める必要が出てきた．位置を管理するために 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
        }
    }
}

peek と next_token は今後ずっと使うヘルパー．

.clone() で Vec の要素をコピーしている．所有権の問題を回避するいつものやつ．

parse を実装する

impl Parser {
    // ... new, peek, next_token は省略 ...

    fn parse(&mut self) -> Expr {
        // まず左辺（数値）を読む
        let mut left = self.parse_primary();

        // Plus が続く限り，右辺を読んで BinOp にまとめる
        while let Some(Token::Plus) = self.peek() {
            let op = self.next_token().unwrap(); // Plus を消費
            let right = self.parse_primary();
            left = Expr::BinOp {
                op,
                left: Box::new(left),
                right: Box::new(right),
            };
        }

        left
    }

    // 数値を 1 つ読む
    fn parse_primary(&mut self) -> Expr {
        match self.next_token() {
            Some(Token::Number(n)) => Expr::Number(n),
            other => panic!("expected number, got {:?}", other),
        }
    }
}

while let Some(Token::Plus) = self.peek() は「次のトークンが Plus の間ループする」という意味．

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

  1. parse_primary() → Number(1.0) が left に
  2. peek が Plus → ループに入る
  3. Plus を消費，parse_primary() → Number(2.0) が right に
  4. left = BinOp { Plus, Number(1), Number(2) }
  5. peek がまた Plus → もう一周
  6. Plus を消費，parse_primary() → Number(3.0) が right に
  7. left = BinOp { Plus, BinOp { Plus, 1, 2 }, Number(3) }

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,
                _ => panic!("unknown operator: {:?}", op),
            }
        }
    }
}

*left で Box<Expr> の中身の Expr を取り出している．左辺と右辺をそれぞれ再帰的に eval して足す．

動かしてみる

fn main() {
    let inputs = vec!["1 + 2", "10 + 20 + 30", "3.14 + 0.86"];

    for input in inputs {
        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!("{} = {}", input, result);
    }
}
1 + 2 = 3
10 + 20 + 30 = 60
3.14 + 0.86 = 4

この章の完成コード

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

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

        while let Some(Token::Plus) = self.peek() {
            let op = self.next_token().unwrap();
            let right = self.parse_primary();
            left = Expr::BinOp {
                op,
                left: Box::new(left),
                right: Box::new(right),
            };
        }

        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,
                _ => panic!("unknown operator: {:?}", op),
            }
        }
    }
}

fn main() {
    let input = String::from("1 + 2");

    let mut lexer = Lexer::new(input);
    let tokens = lexer.tokenize();
    println!("Tokens: {:?}", tokens);

    let mut parser = Parser::new(tokens);
    let ast = parser.parse();
    println!("AST: {:?}", ast);

    let result = eval(ast);
    println!("Result: {}", result);
}

足し算ができるようになった．次の章では引き算を追加する．やることはほぼ同じ — パターンに慣れよう．

関連コンテンツ

chapter練習: 数値をパースして表示する
#lexer#practice
chapter練習: 引き算
#parser#practice
chapter練習: 掛け算と割り算
#parser#practice
chapter練習: 演算子の優先順位と仕上げ
#parser#precedence#repl
← 本に戻る