Rustのparser combinator nomを使ってみる。

nom

nomは、Rustのパーザコンビネータ。バイト列や文字列を解析するコードを簡単に書くことができる。文法構造の個々のパーツを解析するパーザを関数として書き、それを組み上げていくことで、文法全体を構成する。nomはジェネリックに書かれているので、入力データ構造もパーズされた結果も、ユーザが任意に設計することができる。

これを使って簡単なコマンドライン計算機を書いてみる。動作イメージはこんな感じ。

> ./rcalc '(1 + 2) * 3'
9

加減乗除とカッコが使えるようにする。乗除は加減よりも優先順位が高いが、カッコを使って演算の順番を制御する。

文法

BNF(風)で書くとこのようになる。

factor ::= NUMBER_LITERAL | '(' expr ')'
term ::= factor | factor ('*'|'/') factor 
expr ::= term   | term   ('+'|'-') term  

データ構造

パースした結果の表現としてASTを定義する。2項演算と数値リテラルだけ用意する。カッコはASTにはなくていい。数値リテラルはf64として直接表現する。このASTはevalすると値としてf64を返す。

pub trait AST {
  fn eval(&self) -> f64;
}

impl AST for f64 {
  fn eval(&self) -> f64{ *self }
}

pub enum Operator {
  Add, Sub, Mul,Div
}

pub struct BinOp {
  pub op: Operator, 
  pub lhs: Box<dyn AST>,
  pub rhs: Box<dyn AST>
}

impl AST for BinOp {
  fn eval(&self) -> f64 {
    let (lhs, rhs) = (self.lhs.eval(),  self.rhs.eval());
    match self.op {
      Operator::Add => lhs + rhs,
      Operator::Sub => lhs - rhs,
      Operator::Mul => lhs * rhs,
      Operator::Div => lhs / rhs,
    }
  }
}

factor

factor は数値リテラルか、式をカッコで囲んだもの。数値リテラルは、数字だけの列、もしくは数字だけの列2つをピリオドでつないだもの。
tuple関数は複数のパーサを連結する。
map関数を使うと、パース結果を処理するクロージャを指定して結果を変換するパーサを構成することができる。

fn factor(input: &str) -> IResult<&str, Box<dyn AST>> {
  fn literal(input: & str) -> IResult<&str, Box<dyn AST>> {
    let float_literal = map(tuple((digit1, tag("."), digit1)), 
      |(n, _, m)| format!("{}.{}", n, m));
    let int_literal = map(digit1, |v: &str| v.to_owned());

    let (input, v) = alt((float_literal, int_literal))(input)?;
    Ok((input, Box::new(f64::from_str(&v).unwrap())))
  }

  fn exp_factor(input: &str) -> IResult<&str, Box<dyn AST>> {
    let (input, (_, _, e, _, _)) = 
      tuple((tag("("), space0, expr,  space0, tag(")")))(input)?;
    return Ok((input, e))
  }
  Ok(alt((exp_factor, literal))(input)?)
}

term

term はfactor1つ、もしくはfactor間の乗除算。

fn term(input: &str) -> IResult<&str, Box<dyn AST>> {
  fn binary_term(input: &str) -> IResult<&str, Box<dyn AST>> {
    let (input, (lhs, _, v, _, rhs)) = 
      tuple((factor, space0, alt((tag("*"),tag("/"))),  space0, factor))(input)?;
    if v == "*" {
      Ok((input, Box::new(BinOp{op: Operator::Mul, lhs, rhs})))
    } else {
      Ok((input, Box::new(BinOp{op: Operator::Div, lhs, rhs})))
    }
  }
  Ok(alt((binary_term, factor,))(input)?)
}

expr

expr はterm1つもしくはterm間の加減算。

fn expr(input: &str) -> IResult<&str, Box<dyn AST>> {
  fn binary_expr(input: &str) -> IResult<&str, Box<dyn AST>> {
    let (input, (lhs, _, v, _, rhs)) = tuple((term, space0, alt((tag("+"),tag("-"))), space0, expr))(input)?;
    if v == "+" {
      Ok((input, Box::new(BinOp{op: Operator::Add, lhs, rhs})))
    } else {
      Ok((input, Box::new(BinOp{op: Operator::Sub, lhs, rhs})))
    }
  }
  Ok(alt((binary_expr, term))(input)?)
}

main

mainはこのように書く。引数をチェックして、パースした結果に対してevalを呼び出してプリントする。パースエラーの場合にはエラーをそのまま出力。

fn main() {
  let args: Vec<String> = std::env::args().collect();
  if args.len() != 2 {
    eprintln!("USAGE: {} 'EXPRESSION' ", args[0]);
    std::process::exit(0);
  }
  match expr(& args[1].trim()) {
    Ok((rest, ast)) => {
      if rest.len() == 0 {
        println!("{}", ast.eval());
      } else {
        eprintln!("Error: cannot parse all the input");
      }
    },
    Err(e) => eprintln!("{:?}", e)
  }
}

所感

たぶんもっと良い書き方があるはず。繰り返しとか省略可能とかを書く方法がいかにもありそうなのだけど。。