पुनरावर्ती उप-पैटर्न के साथ नियमित अभिव्यक्ति इंजन पार्स रेगेक्स कैसे करता है?

Question

यह नियमित अभिव्यक्ति से मेल खाता खोल देना: ^((.)(?1)\2|.?)$

यह कैसे काम करता आसपास मेरे सिर लपेटो नहीं कर सकते। रिकर्सन कब समाप्त होता है, और जब रेगेक्स रिकर्सिव सबपर्टर्न से टूट जाता है और "|.?" भाग पर जाता है?

धन्यवाद।

संपादित करें: माफ करना मैं \2 और (?1)

(?1) की व्याख्या नहीं था - (अपने आप को) पहली subpattern को संदर्भित करता है

\2 - दूसरे subpattern के एक मैच था जिसमें (.)

है वापस करने के लिए संदर्भ

PHP में लिखे गए उदाहरण के ऊपर। मेल खाता है दोनों "अब्बा" (कोई मध्य विलोमपद चरित्र) और "abcba" - एक मध्यम, गैर परिलक्षित चरित्र

Answer 1

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

^ और $ दावा शुरुआत और क्रमशः स्ट्रिंग के अंत है। हम दोनों के बीच में सामग्री है, जो और अधिक रोचक है पर नजर डालते हैं: पहला हिस्सा (.)(?1)\2 पर

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

देखो, हम देख सकते हैं कि यह अंत में किसी भी चरित्र, और है कि एक ही चरित्र बनाने का प्रयास करेगा (वापस संदर्भ \2, जो (.) से मेल खाने वाले चरित्र को संदर्भित करता है)। बीच में, यह पूरी तरह से कैप्चरिंग समूह 1 के लिए मिल जाएगा। ध्यान दें कि (.) शुरुआत में एक वर्ण से मेल खाता है और \2 अंत में उसी वर्ण से मेल खाता है) जिसके लिए स्ट्रिंग कम से कम होने की आवश्यकता होती है 2 अक्षर पहले भाग का उद्देश्य स्ट्रिंग के समान सिरों को दोहरा रहा है।

दूसरे भाग .? पर देखें, हम देख सकते हैं कि यह एक या 0 वर्ण से मेल खाएगा। यह केवल तब मिलान किया जाएगा जब स्ट्रिंग में प्रारंभिक लंबाई 0 या 1 हो, या रिकर्सिव मैच से बचे हुए के बाद 0 या 1 वर्ण हो। स्ट्रिंग को दोनों सिरों से कटा हुआ होने के बाद दूसरे भाग का उद्देश्य रिक्त स्ट्रिंग या एकल अकेला चरित्र से मेल खाना है।

पुनरावर्ती मिलान काम करता है:

• पूरी स्ट्रिंग पारित करने के लिए विलोमपद, ^ और $ द्वारा माँगे होना चाहिए। हम किसी भी यादृच्छिक स्थिति से मिलान शुरू नहीं कर सकते हैं।
• यदि स्ट्रिंग < = 1 वर्ण है, तो यह गुजरती है।
• यदि स्ट्रिंग> 2 वर्ण है, चाहे इसे स्वीकार किया गया हो, केवल पहले भाग द्वारा तय किया जाता है। और यदि मैचों में 2 सिरों से कटा हुआ किया जाएगा।
• बचाए जाने पर बचे हुए, केवल 2 सिरों द्वारा कटाया जा सकता है, या यदि इसकी लंबाई < = 1 है तो गुजरती है।

Answer 2

regex अनिवार्य रूप से निम्नलिखित छद्म कोड के बराबर है:

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

मैं PCRE regexps के लिए किसी भी अच्छा डिबगिंग उपयोगिता नहीं मिली है।

$ 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 
------------------------------------------------------------------ 

पर्ल PCRE की तुलना में बेहतर डीबगिंग टूल है, echo 123454321 | perl -Mre=debug -ne '/^((.)(?1)\2|.?)$/x' का प्रयास करें: अधिक मैं मिल सकता है बाईटकोड डंप करने के लिए कैसे किया गया था। यह न केवल कुछ बाईटकोड कि PCRE जैसी ही है देता है, लेकिन यह भी हर कदम से पता चलता है, और भस्म और प्रत्येक चरण में इनपुट के कुछ हिस्सों शेष:

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

आप देख सकते हैं, पर्ल पहले सभी इनपुट की खपत (.) तक रिकर्सिंग विफल हो जाती है, फिर बैकट्रैकिंग शुरू होती है और दूसरी शाखा को .? से बदलती है और शेष भाग \2 का शेष भाग होता है, जब यह अंततः सफल होने तक बैकट्रैक विफल रहता है।