مدونة ماكيومار تحميل...

مدونة ماكيومار

التصنيفات

مبدأي الطمع والكسل في التعبيرات المنتظمة Gready and Lazy quantifiers

16/03/2019
0 تعليقات 
التعبيرات المنتظمة
       

قيم 0من  0 تقيم

محددات الكميات الطماعة Greedy quantifiers

تعرفنا على محددات الكميات Regex Quantifiers التي نستطيع من خلالها التحكم في عدد المطابقات وذكرنا أن النجمة * أو علامة الجمع + تقوم بمحاولة جلب أكبر قدر من المطابقات. هذا مانقصده بالطمع، وهو أنها طماعة ومتعطشة دائما لجلب أكبر قدر من المطابقات.
وهنا نستطيع تعريف محدد الكمية الطماع بأنه المحدد الذي يقوم بتكرار رمز Atom معين في النمط أكبر قدر من الإمكان، للحصول على أكبر قدر من المطابقات قبل الإنتقال للرمز التالي في النمط. ولكن أحيانً هذا الطمع يجعل النمط يفشل في مرحلة ما، فيقوم المحرك بالتخلي أن جزء من طمعه تدريجياً محاولاً مطابقة كامل النمط وهذا ما نسميه التتبع الخلفي Regex backtracking.
مثلاً عند تطبيق النمط \d+.+\d+ على النص 123abc8 يأخذ المحرك الخطوات التالية:
  • يقوم المحرك بتطبيق النمط \d فيقوم بالمطابقة مع 1
  • يجد المحرك أنه يحتاج لتكرار الرمز \d بسبب وجود + فيستكمل المطابقة حتى يطابق 123
  • ينتقل المحرك إلى النقطة . التي تطابق أي شيء (ليس كل شيء) وبالتالي تطابق a
  • يجد المحرك أنه يحتاج لتكرار الرمز . بسبب وجود + فيستكمل المطابقة حتى يطابق abc8
  • النص الآن انتهى ومازال هناك رمز في النمط لم يتم مطابقته وهو \d+
  • يعرف المحرك أنه كان طماعاً أكثر من اللازم فيقوم بالتخلي عن جزء من المطابقة التي نتجت عن تطبيق .+ فيقوم بالتراجع حرف واحد من المطابقة لتصبح abc
  • ينتقل المحرك إلى \d+ فتحدث مطابقة مع 8

مثال آخر:

عند تطبيق النمط .+apple على الجملة [ien]A tasty apple[/ien] يأخذ المحرك الخطوات التالية:

  • تقوم . بمطابقة الحرف A
  • بسبب وجود + يقوم المحرك بمطابقة كامل النص
  • ينتقل المحرك في النمط لمحاولة مطابقة a، لكن النص انتهى
  • يعرف المحرك أنه كان طماعاً أكثر من اللازم فيقوم بالتخلي عن جزء من المطابقة التي نتجت عن تطبيق .+ فيقوم بالتراجع حرف واحد من المطابقة، أي الحرف e.
  • يحاول المحرك مطابقة a مع e لكن لايحدث تطابق
  • يعود المحرك مرة أخرى إلى نتيجة مطابقة .+ ليتخلى عن حرف آخر وهو L
  • يحاول المحرك مطابقة a مع L لكن لايحدث تطابق
  • يعود المحرك مرة أخرى إلى نتيجة مطابقة .+ ليتخلى عن حرف آخر وهو p الثانية
  • يحاول المحرك مطابقة a مع p لكن لايحدث تطابق
  • يعود المحرك مرة أخرى إلى نتيجة مطابقة .+ ليتخلى عن حرف آخر وهو p الأولى
  • يحاول المحرك مطابقة a مع p لكن لايحدث تطابق
  • يعود المحرك مرة أخرى إلى نتيجة مطابقة .+ ليتخلى عن حرف آخر وهو a
  • يحاول المحرك مطابقة a مع a وهنا يحدث التطابق
  • يقوم المحرك باستكمال كامل النمط ليحدث التطابق مع apple في النص.

محددات الكميات الكسلانة Lazy quantifiers

إذا كانت محددات الكميات الطماعة تقوم بالمطابقة قدر الإمكان، مع إمكانية التخلي عن جزء من المطابقة إذا تسبب الطمع في فشل باقي النمط، فإن محددات الكميات الكسلانة تقوم بالمطابقة بأقل قدر ممكن، محاولة مطابقة باقي النمط أولاً وفي حالة فاشل باقي النمط يقوم بزيادة عدد المطابقات واحدة تلو أخرى حتى تحدث مطابقة كامل النمط.

يتم تحويل محددة الكمية من طماع إلى كسلان باستخدام علامة الإستفهام قبل مُحدِد الكمية هكذا +?

مثلاً عند تطبيق النمط \d+.+?\d+ على النص 123abc8 يأخذ المحرك الخطوات التالية:

  • يقوم المحرك بتطبيق النمط \d فيقوم بالمطابقة مع 1
  • يجد المحرك أنه يحتاج لتكرار الرمز \d بسبب وجود + يطابق 123
  • ينتقل المحرك إلى النقطة . التي تطابق أي شيء فتطابق  a
  • يجد المحرك أنه بحاجة لتكرار .  ولكن بسبب وجود ? فيطابق أقل مايمكن وبالتالي يكتفي مؤقتاً بالحرف a
  • ينتقل المحرك للرمز \d
  • يحاول المحرك مطابقة \d مع b فيفشل
  • يقرر المحرك الرجوع إلى .+ لزيادة المطابقات بمقدار واحد فيطابق ab
  • ينتقل المحرك إلى النقطة \d
  • يحاول المحرك في مطابقة \d مع c فيفشل
  • يقرر المحرك الرجوع إلى .+ لزيادة المطابقات بمقدار واحد فيطابق abc
  • ينتقل المحرك إلى النقطة \d
  • يحاول المحرك مطابقة \d مع 8 فينجح
  • بما أن + تكتفي بمطابقة واحده ينجح كامل النمط

لاحظ إذا قمنا باستخدام  .* بدلا عن .+ في المثال السابق فإن أقل شيء يمكن مطابقته هنا هو اللاشيء لأن * تطابق لاشيء أو أكثر، وبالتالي يأخذ المحرك الخطوات التالية

  • يقوم المحرك بتطبيق النمط \d فيقوم بالمطابقة مع 1
  • يجد المحرك أنه يحتاج لتكرار الرمز \d بسبب وجود + يطابق 123
  • ينتقل المحرك إلى النقطة . التي تطابق أي شيء ولكن يمكن للمحرك مطابقة اللاشيء بسبب * فيتم التطابق مع اللاشيء
  • يجد المحرك أنه بحاجة لتكرار . لاشيء أو أكثر ولكن بسبب وجود ? فيطابق أقل مايمكن وبالتالي يكتفي مؤقتاً باللاشيء (أي يظل موضع المحرك في النص قبل الحرف a)
  • ينتقل المحرك للرمز \d
  • يحاول المحرك في مطابقة \d مع a فيفشل
  • يقرر المحرك الرجوع إلى .+ لزيادة المطابقات بمقدار واحد فيطابق a
  • يحاول المحرك في مطابقة \d مع b فيفشل
  • يقرر المحرك الرجوع إلى .+ لزيادة المطابقات بمقدار واحد فيطابق ab
  • ينتقل المحرك إلى النقطة \d
  • يحاول المحرك مطابقة \d مع c فيفشل
  • يقرر المحرك الرجوع إلى .+ لزيادة المطابقات بمقدار واحد فيطابق abc
  • ينتقل المحرك إلى النقطة \d
  • يحاول المحرك مطابقة \d مع 8 فينجح
  • بما أن + تكتفي بمطابقة واحده ينجح كامل النمط

يجب الحذر عند استخدام محددات الكميات مع النقطة . لأنها قد تؤدي إلا نتائج غير متوقعة. فمثلا إذا أردت البحث عن النصوص التي توجد داخل علامة التنصيص Double quotes وليكن “string” ، فإن استخدام النمط  /”.*”/ سيفى بالغرض عند تطبيقه على الجملة [ien]Put a “string” between double quotes[/ien] لكن عند تطبيقه على الجملة [ien]These are “string one” and “string two”[/ien] تكون نتيجة المطابقة هي “string one” and “string two” لأن * ستجعل المحرك لن يتوقف عن مطابقة النقطة حتى ينتهي النص. وبالتالي نحتاج لأن نخبر المحرك بأن يطابق النقطة أقل مايمكن في النص عن طريق تحويل أداء النجمة * إلى نجمة كسولة بوضع علامة ؟ بعد النجمة. وبالتالي عندما يجد أول مطابقة “string one” سيقوم باسترجاع المطابقة ولكن سيجد أن النص مازال لم ينتهي فيقوم  بتطبيق النمط مرة أخرى على ما تبقى من النص فيجد مطابقة أخرى وهي “string two” وسبق وشرحنا كيف يتحول المحرك من حالة الطمع إلى الكسل.

اترك تعليقاً

من نفس التصنيف