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 0 … s n ist ein halboffenes Intervall über N, so dass s a 0 … s a 1 - 1 von R akzeptiert wird .
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:
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.
Wenn :
- Der führende Teil von passt besser zu S als der führende Teil von b oder
- 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 .
Wenn :
- ist eine Übereinstimmung für S und b ist nicht oder
Alle anderen syntaktischen Formen werden aus Gründen der Übereinstimmungspriorität auf die obigen drei reduziert:
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.
Bearbeiten: Dies ist eine vollständige Überarbeitung der Frage, um zu klären, was gestellt wurde.
quelle
\tt
hindert LaTeX nicht daran, Sonderzeichen und Kontrollsequenzen zu interpretieren!)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 keineaaaa
Ergebnisse. Dies liegt jedoch nur daran, dass Zweige in einer anderen Reihenfolge als versucht werdena+
. Wenn Sie es mit Ankern (wie'aaaa' =~ /^a+?\z/
in Perl) richtig machen, erhalten Sieaaaa
als Ergebnis.//g
in Perl) zurückgeben würde?Antworten:
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 gefundenaaaa
und es wird gespeichert, welche Teilzeichenfolge in einer speziellen Variablen übereinstimmt. Selbst wenn mehr als eine Teilzeichenfolge vorhanden ist,aaaa
die 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.
quelle
a+
unda+?
sind in diesem Sinne nicht gleichwertig:aaaa
ist kein Match für letztere.abbb
nicht in L (a*(..)*
), da die erste Übereinstimmung in der Zeichenfolgeabbb
mit dem regulären Ausdrucka*(..)*
istabb
. 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.a+?
passtaaaa
. Ich weiß, dass Ruby Regexpes es tun."aaaa" =~ /a?/
, in Ruby true zurückzugeben, aber das liegt daran, dass das Muster mit einem Teilstring von übereinstimmtaaaa
, nicht daran, dass es übereinstimmtaaaa
.+
(bearbeitet) verpasst und Ruby scheint dem ganzen Wort zu entsprechen (vgl. Rubular.com).