RustとNomで電卓を作る 

## 目次

1. はじめに
1. 環境構築
1. AST実装
1. パーサ実装
1. 入出力実装
1. 終わりに

## はじめに

皆さんこんにちは！
**Rust**言語はお好きですか？ もちろん好きですよね。
**Rust**を知らない？ では**Rust**の素晴らしい点を挙げて紹介してみることにしましょう。

**Rust**の特徴は以下の通りです。

- Mozillaが応援している言語
- 2006年から開発が始まった新しめの言語
- 2016年、2017年、2018年、2019年、2020年のStack Overflow Developer Surveyで「最も愛されているプログラミング言語」で一位を獲得している
- C/C++と同等の処理速度
- C/C++の代替えを目指している
- 静的に型が付く、コンパイラ言語
- 静的に変数の寿命もわかり、自動でメモリを解放（GCより速い！）
- 関数内部限定での極めて賢い型推論
- C/C++と比べて極めて安全
- オブジェクト指向ではないし関数型言語でもない新たな概念を持つ
- デフォルトでスレッドセーフが保証された変数達
- C++のムーブセマンティクスを言語レベルでサポート
- C++と違い、制約付きのテンプレートがある
- DSL作成可能で健全なマクロ
- タプル、代数的データ型とマッチ式もあります
- 標準でテスト機能が付いている
- 標準でパッケージマネージャーがある

素晴らしい言語ですね！勉強しない手はありません。
では、どのように勉強すればいいのでしょうか。

簡単です。四則演算の数式を計算する電卓を作るのです。(?)

これは、**Rust**初級者or中級者向けを想定しています。
少々難しいかもしれませんが、**Rust**に関する解説はあまりしません。（代わりに参照URLを記載したりしています）
私が解説するよりも、既に存在する素晴らしいドキュメントを読んだ方が効率的だからです。

流れを紹介します。

まずは**Rust**の開発環境、プロジェクト作成をします。
そして次は、四則演算の数式の構文構造をデータ構造として定義していきます。
次に、`4+5*(1/10)`等の数式の文字列を解析して、定義したデータ構造へ変換する**パーサ**というものを実装していきます。
最後に入出力インタフェースを実装して完成です。

[今回作る電卓の完成ソースコードはこちらで確認できます]
https://github.com/elipmoc/rust-calc

## 環境構築

まずは**Rust**をインストールしましょう。
**Rust**のバージョンは1.37.0という仮定で話を進めていきます。

**Rust**のインストール方法はコチラを参照してください
https://www.rust-lang.org/

インストールが完了するとcargo, rustc, rustupという三つのプログラムがシェルやcmd, powershell等で使えるようになっています。
`-V`でそれぞれバージョン確認できますので確認してみましょう。

```
$ rustc -V
rustc 1.37.0 (eae3437df 2019-08-13)

$ rustup -V
rustup 1.18.3 (435397f48 2019-05-22)

$ cargo -V
cargo 1.37.0 (9edd08916 2019-08-02)
```

それぞれ軽く説明しますと、

- rustcは**Rust**のコンパイラ

- rustupは**Rust**のコンパイラをバージョン管理するツール

- cargoは**Rust**のパッケージマネージャー

では、早速プロジェクトを作成していきます。

rust_calcという名前でプロジェクト作成。

```
cargo new rust_calc
```

`rust_calc`というフォルダが生成されるので、中身を確認してください。

- `Cargo.toml`

- `src/main.rs`

の二つのファイルがあります。

`Cargo.toml`はプロジェクトの設定を書くファイルです。
`src/main.rs`が`main`関数を定義する**Rust**のソースファイルとなります。

`Cargo.toml`に今回必要になるライブラリを先に書いていきます。
```[dependencies]```の所に```nom="5"```と書きましょう。

```rust
[package]
省略

[dependencies]
nom="5"
```

プロジェクトの配下で`cargo run`コマンドを打って実行してみましょう。
`Hello, world!`が表示されるのを確認してください。

この時、素晴らしいことに`Cargo.toml`の更新を目ざとく検知して、**nom**ライブラリが
自動でダウンロードされ、インストールされているのに気が付くでしょう。`npm i`よりも遥かに便利ですね。(npmとはnode.jsという言語のパッケージマネージャーです)

## AST実装

はじめに、四則演算の数式の構文の構造をデータ構造として定義していきたいと思います。
まず、数式は木構造として定義することができます。
以下の画像を見てください。

![ru3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/208277/9d9481f7-c21f-91d6-ed49-770811f58f28.png)


これは`4*((8+10)-3)`という数式を木構造に変換したものです。
このように数式の構文は木構造へと変換することが可能です。
注意すべきポイントは`()`は木の深さで表現されていることです。元の数式で最も`()`のネストが深い`8+10`は木構造で一番下に来るようにすることで優先順位の表現を可能にしています。

このように作った、構文を構成する必要最低限の要素だけを表現した木構造を**抽象構文木**(abstract syntax tree　略して**AST**)と呼びます。

**AST**の概念もだいたい理解したところで、早速、数式の**AST**を**Rust**で定義していきましょう。

`src/`に`calc`フォルダを作成。

`src/`に`calc.rs`ファイルを作成。

`calc/`に`ast.rs`ファイルを作成。

`calc.rs`に`pub mod ast;`と記述し、`ast.rs`をcalcより上の階層でも使えるように公開します。
**Rust**ではモジュールを公開するのに`pub`修飾子を付けます。

では`ast.rs`に数式の**AST**を定義していきます。

### 定数のAST

とりあえず、最も簡単な定数の構造を定義します。

`ast.rs`に書いていきましょう。

```rust
///定数を表す
pub struct ConstantVal(pub i32);
```

実際に`main.rs`で使ってみます。

```rust
pub mod calc;

fn main() {
    let a=calc::ast::ConstantVal(33);
    println!("ConstantVal={}",a.0);
}
```
`main.rs`で`pub mod calc;`することで、`main`の子モジュールとして`calc`モジュールを登録することで`calc`モジュールを使用できるようにしています。
今回の場合`pub`を付けなくても動きますが、後で行うドキュメント自動生成のためにあえて公開にしています。

このコードは`ConstantVal`を生成して、中身の`33`を`a.0`で表示するだけのものです。簡単ですね！

ところで、ちょっとだけ`ConstantVal`に問題があります。
この`ConstantVal`は不変なものとして扱いたいと思っているのですが……。

```rust
pub mod calc;

fn main() {
    let mut a=calc::ast::ConstantVal(33);
    a.0=25;
    println!("ConstantVal={}",a.0);
}
```

このように`mut`を付ければ、中の値を書き換えれてしまいます。
設計上あまりよくないので、中の値を変えれないようカプセル化しておきましょう。

`ast.rs`を修正

```rust
///定数を表す
pub struct ConstantVal(i32);
```

これでコンパイルすると外部からは中の要素にアクセスできないため、生成することはできなくなりました。

次にそれをなんとかするために関数を実装していきます。

`ast.rs`を修正。

```rust
///定数を表す
pub struct ConstantVal(i32);

impl ConstantVal {
    ///ConstantValを生成する
    pub fn new(val: i32) -> ConstantVal {
        ConstantVal(val)
    }

    ///ConstantValの値を取得する
    pub fn get(&self) -> i32 {
        self.0
    }
}
```

`main.rs`も修正。

```rust
pub mod calc;

fn main() {
    let a = calc::ast::ConstantVal::new(33);
    println!("ConstantVal={}", a.get());
}
```

### 定数のASTのテスト

せっかく、関数を実装したんです。テストも書いてみましょう。**Rust**のテストはありえないぐらい簡単です。
`ast.rs`に直接テスト関数を書くだけです！
`ast.rs`の続きから書いていきましょう。

```rust
//impl ConstantVal {..}の下に書く

#[test]
fn constant_val_test() {
    let expect = 55;
    let constant_val = ConstantVal::new(expect);
    assert_eq!(
        constant_val.get(),
        expect
    );
}
```

`#[test]`が付けられた関数はテスト実行の時のみコンパイルされ、実行されます。

実際にテストを実行してみましょう。準備するものは何もありません。ただコマンドを１つ打つだけです！

```
cargo test
```

### ドキュメント自動生成

次に、標準で備わっているドキュメント生成機能を試してみましょう。

```
cargo doc --no-deps --open
```

このコマンドでドキュメント生成を自動生成して、ブラウザで開くことができます。

[コマンドの詳細]
https://doc.rust-lang.org/cargo/commands/cargo-doc.html

きっとこんな感じになることでしょう。↓

![ru1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/208277/9dd41755-7b4f-1472-b69f-265543989cd2.png)


`///`で書いたコメント文がドキュメントに表示されてますね。
**Rust**では`//`が普通のコメントで`///`がドキュメント用のコメントになります。

### 足し算のAST

次に、足し算の式の構造を定義します。

足し算は`<任意の式>+<任意の式>`という構造になっているはずです。

つまり、足し算の構造は任意の式を二つ持つというわけです。

任意の式についてまだ定義していないのでそちらを定義していきましょう。

任意の式とは、定数、足し算など、さまざまな式のいずれかを取るような構造です。
こういう時は`enum`を使うと簡単にその構造を定義できます。

他の言語だと`enum`は単なる識別子として使いますが。
**Rust**の`enum`はunion型や直和型と呼ばれる概念に近いものです。

`ast.rs`の先頭から書く。

```rust
///任意の式を表す
pub enum Expr {
    ConstantVal(ConstantVal)
}

///定数を表す
pub struct ConstantVal(i32);
.
.
```

任意の式の表現が出来たので、足し算の構造を実装していきます。

```rust
.
.
#[test]
fn constant_val_test() {...}

///足し算を表す
pub struct PlusOp {
    //演算子の左にある式
    left_expr: Expr,
    //演算子の右にある式
    right_expr: Expr,
}

impl PlusOp {
    ///PlusOpを生成する
    pub fn new(left_expr: Expr, right_expr: Expr) -> PlusOp {
        PlusOp { left_expr, right_expr }
    }
}
```

次に足し算の式自体も任意の式に含まれるので、`Expr`に`PlusOp`を追加します。

```rust
///任意の式を表す
pub enum Expr {
    ConstantVal(ConstantVal),
    PlusOp(PlusOp),
}
```

が、残念ながらこれはコンパイルエラーとなります。
これは、C/C++をやっていれば馴染みが深いエラーかもしれません。
`PlusOp`の定義自体に`Expr`が含まれるため、循環参照してしまい、サイズがコンパイル時に不定になるからです。

この問題を解決するために、`Expr`には`PlusOp`自身ではなく、`PlusOp`のポインタを持たせるようにします。
なぜポインタにすると解決するのか。それは、ポインタのサイズは常に一定だからです。

```rust
///任意の式を表す
pub enum Expr {
    ConstantVal(ConstantVal),
    PlusOp(Box<PlusOp>),
}
```

### ASTの評価

ではそろそろ、式の計算を実装していきたいと思います。
これからは、式の計算ではなく、式の評価(evaluate)という言葉を使っていきます。

そのために、各種構造(`Expr`, `ConstantVal`, `PlusOp`)に`eval`という式を評価する関数を定義していきます。

かなり書き換えたので全体のソースコードを載せておきます。

`ast.rs`

```rust
///任意の式を表す
pub enum Expr {
    ConstantVal(ConstantVal),
    PlusOp(Box<PlusOp>),
}

impl Expr {
    ///式を評価する
    pub fn eval(&self) -> i32 {
        match self {
            Expr::ConstantVal(e) => e.eval(),
            Expr::PlusOp(e) => e.eval()
        }
    }
}

///定数を表す
pub struct ConstantVal(i32);

impl ConstantVal {
    ///ConstantValを生成する
    pub fn new(val: i32) -> ConstantVal {
        ConstantVal(val)
    }

    ///定数を評価する
    pub fn eval(&self) -> i32 {
        self.0
    }
}

#[test]
fn constant_val_test() {
    let expect = 55;
    let constant_val = ConstantVal::new(expect);
    assert_eq!(
        constant_val.eval(),
        expect
    );
}

///足し算を表す
pub struct PlusOp {
    //演算子の左にある式
    left_expr: Expr,
    //演算子の右にある式
    right_expr: Expr,
}

impl PlusOp {
    ///PlusOpを生成する
    pub fn new(left_expr: Expr, right_expr: Expr) -> PlusOp {
        PlusOp { left_expr, right_expr }
    }

    ///足し算を評価する
    pub fn eval(&self) -> i32 {
        self.left_expr.eval() + self.right_expr.eval()
    }
}
```

`main.rs`


```rust
pub mod calc;

fn main() {
    let a = calc::ast::ConstantVal::new(33);
    println!("ConstantVal={}", a.eval());
}
```

変更点は、
`Expr`に`eval`関数を実装し、`PlusOp`にも`eval`関数を実装しました。
あとは、`ConstantVal`の`get`関数を`eval`にリネームして、統一をしました。


### AST評価のテスト

`eval`関数が新たに定義されたので、テストも追加していきましょう。

```rust
.
.
impl PlusOp {
    ...
}

#[test]
fn plus_op_test() {
    //13+(5+1)の足し算式を生成
    let plus_op = PlusOp::new(
        Expr::ConstantVal(ConstantVal::new(13)),
        Expr::PlusOp(
            Box::new(
                PlusOp::new(
                    Expr::ConstantVal(ConstantVal::new(5)),
                    Expr::ConstantVal(ConstantVal::new(1)),
                )
            )
        ),
    );
    let expect = 13 + (5 + 1);
    assert_eq!(
        plus_op.eval(),
        expect
    );
}
```

簡単のため、テストは`PlusOp`のみにしました。
また、 `Expr::ConstantVal(ConstantVal::new(5))`という記述は冗長かもしれませんが、今回はこのスタイルで行きます。

これで、足し算と定数を組み合わせた任意の式を表現でき、評価できようになりました。

### 四則演算への拡張

ここからは、四則演算ができるように拡張していきましょう。

`PlusOp`を四則演算全てに対応できるように、改造していきます。

`ast.rs`の`PlusOp`を`BinaryOp`にして修正。

```rust
///演算子種別
pub enum OpKind {
    Add,
    Sub,
    Mul,
    Div,
}

///二項演算子を表す
pub struct BinaryOp {
    //適応する演算子種別
    op_kind: OpKind,
    //演算子の左にある式
    left_expr: Expr,
    //演算子の右にある式
    right_expr: Expr,
}

impl BinaryOp {
    ///BinaryOpを生成する
    pub fn new(op_kind: OpKind, left_expr: Expr, right_expr: Expr) 
        -> BinaryOp 
    {
        BinaryOp { op_kind, left_expr, right_expr }
    }

    ///二項演算式を評価する
    pub fn eval(&self) -> i32 {
        let right = self.right_expr.eval();
        let left = self.left_expr.eval();
        match self.op_kind {
            OpKind::Add => left + right,
            OpKind::Sub => left - right,
            OpKind::Mul => left * right,
            OpKind::Div => left / right
        }
    }
}
```

次に`Expr`も修正していきます。

```rust
///任意の式を表す
pub enum Expr {
    ConstantVal(ConstantVal),
    BinaryOp(Box<BinaryOp>),
}

impl Expr {
    ///式を評価する
    pub fn eval(&self) -> i32 {
        match self {
            Expr::ConstantVal(e) => e.eval(),
            Expr::BinaryOp(e) => e.eval()
        }
    }
}
.
.
```

`plus_op_test`も`binary_op_test`として書き直します。

```rust
.
.
#[test]
fn binary_op_test() {
    //13*(5+1)の式を生成
    let binary_op = BinaryOp::new(
        OpKind::Mul,
        Expr::ConstantVal(ConstantVal::new(13)),
        Expr::BinaryOp(
            Box::new(
                BinaryOp::new(
                    OpKind::Add,
                    Expr::ConstantVal(ConstantVal::new(5)),
                    Expr::ConstantVal(ConstantVal::new(1)),
                )
            )
        ),
    );
    let expect = 13 * (5 + 1);
    assert_eq!(
        binary_op.eval(),
        expect
    );
}
```

これで、四則演算の数式の構文構造を**AST**としてプログラムに落とし込み、評価することができるようになりました！

## パーサ実装

### パーサについて

ここまでで、四則演算の数式を表現できる構造を定義し終えました。
今や、`4+8-2/1`や`(1-2)*(3+8)`などの数式を表現することができます。
ただし、それは自分でプログラムを書いて組み立てていくような面倒なやり方でした。（ちょうど`binary_op_test`のような）
そうではなく、`"4+7/2+1"`などの文字列が与えられたら、それを解析して自動で**AST**を生成したいと思います。このように、「文字列を解析して構造を組み立てていく関数」のことを**パーサ**と呼びます。

`calc`フォルダ内に`parser.rs`というファイルを作ってください。
次に`calc.rs`を以下のようにします。

```rust
pub mod ast;
pub mod parser;
```

さて、**パーサ**を実装する前に、先に今回の数式の構文をしっかりとBNFで定義しておきましょう。(BNFの説明については省略します。)

```bnf
記号のルール
[中身] は中身が「あっても無くても良い」という構文を意味する。
| は「または」を意味する。例えば'a'|'b'で'a'または'b'にマッチする構文。
() は単純に優先順位を明示しているだけ。

<expr>       := <term> [ ('+'|'-') <expr> ]
<term>       := <factor> [ ('*'|'/') <term> ]
<factor>     := <const_val> | <paren_expr>
<paren_expr> := '(' <expr> ')'
<const_val>  := 1つ以上の数字
```

**パーサ**はある小さな単位の構文を解析し、変換するものです。
今回はBNFに習って、`expr`, `term`, `factor`, `paren_expr`, `const_val`という単位で**パーサ**を実装していきます。
**パーサ**は**パーサ**同士を組み合わせてさらに大きく複雑な**パーサ**を構成することができます。**パーサ**を組み合わせるヘルパ関数のことを**パーサコンビネータ**と呼びます。

**パーサ**と**パーサコンビネータ**を1から自作するのは大変なので、**nom**というパーサライブラリを使用します。

### nomを使ってみよう
[nomのGithub] https://github.com/Geal/nom

[nomのドキュメント] https://docs.rs/nom/5.0.1/nom/

まず、**nom**の使い方を見ていきましょう。
**nom**にはいくつかデフォルトで用意されている**パーサ**があるのでそれを使ってみます。

`parser.rs`に書いていきます。

```rust
use nom::character::complete::digit1;
use nom::IResult;

#[test]
fn digit1_test() {
    let s = "63abc";
    let result: IResult<&str, &str> = digit1(&s);
    let (no_used, used) = result.unwrap();
    assert_eq!("63", used);
    assert_eq!("abc", no_used);
}
```

`digit1`は少なくとも1つ以上の数字を**パース**(**パーサ**を使って解析し変換することをそう言う。)する**パーサ**です。
**パーサ**の返り値は`IResult<&str,&str>`です。（他の型を指定することも可能ですが）

具体的には`IResult<パースされなかった残りの文字列,パースされたもの>`となっています。
**パース**が成功した場合`unwrap()`で`(残りの文字列,パースされたもの)`というタプルを受け取れます。

`63`は`digit1`で**パース**されますが、`abc`は数字じゃないので**パース**されずに残るわけですね。

### 定数のパーサ

事前準備が終わったので早速、定数の**パーサ**を書いていきます。

BNFではこう定義していました

```
<const_val>  := 1つ以上の数字
```

`digit1`を使いつつ、定数の**パーサ**を実装したいと思います。

```rust
.
.
#[test]
fn digit1_test() {...}

use super::ast::*;

///定数のパーサ
pub fn constant_val_parser(s: &str) -> IResult<&str, ConstantVal> {
    use std::str::FromStr;
    let (no_used, used) = digit1(s)?;
    let val = FromStr::from_str(used).unwrap();
    Ok((no_used, ConstantVal::new(val)))
}
```

では`constant_val_parser`について説明していきます。

まず、返り値が`IResult<&str,&str>`ではなく、`IResult<&str, ConstantVal>`になっている点に注意してください。
`constant_val_parser`は**パース**結果として`ConstantVal`を返したいので、このような型になっています。

2行目では、`digit1`を使い数字の文字列を**パース**しています。
`IResult`型の値の中身を`?`演算子で取り出して、`(no_used, used)`という風に変数に格納します。

3行目では、`FromStr::from_str`を使って、文字列を`i32`に変換しています。
必ず成功すると仮定して`unwrap()`で中身を取り出します。
最後に`IResult`で残りの文字列と**パース**結果である`ConstantVal`を返します。

------------------------------------------------------------------------------------------------

#### パーサのルール

**パーサ**同士を組み合わせて新しい**パーサ**を作れるようにするため、**パーサ**の作成ルールがあります。
それは返り値の型を`IResult`にすることです。

`IResult`は`Result`のエイリアスです。

```rust
type IResult<I, O, E = (I, ErrorKind)> = Result<(I, O), Err<E>>;
```

`I`がまだ**パース**されてない残り物の型。

`O`が**パース**結果の型。

`E`は**パース**が失敗した時に返すエラーの型です。

------------------------------------------------------------------------------------------------

### 定数のパーサをテスト

では、本当に期待通り**パーサ**が実装できているか、テストを書いていきます。

```rust
.
.
///定数のパーサ
pub fn constant_val_parser(s: &str) -> IResult<&str, ConstantVal> {...}

#[test]
fn constant_val_parser_test() {
    let (_, actual) = constant_val_parser("889").unwrap();
    let expect = ConstantVal::new(889);
    assert_eq!(actual, expect);
}
```

動きそうですがこのテストはコンパイルエラーになります。

エラー内容を抜粋するとこんな感じです。

```
 help: the trait `std::fmt::Debug` is not implemented for `calc::ast::ConstantVal`
```

要約すると、`ConstantVal`には`Debug`のトレイトが無いからだめだよって感じです。
`assert_eq!`は比較対象に`Debug`,`PartialEq`のトレイトを要求します。

`ast.rs`に定義されているデータ構造をテストをしやすくするため、全て`Debug`, `PartialEq`トレイトを持たせたいと思います。
これらのトレイトはコンパイラに自動実装させることが可能なのでそれを使用します。

```rust
///任意の式を表す
#[derive(Debug,PartialEq)]
pub enum Expr {...}
.
.

///定数を表す
#[derive(Debug,PartialEq)]
pub struct ConstantVal(i32);
.
.

///演算子種別
#[derive(Debug,PartialEq)]
pub enum OpKind {...}

///二項演算子を表す
#[derive(Debug,PartialEq)]
pub struct BinaryOp {...}
.
.
```

今度はうまくテストが通ったと思います。

### 式のパーサ

次に全ての式の組み合わせを**パース**する**パーサ**を作っていきます。

BNFではこう定義していました。

```
<expr>       := <term> [ ('+'|'-') <expr> ]
```

現時点では定数の**パーサ**だけしかないので、とりあえず仮です。

```rust
.
.
#[test]
fn digit1_test() {...}

use super::ast::*;

///式のパーサ
pub fn expr_parser(s: &str) -> IResult<&str, Expr> {
    constant_val_parser(s)
        .map(|(no_used, constant_val)|
            (no_used, Expr::ConstantVal(constant_val))
        )
}

///定数のパーサ
.
.
```

`constant_val_parser`の返り値が`IResult<&str,ConstantVal>`で、
`expr_parser`はその型を`map`関数を使って`IResult<&str,Expr>`に変換しているだけです。

### 丸括弧付きの式のパーサ

次は`(任意の式)`のような丸括弧付きの式の**パーサ**を作っていきます。

BNFではこう定義していました。

```
<paren_expr> := '(' <expr> ')'
```


```rust
.
.
///式のパーサ
pub fn expr_parser(s: &str) -> IResult<&str, Expr> {...}

use nom::character::complete::char;

///丸括弧で囲まれた式のパーサ
pub fn paren_expr_parser(s: &str) -> IResult<&str, Expr> {
    let (no_used, _) = char('(')(s)?;
    let (no_used, expr) = expr_parser(no_used)?;
    let (no_used, _) = char(')')(no_used)?;
    Ok((no_used, expr))
}

#[test]
fn paren_expr_parser_test() {
    let (_, actual) = paren_expr_parser("(76)").unwrap();
    let expect = Expr::ConstantVal(ConstantVal::new(76));
    assert_eq!(actual, expect);
}

///定数のパーサ
.
.
```

新しく出てきた`char`は指定した1文字を**パース**する**パーサ**です。

### 因子のパーサ

次に、定数**パーサ**と丸括弧式**パーサ**を1つの**パーサ**としてまとめたいと思います。
理由は、この二つの式は優先順位が同じだからです。
これらは一般的に因子(factor)と呼ばれるものなので、`factor_parser`という名前で作っていきます。

BNFではこう定義していました。

```
<factor>     := <const_val> | <paren_expr>
```

```rust
.
.
fn digit1_test() {...}

use super::ast::*;
use nom::branch::alt;
use nom::combinator::map;

///式のパーサ
pub fn expr_parser(s: &str) -> IResult<&str, Expr> {
    factor_parser(s)
}

///因子のパーサ
pub fn factor_parser(s: &str) -> IResult<&str, Expr> {
    alt((
        map(
            constant_val_parser, 
            |constant_val| Expr::ConstantVal(constant_val)
        ),
        paren_expr_parser
    ))(s)
}

#[test]
fn factor_parser_test() {
    let (_, actual) = factor_parser("4").unwrap();
    let expect = Expr::ConstantVal(ConstantVal::new(4));
    assert_eq!(actual, expect);

    let (_, actual) = factor_parser("(3)").unwrap();
    let expect = Expr::ConstantVal(ConstantVal::new(3));
    assert_eq!(actual, expect);
}

use nom::character::complete::char;
.
.
```

今回は新しく、`alt`と`map`が出てきました。
`alt`は「または」を表現することができる**パーサコンビネータ**です。
`alt`は複数の**パーサ**を「または」で結合した新しい**パーサ**を作成できます。
どれか一つでも**パース**が成功したら、そこでストップし、結果を返すような動作をします。
今回は「定数または丸括弧式」を表現するために使ってます。
次に`map`ですが、これは渡された**パーサ**の**パース**結果の値を変換した新たな**パーサ**を生成する**パーサコンビネータ**です。
`constant_val_parser`**パーサ**の**パース**結果の型は`ConstantVal`なので、整合性を保つために`Expr`型に変換してやる必要があるわけです。
後は、`expr_parser`を修正して定数と丸括弧式を**パース**できるようにしておきます。

### 項のパーサ

お次は掛け算、割り算の**パーサ**を作っていきましょう。
掛け算、割り算は優先順位を同じと仮定すると、まとめて一つの**パーサ**として実装するのが楽です。
これは一般的に項(term)と呼ばれるものなので、`term_parser`として実装していきます。

BNFではこう定義していました。

```
<term>       := <factor> [ ('*'|'/') <term> ]
```

かなり複雑なので覚悟をしてください。

```rust
.
.
///式のパーサ
pub fn expr_parser(s: &str) -> IResult<&str, Expr> {
    term_parser(s)
}

use nom::sequence::tuple;
use nom::combinator::opt;

///項のパーサ
pub fn term_parser(s: &str) -> IResult<&str, Expr> {

    //*/記号をOpKind型にパースするパーサ
    let op_kind_parser =
        map(
            alt((char('*'), char('/'))),
            |op_char|
                match op_char {
                    '*' => OpKind::Mul,
                    '/' => OpKind::Div,
                    _ => panic!("error!")
                },
        );
    
    //掛け算、割り算のパーサ
    let binary_parser = tuple((
        factor_parser,
        opt(
            tuple((
                op_kind_parser,
                term_parser
            ))
        )
    ));

    //掛け算、割り算のパーサのパースされた値をmapで調整
    map(binary_parser, |(head_expr, tail_expr_opt)| {
        if let Option::Some((op_kind, tail_expr)) = tail_expr_opt {
            Expr::BinaryOp(
                Box::new(
                    BinaryOp::new(op_kind, head_expr, tail_expr)
                )
            )
        } else {
            head_expr
        }
    })(s)
}

#[test]
fn term_parser_test() {
    let (_, actual) = term_parser("4*2/1").unwrap();

    let temp = Expr::BinaryOp(Box::new(
        BinaryOp::new(
            OpKind::Div,
            Expr::ConstantVal(ConstantVal::new(2)),
            Expr::ConstantVal(ConstantVal::new(1)),
        )
    ));
    let expect = Expr::BinaryOp(Box::new(
        BinaryOp::new(
            OpKind::Mul,
            Expr::ConstantVal(ConstantVal::new(4)),
            temp,
        )
    ));
    assert_eq!(actual, expect);
}

///因子のパーサ
.
.
```

新たに、`tuple`と`opt`が出てきました。
これは両方とも**パーサコンビネータ**です。

`tuple`は複数の**パーサ**を受け取り、それを１つに結合した新たな**パーサ**を生成します。
例えば、

```rust
tuple(( 
    char('a'),
    char('b'),
    char('c'),
))
```
とすれば、`abc`という文字列を**パース**する**パーサ**が生成されます。
**パース**結果の型は`(char,char,char)`となります。

`opt`は受け取った**パーサ**から、「無くてもいい、あってもいい」という**パーサ**を生成します。
例えば、

```rust
opt(char('h'))
```
とすれば、`h`にマッチしてもいいし、マッチしなくても良いという**パーサ**が生成されます。
**パース**結果の型は`Option<char>`となります。

### 式のパーサ再び

最後は`expr_parser`に足し算と引き算を実装していきます。
これは、`term_parser`とほとんど同じような実装になります。

一応BNFも再度置いておきます。

```
<expr>       := <term> [ ('+'|'-') <expr> ]
```

```rust
///式のパーサ
pub fn expr_parser(s: &str) -> IResult<&str, Expr> {
    //+-記号をOpKind型にパースするパーサ
    let op_kind_parser =
        map(
            alt((char('+'), char('-'))),
            |op_char|
                match op_char {
                    '+' => OpKind::Add,
                    '-' => OpKind::Sub,
                    _ => panic!("error!")
                },
        );

    //足し算、引き算のパーサ
    let binary_parser = tuple((
        term_parser,
        opt(
            tuple((
                op_kind_parser,
                expr_parser
            ))
        )
    ));

    //足し算、引き算のパーサのパースされた値をmapで調整
    map(binary_parser, |(head_expr, tail_expr_opt)| {
        if let Option::Some((op_kind, tail_expr)) = tail_expr_opt {
            Expr::BinaryOp(
                Box::new(
                    BinaryOp::new(op_kind, head_expr, tail_expr)
                )
            )
        } else {
            head_expr
        }
    })(s)
}
```

これで**パーサ**は完成です。
`expr_parser`のテストは省略したいと思います。

## 入出力の実装

### 便利関数の実装

いよいよ、`main.rs`に入出力処理を書いて、電卓の入出力インターフェース実装していきたいと思います。
最初に利便性のため、文字列を**パース**して評価する関数を`calc.rs`に実装していきます。

```rust
pub mod ast;
pub mod parser;

use nom::Err;
use nom::error::ErrorKind;

///受け取った文字列をパースして評価する
pub fn expr_eval(s: &str) -> Result<i32, Err<(&str, ErrorKind)>> {
    parser::expr_parser(s)
        .map(|(_, expr)| expr.eval())
}

#[test]
fn expr_eval_test() {
    assert_eq!(
        expr_eval("1+2+3+4+5").unwrap(),
        1 + 2 + 3 + 4 + 5
    );

    assert_eq!(
        expr_eval("1+2*3-7").unwrap(),
        1 + 2 * 3 - 7
    );

    assert_eq!(
        expr_eval("(2*24)/(5+3)").unwrap(),
        (2 * 24) / (5 + 3)
    );
}
```

### 入出力の実装

では、定義した`expr_eval`を用いて`main.rs`に入出力を実装していきます。

```rust
pub mod calc;

use crate::calc::expr_eval;

fn main() {
    loop {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).ok();
        match expr_eval(&s) {
            Ok(val) => println!("ok:{}", val),
            _ => println!("構文エラー")
        }
    }
}
```

完成です！
`cargo run`で実行してみましょう。

![ru2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/208277/4fd56c4f-3040-babb-5e30-156b9ee54e44.png)


## 終わりに

お疲れ様です。

### 今後の課題

今回の電卓の**パーサ**にはいくつかの課題がまだ残されています。

#### 【`4+`のような数式が通ってしまう。】
これは**nom**の`eof`**パーサ**を使うことで解消できます。

#### 【`47　+　3`のようにスペースを入れるとエラーになる。】
これは**nom**の`ws`**パーサコンビネータ**を使うことで解消できます。

#### 【同じ優先順位の演算子は右から計算されてしまう】
現状の実装では、
例えば`1-2-3`だと、`1-(2-3)`のように右から順番に計算されてしまいます。
`1-2-3`の結果は`-4`になるべきなのでこれはおかしいですね。
BNFを修正する必要があります。

現状のBNFを見てみましょう。

```
<expr>       := <term> [ ('+'|'-') <expr> ]
```
BNFをそのまま解釈すると、右に行けば行くほどASTの木が深くなってしまいます。
プログラムとBNFを修正して改善する必要があるでしょう。