Buggy `re`-Engine

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.

Soll das Bestandteil der Engine werden und ein improved-Ticket hinzugefügt werden?

Ja
3
27%
Nein (Begründung bitte im Thread posten)
8
73%
 
Abstimmungen insgesamt: 11
poker
User
Beiträge: 146
Registriert: Donnerstag 20. September 2007, 21:44

Buggy `re`-Engine

Beitragvon poker » Donnerstag 20. September 2007, 23:25

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.
Zuletzt geändert von poker am Freitag 21. September 2007, 17:46, insgesamt 1-mal geändert.
Benutzeravatar
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Beitragvon mitsuhiko » Freitag 21. September 2007, 06:39

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.
TUFKAB – the user formerly known as blackbird
Benutzeravatar
Michael Schneider
User
Beiträge: 566
Registriert: Samstag 8. April 2006, 12:31
Wohnort: Bremen
Kontaktdaten:

Re: Buggy `re`-Engine

Beitragvon Michael Schneider » Freitag 21. September 2007, 07:39

poker hat geschrieben: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
Diese Nachricht zersört sich in 5 Sekunden selbst ...
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Re: Buggy `re`-Engine

Beitragvon birkenfeld » Freitag 21. September 2007, 08:20

poker hat geschrieben: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.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Freitag 21. September 2007, 11:55

blackbird hat geschrieben: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?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Beitragvon birkenfeld » Freitag 21. September 2007, 12:00

Unmaintained ist falsch. sre ist genauso maintained wie alle anderen Libraries, die nicht speziell von einer Person gepflegt werden.
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Re: Buggy `re`-Engine

Beitragvon HWK » Freitag 21. September 2007, 12:30

Michael Schneider hat geschrieben:
poker hat geschrieben: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
User
Beiträge: 146
Registriert: Donnerstag 20. September 2007, 21:44

Beitragvon poker » Freitag 21. September 2007, 17:40

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.


Michael Schneider hat geschrieben: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

Beitragvon BlackJack » Freitag 21. September 2007, 18:53

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
User
Beiträge: 146
Registriert: Donnerstag 20. September 2007, 21:44

Beitragvon poker » Freitag 21. September 2007, 19:45

BlackJack hat geschrieben:Was sind die Auswirkungen auf Rückreferenzen?

Könntest du ein wenig weiter ausholen?

BlackJack hat geschrieben: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.

BlackJack hat geschrieben:Lässt sich das effizient implementieren?

BlackJack hat geschrieben: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.

BlackJack hat geschrieben:Auswirkungen auf den Rest der API?
IMO Keine, wenn man eine zusätzliche match Funktion einführt.

BlackJack hat geschrieben: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
Benutzeravatar
Michael Schneider
User
Beiträge: 566
Registriert: Samstag 8. April 2006, 12:31
Wohnort: Bremen
Kontaktdaten:

Beitragvon Michael Schneider » Sonntag 23. September 2007, 00:03

poker hat geschrieben:
Michael Schneider hat geschrieben: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 :-D:

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
Diese Nachricht zersört sich in 5 Sekunden selbst ...
poker
User
Beiträge: 146
Registriert: Donnerstag 20. September 2007, 21:44

Beitragvon poker » Sonntag 23. September 2007, 02:24

Michael Schneider hat geschrieben:Die RE-engine erzeugt de fakto für jede geöffnete runde Klammer eine Gruppe und
Exakt.

Michael Schneider hat geschrieben: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
Zuletzt geändert von poker am Donnerstag 4. Oktober 2007, 20:24, insgesamt 1-mal geändert.
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Beitragvon birkenfeld » Sonntag 23. September 2007, 08:06

Du kannst natürlich den Autor, Fredrik Lundh, anmailen und fragen...
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
BlackJack

Beitragvon BlackJack » Sonntag 23. September 2007, 09:23

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
User
Beiträge: 146
Registriert: Donnerstag 20. September 2007, 21:44

Beitragvon poker » Sonntag 23. September 2007, 10:43

@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:
birkenfeld hat geschrieben: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 :shock:). 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 :?

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder