FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

RustのパーサジェネレータLALRPOPに入門する(2. 電卓を作る)

パーサジェネレータの続き。

電卓を作る

lalrpop.github.io

次はパーサを使って電卓を作ってみる。電卓は四則演算を行うことができ、*, /の優先度が+, -よりも高い。calculator3.lalrpopは以下のようになる。

  • calculator3.lalrpop
use std::str::FromStr;

grammar;

pub Expr: i32 = {
    <l:Expr> "+" <r:Factor> => l + r,
    <l:Expr> "-" <r:Factor> => l - r,
    Factor,
};

Factor: i32 = {
    <l:Factor> "*" <r:Term> => l * r,
    <l:Factor> "/" <r:Term> => l / r,
    Term,
};

Term: i32 = {
    Num,
    "(" <Expr> ")",
};

Num: i32 = {
    r"[0-9]+" => i32::from_str(<>).unwrap(),
};

ここでは

  • Expr
  • Factor
  • Term
  • Num

の4つを定義している。それぞれ型はi32であり、即時計算を行っている。

  • rust/calculator3/src/main.rs
#[test]
fn calculator3() {
    let v = calculator3::ExprParser::new().parse("((22 * 44) + 66)").unwrap();
    assert!(v == 1034);
}

ASTを作る

次は四則演算を作るASTを作り上げる。文法自体はRustのマクロを使って実装されているので、RustのEnumなどを使ってASTを作り上げることができる。

  • rust/calculator4/src/ast.rs
pub enum Expr {
    Number(i32),
    Op(Box<Expr>, Opcode, Box<Expr>),
}

#[derive(Copy, Clone)]
pub enum Opcode {
    Mul,
    Div,
    Add,
    Sub,
}
  • rust/calculator4/src/calculator4.lalrpop
use std::str::FromStr;
use crate::ast::{Expr, Opcode}; // (0)

grammar;

pub Expr: Box<Expr> = { // (1)
    Expr ExprOp Factor => Box::new(Expr::Op(<>)), // (2)
    Factor,
};

ExprOp: Opcode = { // (3)
    "+" => Opcode::Add,
    "-" => Opcode::Sub,
};

Factor: Box<Expr> = {
    Factor FactorOp Term => Box::new(Expr::Op(<>)),
    Term,
};

FactorOp: Opcode = {
    "*" => Opcode::Mul,
    "/" => Opcode::Div,
};

Term: Box<Expr> = {
    Num => Box::new(Expr::Number(<>)), // (4)
    "(" <Expr> ")"
};

Num: i32 = {
    r"[0-9]+" => i32::from_str(<>).unwrap()
};
  • rust/calculator4/src/main.rs
#[test]
fn calculator4() {
    let expr = calculator4::ExprParser::new()
        .parse("22 * 44 + 66")
        .unwrap();
    assert_eq!(&format!("{:?}", expr), "((22 * 44) + 66)");
}

上記のExprParserは最終的に文字列を出力している。これを扱うのはast.rsに書かれたfmt(&self, fmt: &mut Formatter)を使っている。

  • rust/calculator4/src/ast.rs
impl Debug for Expr {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
        use self::Expr::*;
        match *self {
            Number(n) => write!(fmt, "{:?}", n),
            Op(ref l, op, ref r) => write!(fmt, "({:?} {:?} {:?})", l, op, r),
        }
    }
}


impl Debug for Opcode {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
        use self::Opcode::*;
        match *self {
            Mul => write!(fmt, "*"),
            Div => write!(fmt, "/"),
            Add => write!(fmt, "+"),
            Sub => write!(fmt, "-"),
        }
    }
}