Python 1本うどんコードトランスパイラ (Rust nomの使い方)

[鈴鹿高専 Advent Calender 2021](https://qiita.com/advent-calendar/2021/snct) 12日目の記事です

Rustのパーサコンビネータを紹介したかっただけのはずなのに, どうしてこんなことに

## 1本うどんコードとは

ご本家様 [Qiita - ugis_prog/Python 1本うどんコード](https://qiita.com/ugis_prog/items/ec33a98bd2b5aa1b0f3e)

## 1本うどんコードトランスパイラとは

**1本ではない普通のPythonスクリプトを, 1本うどんに麺打ちします.**
コード全体とか仕様は[github - niuez/UDON\_generator](https://github.com/niuez/UDON_generator)にあります.

## Playground

[Playgroundあります](https://niuez.github.io/UDON_generator/) あそべ

## 環境

Rustを用いて実装.  Pythonパーサは[nom](https://github.com/Geal/nom)というパーサコンビネータを用いて実装しました.

## パーサコンビネータ?

パーサコンビネータは, 単純なパーサの関数を関数で組み合わせてパーサを作り, 構文解析を行うライブラリです. nomにおいては, パーサは次のような関数の形をしています.

```rust
use nom::IResult;

fn hoge_parser(s: &str) -> IResult<&str, Hoge> { ... }
```

引数の`s`にはパースしたい文字列が, `IResult<&str, Hoge>`は`Result<(&str, Hoge), nom::error::Error>`と等価です.  
パース成功時はパースで残った文字列とパースした情報が(`(&str, Hoge)`), パース失敗時はエラー(`nom::error::Error`)が戻り値となります.

## 整数のパース

習うより慣れよなので, 早速整数のパースをしてみたいと思います. [Pythonの整数リテラル](https://docs.python.org/ja/3/reference/lexical_analysis.html#grammar-token-python-grammar-integer)を参考に10進数の整数`decinteger`を実装しましょう.

とりあえず, 整数リテラルをパースした情報を格納する構造体を作りましょう.

```rust
#[derive(Debug)]
pub struct Integer {
  num: String, // パースした整数をここに格納
}
```

## 整数のパース 非0版

まず, `nonzerodigit (["_"] digit)*`から実装してみます. `[]`はOption(あってもなくてもいい), `*`は0回以上の繰り返しです.

### `nonzerodigit`

1~9のどれかとマッチするようなので, [`one_of`](https://docs.rs/nom/7.1.0/nom/character/complete/fn.one_of.html)が使えそうです. `one_of("123456789")`が1~9までのどれかの文字をパースする関数です.  

### `digit`

同様に`one_of("0123456789")`ですね.  

### `"_"`

アンダーバー単体なので, [`char`](https://docs.rs/nom/7.1.0/nom/character/complete/fn.char.html)が使えそうです. `char('_')`でパースできます.

### `["_"]`

Option(あってもなくてもいい)は[`opt`](https://docs.rs/nom/7.1.0/nom/combinator/fn.opt.html)が使えます. `opt(char('_'))`となります. 

### `["_"] digit`

パーサを繋げるには[`tuple`](https://docs.rs/nom/7.1.0/nom/sequence/fn.tuple.html)が使えます. `tuple((opt(char('_')), one_of("0123456789")))`となります. `tuple`の中の括弧の量に注意

### `(["_"] digit)*`

0回以上の繰り返しは[`many0`](https://docs.rs/nom/7.1.0/nom/multi/fn.many0.html)が使えます. `many0(tuple((opt(char('_')), one_of("0123456789"))))`となります.

### `nonzerodigit (["_"] digit)*`

すべて繋げると, `tuple((one_of("123456789"), many0(tuple((opt(char('_')), one_of("0123456789"))))))`です. これでパーサは完成しました.

### パースした結果から`Integer`に変換

パースする関数は構成できたので, パースした情報を受け取ってみます.

```rust
// 今実装しているパーサ
pub fn nonzero_integer(s: &str) -> IResult<&str, Integer> {
  // remain_s: パースして左側に残った文字列
  // parse_info: パースした情報
  let (remain_s, parse_info) = tuple((one_of("123456789"), many0(tuple((opt(char('_')), one_of("0123456789"))))))(s)?;

  ...
}
```

- `tuple`: パースした情報をタプルにして返す. 
- `one_of`: パースした文字`char`を返す.
- `many0`: 0回以上パースした情報を`Vec`に入れて返す

以上より, 受け取る変数を以下のように変えられます.
```rust
// nonzero_digit_char: nonzerodigitがパースした文字
// digit_vec: (["_"] digit)の配列
let (remain_s, (nonzero_digit_char, digit_vec)) = ...
```

`digit_vec`も分解します. `_`は無視するので,

```rust
let digits = digit_vec
  .into_iter()
  .map(|(_underbar, digit)| { // クロージャ(ラムダ式?) "_"とdigitのタプルを受け取っている(many0の中身が返す型)
    digit // digitだけが必要なのでこれだけ返す
  })
```

あとは`nonzero_digit_char`と繋げるだけです.

```rust
let number =
  std::iter::once(nonzero_digit_char) // 1要素のイテレータ
  .chain(digits) // イテレータを繋げる
  .collect::<String>(); // charのイテレータをStringに変換

Ok((remain_s, Integer { num: number })) // パースして残った文字列と, Integerを返して終わり
```

### 完成

```rust
pub fn nonzero_integer(s: &str) -> IResult<&str, Integer> {
  let (remain_s, (nonzero_digit_char, digit_vec)) = tuple((one_of("123456789"), many0(tuple((opt(char('_')), one_of("0123456789"))))))(s)?;

  let digits = digit_vec
    .into_iter()
    .map(|(_underbar, digit)| { // クロージャ(ラムダ式?) "_"とdigitのタプルを受け取っている(many0の中身が返す型)
      digit // digitだけが必要なのでこれだけ返す
    })
  let number =
    std::iter::once(nonzero_digit_char) // 1要素のイテレータ
    .chain(digits) // イテレータを繋げる
    .collect::<String>(); // charのイテレータをStringに変換

  Ok((remain_s, Integer { num: number }))
}
```

## 整数のパース全体

0をパースする`"0"+ (["_"] "0")*`に対応した`zero_integer`という関数を作ってあげれば, [`alt`](https://docs.rs/nom/7.1.0/nom/branch/fn.alt.html)を使って,

```rust
alt((nonzero_integer, zero_integer))
```

で非0も0もパースできます.

## トランスパイラ

ここからはトランスパイラの話です. パースした情報を使って, 1本うどんを麺打ちします. 

例えば, `FileInput`というPythonコード全体の文を保持する構造体があります.

```rust
pub struct FileInput {
  stmts: Vec<Statement>,
}
```

1本うどんにトランスパイルするために, 文はすべてリストに押し込まれるのでトランスパイルは以下のように書けます.

```rust
impl FileInput {
  pub fn transpile(self) -> String {
    // 文をトランスパイルしてコンマで繋げる
    let stmts = self.stmts.into_iter().map(|s| s.transpile()).collect::<Vec<_>>().join(", ");
    // `[]`で覆う
    format!("[{}]", stmts)
  }
}
```

この`transpile`関数を全ての要素について一本うどんになるように書きます.

### 代入文のトランスパイル

代入文に関しては場合分けが必要です. セイウチ構文は`identifier := expression`という形にしか使えず`self.num := 15`のような形には使用できません.  

- `identifier = expression` -> `identifier = expression`
- `hoge.attr = expression` -> `hoge.__setattr__("attr", expression)`
- `hoge[index] = expression` -> `hoge.__setitem__(index, expression)`

というふうに場合分けします.

## 実例

```python
class UnionFind:
  def __init__(self, N):
    self.par = []
    for i in range(N):
      self.par.append(i)
  def find(self, x):
    if x != self.par[x]: 
      self.par[x] = self.find(self.par[x])
    return self.par[x]
  def unite(self, x, y):
    x = self.find(x)
    y = self.find(y)
    self.par[y] = x
  def same(self, x, y):
    return self.find(self.par[x]) == self.find(self.par[y])
NQ = list(map(int, input().split()))
N = NQ[0]
Q = NQ[1]
uf = UnionFind(N)
for i in range(0, Q):
  PAB = list(map(int, input().split()))
  P = PAB[0]
  A = PAB[1]
  B = PAB[2]
  if P == 0:
    uf.unite(A, B)
  else:
    print("YNeos"[not uf.same(A, B)::2])
```

```python
[UnionFind := type("UnionFind", (), {"__init__": (lambda self, N : [self.__setattr__("par", []), [[self.par.append(i)] for i in range(N)], None][2]), "find": (lambda self, x : [[self.par.__setitem__(x, self.find(self.par[x]))] if x != self.par[x] else [], self.par[x]][1]), "unite": (lambda self, x, y : [x := self.find(x), y := self.find(y), self.par.__setitem__(y, x), None][3]), "same": (lambda self, x, y : [self.find(self.par[x]) == self.find(self.par[y])][0])}), NQ := list(map(int, input().split())), N := NQ[0], Q := NQ[1], uf := UnionFind(N), [[PAB := list(map(int, input().split())), P := PAB[0], A := PAB[1], B := PAB[2], [uf.unite(A, B)] if P == 0 else [print("YNeos"[slice(not uf.same(A, B), None, 2)])]] for i in range(0, Q)]]
```

なんやねんこれ [ACもしている](https://atcoder.jp/contests/atc001/submissions/27690206)

## しめ

Pythonのパーサなんて一生フルスクラッチしたくないし, うどんを麺打ちしたくない.