Come si analizza il motore di espressioni regolari con i subpattern ricorsivi?

Question

Questa espressione regolare corrisponde palindromi: ^((.)(?1)\2|.?)$

Non può avvolgere la mia testa intorno come funziona. Quando termina la ricorsione e quando l'espressione regolare si interrompe dal subpattern ricorsivo e passa alla parte "|.?"?

Grazie.

edit: mi dispiace, non ho spiegato \2 e (?1)

(?1) - si riferisce al primo criterio (a se stessa)

\2 - back-riferimento ad un match di secondo sotto-regola, che è (.)

Sopra l'esempio scritto in PHP. Risultati entrambi "abba" (senza carattere palindromo metà) e "ABCBA" - ha un mezzo, carattere non riflette

Answer 1

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

Il ^ e $ afferma l'inizio e la fine della stringa rispettivamente. Vediamo il contenuto in mezzo, che è più interessante:

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

Guarda la prima parte (.)(?1)\2, possiamo vedere che cercherà di adattarsi a qualsiasi carattere, e lo stesso carattere alla fine (riferimento all'indietro \2, che si riferisce al carattere corrispondente a (.)). Nel mezzo, corrisponderà ricorsivamente all'intero gruppo di cattura 1. Si noti che vi è un'asserzione implicita (causata da (.) corrispondente a un carattere all'inizio e \2 corrispondente allo stesso carattere alla fine) che richiede che la stringa sia almeno 2 personaggi. Lo scopo della prima parte è tagliare le estremità identiche della stringa, in modo ricorsivo.

Guarda la seconda parte .?, possiamo vedere che corrisponderà a uno o a 0 caratteri. Questo sarà abbinato solo se la stringa ha inizialmente lunghezza 0 o 1, o dopo che l'avanzo dalla corrispondenza ricorsiva è 0 o 1 carattere. Lo scopo della seconda parte è quello di abbinare la stringa vuota o il singolo carattere solitario dopo che la stringa è stata tagliata da entrambe le estremità.

L'abbinamento ricorsiva funziona:

• L'intera stringa deve essere palindromo di passare, affermato da ^ e $. Non possiamo iniziare la corrispondenza da nessuna posizione casuale.
• Se la stringa è < = 1 carattere, passa.
• Se la stringa è> 2 caratteri, se è accettata viene decisa solo dalla prima parte. E sarà tagliato da 2 fini se partite.
• Il rimanente se le partite, può essere troncato solo dai 2 estremi, o passa se la sua lunghezza è < = 1.

Answer 2

L'espressione regolare è sostanzialmente equivalente al seguente pseudo-codice:

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

non ho trovato alcuna utilità bello debug per espressioni regolari PCRE. Il più ho trovato è stato come discarica il bytecode:

$ 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 ha migliori strumenti di debug di PCRE, provare echo 123454321 | perl -Mre=debug -ne '/^((.)(?1)\2|.?)$/x'. Questo dà non solo un po 'di bytecode che è simile a quella di PCRE, ma mostra anche ogni passo, e il consumato e rimanente parti l'ingresso ad ogni passo:

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|.?)$" 

Come si può vedere, il Perl prima consuma tutti gli input ricorsivamente fino al (.) fallisce, quindi inizia il backtracking e prova il secondo ramo dall'alternazione .? e il resto della prima parte \2, quando fallisce il backtrack, fino a quando riesce finalmente.