Unterstützen erweiterte Regexes Rückverweise?

8

Wikipedia sagt , dass erweiterte Regexes die Unterstützung für Rückreferenzen nicht mehr unterstützen, so dass der "grundlegende" Regex-Modus verwendet werden muss um diese zu ermöglichen. Es scheint jedoch, dass eine Anzahl von Implementierungen Rückwärtsreferenzen für erweiterte Regexes unterstützen. Zum Beispiel werden sie mit gcc 4.6 unter Ubuntu Precise unterstützt. FreeBSD-Implementierungen scheinen sie nur im Basismodus zu unterstützen

Boost sagt (und scheint um mit Wikipedia übereinzustimmen, dass Rückreferenzen für erweiterte Regex nicht unterstützt werden, aber Boost :: Regex fügt sie als Erweiterung hinzu.

Ist das nur ein schlecht definierter Teil des Standards, der bei jeder Implementierung anders interpretiert wird?

    
Eli Bendersky 10.11.2012, 14:41
quelle

3 Antworten

6

Wie andere schon gesagt haben, ist es klar, dass POSIX EREs keine Rückverweise unterstützen.

Die in der OpenGroup Basisspezifikation Ausgabe 7 angegebene Begründung, dass keine Rückreferenzen zu EREs hinzugefügt werden sollen, lautet wie folgt:

  

Es wurde vorgeschlagen, dass zusätzlich zu Intervallausdrücken auch Rückreferenzen ('\ n') zu EREs hinzugefügt werden sollten. Dies wurde von den Standardentwicklern als wahrscheinlich abgelehnt, um den Konsens zu verringern.

Zitiert nach: Begründung: Basisdefinitionen: Erweiterte reguläre Ausdrücke

Der Hauptgrund für diese Einschränkung besteht darin, dass POSIX-EREs in einen deterministischen endlichen Automaten (DFA) konvertiert werden können, und tatsächlich wurde die ursprüngliche Implementierung von EREs in Unix als DFA durchgeführt. Die Verwendung eines DFA ermöglicht Garantien über die Leistung der Implementierung. Mustervergleich mit (einer unbegrenzten Anzahl von) Rückverweisen ist ein NP-schweres Problem und vielleicht sogar ein NP-vollständiges Problem. Der Konsens im POSIX-Normenausschuss hätte niemals erreicht werden können, wenn Rückverweise für EREs vorgeschlagen würden, da dies alle Unternehmen, die die ursprüngliche Unix-Implementierung verwenden, zwingen würde, ihren Code in eine nichtdeterministische Implementierung zu ändern und ihre Leistungsgarantien zu streichen von diesen Unternehmen hatten Mitglieder im Ausschuss.

Es wurde auch festgestellt, dass Rückreferenzen in REs weder für Benutzer noch für Implementoren intuitiv sind, und tatsächlich haben sie häufiger als bisher extreme Verwirrung verursacht. Siehe zum Beispiel die Beispiele in RE-Interpretation: The Dark Corners

HINWEIS: Rückverweise in REs sind nicht dieselben wie Verweise auf Untermuster im Substitutionstext in Werkzeugen wie sed.

    
Greg A. Woods 13.11.2012, 06:19
quelle
4

Nach dem IEEE / Open Group-Standard Erweiterte reguläre Ausdrücke werden nicht unterstützt Backreferences (Abschnitt 9.5.1), obwohl mehrere reale Implementierungen dies tun.

    
Yahia 12.11.2012 15:53
quelle
1

Gemäß dem POSIX.1-2008-Standard werden nur reguläre Standardausdrücke unterstützt. Verweise. Abschnitt 9.3.6 beschreibt, wie sie in BREs funktionieren. Der Abschnitt "Erweiterte reguläre Ausdrücke" erwähnt sie überhaupt nicht und die Grammatiklexikalischen Konventionen in Abschnitt 9.5.1 sagen, dass Back-Reference-Token nur für BREs gelten.

    
Adam Rosenfield 12.11.2012 15:57
quelle

Tags und Links