🌊

C言語で書いたVM型正規表現エンジンをWebAssemblyにしてブラウザで動かす

2023/12/10に公開

正規表現

tech

この記事は、茨城県つくば市の町域であるところの天久保とは無関係な任意団体「天久保」のアドベントカレンダーの 5 日目です。今日は 12 月 10 日ですけど。

今となっては学年を抜かされてしまった後輩に急かされてしまったので、急いで書いています。

冬は正規表現の季節

12 月になっていよいよ冬の到来を感じる気候になってきました。冬といえば正規表現です(筑波大学で「オートマトンと形式言語」という授業が開講されるのが冬だから）。

ちょうど一年前、私は生まれて初めて正規表現エンジンを作りました。去年作った正規表現については以下のブログを参照してください:

去年の正規表現エンジンには、以下のような特徴がありました:

TypeScript で記述されている
正規表現をNFA(非決定性有限オートマトン)に変換して実行する

ということで、今年はまた違った正規表現エンジンを書いてみました。去年と同じように全く実用性がない車輪の再発明の遊びです。

今年の正規表現エンジン

今年の正規表現エンジンは、以下のような特徴を持っています:

C 言語で書かれている
正規表現をバイトコードにコンパイルし、それをVMで実行する

最近ちょっとずつ C 言語の読み書きができるようになってきたので、今回はすべて C 言語で書きました。また、正規表現をNFAに変換するのではなく、VMを使ってバックトラックができる正規表現エンジンを作りました。

去年のものはNFAをそのまま実行していたので、今年はそれをDFAに変換してから実行するということも考えましたが、VMってちょっとかっこよい感じがしたので、VMでやることにしました。

実装

リポジトリは https://github.com/sosukesuzuki/fml にあります。Fml という名前はもともとなんの略でもなかったのですが、ChatGPT に後付けで正式名称を考えてくれと言ったら「Fundamental Matching Library」と言われたので、そうなりました。

https://github.com/sosukesuzuki/fml

正規表現エンジンとしての機能は非常にミニマムで、連接(ab)と選択(a|b)とスター(a*)と、優先度のためのカッコのみをサポートしています。

全体のアーキテクチャ

Fmlのアーキテクチャは、以下の図のようになっています:

もとの正規表現をパースして構文木にして、それを命令列にコンパイルします。この命令列と、マッチ対象の文字列を実行するやつに渡して、その文字列が正規表現にマッチするかどうかを判定します。

そして、実行するやつの中身は、以下のようなアーキテクチャになっています:

PC(プログラムカウンタ)は、現在実行している命令を指しています。SP(ストリングポインタ)は、現在見ている文字を指しています。マッチに失敗したときのバックトラックのために、スタックには PC と SP のペアを積んでいきます。今やっているマッチが失敗したら、あらかじめ積んでおいた PC と SP に戻って、マッチを再試行します。具体的な命令セットは以下の4種類です:

命令	説明
char c	現在のSPが指している文字とcを比較する。一致していればマッチ成功。一致していなければマッチ失敗で現在のスレッド終了。
match	マッチ成功で現在のスレッドを終了。
jmp x	xの位置の命令にジャンプする(PCをxに変更)
split x y	2つのスレッドに分岐する。一方のスレッドはxから実行を開始し、もう一方のスレッドはyからスレッドを実行する。どちらのスレッドもSPは現在のものをそのまま引き継ぐ。

このあたりの話は正規表現技術入門という書籍に詳しく乗っているので読んでみてください。

パーサー

パーサーは手書きの再帰下降構文解析です。

構文解析をしながら徐々に字句解析をしていくわけですが、去年書いた正規表現エンジンのパーサーはTypeScriptで書いていたので、一個トークンを読み進めるごとに new Token(...) みたいなことをして新しいトークンのオブジェクトを作っていたのですが、今年は C 言語なので一回 Token 構造体のインスタンス（？）を作ったらそれを構文解析全体を通して使い回すようにしました。このあたりは oniguruma のコードを参考にしました。

普通に考えたらそうした方が良いと思うのですが自分では思いつかなかったので、前に作った LISP 処理系のパーサーはトークンを一個読むごとに malloc をしていた気がします。

あとから思ったけど、もしかしたらパースせずに直接命令列にできたりするかな。するのか？

コンパイル

パーサーによって構文木を作ったら、次はそれを前述の命令にコンパイルします。各演算に対してそれぞれ次のように命令列を生成します(Markdownのテーブル記法で上手く書くことができなかったため画像を貼り付けています):

命令に対応する構造体を以下のように定義しました:

typedef struct Instruction Instruction;

typedef enum InstructionKind {
    INSTRUCTION_MATCH,
    INSTRUCTION_CHAR,
    INSTRUCTION_SPLIT,
    INSTRUCTION_JMP,
} InstructionKind;

typedef struct Instruction {
    InstructionKind kind;
    union {
        struct {
            char c;
        } iChar;

        struct {
            int pos1;
            int pos2;
        } iSplit;

        struct {
            int pos;
        } iJmp;
    } u;
} Instruction;

この命令を生成できるように、構文木をトラバースして、命令列の配列に append する処理を書きました。命令列がどのくらいの長さになるかは事前にはわからないので、size と cap と配列の実体へのポインタを持つ構造体を定義して、cap を超えそうになったら size を拡張して配列を realloc する可変長配列みたいなやつを作りました。

実行するやつ

VM の本体です。命令列を先頭から見ていって前述した通りの処理をします。

マッチに失敗した場合は、スタックから PC と SP のペアをポップして、その時点にまで戻ります。もしスタックが空だった場合は、その時点で全体のマッチが失敗します。

具体例を示します。まず、正規表現 a|b をコンパイルした結果の命令列は以下です:

0: split     1, 3
1: char      a
2: jmp       4
3: char      b
4: match

マッチが失敗するケース

この命令列に対してテキスト c を入力することを考えてみます。当然、マッチしない結果になることが期待されます。

まず最初に split 1, 3 が実行されます。これは 1 行目の命令と 3 行目の命令への分岐です。3行目の命令をまず先に試し、もしもマッチに失敗したら 1 行目の命令にバックトラックすることになります。そのため、スタックに SP を 0 (指している先の文字は c)、PC を 1 としてプッシュします。そして、PC を 3 行目に移し命令を実行します。

この時点で SP が指している文字は c ですから、3 行目の char b とはマッチが失敗します。そしたらスタックからポップしてきて 1 行目の命令にバックトラックします。

1行目の char a を実行します。しかし、今 SP が指している文字は変わらず c で、char a とはマッチが失敗します。そして、またスタックからバックトラック先をポップしようとしますが、もうスタックは空なので、この時点で全体のマッチが失敗します。

マッチが成功するケース

次に、成功するケースを考えてみましょう。テキスト a を入力してみます。この場合、split 1, 3 のところは同じです。char b とのマッチが失敗するところも同じです。しかし、バックトラックして再試行した char a と入力テキストの a のマッチが成功します。マッチが成功したら次の 4 行目の命令 jmp 4 の実行へと進みます。

jmp 4 で 4 行目のマッチまで進むと match 命令に到達します。match 命令は問答無用で全体のマッチを成功させます。

メモリ管理

malloc するだけして free 全くしなくてもこのくらいのプログラムなら普通に動くので全く free してないんですが、練習として今度やってみます。

WebAssembly にコンパイルしてブラウザで動かす

せっかく C 言語で書いたなら WebAssembly にコンパイルしてブラウザで動かしたいなあと思ったので、やってみました(TypeScript で書いたならそのまま動くんだけどね)。また、マッチしたかどうかの結果だけではなくて、構文木や命令列も見れるようになると、デバッグに便利そうです。

ということで作りました:

https://github.com/sosukesuzuki/fml-web

構成

アプリケーション全体としての構成は Vite + React の SPA です。/lib 以下にエントリポイントとなる C 言語のファイルがいくつかあります。このファイルを Emscripten を使って WebAssembly にします。

そして、この /lib に package.json を生やして npm のパッケージとして扱えるようにして、React 側から dynamic import します。*.wasm のファイルを HTML の隣に置く必要があったので https://github.com/sapphi-red/vite-plugin-static-copy を使って /lib 配下からビルド時にコピーしています。

C で作った構文木や命令列を構造体のインスタンスのまま直接 JavaScript の世界に渡すとめんどくさそうなので、JSON の形にして文字列として渡すようにしています。

様子

実際に動いている様子がこちらです:

https://sosukesuzuki.github.io/fml-web/

遊んでみてもいいですが、結構バグってると思います。

おわりに

こういう誰の役にも立たないものを作るのは楽しいですねえ。今年は12月の早いうちに正規表現エンジンを作ることができたので、余裕をもって試験勉強に臨めそうです。