この記事は
パーサジェネレーターLIME入門
パーサジェネレーターLIME入門その２(二項演算式にマッチさせる)
パーサジェネレーターLIME入門その３(単項演算子にマッチさせる)
の続きになります。
今回の要諦
マッチング動作のアルゴリズムを解説します。
マッチャーとは？(過去のおさらい)
Matcherクラスのインスタンスです。
入力文字を与えると受理または非受理の反応をします。
マッチャー同士を演算子を使って合体させる事で更に大きなマッチャーになります。
マッチ型とは？
マッチ型のインスタンスは「入力文字列の●文字目から▲文字目までに一致している」を保持します。
マッチング処理の過程で自動生成されます。
入力文字列への参照も保持しているので、Valueプロパティで一致部分の文字列を取得できます。
また子要素を内包する機能もあります。
例えば「０～３文字目」を指し示している子マッチと「４～２２文字目」を指し示している子マッチを内包している場合、親マッチは「０～２２文字目」という範囲になります。
親マッチが子マッチを内包するルールは以下の通りです。
文字範囲が連続する。
インデックスが０に近い順から並ぶ。
範囲の重複は認めない。
内包する個数に制限は無い。
子マッチは文字範囲の連続する別のマッチと共に親マッチに内包され、親マッチも別のマッチと共に更に大きなマッチの一部となり…合体を重ねていき最終的には１個の大きなマッチが完成します。それがマッチング結果となります。
マッチは木構造であり即ち構文木となります。
「末端マッチ」から原初のマッチが生まれる瞬間
子マッチを持たない原初のマッチが発生する可能性は２つです。
Ａ．１文字に一致するマッチャーに入力文字が与えられた時
Ｂ．長さの無いマッチャーがマッチを発生する条件を満たした時
Ａは話が簡単です。
例えば'A'.To('Z')というマッチャーの場合、入力文字として大文字のどれかが与えられたらマッチが発生します。
Ｂに該当するマッチャーとは、文字列先頭・文字列末尾・単語区切りです。
文字列先頭に関しては、走査中文字インデックスが０の時のみマッチが発生します。
文字列末尾に関しては、走査中文字インデックスが入力文字列の長さと一致する時にマッチが発生します。
単語区切りに関しては、走査中文字インデックスと入力文字列を突き合わせて、前後の文字種が違っていればマッチが発生します。
原初のマッチを生み出すマッチャーを「末端マッチャー」と呼ぶ事にします。
マッチャーも木構造
("醤油"._() | "みそ" | "豚骨") + "ラーメン"の場合、以下のような木構造のマッチャーとなります。
"醤油"._()のように文字列から作ったマッチャーも内部的には１文字単位の末端マッチャーの連結として処理しています。
この例では最下段にある１０個が末端マッチャーです。
末端マッチャーが発生させたマッチはこの木を登っていきます。
左上に連結と付いているマッチャーは下から登ってきたマッチを連結させたマッチを作ります。
+演算子の演算結果として返されるマッチャーがこれです。
「連結マッチャー」と呼ぶ事にします。
左上に選択と付いているマッチャーは下のどの経路から登ってきたマッチでも上に素通りさせます。
|演算子の演算結果として返されるマッチャーがこれです。
「選択マッチャー」と呼ぶ事にします。
左上にゴールと付いているマッチャーがそのものズバリ、ゴールです。
ゴールにたどり着いたマッチはマッチング結果として外に出せる完成品です。
このマッチャーの木に"みそラーメン定食"の８文字を与えた場合の挙動を見てみます。
み
まずはインデックス０み を与えてみます。
入力文字は末端マッチャー全てに与えられます。
「醤」マッチャーや「骨」マッチャーなどがことごとく無反応な中、
唯一、「み」マッチャーから文字範囲０～０のマッチが発生します。
０～０とは、０文字目から始まり０文字目が末尾、という意味です。
「み[0-0]」と呼ぶ事とします。
「み[0-0]」は木を登り、「みそ」マッチャーに到達します。
連結マッチャー内部には子マッチャーと同数の「控室」を持っています。
登ってきたマッチを留め置く為のものです。
同数である理由は、どの子マッチャー出身かで留め置く控室を変えるからです。
今回登ってきたマッチ「み[0-0]」は、「みそ」の筆頭の子「み」出身なので、控室１番に留め置かれます。
「み[0-0]」は自分の後ろに連結すべきマッチと合流するまでこの控室で待機です。
発生した全てのマッチが停止したので、インデックス０みの処理はここまでです。
そ
次はインデックス１そ です。
入力文字は末端マッチャー全てに与えられます。
「そ」マッチャーからマッチ「そ[1-1]」が発生します。
「そ[1-1]」は「みそ」に到達して控室に導かれます。
「そ[1-1]」は「みそ」の２番目の子「そ」出身なので控室２番です。
控室は子マッチャーの数と同数なので控室２番は「みそ」の最後の控室です。
最後の控室に割り当てられたマッチには「後続するマッチを待つ」という選択肢はありません。
「条件の合うマッチと合体する」か「相手にあぶれた事が確定して消滅する」の二択です。
控室に付いた「そ[1-1]」はある条件に基づき隣の控室を探します。
自分より１つ若い番号の控室に自分と文字範囲が連続するマッチは居ないかな？と。
自分より１つ若い番号の控室に居るのは自分のすぐ前に連結されるべきマッチのはずです。
そして自分と文字範囲が連続しているはずです。
今回は控室１番に条件が合致する「み[0-0]」を見つけました。
ここで、「み[0-0]」「そ[1-1]」が合体し親マッチ「みそ[0-1]」が誕生します。
めでたく「そ[1-1]」は「みそ[0-1]」の一部となり、消滅を免れる事ができました。
「みそ[0-1]」にはもう「みそ」に留まる理由はありません。
マッチャーの木を登り「(醤油|みそ|豚骨)」に到達します。
選択マッチャーである「(醤油|みそ|豚骨)」はマッチを留め置く機能はありません。普通に素通りです。
「みそ[0-1]」はまた木を登り、連結マッチャーである「(醤油|みそ|豚骨)ラーメン」の控室１番に留め置かれます。
ここで連結マッチャー「ラーメン」出身の後続マッチが登ってくるまで気長に待つ事になります。
発生した全てのマッチが停止したので、インデックス１その処理はここまでです。
ラ
次はインデックス２ラ です。
例のごとく入力文字は末端マッチャー全てに与えられ、その内の一つ、
「ラ」マッチャーから「ラ[2-2]」が発生し、「ラ[2-2]」はマッチャーの木を登ります。
「ラ[2-2]」の故郷「ラ」は「ラーメン」マッチャーにとって筆頭の子です。
もちろん「ラーメン」の控室１番に留め置かれます。
発生した全てのマッチが停止したので、インデックス２ラの処理はここまでです。
ー
次はインデックス３ー です。
「ー」マッチャーから「ー[3-3]」が発生し、「ー[3-3]」はマッチャーの木を登ります。
「ー[3-3]」は「ラーメン」の控室２番に留め置かれます。
おや、控室１番に合体できそうな「ラ[2-2]」が居ます。合体する事にしましょう。
「ラ[2-2]」と「ー[3-3]」が合体して「ラー[2-3]」の誕生です。
さて、先の「みそ[0-1]」の例では合体した直後に連結マッチャーを後にしましたが、
今回の「ラー[2-3]」はまだ連結マッチャー上で、控室３番に来るべき後続を待たねばなりません。
なので「ラー[2-3]」にふさわしい居場所は控室２番です。
「ラ[2-2]」と「ー[3-3]」が合体した「ラー[2-3]」は控室２番に収まりました。
しかし、控室１番はというと空室になった訳ではありません。
控室１番には未だに「ラ[2-2]」が居座っています。
実は「ラ[2-2]」は合体前に分身して、合体の材料として自分の分身体を差し出したのです。
ついでに言うと各控室は収容可能定員は無制限です。
今回の例では分身する必要は無いのですが、分身が必要な場面も有りうるので一応分身しています。
分身の必要性については後に述べるループマッチャーの解説の際に言及しますが、今回はサラッと流します。
発生した全てのマッチが停止したので、インデックス３ーの処理はここまでです。
メ
次はインデックス４メ です。
「メ」マッチャーから「メ[4-4]」が発生し、マッチャーの木を登ります。
「メ[4-4]」は「ラーメン」の控室３番に留め置かれます。
控室２番の「ラー[2-3]」と控室３番の「メ[4-4]」が合体し、
「ラーメ[2-4]」が控室３番に収まります。
発生した全てのマッチが停止したので、インデックス４メの処理はここまでです。
ン
次はインデックス５ン です。
「ン」マッチャーから「ン[5-5]」が発生し、マッチャーの木を登ります。
「ン[5-5]」は「ラーメン」の控室４番に留め置かれます。
控室３番の「ラーメ[2-4]」と控室４番の「ン[5-5]」が合体し「ラーメン[2-5]」が誕生します。
最後の控室で合体して誕生した「ラーメン[2-5]」は「ラーメン」マッチャーから巣立ってマッチャーの木を登ります。
「ラーメン[2-5]」は「(醤油|みそ|豚骨)ラーメン」の控室２番に収まります。
もちろん控室１番で待っている「みそ[0-1]」と合体し「みそラーメン[0-5]」の誕生です。
最後の控室で誕生した「みそラーメン[0-5]」は「(醤油|みそ|豚骨)ラーメン」を巣立ってマッチャーの木を登ります。
「Root」にたどり着いた「みそラーメン[0-5]」は「Root」内部の唯一の控室に留め置かれます。
発生した全てのマッチが停止したので、インデックス５ンの処理はここまでです。
定
末端マッチャーに「定」に対応する物は無いので全く変化が起きません。
インデックス６定の処理はここまでです。
食
末端マッチャーに「食」に対応する物は無いので全く変化が起きません。
インデックス７食の処理はここまでです。
マッチング結果は？
Rootが内部の控室に溜め込んだマッチ全てがマッチング結果となります。
今回の例では「みそラーメン[0-5]」が唯一のマッチですが、マッチャーの定義と入力文字列次第では複数個存在する可能性があります。
もし、入力文字列が「みそ味ラーメン」だったら？
連結マッチャー「(醤油|みそ|豚骨)ラーメン」の上で「みそ[0-1]」と「ラーメン[3-6]」は合体を試しますが、範囲が連続しないのでできません。
どちらのマッチもそれ以上登ることができず、Rootにたどり着けるマッチはありません。
マッチング結果はゼロ個です。
マッチング動作のまとめ
文字入力ごとに末端マッチャー全てに入力文字が与えられ、入力を受理したマッチャーからは末端マッチが発生します。
マッチは連結マッチャーの控室で足止めされ後続を待ちます。範囲の連続する後続と合体を繰り返し、最終控室に現れた後続と合体できれば完全体となります。
完全体まで到達できれば連結マッチャーを巣立っていき、登った先にある連結マッチャーに足止めされます。
Rootにたどり着くまで 発生→登る→足止め→合体→完全体→登る→足止め→合体→完全体… というサイクルを繰り返します。
Rootにたどり着いたマッチ全てがマッチング結果となります。
続いて「ループマッチャー」の挙動を解説します。
正規表現の「量指定子」に相当する動作を再現するマッチャーです。
例として'A'.To('Z').Times(1,3)というマッチャーに"ABCD"という文字列を与えた際の挙動を見てみます。
A
インデックス０Aを入力してみましょう。
末端マッチから発生した「A[0-0]」がループマッチャーにたどり着きます。
ループマッチャーの最低回数は１回。
「A[0-0]」が到達した時点で条件を満たしているので上に登る事ができます。
でも、最高回数は満たしていないので後続を待って合体する必要もあります。
よって「A[0-0]」は、登る個体と待つ個体の二つに分身します。
登る方の「A[0-0]」はRootの控室に到達し旅を終えます。
待つ方の「A[0-0]」はループマッチャーの控室に収まります。
前回の連結マッチャーでは「どの子マッチャー出身か？」で控室が分けられていました。
今回のループマッチャーでは「ループの何回目か？」で控室が分けられています。
「A[0-0]」はループ１回目なので控室１に収まります。
この時点でループマッチャー上には以下の個体が待機しています。
控室１ 「A[0-0]」
この時点でRootに到達したマッチは以下の通りです。
１回ループ：「A[0-0]」
発生した全てのマッチが停止したので、インデックス０Aの処理はここまでです。
B
インデックス１Bを入力してみましょう。
末端マッチから発生した「B[1-1]」がループマッチャーにたどり着きます。
「B[1-1]」は次の２個体に分身します。
誰とも合体せず「B[1-1]」のままで居る個体。
「A[0-0]」の分身体と合体して「AB[0-1]」となる個体。
前者の「B[1-1]」は更に２個体に分身します。
最低回数以上(１回)なのでループマッチャーから旅立ってRootに到達する個体。
最高回数未満(１回)なのでループマッチャー上で後続を待つ個体。
後者の「AB[0-1]」も更に２個体に分身します。
最低回数以上(２回)なのでループマッチャーから旅立ってRootに到達する個体。
最高回数未満(２回)なのでループマッチャー上で後続を待つ個体。
この時点でループマッチャー上には以下の個体が待機しています。
控室１ 「A[0-0]」「B[1-1]」
控室２ 「AB[0-1]」
この時点でRootに到達したマッチは以下の通りです。
１回ループ：「A[0-0]」「B[1-1]」
２回ループ：「AB[0-1]」
ループマッチャーの控室１に「A[0-0]」が居座っています。
「A[0-0]」はもう誰とも合体せずに消滅を待つだけです。
「A[0-0]」は後続するはずの「?[1-?]」が一つも存在しない事が確認され次第、自動的に破棄されます。
C
インデックス２Cを入力してみましょう。
末端マッチから発生した「C[2-2]」がループマッチャーにたどり着きます。
「C[2-2]」は次の３個体に分身します。
誰とも合体せず「C[2-2]」のままで居る個体。
「B[1-1]」の分身体と合体して「BC[1-2]となる個体。
「AB[0-1]」の分身体と合体して「ABC[0-2]」となる個体。
「C[2-2]」は更に２個体に分身します。
最低回数以上(１回)なのでループマッチャーから旅立ってRootに到達する個体。
最高回数未満(１回)なのでループマッチャー上で後続を待つ個体。
「BC[1-2]も更に２個体に分身します。
最低回数以上(２回)なのでループマッチャーから旅立ってRootに到達する個体。
最高回数未満(２回)なのでループマッチャー上で後続を待つ個体。
「ABC[0-2]」も更に２個体に分身…しません。
「ABC[0-2]」はループ回数の上限である３回に達しています。
もうループマッチャー上で後続を待つ選択肢はありません。
最低回数以上(３回)なのでループマッチャーから旅立ってRootに到達するだけです。
この時点でループマッチャー上には以下の個体が待機しています。
控室１ 「A[0-0]」「B[1-1]」「C[2-2]」
控室２ 「AB[0-1]」「BC[1-2]
この時点でRootに到達したマッチは以下の通りです。
１回ループ：「A[0-0]」「B[1-1]」「C[2-2]」
２回ループ：「AB[0-1]」「BC[1-2]
３回ループ：「ABC[0-2]」
発生した全てのマッチが停止したので、インデックス２Cの処理はここまでです。
D
インデックス３Dを入力してみましょう。
末端マッチから発生した「D[3-3]」がループマッチャーにたどり着きます。
「D[3-3]」は次の３個体に分身します。
誰とも合体せず「D[3-3]」のままで居る個体。
「C[2-2]」の分身体と合体して「CD[2-3]」となる個体。
「BC[1-2]の分身体と合体して「BCD[1-3]となる個体。
「D[3-3]」は更に２個体に分身します。
最低回数以上(１回)なのでループマッチャーから旅立ってRootに到達する個体。
最高回数未満(１回)なのでループマッチャー上で後続を待つ個体。
「CD[2-3]」も更に２個体に分身します。
最低回数以上(２回)なのでループマッチャーから旅立ってRootに到達する個体。
最高回数未満(２回)なのでループマッチャー上で後続を待つ個体。
「BCD[1-3]も更に２個体に分身…しません。
「BCD[1-3]はループ回数の上限である３回に達しています。
もうループマッチャー上で後続を待つ選択肢はありません。
最低回数以上(３回)なのでループマッチャーから旅立ってRootに到達するだけです。
この時点でループマッチャー上には以下の個体が待機しています。
控室１ 「A[0-0]」「B[1-1]」「C[2-2]」「D[3-3]」
控室２ 「AB[0-1]」「BC[1-2]「CD[2-3]」
この時点でRootに到達したマッチは以下の通りです。
１回ループ：「A[0-0]」「B[1-1]」「C[2-2]」「D[3-3]」
２回ループ：「AB[0-1]」「BC[1-2]「CD[2-3]」
３回ループ：「ABC[0-2]」「BCD[1-3]
発生した全てのマッチが停止したので、インデックス３Dの処理はここまでです。
ループマッチャーのまとめ
最低回数以上かつ最高回数以下の全てがマッチとしてみなされます。
最高回数に達した時点でそれ以上の待機を禁じる事で、最高回数を超えるマッチを生成させません。
最低回数がゼロ回だと話が変わってくる
最低回数がゼロ回以上の場合の動作を解説します。
例として'A'.To('Z').Times(0,3)というマッチャーに"ABCD"という文字列を与えた際の挙動を見てみます。
先の'A'.To('Z').Times(1,3)とは最低回数がゼロ回という点以外全て同じです。
最初の文字より前からマッチングは始まっている
今回のループマッチャーは回数指定の最小回数がゼロ回です。
文字を与える前に「長さゼロの文字列にマッチした」と扱う必要があります。
ループマッチャーが文字インデックスが０の位置で長さゼロのマッチを発生させます。
これを「""[0]」と呼ぶ事にします。
長さゼロのマッチは、マッチャーの木に含まれる「最低回数ゼロ回のループマッチャー」全てから発生します。
""._()のように長さゼロの文字列から作ったマッチャーも同じ扱いとなります。
また、後で説明する「単語区切りマッチャー」からも発生します。
今回発生した長さゼロのマッチは、それを発生させたループマッチャー自身にはとどまりません。
長さゼロのマッチは、ゼロ回に一致した結果のマッチなのです。
生まれた瞬間から旅立つ運命です。
ループマッチャーから発生した 「""[0]」はRootに登っていき、Root内部の控室に収まります。
この時点でループマッチャーの控室は空っぽです。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」
A
インデックス０Aを入力してみましょう。
…実は、入力文字を与えた際の動作は最低回数１回以上の時と動作は同じなので省略します。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」
１回ループ：(前回と同じ)
Bの前に
次の文字の前にループマッチャーから長さゼロのマッチが発生します。
今回はインデックス１の前に発生したマッチなので「""[1]」と呼びます。
もちろん「""[1]」はRootに到達します。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」「""[1]」
１回ループ：(前回と同じ)
B
インデックス１Bを入力して…以下省略。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」「""[1]」
１回ループ：(前回と同じ)
２回ループ：(前回と同じ)
Cの前に
次の文字の前にループマッチャーから長さゼロのマッチが発生します。
今回はインデックス２の前に発生したマッチなので「""[2]」と呼びます。
もちろん「""[2]」はRootに到達します。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」「""[1]」「""[2]」
１回ループ：(前回と同じ)
２回ループ：(前回と同じ)
C
インデックス２Cを…以下省略。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」「""[1]」「""[2]」
１回ループ：(前回と同じ)
２回ループ：(前回と同じ)
３回ループ：(前回と同じ)
Dの前に
そろそろお察しの通りループマッチャーから発生した「""[3]」がRootに到達します。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」「""[1]」「""[2]」「""[3]」
１回ループ：(前回と同じ)
２回ループ：(前回と同じ)
３回ループ：(前回と同じ)
D
インデックス３Dを…以下省略。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」「""[1]」「""[2]」「""[3]」
１回ループ：(前回と同じ)
２回ループ：(前回と同じ)
３回ループ：(前回と同じ)
最終文字入力後
実は最終文字入力後にもループマッチャーから長さゼロのマッチが発生します。
ループマッチャーから発生した「""[4]」がRootに到達します。
この時点でRootに到達したマッチは以下の通りです。
０回ループ：「""[0]」「""[1]」「""[2]」「""[3]」「""[4]」
１回ループ：(前回と同じ)
２回ループ：(前回と同じ)
３回ループ：(前回と同じ)
長さゼロのマッチのまとめ
長さゼロのマッチは入力文字と一致して発生するのではなく、入力文字を消費せずに発生します。
LIMEのマッチング処理には入力文字を与えるフェイズとは別に、長さゼロのマッチを発生させるフェイズが存在します。
長さゼロのマッチには以下の４種類があります。
ゼロ回マッチ(先程説明したもの)
単語区切りマッチ(単語用文字と非単語用文字の境界で発生する)
文字列先頭マッチ(マッチング処理の最初に発生する)
文字列末尾マッチ(マッチング処理の最後に発生する)
これらの長さゼロマッチと、入力文字で発生する１文字マッチが末端マッチの全てです。
以下が末端マッチの発生するタイミングの全てです
文字列先頭判定(「文字列先頭マッチ」が発生)
↓
インデックス０入力前(「ゼロ回マッチ」・「単語区切りマッチ」が発生)
↓
インデックス０入力(「１文字マッチ」が発生)
↓
インデックス１入力前(「ゼロ回マッチ」・「単語区切りマッチ」が発生)
↓
インデックス１入力(「１文字マッチ」が発生)
↓
インデックス２入力前(「ゼロ回マッチ」・「単語区切りマッチ」が発生)
↓
インデックス２入力(「１文字マッチ」が発生)
↓
(省略)
↓
インデックス最終入力前(「ゼロ回マッチ」・「単語区切りマッチ」が発生)
↓
インデックス最終入力(「１文字マッチ」が発生)
↓
インデックス最終入力後(「ゼロ回マッチ」・「単語区切りマッチ」が発生)
↓
文字列末尾判定(「文字列末尾マッチ」が発生)
それぞれのタイミングで発生した末端マッチがマッチャーの木を登りながら合体を繰り返し、
Rootまでたどり着けたらそれがマッチング結果のマッチです。
複数の結果からどれを選べば良いのか？
正規表現のデフォルト動作に倣うなら、開始位置が最も先頭に近く、その内で最も長いマッチを選ぶ事になります。
LIMEのバージョンアップ予定
記事執筆時の実装ではデバッグのし易さを優先して文字列の入力にのみマッチングを行う仕様ですが、
いずれは IEnumerable を入力として受け入れる仕様に改造する予定です。
入力を string ではなく IEnumerable として受け入れているのも、後の改造を見越しての仕様です。
IEnumerable を入力できるようになれば逆コンパイラの実装さえ可能になります。
次回予告
次回よりLIME実践編としてトランスコンパイラの実装に挑戦します。
言語は完全新作の筆者独自言語となります。