筆者が在学する筑波大学にはオートマトンと形式言語という授業があります。名前のとおり、主にオートマトンについての授業です。

その授業の中で正規表現と有限オートマトンの等価性についての言及がありました。一応その事実については知っていたのですが、改めて学んだ結果なぜか自分の中で大層盛り上がってしまい、正規表現エンジンを実装することにしました(テスト前はテスト勉強以外のことがしたかったという理由もあります)。

リポジトリは https://github.com/sosukesuzuki/oregexp にあります。多分結構バグってますが。

全体の構成

正規表現エンジンには色々な作り方があると思いますが、今回は初めてでよくわからないので、下記のようなシンプルな構成にしました。

• サポートする文字は[a-zA-Z]のみ
• サポートする演算は基本の 3 つのみ(結合、選択、繰り返し)
• パーサーは手書きの再帰下降構文解析
• NFA で実装する

参考にした書籍

• 計算理論の基礎
• 正規表現技術入門

パーサーを実装する

パーサーは普通に実装しました。

実は筆者は 1 からパーサーを書いたことがありませんでした。@babel/parser などをよく触っていたのでなんとかなるだろうと考えていたのですが、残念ながら左結合の演算子のパーサーを書くことができませんでした...。すべての演算子を右結合にするわけにはいかないので、Rui Ueyama さんの低レイヤを知りたい人のための C コンパイラ作成入門を参考にして実装しました。

ところで、冒頭で紹介したオートマトンと形式言語という授業では後半に自由文脈文法についても学びます。授業を受けた直後はやはり自由文脈文法の気持ちが出来ているので、文法を書いてパーサーを書くのも楽しかったです。

NFA を実装する

NFA は適当に実装します。

いくつかインターフェースを検討しましたが、最終的に次のようなインターフェースになりました。

const nfa = new Nfa([
  {
    label: "q0",
    initial: true,
    transitionRules: {
      a: ["q1"],
    },
  },
  {
    label: "q1",
    transitionRules: {
      b: ["q2"],
    },
  },
  {
    label: "q2",
    accepted: true,
    transitionRules: {},
  },
]);
nfa.read("a");
assert(!nfa.accepted);
nfa.read("b");
assert(nfa.accepted);
nfa.reset();
// or
nfa.run("ab");

これは、次の NFA を表すのコードです。

NFA を実装するのは普通に難しかったです。特に ε 遷移の扱い方が難しかったです。参考にした正規表現技術入門には NFA から ε 遷移を取り除くテクニックが書いてあったのですが、なんとかなるだろと思って愚直に実装したら多くのバグの原因になってしまいました。

逆に ε 遷移以外は簡単だったので、DFA は実装するの簡単なのかなと思いました。

各演算に該当する NFA を作る

冒頭で説明したように、今回作った正規表現エンジンは連結と選択と繰り返しのみをサポートしています。

正規表現技術入門で、正規表現から NFA を作成する方法としてあげられている Thompson の構成をを用いてそれぞれの演算に該当する NFA を構成し、ボトムアップに組み上げていくことにしました。

まず "a" 一文字と等価な NFA はこんな感じ。

結合 "ab" と等価な NFA はこう。

選択 "a|b" と等価な NFA はこう。

繰り返し"a*" と等価な NFA はこう。

ここでは例を簡単に示すために具体的な文字を使いましたが、こんな感じの小さいパーツをガチャガチャくっつけていきます。

それぞれの演算のために Nfa クラスに static メソッドとして concat、select, star を実装しました(プライベートプロパティに触りたいから)。

const newNfa1 = Nfa.concat(nfa1, nfa2);
const newNfa2 = Nfa.select(nfa1, nfa2);
const newNfa3 = Nfa.star(nfa1);

で、木を操作していい感じにトラバースしながらこれらの API を使って組み立てれば NFA の完成です。詳しくは正規表現技術入門を読むとよいと思います。

使った技術

TypeScript と Node.js を使いました。他のライブラリには依存していません。Node.js のコアモジュールもほとんど使ってなかったと思います。

パーサー部とエンジン部を分けて開発するため npm workspaces でパッケージを分けてみました。普通に快適でした。

npm にパブリッシュはしていません。めんどくさいので今後もしないかもしれません。

感想

楽しすぎだったので、またなんか正規表現エンジン実装したいです。今度は別の方法とか別の言語でやってみたいです。