LoginSignup
0
0

More than 1 year has passed since last update.

@mekamaru(mekamaru)

Rust研究：シンプルな数式パーサ

Last updated at Posted at 2023-03-04

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 と組み合わせて数式を計算してみたいと思います。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0