各ノードの実装
では、構文木の各ノードのassemble
メソッドを実装し、正規表現をNFAに変換する部分を作ります。Character
、Union
、Concat
、Star
クラスについて、一つずつ変換の方法を説明します。
これらの4つのノードはInterpreterパターンで実装します。どのノードもassemble
メソッドを持っており、NFAFragment
の作成の一端を担っています。下位のノードが存在する場合は、下位のノードのassemble
メソッドを呼んでNFAFragment
を作ってもらい、得られたフラグメントに自分のノードが表す演算を施して上位に返却します。このように互いのノードが協調し、再帰的にNFAを組み立てます。
Characterクラス
Character
クラスは、1文字の正規表現を表します。例えば、 Character('a')
で表されるノードは、'a'一文字にマッチする正規表現を表します。この正規表現を表すNFAは、以下のように作ることができます。
![Characterノード](http://cz-cdn.shoeisha.jp/static/images/article/3039/Character.png)
説明するまでもなく、初期状態から 'a' が入力されると受理状態(二重丸)に遷移しますので、 'a' はこのNFAに受理されます。また、他の文字の遷移はないので、 'a' 以外の1文字は受け付けません。さらに、 'aa' のように 'a' の後にさらに入力があると、受理状態からの遷移先がないために受理状態にとどまることができず、これもまた受理されません。なので、このNFAは 'a' 一文字の文字列だけを受理します。
この図を元に、フラグメントを作りましょう。黄色い枠が、作るべきフラグメントです。赤で書いている部分が、新しく作成しなければならない部分です。図から、2つの状態とその状態間の 'a' による遷移を作らなければいけないことが分かると思います。実装は、この図に忠実に行います。
class Character(object): def __init__(self, char): self.char = char def assemble(self, context): frag = NFAFragment() s1 = context.new_state() s2 = context.new_state() frag.connect(s1, self.char, s2) frag.start = s1 frag.accepts = frozenset([s2]) return frag
assemble
メソッドを見ると、新しいフラグメントを作り、新しい状態を2つ作成してから、互いにこのCharacterノードが表す文字列である self.char
で繋いでいます。図から、初期状態は遷移元の状態であるs1、受理状態はs2となります。受理状態は複数あり、集合として表現されることに気をつけて下さい。frozensetでラップする必要があります。
Unionクラス
Union
クラスは、和集合演算を表します。Union(A, B)
と言うノードは、 A|B という | で結ばれた正規表現を表します。この、 | 演算をNFAで構築すると以下のようになります。
![Unionノード](http://cz-cdn.shoeisha.jp/static/images/article/3039/Union.png)
縦に2つ並んでいる四角が、正規表現Aから作られたフラグメントと正規表現Bから作られたフラグメントです。図中のεは空文字('')を表します。赤い部分が追加された部分で、新しい状態が一つと、その状態から空文字('')で2つのフラグメントに遷移する矢印が追加されていることがわかります。
このNFAが | 演算をきちんと表しているか、ちょっと検証してみましょう。開始状態におかれたこのNFAは、いきなり空文字によって2つのフラグメントに遷移します。この遷移の際、入力されたのはあくまでも空文字列なので、入力文字はまだ1文字も読みまれずにそのまま残っていることがポイントです。これにより、それぞれのフラグメントには、大本のNFAに入力されたのと同じ入力文字が入力されることになります。ちょうど、2つのフラグメントが同時に入力された文字列の判定を進めるようなイメージです。
NFAでは、されうる遷移のうちいずれかが受理状態に辿り着けばその文字列は受理されたことになります。つまり、フラグメントAで受理状態に着いても、フラグメントBで受理状態に着いても、その文字列は受理されたことになります。これは、正規表現Aか正規表現Bのいずれかにマッチする文字列が受理されることを意味します。よって、 | 演算の定義を満たしていることがわかります。
それでは、実装を見てみます。
class Union(object): def __init__(self, operand1, operand2): self.operand1 = operand1 self.operand2 = operand2 def assemble(self, context): frag1 = self.operand1.assemble(context) frag2 = self.operand2.assemble(context) frag = frag1 | frag2 s = context.new_state() frag.connect(s, "", frag1.start) frag.connect(s, "", frag2.start) frag.start = s frag.accepts = frag1.accepts | frag2.accepts return frag
| 演算は2項演算なので、Unionノードはoperand1とoperand2の二つのノードを保持しています。この2つのノードに対してassemble
を呼ぶことで、和集合演算の対象とすべきフラグメントが得られます。これを、frag1とfrag2としています。
まず、フラグメントの骨組みを作るために、frag1とfrag2を合成してfragを作ります。ちょうど、黄色い四角にフラグメントを2つ置いた状態だと思って下さい。ここに、図を見ながら必要な要素を追加します。まず、新しい状態sを追加し、そこから空文字でそれぞれのフラグメントの開始状態(frag1とfrag2)に接続をしています。
最後に、図を参考にして開始状態と受理状態をセットします。開始状態は追加した新しい状態s、受理状態は双方のフラグメントの和集合となることがわかります。