Chapter 02

定義と方針

j5c8k6m8
j5c8k6m8
2021.07.04に更新

定義

正規表現の定義

正規表現は元々は数学的な概念であり、厳密な定義が存在します。この定義を大まかに説明すると、以下のようになります。

「任意の文字(空文字を含む)を、以下の3つの規則を繰り返し適用して組み合わせた表現を、正規表現とする」

3つの規則

表記 説明
A|B 文字列の和集合(A or B)
AB 文字列の連結
A* 文字列の繰り返し

~正規表現エンジンを作ろう (1) より~

本書の 論理演算可能 な正規表現としては、 新たに2つの規則 を加え、以下の5つの規則を繰り返し適用して組み合わせた表現を、論理演算可能な正規表現とします。

5つの規則

表記 説明
A|B 文字列の和集合(A or B)
A&B 文字列の積集合(A and B)
!A 文字列の補集合
AB 文字列の連結
A* 文字列の繰り返し

否定演算を定義するにあたり、 正規表現の解釈を限定 する必要があります。
正規表現は、「行頭(^)」や「行末($)」などの位置にマッチするもの(アンカー)があるため、これらを使わない場合は、 文字列の一部にマッチする表現 として解釈することが一般的です。
本書では、暗黙的に、正規表現を文字列全体とマッチする表記 として扱います。つまり、 正規表現が文字列集合を示すもの であると解釈します。そうすることで、 否定演算が、正規表現の対象となる文字列集合の補集合を求める演算 として定義できるでしょう。
つまり、 !a という正規表現は、 a 以外の文字列、つまり、 baa の文字列を含んだ文字列集合だと分るでしょう。

NFAとDFA

正規表現とNFAとDFAの等価性

正規表現とNFAは等価であり、互いに変換が可能です。

では、NFAとDFAはどうでしょう? NFAとDFAを比べると、DFAの方が制約が厳しく、表現力も低いように感じます。しかし、実はこの2つも等価であり、互いに変換が可能です。

今回の正規表現エンジンの作成では、これらの性質を利用します。まず、正規表現をより表現力が高いNFAで作成します。そしてこのNFAを、シミュレートが簡単なDFAに変換してから実行します。最終的にDFAに変換するため、今回作成するような方式の正規表現エンジンは、「DFAエンジン」と呼ばれます。

~正規表現エンジンを作ろう (1) より~

さて、論理演算可能な正規表現エンジンを作るためにはどうすればいいでしょうか?本書の実装方式では、 正規表現とNFAが等価であり、NFAとDFAが互いに変換可能なこと に注目します。これは、 正規表現が常にDFAで表現できる ことを意味します。

DFAであれば、 否定演算は受理状態を反転させる事で実現 できるでしょう。これが本書の1つ目のポイントです。否定演算自体を、NFAで実装出来ないわけではありません。ただし、正規表現をDFAとして捉えることで否定演算のイメージが容易となるでしょう。

また、正規表現をNFAを経由せずにDFAに変換し、 論理演算を含む5つの規則も、DFA間のアルゴリズムとして実装 します。これが本書の2つ目のポイントです。こうすることで、正規表現の評価結果であるDFAオブジェクト同士の論理演算に、実装した規則をそのまま適用出来ます。

今回作成するNFAを経由しない正規表現エンジンを、本書では 「純DFAエンジン」 と呼ぶことにします。

実装方針

さて、今回の「純DFAエンジン」を実装する上でのポイントを列挙します。

大方針

  • 正規表現を、 文字列集合の表現 として扱う。通常の正規表現の位置にマッチする ^$ は対象外とする。
  • 正規表現を直接DFAで表現する (純DFAエンジン) 。DFA間で、「和集合」、「積集合」、「否定」、「連結」、「繰り返し」の操作を実装する。
  • 文字列集合は、文字集合の(文字数上限のない)列表現 である。そのため、正規表現の文字クラスに相当する 文字集合に対する定義 も簡易的に行う。

クラス設計

  • 特殊文字を トークンクラス(Token)で定義 する。
  • 正規表現の文字クラスに相当する、 文字集合クラス(Chex)を定義 する。文字集合クラスは論理演算(論理和(和集合)、論理積(積集合)、否定(補集合))を可能とする。
  • 正規表現を表わす、 文字列集合クラス(Spex)を定義 する。全ての文字列集合状態を持つDFAとして内部構造を保持する。論理演算(論理和(和集合)、論理積(積集合)、否定(補集合))と、連結、繰返し演算を可能とする。
  • 入力の正規表現文字列に対する構文解析を、 パーサー(関数)で定義 する。
  • 構文解析結果から文字列集合クラスの構築と、最終的なIFとなるビルド関数を、 ビルダーモジュールのspex関数で定義 する。

ステップ数

本書で示す spexm8p パッケージのリポジトリは、 https://github.com/j5c8k6m8/spex-m8p-py になります。

本書では、全5つの全てのソースコードを記載しています。
ソースコードの行数は以下の表のとおりで、全774行 となります。

チャプター ファイル名 行数
トークンクラス token.py 12
文字集合クラス chex.py 134
文字列集合クラス spex.py 397
パーサーモジュール parser.py 196
ビルダーモジュール builder.py 27