Können Regexe, die nichtreife (widerstrebende) Quantifizierer enthalten, umgeschrieben werden, um sie nicht zu verwenden?

8

Betrachten Sie eine Regex-Sprache mit dem gierigen Quantifizierer , dem nicht-gierigen Quantifizierer ? , geordnete Wechsel- und Charakterklassen. (Dies ist im Wesentlichen eine Subsprache von PCRE ohne Rückreferenzen, umschauende Behauptungen oder einige der anderen schickeren Teile.)?

Eine Übereinstimmung für einen regulären Ausdruck R auf einer Zeichenkette s = s 0s n ist ein halboffenes Intervall über N, so dass s a 0s a 1 - 1 von R akzeptiert wird .[a0,a1)Rs=s0snNsa0sa11R

Wir geben eine rekursive Definition dessen, was eine Übereinstimmung besser macht als eine andere. Eine Übereinstimmung für Regex R in einer Zeichenfolge ist besser als eine andere Übereinstimmung b = [ b 0 , b 1 ) wenn a 0 < b 0 oder wenn a 0 = b 0 und:a=[a0,a1)Rb=[b0,b1)a0<b0a0=b0

  • Wenn eine Zeichenklasse ist: Zeichenklassen haben eindeutige Übereinstimmungen, sodass alle Übereinstimmungen an derselben Position für R gleich sind. Daher ist dieser Fall unmöglich.RR

  • Wenn :R=ST

    • Der führende Teil von passt besser zu S als der führende Teil von b oderaSb
    • Die führenden Teile von und b stimmen gleich gut mit S überein , und der hintere Teil von a passt besser zu T als der hintere Teil von b .abSaTb
  • Wenn :R=S|T

    • ist eine Übereinstimmung für S und b ist nicht oderaSb
    • abSaSb
    • abSTaTb

Alle anderen syntaktischen Formen werden aus Gründen der Übereinstimmungspriorität auf die obigen drei reduziert:

  • R=SRS0|S1|
  • R=S?R|S1|S0

Diese unendlichen Muster werden nur zu Zwecken der Übereinstimmungspriorität verwendet - sie sind nicht Teil der betrachteten Übereinstimmungssprache.

Die "bessere" Beziehung ist eine schwache lineare Ordnung über alle möglichen Übereinstimmungen für ein gegebenes Muster.

S,T ST

S?T

Bearbeiten: Dies ist eine vollständige Überarbeitung der Frage, um zu klären, was gestellt wurde.

uckelman
quelle
1
Ich habe versucht, LaTeX in der Frage zu korrigieren, aber bitte überprüfen Sie, ob es das ist, was Sie gemeint haben. ( \tthindert LaTeX nicht daran, Sonderzeichen und Kontrollsequenzen zu interpretieren!)
Tsuyoshi Ito
2
Sie müssen vorsichtig sein, was Sie unter „Ausdruckskraft“ eines regulären Ausdrucks verstehen. Wenn Sie nur berücksichtigen, welche Sprache der reguläre Ausdruck erkennt, ist es trivial, dass widerstrebende Quantifizierer keine zusätzliche Potenz hinzufügen, da sie die Sprache, die der reguläre Ausdruck überhaupt erkennt, nicht ändern. Aber ich denke, dass Sie über feinere Eigenschaften regulärer Ausdrücke nachdenken, z. B. welche Teilzeichenfolgen erfasst werden und so weiter.
Tsuyoshi Ito
1
Nein, L ( a+?) ist immer noch {a ^ n: n≥1}. Wenn Sie eine nicht verankerte Regex-Übereinstimmung durchführen (z. B. 'aaaa' =~ /a+?/in Perl), erhalten Sie keine aaaaErgebnisse. Dies liegt jedoch nur daran, dass Zweige in einer anderen Reihenfolge als versucht werden a+. Wenn Sie es mit Ankern (wie 'aaaa' =~ /^a+?\z/in Perl) richtig machen, erhalten Sie aaaaals Ergebnis.
Tsuyoshi Ito
1
(1) Ich freue mich zu sehen, dass meine Kommentare und Antworten hilfreich waren, um die Frage besser zu wiederholen (obwohl Sie sie nicht zugegeben haben). (2) Ich hoffe, Sie wissen, dass „die Sätze nicht überlappender Übereinstimmungen, die S und T auf t haben“, nicht genau definiert sind, da es mehrere Sätze nicht überlappender Übereinstimmungen geben kann. Sprechen Sie über die Liste, die eine globale Regex-Übereinstimmung ( //gin Perl) zurückgeben würde?
Tsuyoshi Ito
2
Ihre Frage muss geklärt werden. Sie sprechen immer noch davon, ein Match zu "akzeptieren", wenn gierig oder nicht gierig nichts daran ändert, was akzeptiert wird. Es ist nur ein Mittel, um anzugeben, welche Übereinstimmung gefunden werden soll, wenn nach einer Übereinstimmung gesucht und viele gefunden werden.
Eamon Nerbonne

Antworten:

3

Diese Antwort basiert auf der Annahme, dass die Äquivalenz von zwei regulären Ausdrücken definiert ist, wenn sie dieselbe Sprache erkennen. Die aktuelle Frage wird nicht beantwortet.


Sie haben ein weit verbreitetes Missverständnis, dass widerstrebende Quantifizierer die Menge der Zeichenfolgen ändern, mit denen ein regulärer Ausdruck übereinstimmt. Dies ist nicht der Fall und es wird nur geändert, welche Optionen zuerst ausprobiert werden.

Wenn Sie beispielsweise eine Regex-Übereinstimmung 'aaaa' =~ /a+/in Perl durchführen, wird die erste Übereinstimmung in der Zeichenfolge gefunden aaaaund es wird gespeichert, welche Teilzeichenfolge in einer speziellen Variablen übereinstimmt. Selbst wenn mehr als eine Teilzeichenfolge vorhanden ist, aaaadie mit dem angegebenen regulären Ausdruck übereinstimmt, werden die anderen Übereinstimmungen als die erste Übereinstimmung ignoriert.

Ob Quantifizierer gierig oder ungern sind, beeinflusst, was die erste Übereinstimmung unter vielen Übereinstimmungen ist, aber die Anzahl der Übereinstimmungen ändert sich nicht. In diesem Sinne bleibt die Menge der Zeichenfolgen, mit denen ein regulärer Ausdruck übereinstimmt, unverändert, unabhängig davon, ob Sie übliche gierige Quantifizierer oder widerstrebende Quantifizierer verwenden.

Tsuyoshi Ito
quelle
Nein, ich spreche nicht über die Übereinstimmungen, die ein nicht verankertes Muster für eine bestimmte Zeichenfolge erhält. Ich spreche von der Reihe von Zeichenfolgen, für die ein bestimmtes Muster in ihrer Gesamtheit mit diesen Zeichenfolgen übereinstimmt. Mit anderen Worten, ich bin daran interessiert, Muster neu zu schreiben, um die Äquivalenz über den Satz von Zeichenfolgen aufrechtzuerhalten, für die die erste Übereinstimmung die gesamte Zeichenfolge ist . a+und a+?sind in diesem Sinne nicht gleichwertig: aaaaist kein Match für letztere.
uckelman
1
@uckelman: Gemäß Ihrer Definition ist die Zeichenfolge abbbnicht in L ( a*(..)*), da die erste Übereinstimmung in der Zeichenfolge abbbmit dem regulären Ausdruck a*(..)*ist abb. Dies ist nicht die Standarddefinition der Sprache, die von einem regulären Ausdruck erkannt wird. Wenn Sie wirklich daran interessiert sind, sollten Sie es anders benennen.
Tsuyoshi Ito
uckelman, ich bin mir ziemlich sicher, dass es a+?passt aaaa. Ich weiß, dass Ruby Regexpes es tun.
Raphael
@ Raphael: Ich denke, Sie sprechen davon "aaaa" =~ /a?/, in Ruby true zurückzugeben, aber das liegt daran, dass das Muster mit einem Teilstring von übereinstimmt aaaa, nicht daran, dass es übereinstimmt aaaa.
Tsuyoshi Ito
Ich habe ein +(bearbeitet) verpasst und Ruby scheint dem ganzen Wort zu entsprechen (vgl. Rubular.com).
Raphael