小宮が開発しているソフトについて書いています。
構文木を使って照合するバージョンを引き続き作業中。今のところ順調。
実は、今のバージョンを作っていて、鬼車やPCREがやっていることの意味がようやくわかりました。
この構文木からバイトコードを作って、仮想マシンに実行させれば私のマクロと同じだ！と一人で感動していたら腑に落ちたのです。
そうか、鬼車やPCRも仮想マシンで動いていたんだ・・・と、今頃やっと理解できました。
「正規表現を実装するにはＮＦＡを使わなければならない」と、かたくなに思い込んでいたためにずいぶん回り道をしたものです。
だから、鬼車のソースを見て「どこでNFAを作っているの？」とありもしないものを探してパニックになって、それで理解できなかったんです。
何か、霧がすっきり晴れた感じです。
とは言っても、仮想マシンバージョンは別な機会にして、取り敢えず、構文木で照合するバージョンの公開を目指して作業します。
少し時間がかかりましたが戻り読みの実装も完了しました。
まだテストは不十分ですが（いろいろなケースで試さないとダメなので）、カンタンな正規表現は普通に動いています。
後実装できてない正規表現は、^ と $ です。
行頭一致と行末一致ですね。実はコレ、見た目ほど実装するのはカンタンじゃないんです。
^a
コレなら話はカンタンですが次のように書かれることがあります。
a|^z
0.9.3では、NFAを生成する段階で ^ や $ が普通の文字かメタ文字かを判断しています。
構文解析だけだと、どこでどうやればいいのか、今悩んでいます。
完全に製作途中ですが、現在のソースはこちらです。興味のある方はどうぞ。
従来のソースからNFAに関するものがなくなり、マッチの中心はTREBinCode.IsEqualになりました。
前より美しいでしょ？
TREBinCodeクラスに、今までなかったIsEqual関数を追加しました。その中にcase文で書いています。
もともとTRECodeの子供なのであって当然です。
今までなかった理由は、TREBinCodeはNFAを作った後は単に破棄していたためです。
構文木を作るためにしか使っていなかったのです。
今考えると何てもったいないことをと思います。
ちなみに、現時点では以下のような感じ。そのままコードを載せて置きます。ちゃんと見えなかったらごめんなさい。
function TREBinCode.IsEqual(var AStr: PWideChar): Boolean;
var
SaveP, SubP: PWideChar;
AMatchKind: TRELoopMatchKind;
I, AMin, AMax: Integer;
begin
case FOp of
opEmply:
Result := True;
opConcat:
begin
SaveP := AStr;
if FLeft.IsEqual(AStr) and FRight.IsEqual(AStr) then
Result := True
else
begin
AStr := SaveP;
Result := False;
end;
end;
opUnion:
begin
SaveP := AStr;
Result := FLeft.IsEqual(AStr);
if not Result then
begin
AStr := SaveP;
Result := FRight.IsEqual(AStr);
end;
if not Result then
begin
AStr := SaveP;
Result := False;
end;
end;
opLoop:
begin
Result := False;
SaveP := AStr;
AMatchKind := FMatchKind;
AMin := FMin;
AMax := FMax;
// Min一致
if AMin > 0 then
begin
for I := 1 to AMin do
if not FLeft.IsEqual(AStr) then
Exit;
// {n}ならばバックトラックの必要がないので真を返す
if (AMin = AMax) then
begin
Result := True;
Exit;
end;
if (AMatchKind = lmMin) then
begin
Result := FRight.IsEqual(AStr);
if Result then
Exit;
end;
// 最小値が指定されているときは、PrevPを現在位置に設定
SaveP := AStr;
end
else
begin
// 最小値が0ならばマッチ成功
if AMatchKind = lmMin then
begin
Result := FRight.IsEqual(AStr);
if Result then
Exit;
end;
end;
I := AMin;
repeat
if (AMatchKind = lmMin) then
begin
Result := FRight.IsEqual(AStr);
if Result then
Exit;
end;
if not FLeft.IsEqual(AStr) then
Break;
Inc(I);
until (I = AMax);
if (AMatchKind lmMax) and not FNoBackTrack then
begin
Result := FRight.IsEqual(AStr);
while (not Result) and (AStr > SaveP) do
begin
Dec(AStr);
FRegExp.FMatchData.Back;
SubP := AStr;
Result := FRight.IsEqual(AStr);
if not Result then
AStr := SubP;
end;
if not Result then
AStr := SaveP;
end
else
Result := True;
end;
opLHead:
;
opLTail:
;
opGroup:
begin
SaveP := AStr;
Result := FLeft.IsEqual(AStr);
if Result then
begin
FRegExp.FMatchData.StartP[FGroupIndex] := SaveP;
FRegExp.FMatchData.EndP[FGroupIndex] := AStr;
end
else
AStr := SaveP;
end;
opGroupCall:
;
opAheadMatch:
begin
SaveP := AStr;
Result := FLeft.IsEqual(AStr);
AStr := SaveP;
end;
opAheadNoMatch:
begin
SaveP := AStr;
Result := not FLeft.IsEqual(AStr);
AStr := SaveP;
end;
opBehindMatch:
;
opBehindNoMatch:
;
opNoBackTrack:
;
end;
end;
ループの部分は、TSkREgExp.MatchPrim関数のコードをほぼそのまま持ってきました。
美しいと思いませんか？ 0.9.3と比べて。
すいません、今完全にハイになっています。
グループ、先読み、否定先読みの実装が完了。
正直言って、NFAで実装するよりずっとカンタンに書ける。
アイデアにキー入力が追いつかない。ただ今絶好調！
気のせいかコードも美しく見える。
今のNFAの照合はトリッキーだと思うし。
思ったより早く形になりそうです。形になったらベータ版としてさらします。
構文木で照合するメリットは、コンパイラの最適化の手法が使えそうなことです。
ぶっちゃけ、NFAはどうやって最適化すればいいのかよくわからなかったのですが、コンパイラの最適化の方法なら良書がたくさんありますからね。
取り敢えず、中田育夫先生の本を注文しました。
直前の投稿は予約投稿の日付を間違えていますが、この投稿はほぼリアルタイムで書いています。
構文木をそのまま照合に使うアイデアですが、もっともカンタンな実装（選択、繰り返し、連結）では問題なく動きました。
本当に、何でNFAを作ったんだろう？
SkRegExpに再帰を実装すべくいじっていますが、「何でこんなコードなんだ？」と思うものをたくさん見つけました。
1年以上放置しているので、どうしてそのような実装をしたのかよく覚えていません。
その中でも最大のものが「なぜ、構文木からNFAを作っているのか？」です。
構文木を完全な再帰下降で作れば、NFAを作らなくてもそのまま照合を実行できるんじゃないかと思ったのです。
構文解析しながらオブジェクトを作っているので、構文木そのものが何をすべきか知っていると思うのです。
これがオブジェクト指向ってヤツですよね。
構文解析の手法は拙作の返信屋2007のマクロで使った方法を流用したものです。
この方法は中田育夫先生の著書を参考に作ったと思います。
返信屋2007のマクロは構文木をそのまま実行しています。
それなのに、なぜ、SkRegExpはそうしなかったのかわからないのです。
正規表現とプログラム言語風のマクロ、何が違うのか？と思うのです。
どうしても気になって仕方ありません。気になるとやらずにはいられない性分です。
構文木をそのまま実行するというアイデアに魅力を感じてしまって他のことには手が付かない状態です。
なので、すいませんがSkRegExpの再帰サポートは放り出します。
実は、既に昨日から構文木をそのまま実行するアイデアを実装してます。こっちの方が楽しいです。
再帰をサポートしたバージョンを公開しようと作業を続けています。
テスト用データで動作チェックしていますが、再帰がうまく動かないケースがあって、この2日間苦しんでいます。
具体的には次のような正規表現です。
(?|(g))+$
この正規表現は”()(())”にマッチするんですが、現状マッチできません。
今日、分岐｜に問題がありそうだとわかりました。
でも、他の分岐｜を使った正規表現では問題ないので、どう手を加えたらいいか悩んでいます。
って書いていたら、一つひらめきました。明日試してみます。
書くって大切なんですね。
ネストレベル付き後方参照に時間がかかりそうです。
時間がかかると開発へのモチベーションが落ちてしまうかもしれません。
そこで、再帰をサポートしたバージョンを先行公開することにしました。
ネストレベル付き後方参照ができなくても、再帰ができれば対応するカッコの検索などには使えます。
それなりの用途はあると思います。
公開予定は2月6日で作業を進めて行きます。
ちなみに、再帰を実現するグループ呼び出しのメタ文字はPHP5（鬼車）と同じ g にしました。Perlのヤツはイマイチに感じるので。
鬼車で言うところのネストレベル付き後方参照を導入すべく作業中。
パーサーの対応はすぐに終了。でも、どう実現するかで迷ったまま今日の作業は終わり。
今考えているのは次のような感じ。
if NFACode.Recursion then FMatchData.push; //再帰呼び出し if NFACode.Recursion then FMatchData.pop;
マッチデータ丸ごとスタックに退避させて再帰を処理するのが一番楽に実装できる。
でも、マッチデータ丸ごとだとメモリの無駄遣いかな？
ネストレベル参照するグループはパースの段階でわかるから、それだけ別に処理すべきかな？
でも、そうするとTREMatchDataに手を加えないとダメだし。
これだとテストが面倒くさそうだなあ。
どうしようか考え中。
でも、考えすぎて作業がとまってしまうのだけは避けたいと思っている。