2月15日の照合ループ

今日の照合ループは以下の通り。

function TREMatchEngine.MatchCore(var NFACode: TRENFACode; var AStr: PWideChar): Boolean;
var
  NFAStack, StrStack: TList;

  procedure CreateStack;
  begin
    NFAStack := TList.Create;
    StrStack := TList.Create;
  end;

  procedure DestroyStack;
  begin
    NFAStack.Free;
    StrStack.Free;
  end;

  procedure Push(NFACode: TRENFACode; AStr: PWideChar);
  begin
    NFAStack.Add(NFACode);
    StrStack.Add(AStr);
  end;

  procedure Pop(var NFACode: TRENFACode; var AStr: PWideChar);
  var
    Index: Integer;
  begin
    Index := NFAStack.Count - 1;
    if Index = -1 then
      Exit;

    NFACode := NFAStack[Index];
    NFAStack.Delete(Index);
    AStr := StrStack[Index];
    StrStack.Delete(Index);
  end;

  function SkipNext(NFACode: TRENFACode): TRENFACode;
  begin
    while (NFACode <> nil) and (NFACode.Kind in [nkEmpty, nkGroupEnd, nkStar, nkQuest, nkAheadNoMatch]) do
      NFACode := FStateList[NFACode.TransitTo];

    Result := NFACode;
  end;

var
  Len: Integer;
  SubCode: TRENFACode;
  SubP: PWideChar;
begin
  CreateStack;
  try
    Result := False;
    while NFACode <> nil do
    begin
      if NFACode.Next <> nil then
      begin
        case NFACode.Kind of
          nkStar:
          begin
            SubCode := FStateList[NFACode.TransitTo];
            case NFACode.MatchKind of
              lmNormal:
              begin
                SubCode := SkipNext(SubCode);
                Push(SubCode, AStr);
                NFACode := NFACode.Next;
              end;
              lmMin:
              begin
                Push(SkipNext(NFACode.Next), AStr);
                NFACode := SubCode;
              end;
              else
                NFACode := SubCode.Next;
            end;
          end;
          nkQuest:
          begin
            case NFACode.MatchKind of
              lmNormal:
              begin
                SubCode := SkipNext(NFACode);
                Push(SubCode, AStr);
                NFACode := NFACode.Next;
              end;
             lmMin:
             begin
               SubCode := SkipNext(NFACode.Next);
               Push(SubCode, AStr);
               NFACode := FStateList[NFACode.TransitTo];
             end;
             else
               NFACode := NFACode.Next;
           end;
         end;
         nkAheadNoMatch, nkBehindNoMatch:
         begin
           SubCode := SkipNext(NFACode.Next);
           Push(SubCode, AStr);
         end;
         else
         begin
           SubCode := SkipNext(NFACode.Next);
           Push(SubCode, AStr);
         end;
       end;
     end;

   case NFACode.Kind of
     nkNormal, nkChar:
     begin
       if NFACode.Code.IsEqual(AStr, Len) then
       begin
         NFACode := FStateList[NFACode.TransitTo];
         Inc(AStr, Len);
       end
       else
         NFACode := nil;
     end;
     nkEmpty:
     begin
       NFACode := FStateList[NFACode.TransitTo];
     end;
     nkEnd:
     begin
       FRegExp.FMatchData.EndP[0] := AStr;
       Result := True;
       Exit;
     end;
     nkMatchEnd, nkNoBackTrackEnd:
     begin
       NFACode := FStateList[NFACode.TransitTo];
       Result := True;
       Exit;
     end;
     nkGroupStart:
     begin
       FRegExp.FMatchData.StartP[NFACode.GroupIndex] := AStr;
       NFACode := FStateList[NFACode.TransitTo];
     end;
     nkGroupEnd:
     begin
       FRegExp.FMatchData.EndP[NFACode.GroupIndex] := AStr;
       NFACode := FStateList[NFACode.TransitTo];
     end;
     nkNoBackTrackBegin:
     begin
       NFACode := FStateList[NFACode.TransitTo];
       if not MatchCore(NFACode, AStr) then
       begin
         Result := False;
         Exit;
      end;
    end;
    nkAheadMatch:
    begin
      SubP := AStr;
      NFACode := FStateList[NFACode.TransitTo];
      if not MatchCore(NFACode, SubP) then
      begin
        Result := False;
        Exit;
      end;
    end;
    nkAheadNoMatch:
    begin
      SubP := AStr;
      NFACode := FStateList[NFACode.TransitTo];
      if MatchCore(NFACode, SubP) then
      begin
        Result := False;
        Exit;
      end;
    end;
    nkBehindMatch:
    begin
      SubP := AStr;
      Len := NFACode.Max;
      NFACode := FStateList[NFACode.TransitTo];
      if FRegExp.FTextTopP <= (SubP - Len) then
      begin
        FRegExp.CharPrev(SubP, Len);
        if not MatchCore(NFACode, SubP) then
        begin
          Result := False;
          Exit;
        end;
      end
      else
      begin
        Result := False;
        Exit;
      end;
    end;
    nkBehindNoMatch:
    begin
       SubP := AStr;
       Len := NFACode.Max;
       NFACode := FStateList[NFACode.TransitTo];
       if FRegExp.FTextTopP <> AStr then
         FRegExp.FMatchData.Back(SubP - AStr);
      end;
    end;
  finally
    DestroyStack;
  end;
end;

戻り読みの実装を完了。

SkRegExp 0.9.3 にあって実装してない正規表現は x{n, m} だけ。

難しくはないのだが、どう実装するかでちょっと悩んでいる。

そこができたら TREMatchData クラスを手直ししてテストプログラムを通ったら公開するつもり。

動かないものは修正できないからね。

公開後に、再帰の実装などの新たな正規表現の追加をしたい。

最適化もやっておかなければ。

コメントを残す

メールアドレスが公開されることはありません。