ごく普通のNFAバックトラック

照合用に以下のようなループを作ってみました。

バックトラックによるごく普通のNFAエンジンです。たぶん、このループなら再帰は起こらないのではないかと考えています。

function TREMatchEngine.MatchCore(var AStr: PWideChar): Boolean;
var
  Len: Integer;
  NFACode, SubCode: TRENFACode;
begin
  Result := False;
  FNFAStack.Clear;
  FPtrStack.Clear;
  FRegExp.FMatchData.StartP[0] := AStr;
  NFACode := FStateList[FEntryState];

  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
                  Push(SubCode, AStr);
                  NFACode := NFACode.Next;
                end;
              lmMin:
                begin
                  Push(NFACode, AStr);
                  NFACode := SubCode;
                end;
            else
              NFACode := SubCode.Next;
            end;
          end;
        nkQuest:
          begin
            case NFACode.MatchKind of
              lmNormal:
                begin
                  Push(NFACode, AStr);
                  NFACode := NFACode.Next;
                end;
              lmMin:
                Push(NFACode.Next, AStr);
            else
            end;
            SubCode := FStateList[NFACode.TransitTo];
          end;
      else
        Push(NFACode.Next, AStr);
      end;
    end;
    case NFACode.Kind of
      nkNormal, nkChar:
        begin
          if NFACode.Code.IsEqual(AStr, Len) then
          begin
            NFACode := FStateList[NFACode.TransitTo];
            Inc(AStr);
          end
          else
            NFACode := nil;
        end;
      nkEmpty:
        begin
          NFACode := FStateList[NFACode.TransitTo];
        end;
      nkEnd:
        begin
          FRegExp.FMatchData.EndP[0] := AStr;
          Result := True;
          Exit;
        end;
      nkGroupStart:
        NFACode := MatchGroup(NFACode, AStr);
    end;
    if NFACode = nil then
      Pop(NFACode, AStr);
  end;
end;

x{n,m} の正規表現をどう実現しようか悩んでいますが、この方が格段にわかりやすいループになりますね。

コメントを残す

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