TPerlRegEx - stack overflow

[MaBuSE]

Zitat von liftoff:

Code:

...
    re.RegEx := '({4:\r\n(?:[^\r\n]*\r\n)*-})';

Hallo,
ich habe mit meinen RegEx Experten gesprochen.

Er sagt, Deine RegEx sieht so aus, als hättest Du den Unterschied zwischen greedy und non-greedy nicht richtig verstanden, als Du diese Expression erstellt hast. Es sieht so aus, als wolltest Du das non-greedy manuell erzwingen. Das macht die RegEx nur unnötig kompliziert.

Folgende Expression würde alles zwischen dem '{4:' und '-}' auswählen. Mit der non-greedy Option '?' die nach dem Wildcard '*' steht, wird das Ergebnis möglichst kurz gehalten.

Code:

...
    re.RegEx := '(\{4\:.*?-\})';
...

'{4: bla bla bla bla -}{4: bla bla -}'

-> '{4: bla bla bla bla -}' wird ausgewählt

Code:

...
    re.RegEx := '(\{4\:.*-\})'; // ohne ? -> greedy
...

ohne ? -> greedy wird folgendes ausgewählt:

'{4: bla bla bla bla -}{4: bla bla -}'

Durch die Vereinfachung der RegEx ist es nicht nur einfacher zu lesen sondern es werden auch weniger rekursive Aufrufe nötig, also auch der Stack weniger beansprucht
Ich hoffe das hilft Dir weiter.

cu
MaBuSE

[edit]
Obiges Beispiel funktioniert natürlich nur wenn die SingleLine Option aktiv ist. Nur dann steht der '.' auch für ein '/n'.

Delphi-Quellcode:

...
//    re.Options := [preCaseLess, preSingleLine];
//    re.RegEx := '(\{4\:.*?-\})';

    // alternativ kann man die Optionen auch in die RegEx schreiben: 
    // '?' -> jetzt kommen Optionen -> 's' = SingleLine ; 'i' = CaseLess -> ':' = Optionen Ende
    re.Options := [];
    re.RegEx := '(?si:\{4\:.*?-\})';
...

Habe ich ausprobiert funktioniert.
[/edit]

[edit] Beispiel:

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

uses
  RegularExpressionsCore;

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var re : TPerlRegEx;
    teststr : UTF8String;
    l1 : integer;
begin
  try
    re := TPerlRegEx.create;
    re.State := [];
    re.Options := [];
    re.RegEx := '(?si:\{4\:.*?-\})';
    re.Compile;

    //    Nun Beispielstring mit Inhalt
    //    {4:
    //    :00X:ABCDEFB0123456789
    //    :00X:ABCDEFB0123456789
    //    -}
    //    ...
    //    {4:
    //    :00X:ABCDEFB0123456789
    //    :00X:ABCDEFB0123456789
    //    -}
    //    zusammenbauen

    TestStr := '{4:'+chr(13)+chr(10);
    for l1 := 1 to 2 do
    begin
      TestStr := TestStr + ':00X:ABCDEFB0123456789' +chr(13)+chr(10);
    end;
    TestStr := TestStr + '-}';
    TestStr := TestStr + TestStr + TestStr + TestStr;

    re.Subject := TestStr;

    if re.Match then
    begin
      Memo1.Lines.Add(re.MatchedText);
      Memo1.Lines.Add('-------------------');

      while re.MatchAgain do
      begin
        Memo1.Lines.Add(re.MatchedText);
        Memo1.Lines.Add('-------------------');
      end;
    end
    else
    begin
      Memo1.Lines.Add('Kein Treffer')
    end;

  except
    on E: Exception do
      Memo1.Lines.Add(E.ClassName+ ': '+ E.Message);
  end;
end;

end.

[/edit]

[liftoff]

Wow. Danke fur die ausführliche Untersuchung.
Ich möchte, dass sich das nur matcht, wenn die unter #11 beschriebenen Kriterien zutreffen.
Also nach {4: ein Umbruch, danach Zeilen mit Egal plus Umbruch und danach eine letzte Zeile mit einem -} am Anfang.

So ganz habe ich aber in der Tat den Zusammenhang mit dem Stack noch nicht ergründen können.

[MaBuSE]

Zitat von liftoff:

Wow. Danke fur die ausführliche Untersuchung.

Gern geschehen. Übrigens willkommen in der DP

Zitat von liftoff:

Ich möchte, dass sich das nur matcht, wenn die unter #11 beschriebenen Kriterien zutreffen.
Also nach {4: ein Umbruch, danach Zeilen mit Egal plus Umbruch und danach eine letzte Zeile mit einem -} am Anfang.

Dann solltest Du noch zusätzlich je einen Zeilenumbruch einfügen '/n'. re.RegEx := '(\{4\:/n.*?/n-\})';

Zitat von liftoff:

So ganz habe ich aber in der Tat den Zusammenhang mit dem Stack noch nicht ergründen können.

Im Wesentlichen wird zwischen HEAP und STACK unterschieden. Auf Daten die auf den Stack gelegt werden kann man relativ schnell zugreifen, dafür ist die Stackgröße beschränkt. Auf Daten im Heap kann langsamer zugegriffen werden, dafür ist im Heap viel mehr Platz.

Parameter von Prozeduren und Funktionen werden auf dem Stack gespeichertund nach dem Ende der Funktion wieder freigegeben.
Bei einer Rekursion ruft sich eine Funktion selbst auf. Wenn eine Funktion sich z.B. 100 mal aufruft, dann wird auch 100 mal Stack für Parameter benötigt.

Ich hoffe das hilft Dir weiter.

[liftoff]

Nene. Stack und Heap, hab ich lieb. Damit kenne ich mich schon aus.

Nur den Zusammenhang zwischen greedy und lazy im Zusammenhang mit dem PCRE-Stack hab ich nicht verstanden.

Hier ein glaube ich altes Beispiel.

banane

b(an)+ liefert 'banan'

b(an)+? liefert der Faulheit wegen nur noch 'ban'

Hänge ich dem Ausdruck ein e an

b(an)+?e

liefert das 'banane'. Er ackert also den Match mit (an)+? zwei Mal durch.

Genauso verhält es sich mit meinem Ausdruck ganz oben. Nur statt 'an' eben einzelne Zeilen mit einem Umbruch am Ende.

Wieso liefert greedy einen stack overflow und lazy keinen. Die X Zeilen muss er in beiden Fällen durchlaufen.

Meinste statt /n vielleicht nicht eher \n ?
Statt \n nehme ich \r\n, also einen Windows-Umbruch #13#10.

[MaBuSE]

Zitat von liftoff:

Wieso liefert greedy einen stack overflow und lazy keinen. Die X Zeilen muss er in beiden Fällen durchlaufen.

Sorry, hab dich falsch verstanden.
In Deiner XE Ent. Version sind ja alle Quelltexte enthalten.
IN Projektoptionen Debug-DCUs anschalten und einfach mal in die Match Methode reindebuggen

Zitat von liftoff:

Meinste statt /n vielleicht nicht eher \n ?
Statt \n nehme ich \r\n, also einen Windows-Umbruch #13#10.

Stimmt

[Uwe Raabe]

Zitat von MaBuSE:

In Deiner XE Ent. Version sind ja alle Quelltexte enthalten.
IN Projektoptionen Debug-DCUs anschalten und einfach mal in die Match Methode reindebuggen

Die PCRE-Implementation liegt zwar als C-Source vor, wird aber von Delphi als vorcompilierte OBJ-Dateien (ohne Debug-Info) eingelinkt. Leider gestaltet sich das Debuggen so etwas schwieriger als gewohnt.