正規表現エンジン（ロブ・パイクのバックトラック実装）をRubyで写経した

元になっているのは『プログラミング作法』に載っている、ロブ・パイクが書いたコード（以下「ロブ・パイク版」）ですが、[40行以内で正規表現エンジンを構築 | POSTD](https://postd.cc/build-your-own-regex/) の方を見て書いてみました。JavaScript の方が読み慣れているのと、[リポジトリ](https://github.com/nadrane/build-your-own-regex)にテストコードが用意されていたためです。


<!--
ほとんど同じですが、若干冗長な書き方に寄せています。
また、元記事では メタ文字として `*`, `?`, `.`, `^`, `$` のみに対応していますが、
ためしに `+` も使えるように改造してみました。
-->


<!--
上記 POSTD の記事でも紹介されている
[この記事](https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html)
（さっと見た感じでは『
[ビューティフル・コード](https://www.oreilly.co.jp/books/9784873113630/)
』でブライアン・カーニハンが書いている章と同じ内容）
を読むと、教育用のコードが必要だったが既存のものは大きすぎるのでどうしたもんかねとロブ・パイクに相談したところ、1,2時間オフィスにこもって30行くらいの正規表現エンジンを作ってくれた、ということが書いてあります。

> Rob disappeared into his office, and at least as I remember it now, appeared again in no more than an hour or two with the 30 lines of C code that subsequently appeared in Chapter 9 of TPOP. 

※ TPOP = The Practice of Programming

なるほど、そもそもがそういう経緯で書かれた、つまり教育・解説用途で生まれたコードだったわけですね。
-->

<!--
同書（p148）によると、コードの初出は [プログラミング作法](https://asciidwango.jp/post/155982762075) だそうです。
-->



<!-- ################################ -->

```ruby
def drop(text, n)
  text.chars.drop(n).join()
end

def empty?(str)
  str.nil? || str.empty?
end

def match_one(pattern_char, char)
  return true if empty?(pattern_char)
  return false if empty?(char)

  pattern_char == "." || pattern_char == char
end

# ロブ・パイク版では match
def search(pattern, text)
  if pattern[0] == "^"
    match(drop(pattern, 1), text)
  else
    match(".*" + pattern, text)
  end
end

# ロブ・パイク版では matchhere
def match(pattern, text)
  return true if empty?(pattern)
  return true if empty?(text) && pattern == "$"

  case pattern[1]
  # when "?"
  #   match_question(pattern, text)
  when "*"
    match_star(pattern, text)
  else
    match_one(pattern[0], text[0]) &&
      match(drop(pattern, 1), drop(text, 1))
  end
end

# def match_question(pattern, text)
#   (
#     match_one(pattern[0], text[0]) &&
#     match(drop(pattern, 2), drop(text, 1))
#   ) ||
#     match(drop(pattern, 2), text)
# end

def match_star(pattern, text)
  (
    match_one(pattern[0], text[0]) &&
    match(pattern, drop(text, 1))
  ) ||
    match(drop(pattern, 2), text)
end
```

<!-- ################################ -->

<!--
たったこれだけで正規表現の基本的な機能が実現できるというのは驚きですね。
-->

たったこれだけで正規表現の基本的な機能が実現できるのすごい＆おもしろいですね。

ロブ・パイク版では `.` `^` `$` `*` だけをメタ文字としてサポートする最低限の実装をまず示し、演習問題で `?` などを追加する流れになっています（なので、上に貼ったコードでは `?` の部分をコメントアウトしてみました）。


----

書籍『ビューティフルコード』では「1章 正規表現マッチャ」をブライアン・カーニハンが書いており、ロブ・パイク版について解説しています。

このコードが生まれた経緯について書かれていて、ここもおもしろい。

> 　1998年、ロブ・パイク（Rob Pike）と私は、『プログラミング作法』（原題『The Practice of Programming』、Addison-Wesley刊）という本を執筆していました。（略）
> 　問題は、既存の正規表現パッケージはどれも大き過ぎたということでした。（略）それでは教育用に適しているとは到底言えません。
> 　そこで私はロブに、正規表現の基本的な考え方が読み取れる最小限の、ただしそれでいて有用でつまらなくないパターンが書けるようなパッケージを探そうと提案しました。コードが本の1ページに納まるようなら理想的だと思いました。
> 　ロブは自分の部屋に入って行きました。今思い返してみると、1〜2時間も経たないうちだったと思います。彼は30行のCのコードを携えて部屋から出て来ました。そのコードが、『プログラミング作法』の第9章に掲載されているものです。（略）





# 参考

<!--
- [40行以内で正規表現エンジンを構築 | POSTD](https://postd.cc/build-your-own-regex/)
  - 「1章 正規表現マッチャ」をブライアン・カーニハンが書いており、ロブ・パイク版が生まれた経緯などが書かれています。
    さっと見た感じでは [A Regular Expression Matcher（www.cs.princeton.edu）](https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html) がと同じ内容。
  - さっと見た感じでは [A Regular Expression Matcher（www.cs.princeton.edu）](https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html) が「1章 正規表現マッチャ」と同じ内容。
-->

- [O'Reilly Japan - ビューティフルコード](https://www.oreilly.co.jp/books/9784873113630/)
  - 英語ですが [A Regular Expression Matcher（www.cs.princeton.edu）](https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html) で「1章 正規表現マッチャ」と同じ内容が読めるようです。
- プログラミング作法
  - [アスキードワンゴ](https://asciidwango.jp/post/155982762075)
  - [達人出版会](https://tatsu-zine.com/books/practice-of-programming)
- [正規表現技術入門 ――最新エンジン実装と理論的背景：書籍案内｜技術評論社](https://gihyo.jp/book/2015/978-4-7741-7270-5)
  - 「5.1 基本的なVM型エンジンの実装」にロブ・パイク版についての説明があります。

# この記事を読んだ人は（ひょっとしたら）こちらも読んでいます

<!-- Ruby: 入れ子の配列だけをパースできるパーサを作る（手書きの再帰下降パーサ） #Ruby - Qiita -->
https://qiita.com/sonota88/items/816b6b8d7a362ef4e332

<!-- 四則演算と剰余のみのexprコマンドをRubyで作ってみた -->
https://zenn.dev/sonota88/articles/06c540eda79b98

<!-- Rubyで素朴なdiff（動的計画法）を書いてみた - Qiita -->
<!-- https://qiita.com/sonota88/items/5f040d7aaf494477eefa -->
<!-- Rubyで素朴なdiffコマンドを書いてみた（動的計画法） -->
https://zenn.dev/sonota88/articles/6efd83d606cc2f

<!-- （2週間ちょっとで）Rubyでかんたんな自作言語のコンパイラを作った #Ruby - Qiita -->
https://qiita.com/sonota88/items/2b95378b43a22109513c