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

99

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 n b n übereinzustimmen . Verschachtelte Referenzen werden zuerst eingeführt in: Wie findet dieser Regex dreieckige Zahlen?

Eine der archetypischen nicht regulären Sprachen ist:

L = { an bn: 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

Verknüpfte Fragen

Polygenschmierstoffe
quelle
4
Diese Serie wurde mit Genehmigung einiger Mitglieder der Community gestartet ( meta.stackexchange.com/questions/62695/… ). Wenn der Empfang gut ist, plane ich, weitere fortgeschrittenere und grundlegendere Funktionen von Regex zu behandeln.
Polygenelubricants
Teil 3: stackoverflow.com/questions/3664881/…
Polygenelubricants
Wow, ich wusste nie, dass Javas Regexs nicht auf reguläre Ausdrücke beschränkt sind. Ich denke, das erklärt, warum ich immer gedacht habe, dass sie nicht vollständig implementiert werden. Ich meine, dass in Java Regexs keine Komplement-, Differenz- oder Produktoperatoren integriert sind, aber das ist sinnvoll, da sie nicht auf reguläre Sprachen beschränkt sind.
Lan
Diese Frage wurde zu den häufig gestellten Fragen zum Stapelüberlauf für reguläre Ausdrücke unter "Advanced Regex-Fu" hinzugefügt .
Aliteralmind

Antworten:

139

Die Antwort lautet natürlich JA! Sie können mit Sicherheit ein Java-Regex-Muster schreiben, das mit a n b n ü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 n 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 n 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 5000 b 5000 . 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 n b n ü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 n b n c n !!

So haben wir gesehen , wie man überein einen n b n , die nicht regelmäßig, aber immer noch kontextfrei, aber können wir auch passen eine n b n c n , 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 $

Polygenschmierstoffe
quelle
Zweifellos kann diese lange Antwort Fehler / Tippfehler enthalten. Bitte hinterlassen Sie Feedbacks als Kommentare, damit ich sie selbst überarbeiten kann.
Polygenelubricants
Gut gemacht. Es wird eine Weile dauern, bis ich es gelesen habe, aber die allerletzte Zeile ist im Grunde unmöglich zu lesen. Es ist so eine kleine Schrift. ------ Oh, Moment mal. Ist das ein feature? .... Ich bin mir nicht sicher, ob es eine gute Idee ist. Ich weiß, was das letzte Symbol ist, aber es kann nicht gelesen werden (abgesehen vom Kopieren und Einfügen).
Peter Ajtai
6
@Peter: Markieren Sie den kleinen Text und kopieren Sie ihn und fügen Sie ihn in etwas anderes ein. Es ist absichtlich schwer zu lesen: Es ist ein Spoiler, die Lösung für das Bonus-Puzzle.
Polygenelubricants
8
+1: Fantastische Erklärung, diese "Fortgeschrittenen Artikel" sind brillante Ideen.
Callum Rogers
1
@LarsH PHPs preg_match()sind ein Beispiel für PCRE . Java-Regexe scheinen auf einer älteren Version von Perl-Regexps zu basieren . Dies bedeutet, dass PHP-Regexe leistungsfähiger sind als die Version in Java. Ab dem 21.02.2013 gibt pcre.txt an , dass es ungefähr Perl 5.12 entspricht . Während Perl derzeit bei 5,16 ist, mit 5,18 ein paar Monate frei. (Es wurde in dieser Zeit nicht viel zu Regexes hinzugefügt)
Brad Gilbert
20

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)$/
Jaytea
quelle
+1 Wow, ich wusste nicht, dass PCRE rekursives Muster unterstützt (ich lerne immer noch! Jeden Tag!). Ich habe den Artikel überarbeitet, um diese Informationen aufzunehmen. Ich denke jedoch nicht, dass rekursives Muster übereinstimmen a^n b^n c^nkann.
Polygenelubricants
Es ist zu beachten, dass diese Option einfacher ist, aber nicht so gut wie die veröffentlichte Antwort - die Rekursion läuft bei langen Zeichenfolgen über.
Kobi
@Kobi Dies hängt von Ihrer Definition von "gut" ab. Beispielsweise ist die rekursive Lösung um eine Größenordnung schneller als die andere ( codepad.viper-7.com/CWgy7c ). Und es ist viel einfacher zu verstehen. Die rekursive Lösung ist so ziemlich die direkte Umwandlung der Grammatik in einen regulären Ausdruck (eigentlich könnte man sie einfach in grammatikalisierter Form schreiben, es würde funktionieren).
NikiC
1
@polygeniclubricants, Sie können dieses Muster mit zwei rekursiven Mustern abgleichen, eines, um as und bs ohne Erfassung zu verbrauchen (und überprüft, ob es dieselbe Menge mit Rekursion gibt), gefolgt von einem Erfassungsregex, der gierig alle a verbraucht, und wendet dann das rekursive Muster an Muster zu verbrauchen und zu überprüfen, ob es die gleiche Anzahl von bs und cs gibt. Der reguläre Ausdruck lautet : /^(?=(a(?-1)?b)c)a+(b(?-1)?c)$/x. Gutschrift an: nikic.github.io/2012/06/15/…
Josh Reback
11

Wie in der Frage erwähnt - mit der .NET-Ausgleichsgruppe können die Muster vom Typ a n b n c n d n … z n 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

kennytm
quelle
1
@poly: Danke :). Eigentlich bin ich mit .NET-Mustern nicht vertraut, aber für diese Art von Mustern ist es sehr einfach, Gruppen auszugleichen. Deshalb ergänze ich diese Antwort.
Kennytm
Kannst du das mit rekursivem Muster machen? Denn wenn Sie nicht können, ist das eine interessante Wendung, die Balancing Group Dinge tun kann, die rekursives Muster nicht kann. (Und ja, ich schätze die Ergänzung sehr).
Polygenelubricants
Der Grund, warum ich die .NET-Lösung weggelassen habe, war übrigens, dass ich Pläne für "Wie können wir a^n b^nmit .NET-Regex übereinstimmen ?" habe. Artikel in der Zukunft, aber Sie können ihn gerne schreiben, wenn Sie möchten. Ich mache diese Artikel nicht nur für mich selbst; Ich möchte andere dazu ermutigen, auch gute Inhalte auf der Website zu haben.
Polygenelubricants
Bitte aktualisieren Sie, wenn Sie einen Weg finden, dies mit rekursiven Mustern zu tun. Ich habe mit ausgleichenden Gruppen herumgespielt, um Wörter zu erfassen, deren Länge eine Fibonacci-Serie ergibt, und konnte sie nicht zum Laufen bringen. Es kann möglich sein, sich umzuschauen, ähnlich wie ich es getan habe.
Kobi
1
Ich möchte nur darauf hinweisen, dass die PCRE-Version dieses Musters leicht fehlerhaft ist, da sie übereinstimmt, wenn der nächste Teil der Zeichen länger als der vorherige ist. Siehe hier: regex101.com/r/sdlRTm/1 Sie müssen hinzufügen (?!b), (?!c)usw. , nachdem die Aufnahmegruppen wie so: regex101.com/r/sdlRTm/2
jaytea