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

## nom
[nom](https://docs.rs/nom/latest/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`を返す。

``` Rust
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`関数を使うと、パース結果を処理するクロージャを指定して結果を変換するパーサを構成することができる。

``` Rust
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間の乗除算。

``` Rust
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間の加減算。

``` Rust
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`を呼び出してプリントする。パースエラーの場合にはエラーをそのまま出力。

``` Rust
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)
  }
}
```

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