Rust 初心者です。もう一か月半も Rust を使ってるのですがいまだに自信がつきません。

今回は Rust で数式パーサを作ってみました。

数式を与えると、数式の抽象構文木 (AST; Abstract Syntax Tree) を作成します。
また、スタックマシンのコマンドに変換するところも実装してみました。

以下、エッセンスを紹介します。

数式の構文定義

数式の構文の BNF (Backus–Naur form) は以下のように与えました。

expr  ::= expr2 [ [ '+' | '-' ] expr2 ]*
expr2 ::= expr3 [ [ '*' | '/' ] expr3 ]*
expr3 ::= number | '(' expr ')'
number ::= digit+
digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

シンプルにするため、正の整数の四則演算に限定しました。
数式における演算子の優先順位、+,- ＜＜ *,/ ＜＜ (,) に対応させる形で、expr1, expr2, expr3 の構文ルールを与えています。
また、演算子 - と / は「交換法則」が成り立たないことから、同じ優先順位の演算子同士が並ぶ場合は左の項を優先します。

例： X + Y - Z では + と - の二つの演算子が出現するが同じ優先順位なので左を優先して (X + Y) - Z とする。

この程度の構文仕様なら ANTLR などのパーサジェネレータを使わなくても自分でパーサを実装できそうです。

数式の AST

先ほどの数式の構文に対して、パースした後の内部表現の型を以下に示します。
演算子の優先順位はすでにパーサが解決した後なので先ほどの expr1,expr2,expr3 のような構文上の分類は考慮する必要はありません。

演算子の優先順位を考える必要がないので、数式に出現する数字 Expr::Number と二項演算子の式 Expr::BinaryExpr の二種類だけを考えればよいことになります。
Expr::BinaryExpr の二つのオペランド部分が Expr になっていて、再帰的な型になっています。
この部分、Box でラップしないとコンパイラにしかられました。

// 数式の AST (Abstract Syntax Tree)
#[derive(Debug, PartialEq)]
pub enum Expr {
    Number (i32),
    BinaryExpr (Op, Box<Expr>, Box<Expr>),
}

// 二項演算子
#[derive(Debug, PartialEq)]
pub enum Op {
    Add,
    Sub,
    Mul,
    Div,
}

数式パーサ

最初に数式パーサの呼び出し方を示します。与えられた数式の文字列をパースし、対応する AST を返します。

let p = Parser::new();
let ast = p.parse("111 + 222 + 333")?;

この例ではパースの結果、変数 ast に次のような AST が代入される想定です。

Expr::BinaryExpr(Op::Add, 
    Expr::BinaryExpr(Op::Add, Expr::Number(111), Expr::Number(222)), 
    Expr::Number(333)
)

数式パーサの実装例です。

メソッドの呼び出しは、parse → parse_expr → parse_expr2 → parse_expr3 → parse_expr … というように再帰的に行われます。

// 数式パーサ

pub struct Parser {
    // 処理中のトークンの位置
    pos: usize,
    // トークン列
    tokens: Vec<Token>,
}

impl Parser {

    pub fn new () -> Self {
        Parser {
            pos: 0,
            tokens: vec![],
        }
    }

    pub fn parse (&mut self, expr_str:&str) -> Result<Expr> {
        let bytes:&[u8] = expr_str.as_bytes();

        // [MEMO] Read だけなら
        // let mut r = BufReader::new (bytes);
        // でもよいが、今回は Seek も使うので Cursor でラップする
        let mut r = BufReader::new (Cursor::new(bytes));

        // トークン列の読み出し
        if let Some(tokens) = read_tokens_from_reader(&mut r)? {
            self.tokens = tokens;
            self.pos = 0;
        } else {
            return Err(Error::ParseError);
        }


        self.parse_expr ()
    }

    // 次のトークンをトークン列から取得する
    fn next_token (&mut self) -> Option<Token> {
        if self.pos >= self.tokens.len () {
            return None;
        }
        let r = self.tokens[self.pos];
        self.pos += 1;
        Some(r)
    }

    // 処理中のトークンの位置を一つ前の位置に戻す
    fn back (&mut self) {
        if self.pos > 0 {
            self.pos -= 1;
        }
    }

    // 数式のパース
    fn parse_expr (&mut self) -> Result<Expr> {
        let mut left = self.parse_expr2 ()?;

        loop {
            if let Some(op) = self.next_token () {

                match op {
                    Token::Add|Token::Sub => {},
                    _ => {
                        self.back ();
                        return Ok(left);
                    },
                }
                let right = self.parse_expr2 ()?;

                match op {
                    Token::Add => {
                        left = Expr::BinaryExpr (Op::Add, Box::new(left), Box::new(right));
                    },
                    Token::Sub => {
                        left = Expr::BinaryExpr (Op::Sub, Box::new(left), Box::new(right));
                    },
                    _ => {
                        self.back();
                        break;
                    },
                }
            } else {
                // None がきたらそれ以上読めないのでループを抜ける
                break
            }
        }

        Ok(left)
    }

    fn parse_expr2 (&mut self) -> Result<Expr> {
        let mut left = self.parse_expr3 ()?;

        loop {
            if let Some(op) = self.next_token () {

                match op {
                    Token::Mul|Token::Div => {},
                    _ => {
                        self.back ();
                        return Ok(left);
                    },
                }

                let right = self.parse_expr3 ()?;

                match op {
                    Token::Mul => {
                        left = Expr::BinaryExpr (Op::Mul, Box::new (left), Box::new (right));
                    },
                    Token::Div => {
                        left = Expr::BinaryExpr (Op::Div, Box::new (left), Box::new (right));
                    },
                    _ => {
                        self.back ();
                        break;
                    },
                }
            } else {
                break
            }
        }

        Ok(left)
    }

    fn parse_expr3 (&mut self) -> Result<Expr> {
        if let Some(token) = self.next_token () {
            match token {
                Token::Number (value) => {
                    return Ok(Expr::Number (value));
                },
                Token::Lp => {
                    let expr = self.parse_expr ()?;
                    if let Some(token) = self.next_token () {
                        if token == Token::Rp {
                            return Ok (expr);
                        }
                    }
                },
                _ => {
                    self.back ();
                },
            }
        }

        Err(Error::ParseError)
    }
}

トークン

トークンの型は次のように与えました。

数字、四則演算子、左右の括弧だけです。

#[derive(Debug, PartialEq, Copy, Clone)]
pub enum Token {
    Number (i32),
    Add,
    Sub,
    Mul,
    Div,
    Lp,
    Rp,
}

トークンを読みだす部分の実装例です。
今回も BufReader にトレイトを適用してメソッドを追加しました。
また、今回は数字の読み出しで 1 バイトだけ先読みが発生するため、Read に加えて Seek も使いました。

// 文字列からトークンを読みだす
pub fn read_tokens_from_str(expr_str:&str) -> ResultOption<Vec<Token>> {
    let bytes:&[u8] = expr_str.as_bytes();

    // [MEMO] Read だけ必要なら
    // let mut r = BufReader::new (bytes);
    // でもよいが、今回は Seek も必要なので Cursor でラップする
    let mut r = BufReader::new (Cursor::new(bytes));

    read_tokens_from_reader(&mut r)
}

// バッファリーダーからトークンを読みだす
pub fn read_tokens_from_reader <R:Read+Seek> (r:&mut BufReader<R>) -> ResultOption<Vec<Token>> {
    let mut tokens:Vec<Token> = vec![];

    loop {
        match r.read_token ()? {
            Some(token) => tokens.push (token),
            None => break,
        }
    }

    if tokens.len() < 1 {
        return Ok(None)
    }

    Ok(Some(tokens))
}

impl<R:Read+Seek> MyRead for std::io::BufReader<R>{}

// 使用する文字コード
const CR:u8 = 0x0D; // Carriage Return
const LF:u8 = 0x0A; // Line Feed
const HT:u8 = 0x09; // Horizontal Tabulation
const SP:u8 = 0x20; // SPace
const LP:u8 = 0x28; // (
const RP:u8 = 0x29; // )
const MUL:u8 = 0x2A; // *
const ADD:u8 = 0x2B; // +
const SUB:u8 = 0x2D; // -
const DIV:u8 = 0x2F; // /
const NUM0:u8 = 0x30; // 0
const NUM9:u8 = 0x39; // 9

// トークン読み出し対応トレイト
pub trait MyRead: Read+Seek {

    // トークンの読み出し
    fn read_token(&mut self) -> ResultOption<Token> {

        loop {
            if let Some(c) = self.read_1byte ()? {
                if is_space (c) {
                    continue
                } else if c == LP {
                    return Ok(Some(Token::Lp))
                } else if c == RP {
                    return Ok(Some(Token::Rp))
                } else if c == MUL {
                    return Ok(Some(Token::Mul))
                } else if c == ADD {
                    return Ok(Some(Token::Add))
                } else if c == SUB {
                    return Ok(Some(Token::Sub))
                } else if c == DIV {
                    return Ok(Some(Token::Div))
                } else if c >= NUM0 && c <= NUM9 {
                    return Ok(Some(self.read_number (i32::from (c - NUM0))?));
                } else {
                    return Err(Error::UnknownCharacter)
                }
            }
            break
        }

        return Ok(None)
    }

    // 数字の読みだし
    fn read_number (&mut self, number:i32) -> Result<Token> {
        let mut number:i32 = number; 
        loop {
            // 1バイト読みだして
            if let Some(c) = self.read_1byte()? {
                // 数字の場合はすでに読みだしている値を10倍して桁あげして加算
                if c >= NUM0 && c <= NUM9 {
                    number = number * 10 + i32::from(c - NUM0);
                    continue
                } else {
                    // 1バイト戻してループを抜ける
                    self.seek(SeekFrom::Current(-1))?;
                }
            }
            break
        }

        return Ok(Token::Number(number))
    }

    // 1バイトを読みだすデフォルトメソッド
    fn read_1byte (&mut self) -> ResultOption<u8> {
        // (以前紹介したので省略)
}

// 空白かどうかを判定する
fn is_space (c:u8) -> bool {
    c == CR || c == LF || c == HT || c == SP
}

スタックマシンのコマンド

数式の AST をスタックマシンのコマンドにコンパイルする部分も作りました。

// スタックマシンのコマンド
#[derive(Debug, PartialEq, Clone)]
pub enum Code {
    Add,
    Sub,
    Mul,
    Div,
    Push (i32),
}
    
impl std::fmt::Display for Command {
    fn fmt (&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // 省略

想定するスタックマシンではレジスタはなく、スタックだけで演算処理を行います。
例えば、111 + 222 ならば、こんな感じです。

push 111
push 222
add

スタックから 111 と 222 を pop して加算（add）を行った結果となる 333 が push される想定です。
最新の計算結果は常にスタックの先頭に積まれます。

今回はスタックマシンそのものは実装しません。

以下、コンパイラの実装例です。

use crate::err::Result;
use crate::ast::{Expr,Op};

// 数式の AST をスタックマシンのコードにコンパイルする
pub fn compile(expr: Expr) -> Result<Vec<Command>> {
    let mut result:Vec<Command> = vec![];

    match expr {

        Expr::Number (value) => {
            result.push(Code::Push(value));
        },

        Expr::BinaryExpr (op, left_expr, right_expr) => {
            let left_commands = compile(*left_expr)?; // left_expr は Box でラップされてる
            for command in left_commands {
                result.push(command);
            }
            let right_commands = compile(*right_expr)?; // right_expr は Box でラップされてる
            for command in right_commands {
                result.push(command);
            }
            result.push(match op {
                Op::Add => Command::Add,
                Op::Sub => Command::Sub,
                Op::Mul => Command::Mul,
                Op::Div => Command::Div,
            });

        },
    };

    Ok(result)    
}

数式の AST 構造に基づいて再帰的に実装できるのでシンプルです。
左のオペランドをコンパイルしたら、右のオペランドをコンパイルして、最後に演算子に対応するコマンドを追加する、という流れです。

実行例

main.rs の実装例です。
引数で与えた数式をパースし、コンパイルし、スタックマシンへのコマンド列を表示します。

// main.rs
use std::env;
use calc::err::Result;
use calc::parse::Parser;
use calc::compile::compile;

fn main() {
    let args:Vec<String> = env::args().collect();
    let expr:&str = &args[1];

    if let Err(e) = process(expr) {
        eprintln!("[Error] {:?}", e);
    }
}

fn process(expr: &str) -> Result<()> {

    // 数式をパースする
    let mut p = Parser::new ();
    let ast = p.parse(expr)?;
    eprintln!("[DEBUG] ast = {:?}", ast);

    // 数式の AST をスタックマシンのコマンド列にコンパイルする
    let commands = compile(ast)?;

    // コマンド列の表示
    encode (commands);
    Ok(())
}

// コマンド列の表示
fn encode(codes: Vec<Code>) {
    for code in codes {
        println!("{}", code);
    }
}

これを expr.exe という名前の実行ファイルでコンパイルしました。

以下、実行例です。

C:\work>expr.exe "10 + 20"
[DEBUG] ast = BinaryExpr(Add, Number(10), Number(20))
push 10
push 20
add

C:\work>expr.exe "10 + 20 + 30"
[DEBUG] ast = BinaryExpr(Add, BinaryExpr(Add, Number(10), Number(20)), Number(30))
push 10
push 20
add
push 30
add

C:\work>expr.exe "10 + 20 * 30"
[DEBUG] ast = BinaryExpr(Add, Number(10), BinaryExpr(Mul, Number(20), Number(30)))
push 10
push 20
push 30
mul
add

C:\work>expr.exe "(10 + 20) * 30"
[DEBUG] ast = BinaryExpr(Mul, BinaryExpr(Add, Number(10), Number(20)), Number(30))
push 10
push 20
add
push 30
mul

今回は数式パーサを Rust で実装してみました。

次回は簡単なスタックマシンを Rust 実装し、今回作成した expr.exe と組み合わせて数式を計算してみたいと思います。