Wie können wir ein ^ nb ^ n mit Java-Regex abgleichen?

_{Dies ist der zweite Teil einer Reihe von Artikeln über pädagogische Regex. Es zeigt, wie Lookaheads und verschachtelte Referenzen verwendet werden können, um mit der nicht regulären Sprache a ⁿ b ⁿ übereinzustimmen . Verschachtelte Referenzen werden zuerst eingeführt in: Wie findet dieser Regex dreieckige Zahlen?}

Eine der archetypischen nicht regulären Sprachen ist:

L = { aⁿ bⁿ: n > 0 }

Dies ist die Sprache aller nicht leeren Zeichenfolgen, die aus einer Anzahl von a's, gefolgt von einer gleichen Anzahl von b' s bestehen. Beispiele für Strings in dieser Sprache sind ab, aabb, aaabbb.

Es kann gezeigt werden, dass diese Sprache durch das Pump-Lemma nicht regelmäßig ist . Es ist in der Tat eine archetypische kontextfreie Sprache , die durch die kontextfreie Grammatik erzeugt werden kann S → aSb | ab.

Nichtsdestotrotz erkennen moderne Regex-Implementierungen eindeutig mehr als nur reguläre Sprachen. Das heißt, sie sind nach der Definition der formalen Sprachtheorie nicht "regelmäßig". PCRE und Perl unterstützen rekursiven regulären Ausdruck und .NET unterstützt die Definition von Ausgleichsgruppen. Noch weniger "ausgefallene" Funktionen, z. B. Backreference Matching, bedeuten, dass Regex nicht regelmäßig ist.

Aber wie mächtig sind diese "grundlegenden" Funktionen? Können wir Lzum Beispiel mit Java Regex erkennen ? Können wir vielleicht lookarounds und verschachtelte Referenzen kombinieren und ein Muster, das funktioniert mit zB String.matchesStrings passen wie ab, aabb, aaabbb, etc?

Verweise

• perlfaq6: Kann ich reguläre Perl-Ausdrücke verwenden, um ausgeglichenen Text abzugleichen?
• MSDN - Sprachelemente für reguläre Ausdrücke - Ausgleichsgruppendefinitionen
• pcre.org - PCRE-Manpage
• reguläre-Ausdrücke.info - Lookarounds und Gruppierungen und Rückreferenzen
• java.util.regex.Pattern

Verknüpfte Fragen

• Beeinflusst Lookaround, welche Sprachen durch reguläre Ausdrücke abgeglichen werden können?
• .NET Regex Balancing Groups vs PCRE Recursive Patterns

Die Antwort lautet natürlich JA! Sie können mit Sicherheit ein Java-Regex-Muster schreiben, das mit a ⁿ b ⁿ übereinstimmt . Es wird ein positiver Lookahead für die Behauptung und eine verschachtelte Referenz für das "Zählen" verwendet.

Anstatt das Muster sofort herauszugeben, führt diese Antwort den Leser durch den Prozess der Ableitung. Während die Lösung langsam aufgebaut wird, werden verschiedene Hinweise gegeben. In dieser Hinsicht enthält diese Antwort hoffentlich viel mehr als nur ein weiteres ordentliches Regex-Muster. Hoffentlich lernen die Leser auch, wie man "in Regex denkt" und wie man verschiedene Konstrukte harmonisch zusammenfügt, damit sie in Zukunft selbst mehr Muster ableiten können.

Die Sprache, die zur Entwicklung der Lösung verwendet wird, ist PHP für ihre Prägnanz. Der endgültige Test nach Fertigstellung des Musters wird in Java durchgeführt.

Schritt 1: Suchen Sie nach einer Bestätigung

Beginnen wir mit einem einfacheren Problem: Wir möchten a+am Anfang eines Strings übereinstimmen , aber nur, wenn sofort darauf folgt b+. Wir können verwenden ^, um unser Match zu verankern , und da wir nur das a+ohne das Matching wollen b+, können wir die Lookahead- Behauptung verwenden (?=…).

Hier ist unser Muster mit einem einfachen Testgeschirr:

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}
 
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
 
$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

Die Ausgabe ist ( wie auf ideone.com zu sehen ):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

Dies ist genau die Ausgabe, die wir wollen: Wir stimmen überein a+, nur wenn sie am Anfang der Zeichenfolge steht und nur, wenn sie unmittelbar gefolgt wird b+.

Lektion : Sie können Muster in Lookarounds verwenden, um Aussagen zu treffen.

Schritt 2: Erfassen in einem Lookahead (und Freiraummodus)

Nun lassen Sie uns sagen , dass , obwohl wir nicht das wollen , b+werden Teil des Spiels, wir wollen erfassen es trotzdem in Gruppe 1. Auch, wie wir ein komplizierteres Muster antizipieren mit, lassen Sie uns die Verwendung xModifikator für Freiabstand , so dass wir kann unsere Regex besser lesbar machen.

Aufbauend auf unserem vorherigen PHP-Snippet haben wir jetzt das folgende Muster:

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead
 
testAll($r2, $tests);

Die Ausgabe ist jetzt ( wie auf ideone.com zu sehen ):

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

Beachten Sie, dass z. B. aaa|bdas Ergebnis von join-ing ist, mit dem jede Gruppe erfasst wurde '|'. In diesem Fall werden Gruppe 0 (dh was mit dem Muster übereinstimmt) aaaund Gruppe 1 erfasst b.

Lektion : Sie können innerhalb eines Lookarounds erfassen. Sie können den freien Abstand verwenden, um die Lesbarkeit zu verbessern.

Schritt 3: Umgestaltung des Lookaheads in die "Schleife"

Bevor wir unseren Zählmechanismus einführen können, müssen wir eine Änderung an unserem Muster vornehmen. Derzeit befindet sich der Lookahead außerhalb der +Wiederholungsschleife. Dies ist bisher in Ordnung, weil wir nur behaupten wollten, dass es eine b+Gefolgschaft gibt a+, aber was wir schließlich wirklich tun wollen, ist zu behaupten, dass es für jede aÜbereinstimmung innerhalb der "Schleife" eine entsprechende gibt b.

Machen wir uns vorerst keine Gedanken über den Zählmechanismus und führen das Refactoring wie folgt durch:

• Erster Refactor a+zu (?: a )+(beachten Sie, dass (?:…)es sich um eine nicht erfassende Gruppe handelt)
• Bewegen Sie dann den Lookahead in diese nicht erfassende Gruppe
  • Beachten Sie, dass wir jetzt "überspringen" müssen, a*bevor wir das "sehen" b+können. Ändern Sie daher das Muster entsprechend

Wir haben jetzt also Folgendes:

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

Die Ausgabe ist die gleiche wie zuvor ( wie auf ideone.com zu sehen ), daher ändert sich diesbezüglich nichts. Wichtig ist, dass wir jetzt bei jeder Iteration der +"Schleife" die Behauptung aufstellen . Bei unserem aktuellen Muster ist dies nicht erforderlich, aber als nächstes werden wir Gruppe 1 unter Verwendung der Selbstreferenz für uns "zählen" lassen.

Lektion : Sie können innerhalb einer nicht erfassenden Gruppe erfassen. Lookarounds können wiederholt werden.

Schritt 4: Dies ist der Schritt, in dem wir mit dem Zählen beginnen

Folgendes werden wir tun: Wir werden Gruppe 1 so umschreiben, dass:

• Am Ende der ersten Iteration von +, wenn die erste aübereinstimmt, sollte sie erfassenb
• Wenn am Ende der zweiten Iteration eine andere aübereinstimmt, sollte sie erfasst werdenbb
• Am Ende der dritten Iteration sollte es erfasst werden bbb
• ...
• Am Ende der n- ten Iteration sollte Gruppe 1 b ⁿ erfassen
• Wenn es nicht genug gibt b, um in Gruppe 1 zu erfassen, schlägt die Behauptung einfach fehl

Also muss Gruppe 1, die jetzt ist (b+), in so etwas umgeschrieben werden (\1 b). Das heißt, wir versuchen, a bzu der Gruppe 1 hinzuzufügen, die in der vorherigen Iteration erfasst wurde.

Hier besteht ein kleines Problem darin, dass diesem Muster der "Basisfall" fehlt, dh der Fall, in dem es ohne Selbstreferenz übereinstimmen kann. Ein Basisfall ist erforderlich, da Gruppe 1 "nicht initialisiert" startet. Es wurde noch nichts erfasst (nicht einmal eine leere Zeichenfolge), sodass ein Selbstreferenzversuch immer fehlschlägt.

Es gibt viele Möglichkeiten, dies zu umgehen, aber jetzt wollen wir nur den Selbstreferenzabgleich optional machen , d \1?. H. Dies mag perfekt funktionieren oder auch nicht, aber lassen Sie uns sehen, was das bewirkt, und wenn es ein Problem gibt, werden wir diese Brücke überqueren, wenn wir dazu kommen. Außerdem werden wir noch einige Testfälle hinzufügen, während wir gerade dabei sind.

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
 
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

Die Ausgabe ist jetzt ( wie auf ideone.com zu sehen ):

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

Aha! Es sieht so aus, als wären wir der Lösung jetzt wirklich nahe! Wir haben es geschafft, Gruppe 1 mithilfe der Selbstreferenz zum "Zählen" zu bringen! Aber warte ... mit dem zweiten und dem letzten Testfall stimmt etwas nicht !! Es gibt nicht genug bs und irgendwie hat es falsch gezählt! Wir werden im nächsten Schritt untersuchen, warum dies passiert ist.

Lektion : Eine Möglichkeit, eine selbstreferenzierende Gruppe zu "initialisieren", besteht darin, den Selbstreferenzabgleich optional zu machen.

Schritt 4½: Verstehen, was schief gelaufen ist

Das Problem ist, dass, da wir den Selbstreferenzabgleich optional gemacht haben, der "Zähler" auf 0 zurückgesetzt werden kann, wenn nicht genug vorhanden sind b. Lassen Sie uns genau untersuchen, was bei jeder Iteration unseres Musters aaaaabbbals Eingabe passiert .

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

Aha! Bei unserer 4. Iteration konnten wir immer noch übereinstimmen \1, aber wir konnten nicht übereinstimmen \1b! Da wir zulassen, dass der Selbstreferenzabgleich optional ist \1?, zieht sich der Motor zurück und hat die Option "Nein, danke" gewählt, mit der wir dann nur übereinstimmen und erfassen können b!

Beachten Sie jedoch, dass Sie außer bei der ersten Iteration immer nur die Selbstreferenz abgleichen können \1. Dies ist natürlich offensichtlich, da es das ist, was wir gerade in unserer vorherigen Iteration erfasst haben, und in unserem Setup können wir es immer wieder abgleichen (z. B. wenn wir das bbbletzte Mal erfasst haben, ist garantiert, dass es noch vorhanden sein wird bbb, aber es kann oder kann bbbbdiesmal nicht sein ).

Lektion : Vorsicht vor dem Zurückverfolgen. Die Regex-Engine führt so viele Rückverfolgungen durch, wie Sie zulassen, bis das angegebene Muster übereinstimmt. Dies kann die Leistung (dh das katastrophale Zurückverfolgen ) und / oder die Korrektheitbeeinträchtigen.

Schritt 5: Selbstbesitz zur Rettung!

Das "Update" sollte jetzt offensichtlich sein: Kombinieren Sie optionale Wiederholung mit besitzergreifendem Quantifizierer. Das heißt, anstatt einfach zu ?verwenden ?+(denken Sie daran, dass eine Wiederholung, die als besitzergreifend quantifiziert wird, nicht zurückverfolgt wird, selbst wenn eine solche "Zusammenarbeit" zu einer Übereinstimmung des Gesamtmusters führen kann).

In sehr informell ausgedrückt, ist es das , was ?+, ?und ??sagt:

?+

• (optional) "Es muss nicht da sein"
  • (besitzergreifend) "aber wenn es da ist, musst du es nehmen und nicht loslassen!"

?

• (optional) "Es muss nicht da sein"
  • (gierig) "aber wenn es so ist, kannst du es jetzt nehmen,"
    • (Rückverfolgung) "aber Sie werden möglicherweise gebeten, es später loszulassen!"

??

• (optional) "Es muss nicht da sein"
  • (widerstrebend) "und selbst wenn es so ist, musst du es noch nicht nehmen"
    • (Rückverfolgung) "aber Sie werden möglicherweise gebeten, es später zu nehmen!"

In unserem Setup \1wird es nicht beim ersten Mal da sein, aber es wird immer zu jeder Zeit danach da sein, und wir wollen es dann immer anpassen. Somit \1?+würde genau das erreicht, was wir wollen.

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Jetzt ist die Ausgabe ( wie auf ideone.com zu sehen ):

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

Voilà !!! Problem gelöst!!! Wir zählen jetzt richtig, genau so, wie wir es wollen!

Lektion : Lernen Sie den Unterschied zwischen gieriger, widerstrebender und besitzergreifender Wiederholung. Optional-besitzergreifend kann eine leistungsstarke Kombination sein.

Schritt 6: Feinschliff

Was wir jetzt haben, ist ein Muster, das awiederholt übereinstimmt , und für jedes aübereinstimmende Muster gibt es ein entsprechendes Muster bin Gruppe 1. Das wird +beendet, wenn es keine mehr agibt oder wenn die Behauptung fehlgeschlagen ist, weil es kein entsprechendes bfür gibt an a.

Um den Job zu beenden, müssen wir einfach an unser Muster anhängen \1 $. Dies ist nun ein Rückverweis auf die Übereinstimmung von Gruppe 1, gefolgt vom Ende des Linienankers. Der Anker stellt sicher, dass bdie Zeichenfolge keine zusätzlichen Elemente enthält. mit anderen Worten, dass wir tatsächlich ein ⁿ b ^{n haben} .

Hier ist das endgültige Muster mit zusätzlichen Testfällen, einschließlich eines mit 10.000 Zeichen Länge:

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);
 
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

Es findet 4 Treffer: ab, aabb, aaabbb, und die eine ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Die Ausführung auf ideone.com dauert nur 0,06 Sekunden .

Schritt 7: Der Java-Test

Das Muster funktioniert also in PHP, aber das ultimative Ziel ist es, ein Muster zu schreiben, das in Java funktioniert.

public static void main(String[] args) {
 
        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }
 
}
 
static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

Das Muster funktioniert wie erwartet ( wie auf ideone.com zu sehen ).

Und jetzt kommen wir zum Schluss ...

Es muss gesagt werden, dass die a*im Lookahead und in der Tat die "Hauptschleife +" beide das Zurückverfolgen erlauben. Die Leser werden aufgefordert zu bestätigen, warum dies kein Problem in Bezug auf die Korrektheit ist und warum es gleichzeitig funktionieren würde, beide besitzergreifend zu machen (obwohl das Mischen von obligatorischen und nicht obligatorischen besitzergreifenden Quantifizierern im selben Muster möglicherweise zu Fehlwahrnehmungen führen kann).

Es sollte auch gesagt werden, dass es zwar ordentlich ist, dass es ein Regex-Muster gibt, das mit a ⁿ b ⁿ übereinstimmt , dies jedoch in der Praxis nicht immer die "beste" Lösung ist. Eine viel bessere Lösung besteht darin, einfach ^(a+)(b+)$die Länge der von den Gruppen 1 und 2 in der Hosting-Programmiersprache erfassten Zeichenfolgen abzugleichen und dann zu vergleichen.

In PHP sieht es ungefähr so aus ( wie auf ideone.com zu sehen ):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

Der Zweck dieses Artikels ist NICHT , die Leser davon zu überzeugen, dass Regex fast alles kann. Es ist eindeutig nicht möglich, und selbst für die Dinge, die es tun kann, sollte eine zumindest teilweise Delegierung an die Hosting-Sprache in Betracht gezogen werden, wenn dies zu einer einfacheren Lösung führt.

Wie oben erwähnt, ist dieser Artikel zwar unbedingt [regex]für den Stapelüberlauf gekennzeichnet, es geht aber möglicherweise um mehr. Während es sicherlich wertvoll ist, etwas über Behauptungen, verschachtelte Referenzen, besitzergreifende Quantifizierer usw. zu lernen, ist die größere Lektion hier vielleicht der kreative Prozess, mit dem man versuchen kann, Probleme zu lösen, die Entschlossenheit und die harte Arbeit, die es oft erfordert, wenn man ausgesetzt ist verschiedene Einschränkungen, die systematische Zusammensetzung aus verschiedenen Teilen, um eine funktionierende Lösung zu erstellen, usw.

Bonusmaterial! PCRE rekursives Muster!

Da wir PHP aufgerufen haben, muss gesagt werden, dass PCRE rekursive Muster und Unterprogramme unterstützt. Daher funktioniert das folgende Muster für preg_match( wie auf ideone.com zu sehen ):

$rRecursive = '/ ^ (a (?1)? b) $ /x';

Derzeit unterstützt Javas Regex kein rekursives Muster.

Noch mehr Bonusmaterial! Passend zu a ⁿ b ⁿ c ⁿ !!

So haben wir gesehen , wie man überein einen ⁿ b ⁿ , die nicht regelmäßig, aber immer noch kontextfrei, aber können wir auch passen eine ⁿ b ⁿ c ⁿ , die nicht einmal kontextfrei ist?

Die Antwort lautet natürlich JA! Die Leser werden aufgefordert, zu versuchen, dies selbst zu lösen. Die Lösung finden Sie weiter unten (mit Implementierung in Java auf ideone.com ).

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $

Da PCRE, das rekursive Muster unterstützt, nicht erwähnt wurde, möchte ich nur auf das einfachste und effizienteste Beispiel für PCRE hinweisen, das die betreffende Sprache beschreibt:

/^(a(?1)?b)$/

Wie in der Frage erwähnt - mit der .NET-Ausgleichsgruppe können die Muster vom Typ a ⁿ b ⁿ c ⁿ d ⁿ … z ⁿ leicht als abgeglichen werden

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))
$

Zum Beispiel: http://www.ideone.com/usuOE

Bearbeiten:

Es gibt auch ein PCRE-Muster für die verallgemeinerte Sprache mit rekursivem Muster, aber ein Lookahead ist erforderlich. Ich denke nicht, dass dies eine direkte Übersetzung des oben genannten ist.

^
  (?=(a(?-1)?b))  a+
  (?=(b(?-1)?c))  b+
  ...
  (?=(x(?-1)?y))  x+
     (y(?-1)?z)
$

Zum Beispiel: http://www.ideone.com/9gUwF