🐥
Rust で正規表現エンジンを実装した話 その①
概要
以下の2点から、Rustで正規表現エンジンを実装しました。
- Rustを学ぶ
- 正規表現の仕組みを理解する
知識の整理をかねて、実装したコードの解説を記載します。
ソースコードは以下のリポジトリに含まれています。
本記事で使用するコードは、正規表現エンジンの処理を解説のしやすさを優先して、エラー処理を考慮していません。
正規表現エンジンの種類
正規表現エンジンには、以下の2種類の実装があります。
- VM型
- DFA型
今回実装したエンジンはVM型です。
2種類のエンジンの違いや、メリットなどに興味がある方は以下の本を読むことをお勧めします。
処理の流れ
VM型の正規表現エンジンは大きく分けると、以下の3つの処理を行っています。
- パターンをパースし、抽象構文木(AST)を生成する
- ASTから命令列を生成する
- 文字列がパターンと一致するか評価する
その②以降で、各処理の説明・実装内容を記載していきます。
以下はリンクです。
Discussion