Wie parset Regulärer Ausdruck Engine regex mit rekursiven Subpattern?

Question

Dieser reguläre Ausdruck Palindrome: ^((.)(?1)\2|.?)$

kann nicht meinen Kopf wickeln um, wie es funktioniert. Wann endet die Rekursion, und wenn regex vom rekursiven Untermuster abbricht und zum "|.?" Teil geht?

Danke.

edit: sorry ich nicht \2 und (?1) erklären hat

(?1) - bezieht sich auf erste Unter-Pattern (an sich selbst)

\2 - Rückverweis auf eine Übereinstimmung der zweiten Untermuster, die (.)

ist

Oben beschriebenes Beispiel in PHP. Spielen beide „abba“ (keine Mitte Palindrom-Zeichen) und „abcba“ - hat einen mittleren, nicht reflektierte Charakter

Answer 1

^((.)(?1)\2|.?)$

Die ^ und $ den Anfang und das Ende des Strings bzw. behauptet. Lassen Sie uns zwischendurch auf den Inhalt schauen, was noch interessanter ist:

((.)(?1)\2|.?) 
1------------1 // Capturing group 1 
2-2   // Capturing group 2 

Blick auf den ersten Teil (.)(?1)\2, können wir sehen, dass es versuchen, alle Zeichen zu finden, und das gleiche Zeichen am Ende (Rückverweis \2, die sich auf das durch (.) gemachte Zeichen bezieht). In der Mitte wird es rekursiv für die gesamte Erfassungsgruppe 1 übereinstimmen. Beachten Sie, dass es eine implizite Assertion gibt (verursacht durch (.), die ein Zeichen am Anfang und \2 mit dem gleichen Zeichen am Ende übereinstimmt), die die Zeichenfolge mindestens benötigt 2 Zeichen. Der Zweck des ersten Teils besteht darin, die identischen Enden der Kette rekursiv zu zerhacken.

Betrachten Sie den zweiten Teil .?, können wir sehen, dass es ein oder 0 Zeichen übereinstimmen wird. Dies wird nur dann abgeglichen, wenn die Zeichenfolge anfänglich die Länge 0 oder 1 hat oder nachdem der Rest der rekursiven Übereinstimmung 0 oder 1 Zeichen lang ist. Der Zweck des zweiten Teils besteht darin, die leere Saite oder das einzelne einsame Zeichen abzustimmen, nachdem die Saite von beiden Enden abgeschnitten wurde.

Die rekursive Matching funktioniert:

• Die gesamte Zeichenfolge muss Palindrom sein, von ^ und $ behauptet passieren. Wir können nicht von irgendeiner zufälligen Position abgleichen.
• Wenn die Zeichenfolge < = 1 Zeichen ist, wird es übergeben.
• Wenn die Zeichenfolge> 2 Zeichen ist, wird nur vom ersten Teil entschieden, ob sie akzeptiert wird. Und wenn es Übereinstimmungen gibt, wird es um 2 Enden zerhackt.
• Der Rest, wenn Übereinstimmungen, kann nur durch die 2 Enden gehackt werden, oder besteht, wenn seine Länge < = 1 ist.

Answer 2

Die regex ist im wesentlichen äquivalent zu dem folgenden Pseudocode:

palin(str) { 
    if (length(str) >= 2) { 
     first = str[0]; 
     last = str[length(str)-1]; 
     return first == last && palin(substr(str, 1, length(str)-2)); 
    } else 
     // empty and single-char trivially palindromes 
     return true; 
} 

Answer 3

Ich habe gefunden, kein schönes Debugging-Dienstprogramm für PCRE regexps. Je mehr ich finden konnte, war, wie die Bytecode-Dump:

$ pcretest -b 
PCRE version 7.6 2008-01-28 

    re> /^((.)(?1)\2|.?)$/x 
------------------------------------------------------------------ 
    0 39 Bra 
    3 ^
    4 26 CBra 1 
    9 6 CBra 2 
14  Any 
15 6 Ket 
18 6 Once 
21 4 Recurse 
24 6 Ket 
27  \2 
30 5 Alt 
33  Any? 
35 31 Ket 
38  $ 
39 39 Ket 
42  End 
------------------------------------------------------------------ 

Perl besser Debugging-Tools als PCRE hat, versuchen echo 123454321 | perl -Mre=debug -ne '/^((.)(?1)\2|.?)$/x'. Dies gibt nicht nur einige Bytecode, die PCRE der ähnlich ist, aber es zeigt auch, jeden Schritt, und die und bei jedem Schritt Teile des Eingangs verbleibenden konsumierte:

Compiling REx "^((.)(?1)\2|.?)$" 
Final program: 
    1: BOL (2) 
    2: OPEN1 (4) 
    4: BRANCH (15) 
    5:  OPEN2 (7) 
    7:  REG_ANY (8) 
    8:  CLOSE2 (10) 
    10:  GOSUB1[-8] (13) 
    13:  REF2 (19) 
    15: BRANCH (FAIL) 
    16:  CURLY {0,1} (19) 
    18:  REG_ANY (0) 
    19: CLOSE1 (21) 
    21: EOL (22) 
    22: END (0) 
floating ""$ at 0..2147483647 (checking floating) anchored(BOL) minlen 0 
Guessing start of match in sv for REx "^((.)(?1)\2|.?)$" against "12321" 
Found floating substr ""$ at offset 5... 
Guessed: match at offset 0 
Matching REx "^((.)(?1)\2|.?)$" against "12321" 
    0 <> <12321>    | 1:BOL(2) 
    0 <> <12321>    | 2:OPEN1(4) 
    0 <> <12321>    | 4:BRANCH(15) 
    0 <> <12321>    | 5: OPEN2(7) 
    0 <> <12321>    | 7: REG_ANY(8) 
    1 <1> <2321>    | 8: CLOSE2(10) 
    1 <1> <2321>    | 10: GOSUB1[-8](13) 
    1 <1> <2321>    | 2: OPEN1(4) 
    1 <1> <2321>    | 4: BRANCH(15) 
    1 <1> <2321>    | 5:  OPEN2(7) 
    1 <1> <2321>    | 7:  REG_ANY(8) 
    2 <12> <321>    | 8:  CLOSE2(10) 
    2 <12> <321>    | 10:  GOSUB1[-8](13) 
    2 <12> <321>    | 2:  OPEN1(4) 
    2 <12> <321>    | 4:  BRANCH(15) 
    2 <12> <321>    | 5:   OPEN2(7) 
    2 <12> <321>    | 7:   REG_ANY(8) 
    3 <123> <21>    | 8:   CLOSE2(10) 
    3 <123> <21>    | 10:   GOSUB1[-8](13) 
    3 <123> <21>    | 2:   OPEN1(4) 
    3 <123> <21>    | 4:   BRANCH(15) 
    3 <123> <21>    | 5:    OPEN2(7) 
    3 <123> <21>    | 7:    REG_ANY(8) 
    4 <1232> <1>    | 8:    CLOSE2(10) 
    4 <1232> <1>    | 10:    GOSUB1[-8](13) 
    4 <1232> <1>    | 2:    OPEN1(4) 
    4 <1232> <1>    | 4:    BRANCH(15) 
    4 <1232> <1>    | 5:     OPEN2(7) 
    4 <1232> <1>    | 7:     REG_ANY(8) 
    5 <12321> <>    | 8:     CLOSE2(10) 
    5 <12321> <>    | 10:     GOSUB1[-8](13) 
    5 <12321> <>    | 2:     OPEN1(4) 
    5 <12321> <>    | 4:     BRANCH(15) 
    5 <12321> <>    | 5:      OPEN2(7) 
    5 <12321> <>    | 7:      REG_ANY(8) 
                 failed... 
    5 <12321> <>    | 15:     BRANCH(19) 
    5 <12321> <>    | 16:      CURLY {0,1}(19) 
                 REG_ANY can match 0 times out of 1... 
    5 <12321> <>    | 19:      CLOSE1(21) 
                  EVAL trying tail ... 9d86dd8 
    5 <12321> <>    | 13:       REF2(19) 
                  failed... 
                 failed... 
                 BRANCH failed... 
    4 <1232> <1>    | 15:    BRANCH(19) 
    4 <1232> <1>    | 16:     CURLY {0,1}(19) 
                REG_ANY can match 1 times out of 1... 
    5 <12321> <>    | 19:     CLOSE1(21) 
                 EVAL trying tail ... 9d86d70 
    5 <12321> <>    | 13:      REF2(19) 
                 failed... 
    4 <1232> <1>    | 19:     CLOSE1(21) 
                 EVAL trying tail ... 9d86d70 
    4 <1232> <1>    | 13:      REF2(19) 
                 failed... 
                failed... 
                BRANCH failed... 
    3 <123> <21>    | 15:   BRANCH(19) 
    3 <123> <21>    | 16:    CURLY {0,1}(19) 
               REG_ANY can match 1 times out of 1... 
    4 <1232> <1>    | 19:    CLOSE1(21) 
                EVAL trying tail ... 9d86d08 
    4 <1232> <1>    | 13:     REF2(19) 
                failed... 
    3 <123> <21>    | 19:    CLOSE1(21) 
                EVAL trying tail ... 9d86d08 
    3 <123> <21>    | 13:     REF2(19) 
                failed... 
               failed... 
               BRANCH failed... 
    2 <12> <321>    | 15:  BRANCH(19) 
    2 <12> <321>    | 16:   CURLY {0,1}(19) 
              REG_ANY can match 1 times out of 1... 
    3 <123> <21>    | 19:   CLOSE1(21) 
               EVAL trying tail ... 9d86ca0 
    3 <123> <21>    | 13:    REF2(19) 
    4 <1232> <1>    | 19:    CLOSE1(21) 
               EVAL trying tail ... 0 
    4 <1232> <1>    | 13:    REF2(19) 
    5 <12321> <>    | 19:    CLOSE1(21) 
    5 <12321> <>    | 21:    EOL(22) 
    5 <12321> <>    | 22:    END(0) 
Match successful! 
Freeing REx: "^((.)(?1)\2|.?)$" 

Wie Sie sehen können, Perl verbraucht zuerst alle Eingaben rekursiv bis (.) schlägt fehl, dann beginnt Backtracking und versucht den zweiten Zweig von der Alternation .? und den Rest des ersten Teils \2, wenn das fehlschlägt Backtracks, bis es schließlich erfolgreich ist.