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

鈴鹿高専 Advent Calender 2021 12日目の記事です

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

1本うどんコードとは

ご本家様 Qiita - ugis_prog/Python 1本うどんコード

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

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

Playground

Playgroundあります あそべ

環境

Rustを用いて実装. Pythonパーサはnomというパーサコンビネータを用いて実装しました.

パーサコンビネータ?

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

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の整数リテラルを参考に10進数の整数decintegerを実装しましょう.

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

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

整数のパース 非0版

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

nonzerodigit

1~9のどれかとマッチするようなので, one_ofが使えそうです. one_of("123456789")が1~9までのどれかの文字をパースする関数です.

digit

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

"_"

アンダーバー単体なので, charが使えそうです. char('_')でパースできます.

["_"]

Option(あってもなくてもいい)はoptが使えます. opt(char('_'))となります.

["_"] digit

パーサを繋げるにはtupleが使えます. tuple((opt(char('_')), one_of("0123456789")))となります. tupleの中の括弧の量に注意

(["_"] digit)*

0回以上の繰り返しはmany0が使えます. many0(tuple((opt(char('_')), one_of("0123456789"))))となります.

nonzerodigit (["_"] digit)*

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

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

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

// 今実装しているパーサ
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に入れて返す

以上より, 受け取る変数を以下のように変えられます.

// nonzero_digit_char: nonzerodigitがパースした文字
// digit_vec: (["_"] digit)の配列
let (remain_s, (nonzero_digit_char, digit_vec)) = ...

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

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

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

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

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

完成

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を使って,

alt((nonzero_integer, zero_integer))

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

トランスパイラ

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

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

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

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

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)

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

実例

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])

[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もしている

しめ

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