كيف يكتشف نمط PCRE هذا palindromes؟

Question

_{هذا السؤال هو مظاهرة تعليمية لاستخدام Lookahead ، والمرجع المتداخل ، والشرطية في نمط PCRE لتتناسب مع جميع palindromes ، بما في ذلك تلك التي لا يمكن مطابقتها بالنمط العودية الواردة في صفحة MAN PCRE.}

فحص نمط PCRE هذا في مقتطف PHP:

$palindrome = '/(?x)
^
  (?:
      (.) (?=
              .*
              (
                \1
                (?(2) \2 | )
              )
              $
          )
  )*
  .?
  \2?
$


/';

يبدو أن هذا النمط يكتشف palindromes ، كما هو موضح في حالات الاختبار هذه (انظر أيضا على ideone.com):

$tests = array(
  # palindromes
  '',
  'a',
  'aa',
  'aaa',
  'aba',
  'aaaa',
  'abba',
  'aaaaa',
  'abcba',
  'ababa',

  # non-palindromes
  'aab',
  'abab',
  'xyz',
);

foreach ($tests as $test) {
  echo sprintf("%s '%s'\n", preg_match($palindrome, $test), $test);  
}

فكيف يعمل هذا النمط؟

---

ملحوظات

يستخدم هذا النمط أ إشارة متداخلة, ، وهي تقنية مماثلة تستخدم في كيف يكتشف جافا Regex هذا palindromes؟, ، ولكن على عكس نمط Java ، لا يوجد Lookbehind (لكنه يستخدم ملف الشرط).

لاحظ أيضًا أن PCRE صفحة الرجل يقدم نمطًا متكررًا لتتناسب مع بعض palindromes:

# the recursive pattern to detect some palindromes from PCRE man page
^(?:((.)(?1)\2|)|((.)(?3)\4|.))$

تحذر صفحة الرجل من أن هذا النمط المتكرر لا يمكنه اكتشاف جميع palindromes (انظر: لماذا ستتطابق هذا Regex المتكرر فقط عندما تكرر الشخصية 2^ن - 1 مرات؟ و أيضا على ideone.com) ، لكن النمط المرجعي المتداخل/النموذج الإيجابي المقدم في هذا السؤال يمكن.

Answer 1

دعونا نحاول أن نفهم regex من خلال بنائه. أولاً ، يجب أن تبدأ palindrome وتنتهي بنفس تسلسل الحرف في الاتجاه المعاكس:

^(.)(.)(.) ... \3\2\1$

نريد إعادة كتابة هذا بحيث ... يتبعه فقط طول أنماط محدودة ، بحيث يكون من الممكن أن نحوله إلى أ *. هذا ممكن مع lookahead:

^(.)(?=.*\1$)
 (.)(?=.*\2\1$)
 (.)(?=.*\3\2\1$) ...

ولكن لا تزال هناك أجزاء غير شائعة. ماذا لو استطعنا "تسجيل" المجموعات التي تم التقاطها مسبقًا؟ إذا كان من الممكن أن نتمكن من إعادة كتابته على النحو التالي:

^(.)(?=.*(?<record>\1\k<record>)$)   # \1     = \1 + (empty)
 (.)(?=.*(?<record>\2\k<record>)$)   # \2\1   = \2 + \1
 (.)(?=.*(?<record>\3\k<record>)$)   # \3\2\1 = \3 + \2\1
 ...

التي يمكن تحويلها إلى

^(?: 
    (.)(?=.*(\1\2)$)
 )*

جيد تقريبا ، باستثناء ذلك \2 (الالتقاط المسجل) ليس فارغًا في البداية. سوف يفشل فقط في مطابقة أي شيء. نحن بحاجة إلى مطابقة فارغة إذا لم يكن الالتقاط المسجل موجودًا. هذه هي الطريقة التي يتسلل التعبير الشرطي في.

(?(2)\2|)   # matches \2 if it exist, empty otherwise.

لذلك يصبح تعبيرنا

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*

الآن يطابق النصف الاول من palindrome. ماذا عن النصف الثاني؟ حسنًا ، بعد مطابقة الشوط الأول ، التقاط المسجل \2 سوف تحتوي على النصف الثاني. لذلك دعونا فقط نضعه في النهاية.

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*\2$

نريد أن نعتني بال palindrome ذات الطول الفردي أيضًا. سيكون هناك شخصية مجانية بين الشوط الأول والثاني.

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2$

هذا يعمل بشكل جيد إلا في حالة واحدة - عندما يكون هناك حرف واحد فقط. هذا مرة أخرى بسبب \2 لا يتطابق مع شيء. لذا

^(?: 
    (.)(?=.*(\1(?(2)\2|))$)
 )*.?\2?$
#      ^ since \2 must be at the end in the look-ahead anyway.