Buggy `re`-Engine

[poker]

Hallo Python-Gemeinschaft

Mir ist heute nachmittag etwas eigenartiges aufgefallen
Kann es sein, das die `re`-Engine ein wenig "Buggy" ist?

Code: Alles auswählen

In [1]: import re
In [2]: m = re.search(r'(\*)\s*(?:([0-9]+)(\s*))*(\\\*)', "* 100 1 5 \*")
In [3]: m.group()
Out[3]: '* 100 1 5 \\*'
In [4]: m.groups()
Out[4]: ('*', '5', ' ', '\\*')

Wie man sieht, fällt die Gruppierung nicht wirklich exakt aus. Alle submatches des Ausdrucks

Code: Alles auswählen

(?:([0-9]+)(\s*))*

werden nicht in die Gruppierung übernommen, sondern lediglich der letzte. Erwartet hätte ich ein tuple in tuple zwischen ``*`` und ``\*':

Code: Alles auswählen

('*', ('100', ' ', '1', ' ', '5', ' '), '\\*')

oder noch besser sowas (was komplizierter zu realisieren ist...):

Code: Alles auswählen

('*', (('100', ' '), ('1', ' '), ('5', ' ')), '\\*')

Für komplexere Ausdrücke ist ``re`` dadurch nicht wirklich geeignet.

Ich weiß ja nicht wie _sre.c
genau Arbeitet, aber zumindestens die erste Form ist total trivial zu realisieren! Weiß einer genaueres weshalb das nicht implementiert wurde (Eventuell kein Bedarf?).



Was meint ihr dazu? Wäre es was für ein improved-Ticket?

mfg

P.S.: Bevor gleich einige anfangen mit alternativen Scripts für das Problem anzukommen: Ja ich weiß, das sich das oben auch anderes realisieren ließe:

Code: Alles auswählen

In [14]: m = re.search(r'(\*)\s*([0-9 ]+)(\\\*)', "* 100 1 5 \*")
In [15]: for subm in re.finditer(r'([0-9]+)(\s*)', m.groups()[1]):
   ....:         print subm.groups()
   ....:
('100', ' ')
('1', ' ')
('5', ' ')

Das ist aber nicht das Topic, sondern nur allgemein das geschilderte Problem.

[mitsuhiko]

Erstens ist das genau das Verhalten, dass man sich von re erwartet. Mir wäre jetzt auch keine Engine bekannt, die das anders löst. Und zweitens ist sre unmaintained, das heißt Ticket erstellen wird kaum was bringen.

[Michael Schneider]

Wie man sieht, fällt die Gruppierung nicht wirklich exakt aus. Alle submatches des Ausdrucks

Code: Alles auswählen

(?:([0-9]+)(\s*))*

werden nicht in die Gruppierung übernommen

Hi Poker,

also meine Doku besagt, dass "(?:" bedeutet: die folgende Gruppierung ist vom Ergebnis explizit auszuschließen!
Wenn Du die Gruppierung im Ergebnis haben willst, benutze die Klammern ohne "?:".

Grüße,
Michel

[birkenfeld]

Kann es sein, das die `re`-Engine ein wenig "Buggy" ist?

Nein. Das Verhalten ist konsistent mit jeder anderen RE-Engine, die ich kenne.

Für komplexere Ausdrücke ist ``re`` dadurch nicht wirklich geeignet.

Für richtig komplexe Ausdrücke kannst du mit REs eh nichts anfangen.

Ich weiß ja nicht wie _sre.c
genau Arbeitet, aber zumindestens die erste Form ist total trivial zu realisieren!

Ein Patch wird immer gern gesehen.

Weiß einer genaueres weshalb das nicht implementiert wurde (Eventuell kein Bedarf?).

Weil es, wie gesagt, schon immer so implementiert wurde.

[Leonidas]

Und zweitens ist sre unmaintained, das heißt Ticket erstellen wird kaum was bringen.

Was? Effbot hat die fallen gelassen? Und wie wird das in Zukunft ablaufen?

[birkenfeld]

Unmaintained ist falsch. sre ist genauso maintained wie alle anderen Libraries, die nicht speziell von einer Person gepflegt werden.

[HWK]

Wie man sieht, fällt die Gruppierung nicht wirklich exakt aus. Alle submatches des Ausdrucks

Code: Alles auswählen

(?:([0-9]+)(\s*))*

werden nicht in die Gruppierung übernommen

Hi Poker,

also meine Doku besagt, dass "(?:" bedeutet: die folgende Gruppierung ist vom Ergebnis explizit auszuschließen!
Wenn Du die Gruppierung im Ergebnis haben willst, benutze die Klammern ohne "?:".

Grüße,
Michel

Code: Alles auswählen

>>> import re
>>> m = re.search(r'(\*)\s*(([0-9]+)(\s*))*(\\\*)', "* 100 1 5 \*")
>>> m.group()
'* 100 1 5 \\*'
>>> m.groups()
('*', '5 ', '5', ' ', '\\*')

Das ist nicht wirklich, was er haben will.
MfG
HWK

[poker]

Hallo birkenfeld und blackbird,

Dass das von mir erwartete in sofern konsistent ist wie in jeder anderen RE-Engine (Kenne perl, grep, ein wenig ruby) ist mir bewusst, aber diese Engines (bis auf die von ruby) geben auch kein match-object mit Zugriff auf Groups zurück. Da ich die Python RE-Engine von den Möglichkeiten her für sehr ausgereift halte (Umfang, Mehrere Arten zu gruppieren => (...), (?:...), (?P<name>...)), hielt ich das für selbstverständlich.

Hi Poker,

also meine Doku besagt, dass "(?:" bedeutet: die folgende Gruppierung ist vom Ergebnis explizit auszuschließen!
Wenn Du die Gruppierung im Ergebnis haben willst, benutze die Klammern ohne "?:".

Grüße,
Michel

Nein darum geht es nicht, lies dir nochmal den Post ganz genau durch.


Wenn ich dich richtig verstehe, birkenfeld, hättest du aber nichts dagegen wenn das die RE-Engine könnte, oder? Weil du meinst, patches sind gerne gesehen.

Aber wie sieht ihr das? Würdet ihr es gut finden wenn die RE-Engine das könnte?

Und auf die Frage "Wäre es was für ein improved-Ticket?" habt ihr auch noch nicht geantwortet. Ja/Nein?

Danke das ihr euch Zeit genommen habt, mfg poker.


EDIT: Hab ne Umfrage hinzugefügt.

[BlackJack]

Ich habe mal mit "Nein" gestimmt weil mir das ein wenig zu unausgereift vorkommt. Was sind die Auswirkungen auf Rückreferenzen?

Wie sieht's mit dem Speicher aus der verbraucht wird, auch wenn man die `re` nur zum Matchen benutzt und da vielleicht so eine Gruppe vorkommt, die auf tausende von Stellen matcht. Damit rechnet niemand!

Lässt sich das effizient implementieren?

Auswirkungen auf den Rest der API?

Was passiert wenn solche Gruppen verschachtelt werden? Konsequenzen?

Ich denke das "patches sind gern gesehen" beinhaltet hier auch, das sich derjenige, der das Feature haben möchte, auch selbst um die Folgenabschätzung kümmert. Also das ganze erst einmal ausprobiert.

[poker]

Was sind die Auswirkungen auf Rückreferenzen?

Könntest du ein wenig weiter ausholen?

Wie sieht's mit dem Speicher aus der verbraucht wird, auch wenn man die `re` nur zum Matchen benutzt und da vielleicht so eine Gruppe vorkommt, die auf tausende von Stellen matcht. Damit rechnet niemand!

Das ist ein gutes Argument. Klar, da alle sub(sub...sub...)-matches in den groups vorhanden wären, würde auch der benötigte Speicher ansteigen.

Das Problem könnte man aber umgehen in den man eine neue match Funktion hinzufügt und somit die alten unangetastet lässt (Damit bleibt das bisherige Verhalten gewährleistet).

Die neue match Funktion behandelt die Gruppen dann so wie gefordert. Damit hätte man dann vier Funktionen: ``finditer``, ``search``, ``match`` + die vierte erweiterte die besser mit Gruppen umgehen kann.

Zusätzlich könnte man die vierte so schreiben, das per Argument der Modus (``search``-like = any position oder ``match``-like = at start) eingestellt werden kann Damit hätte man eine Erweiterte Funktion die wahlweise wie ``re.search`` oder ``re.match`` arbeitet, aber die alle sub matches hinzufügt.

Lässt sich das effizient implementieren?

Was passiert wenn solche Gruppen verschachtelt werden? Konsequenzen?

Nein, natürlich nicht so wie du es gerne haben willst Das Problem ist ja, das eine obere Instanz (Nicht mit Instanz einer Klasse bitte verwechseln) existieren muss, die in der Lage ist die einzelnen sub matches richtig zuzuordnen. Dass das ganz die Laufzeit erhöht ist ganz natürlich.

Ich denke aber trotzdem, dass das ganze trotzdem trivial umzusetzen ist (In Relation zu den skills die man als Python Core-Dev haben muss). Ich lasse mich aber gerne eines besseren belehren.

Auswirkungen auf den Rest der API?

IMO Keine, wenn man eine zusätzliche match Funktion einführt.

Ich denke das "patches sind gern gesehen" beinhaltet hier auch, das sich derjenige, der das Feature haben möchte, auch selbst um die Folgenabschätzung kümmert. Also das ganze erst einmal ausprobiert.

Mein C-Skills sind nicht im professionellen bereich angesiedelt und auch ein wenig eingerostet, daher könnte ich wenn dann nur ein POC in Python schreiben.

Ich danke dir aber sehr für dein Post, da du mir einen Denkanstoß gegeben hast. Wie im ersten post geschrieben, habe ich das ganze erst gestern entdeckt und dadurch noch keine Gelegenheit gehabt die Konsequenzen zu durchdenken.

Ich denke daher, eine Einführung einer zusätzlichen match Funktion wäre das beste (Gibt es eine Möglichkeit die Umfrage diesbezüglich abzuändern?)

mfg

[Michael Schneider]

Hi Poker,

also meine Doku besagt, dass "(?:" bedeutet: die folgende Gruppierung ist vom Ergebnis explizit auszuschließen!
Wenn Du die Gruppierung im Ergebnis haben willst, benutze die Klammern ohne "?:"...

Nein darum geht es nicht, lies dir nochmal den Post ganz genau durch.

Hi Poker,

sorry, habe das falsch verstanden.

Auch wenn ich nicht mitreden kann, wenigstens dass ich es verstehe :

Die RE-engine erzeugt de fakto für jede geöffnete runde Klammer eine Gruppe und Du hättest gern, dass unter Verwendung von + und * mehr Gruppen angelegt werden, als Klammerpaare existieren? Aus meiner Sicht stellt das schon eine grundlegende Änderung dar. Aber ich bin ja kein Experte.

Ich würde das mit diesem kleinen workaround lösen (geht aber nur bei so einfachen, vorhersehbaren Mustern):

Code: Alles auswählen

import re
m = re.search(r'(\*)\s*((?:(?:[0-9]+)(?:\s*))+)(\\\*)', "* 100 1 5 \*")
result = list(m.groups())
sub_list = re.findall(r'(?:([0-9]+)(\s*))', result[1])
result[1] = tuple(sub_list)
print tuple(result)

@Blacky: na, sind die Namen so angenehmer zu lesen?

Grüße,
Michel

[poker]

Die RE-engine erzeugt de fakto für jede geöffnete runde Klammer eine Gruppe und

Exakt.

Du hättest gern, dass unter Verwendung von + und * mehr Gruppen angelegt werden, als Klammerpaare existieren?

Jain, nicht mehr Gruppen als Klammerpaare existieren sondern praktisch das alle matches der sub Gruppe auch in die Gruppe einfließen.

Das ist ja hier z.B. nicht der Fall, da immer nur der letzte Treffer zugeordnet wird.

Code: Alles auswählen

In [67]: print re.search(r'(<)(?:\s*([0-9]+)\s*)*(>)', "<42 173 0 >").groups()
('<', '0', '>')
In [68]:

Nett wäre es wenn es eine **extra** match Funktion geben würde die Folgendes daraus erzeugt:

Code: Alles auswählen

('<', (('42',), ('173',), ('0',)), '>')

IMO wird momentan das Prinzip von Gruppen ad absurdum geführt, wenn man Verschachtelte Gruppen hat, was aber denoch praktikabler ist unter Berücksichtigung der von BlackJack genannten Aspekten (Laufzeit, Speicherverbrauch).

Aber ob sich der Aufwand lohnt? IMO spricht die Umfrage und das allgemeine Interesse für sich (=NULL). Ich werde mich dennoch weiter mit ``sre_compile`` und ``sre_parse`` beschäftigen (Sind viele nette utils drinnen. Aber leider nichts davon dokumentiert.) und dann versuchen in Python ein POC zu schreiben.

Momentan bin ich gerade dabei die zusammenhänge von REs und der internen Repräsentation in form von ``sre_parse.Pattern`` und ``sre_parse.SubPattern`` zu analysieren und schriftlich zu fixieren, so das ich schon mal weiß was in was mündet.

Code: Alles auswählen

In [87]: import sre_parse as srep
In [88]: import sre_compile as srec
In [89]: srep.parse(r"\*")
Out[89]: [('literal', 42)]
In [90]: unichr(42)
Out[90]: u'*'
In [91]: srep.parse(r"x|y|z")
Out[91]: [('in', [('literal', 120), ('literal', 121), ('literal', 122)])]
In [92]: srep.parse(r"x|y|zz")
Out[92]: [('branch', (None, [[('literal', 120)], [('literal', 121)], [('literal', 122), ('literal', 122)]]))]
In [93]: p = srep.parse("\*",0)
In [94]: srec._code(p,0)
Out[95]: [17, 8, 3, 1, 1, 1, 1, 42, 0, 19, 42, 1]
In [96]:

Weiß zufällig jemand ob es dazu eine Dokumentation/Spezifikation gibt? Oder muss ich wirklich erst alles selber analysieren und schriftlich fixieren?

mfg

[birkenfeld]

Du kannst natürlich den Autor, Fredrik Lundh, anmailen und fragen...

[BlackJack]

Ein Grund warum diese Änderung mich nicht so begeistert ist, dass ich bei solchen komplexen Sachen dann doch lieber zu einem echten Parser greife.

Code: Alles auswählen

from pyparsing import Group, Literal, nums, OneOrMore, Word

def grammar():
    number = Word(nums).setParseAction(lambda s, loc, toks: [int(toks[0])])
    numbers = Group(OneOrMore(number))
    grammar = Literal('<') + numbers + Literal('>')
    return grammar

def main():
    parser = grammar()
    result = parser.parseString('<42 173 0 >')
    print result

Ausgabe:

Code: Alles auswählen

['<', [42, 173, 0], '>']

[poker]

@birekenfeld: Danke, werde ich machen.

@BlackJack: Try this: http://simpleparse.sourceforge.net/scan ... parse.html
ist IMO angenehmer
Ausserdem verstehe ich deine abneigung gegen REs nicht?

@birekenfeld:

Für richtig komplexe Ausdrücke kannst du mit REs eh nichts anfangen.

Ist nicht exakt zutreffend, da Oniguruma eine der Leistungsfähigsten regexp Engines ist und viele Möglichkeiten bietet, die diese Aussage leicht blass aussehen lässt (Hab mal gestern wider seit sehr lange Zeit mit Ruby gespielt und den neusten Snappshot mit Oniguruma getestet ). Man siehe hier. Conditions werden wohl auch bald folgen und hoffentlich viele der Vorschläge von WoNàDo ... Und der nächste schritt wird sicherlich in Zukunft in die Richtung gehen wie ich mir das so gedacht habe.

@
BTW: Sehe ich das richtig das allgemein kein bedarf nach komplexeren regexp hier herrscht? Warum? Das Ruby Forum scheint da aufgeschlossener zu sein

[mitsuhiko]

Ich hab einige Regular Expressions, die das momentane Verhalten erwarten. Wenn man das also ändert bricht man ziemlich viel bestehenden Code. Wenn muss das eine Flag bekommen.

[poker]

Ich hab einige Regular Expressions, die das momentane Verhalten erwarten. Wenn man das also ändert bricht man ziemlich viel bestehenden Code. Wenn muss das eine Flag bekommen.

Hi, siehe hier: http://www.python-forum.de/post-78118.html#78118

Das Problem könnte man aber umgehen in den man eine neue match Funktion hinzufügt und somit die alten unangetastet lässt (Damit bleibt das bisherige Verhalten gewährleistet).

Die neue match Funktion behandelt die Gruppen dann so wie gefordert.

...

Alles bleibt beim alten nur eine zusätzliche Funktion kommt hinzu

BTW: Ich mach mal heute Abend einen neuen Thread auf mit einer passenderen Umfrage. Ich glaube nämlich das noch ein par mehr den von mir verlinkten post übersehen haben.

Der Thread kann dann eigentlich geclosed werden

Danke für eure Aufmerksamkeit, mfg

[Leonidas]

@birekenfeld:

Für richtig komplexe Ausdrücke kannst du mit REs eh nichts anfangen.

Ist nicht exakt zutreffend, da Oniguruma eine der Leistungsfähigsten regexp Engines ist und viele Möglichkeiten bietet, die diese Aussage leicht blass aussehen lässt (Hab mal gestern wider seit sehr lange Zeit mit Ruby gespielt und den neusten Snappshot mit Oniguruma getestet ). Man siehe hier. Conditions werden wohl auch bald folgen und hoffentlich viele der Vorschläge von WoNàDo ... Und der nächste schritt wird sicherlich in Zukunft in die Richtung gehen wie ich mir das so gedacht habe.

Klar, man kann mit Res vieles machen. Jedoch sind sie nicht immer die Lösung, besonders wenn es komplizierter wird. In den Rubyforen hat WoNaDo mal einen möglicherweise korrekten URL-Mathcer geschrieben. Aber matcht er korrekt? Weiß niemand, denn niemand versteht ihn, weil es eine Übersetzung eines mehrere tausende Zeichen langen ausdrucks aus Perl ist.

Um mal ein letztjähriges Zitat aus meinen IRC-Logs zu holen:

<mitsuhiko> Leonidas: 2007 programmiert wonado eh nur noch in turing vollständigen regular expressions

Das ist eben das was man in Python nicht haben will - eine Verlagerung der Features der Sprache in die Regex-Engine. "There should be one-- and preferably only one --obvious way to do it."

BTW: Sehe ich das richtig das allgemein kein bedarf nach komplexeren regexp hier herrscht? Warum? Das Ruby Forum scheint da aufgeschlossener zu sein

Weil Ruby von der Perl-Seite her geht, und dort Regular-Expressions sehr oft nötig sind. Für die Anwendungsbereiche für die Perl gedacht ist, stimmt das auch. Für Python ist das hingegen nicht der Fall. Python stellt Klarheit vor möglicherweise kryptischen Ausdrücken und die Leute im Python-Forum bevorzugen auch lieber Python-Code als reguläre Ausdrücke.

Übrigens ist eine neue Funktion blöd, lieber ein Flag, das per default aus ist.

[poker]

Klar, man kann mit Res vieles machen. Jedoch sind sie nicht immer die Lösung, besonders wenn es komplizierter wird.

Da will ich dir auch garnicht widersprechen und hast auch meine volle Zustimmung. Aber in maßen eingesetzt ist das eine Feine Sache. Und warum sollte man nur wegen dem **wenn** so ablehnend reagieren?

Beispiel: Ich kann mir eine Klassenhierarchie aufbauen wo die letzte Klasse 100 `ancestors`` hat. Klar ist das scheiße und ein anti pattern. Aber nur **weil das** möglich ist, sagen wir doch nicht auf einmal das Klassen abgeschafft werden sollen? So sehe ich das auch mit den REs. Sparsam eingesetzt ist das ein gute Sache und ich sehe nicht ein warum man den Sprachumfang **kastrieren** sollte nur weil man es übertreiben kann?

Um mal ein letztjähriges Zitat aus meinen IRC-Logs zu holen:

<mitsuhiko> Leonidas: 2007 programmiert wonado eh nur noch in turing vollständigen regular expressions

Ja irgendwann schaft das noch Wolfgang und hat ne Engine dir Wirklich turing vollständigen ist Halte ich persönlich für übertrieben, aber aus seinem Tätigkeitsumfeld absolut nachvollziehbar. Für seine Analysen ist er eben darauf angewiesen; und er ist ja auch ein Meister auf dem Gebiet der REs (Wer oder was ist Fridl!!111!! Frag Wolfgang ).

Das ist eben das was man in Python nicht haben will - eine Verlagerung der Features der Sprache in die Regex-Engine. "There should be one-- and preferably only one --obvious way to do it."

O.K. kann ich auch nachvollziehen aus pythonista Sicht, aber finde ich dennoch schade.

Weil Ruby von der Perl-Seite her geht, und dort Regular-Expressions sehr oft nötig sind. Für die Anwendungsbereiche für die Perl gedacht ist, stimmt das auch. Für Python ist das hingegen nicht der Fall. Python stellt Klarheit vor möglicherweise kryptischen Ausdrücken und die Leute im Python-Forum bevorzugen auch lieber Python-Code als reguläre Ausdrücke.

Naja O.K. dann spare ich mir die Arbeit mit dem neuen Thread und mach mich daran oniguruma für Python zu wrappen

mfg

[birkenfeld]

Weil Ruby von der Perl-Seite her geht, und dort Regular-Expressions sehr oft nötig sind. Für die Anwendungsbereiche für die Perl gedacht ist, stimmt das auch. Für Python ist das hingegen nicht der Fall. Python stellt Klarheit vor möglicherweise kryptischen Ausdrücken und die Leute im Python-Forum bevorzugen auch lieber Python-Code als reguläre Ausdrücke.

Naja O.K. dann spare ich mir die Arbeit mit dem neuen Thread und mach mich daran oniguruma für Python zu wrappen

Das ist sicher eine gute Idee. Wenn sich das dann durchsetzt, spricht ja auch nichts gegen eine Aufnahme in die Standardbibliothek.