كيفية التعامل مع مباريات Neverending من regexes المقدمة من المستخدم

Question

لننظر في الخطين التاليين في C# (باستخدام Framework .NET 3.5)

Regex regex = new Regex(@"^((E|e)t )?(M|m)oi (?<NewName>[A-Za-z]\.?\w*((\-|\s)?[A-Za-z]?\w{1,})+)$", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Match m = regex.Match("moi aussi jaimerai etre un ordinateur pour pas m'énnerver ");

(آسف إنه برنامج فرنسي :))

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

هل يعرف أحدهم ما إذا كانت هذه مشكلة معروفة في التعبير العادي .NET وإذا كانت هناك طريقة سهلة للعمل من حوله أو يجب عليّ ربط هذه الخطوط وإحباطها إذا لزم الأمر (بالتأكيد لا أرغب في القيام بذلك ).

Answer 1

أعتقد أنه يجب عليك ببساطة تشغيل مطابقة Regex على سلسلة رسائل منفصلة والسماح بإحباطها إذا تم الوصول إلى الحد الأقصى لوقت معين.

Answer 2

إذا أدخلت التعبير في regexbuddy ، فإنه يعرض الرسالة التالية

تم إحباط محاولة المباراة في وقت مبكر لأن التعبير العادي معقد للغاية. قد لا يكون محرك Regex الذي تخطط لاستخدامه به قادرًا على التعامل معه على الإطلاق والتعطل. ابحث عن "التراجع الكارثي" في ملف المساعدة لمعرفة كيفية تجنب هذا الموقف.

يبحث التراجع الكارثي يعطي التفسير التالي

تعبيرات منتظمة هاربة: التراجع الكارثي
النظر في التعبير العادي (x+x+)+y. قبل أن تصرخ في رعب وتقول إن هذا المثال المفتعل يجب أن يكتب على أنه xx+y لتتناسب تمامًا مع تلك الكميات المتداخلة بشكل رهيب: فقط افترض أن كل "X" يمثل شيئًا أكثر تعقيدًا ، مع وجود سلاسل معينة تتوافق مع كل من "X" . راجع القسم الخاص بملفات HTML أدناه للحصول على مثال حقيقي.

دعنا نرى ما يحدث عند تطبيق هذا regex على xxxxxxxxxy. أول x+ سوف يتطابق مع جميع الأحرف 10 ×. فشل x+ الثاني. أول x+ ثم تراجع عن 9 مباريات ، والثاني يلتقط x المتبقية. لقد تماثل المجموعة الآن مرة واحدة. تكرر المجموعة ، لكنها تفشل في أول X+. منذ تكرار واحد كان كافيا ، تطابق المجموعة. y تطابق y ويتم العثور على المباراة الشاملة. تم إعلان regex وظيفية ، ويتم شحن الكود إلى العميل ، وينفجر جهاز الكمبيوتر الخاص به. تقريبيا.

يتحول Regex أعلاه القبيح عندما تكون Y مفقودة من سلسلة الموضوع. عندما تفشل y ، فإن محرك regex يتراجعون. المجموعة لديها تكرار واحد يمكن أن تتراجع. تطابق X+ الثاني فقط X ، لذلك لا يمكن التراجع. ولكن أول x+ يمكن أن يتخلى عن x واحد. يطابق X+ الثاني على الفور xx. المجموعة لديها مرة أخرى تكرار واحد ، وفشل التكرار التالي ، وفشل Y. التراجع مرة أخرى ، يحتوي X+ الثاني الآن على موضع تراجع واحد ، مما يقلل من مطابقة X. المجموعة تحاول التكرار الثاني. تطابق X+ الأول ولكن الثانية عالقة في نهاية السلسلة. التراجع مرة أخرى ، يقلل أول X+ في التكرار الأول للمجموعة إلى 7 أحرف. يطابق X+ الثاني xxx. فشل Y ، يتم تقليل x+ الثاني إلى xx ثم x. الآن ، يمكن للمجموعة مطابقة التكرار الثاني ، مع X واحد لكل X+. ولكن هذا (7،1) ، (1،1) مزيج فشل أيضا. لذلك يذهب إلى (6،4) ثم (6،2) (1،1) ثم (6،1) ، (2،1) ثم (6،1) ، (1،2) ثم أنا أعتقد أنك تبدأ في الحصول على الانجراف.

إذا جربت هذا regex على سلسلة 10x في مصحح الأخطاء في RegexBuddy ، فسوف يستغرق الأمر 2558 خطوة لمعرفة النهائي y مفقود. لسلسلة 11x ، يحتاج إلى 5118 خطوة. لمدة 12 ، يستغرق 10238 خطوة. من الواضح أن لدينا تعقيد أسي لـ O (2^n) هنا. في 21x ، ينحني مصحح الأخطاء عند 2.8 مليون خطوة ، حيث تشخيص حالة سيئة من التراجع الكارثي.

regexbuddy تسامح لأنه يكتشف أنه يسير في دوائر, ، ويؤدي محاولة المباراة. سوف تستمر محركات Regex الأخرى (مثل .NET) إلى الأبد, ، في حين أن الآخرين سوف يتعطلون مع سعة مكدس (مثل Perl ، قبل الإصدار 5.10). تعتبر فائض المكدس سيئًا بشكل خاص على النوافذ ، لأنها تميل إلى جعل تطبيقك يختفي دون تتبع أو تفسير. كن حذرًا جدًا إذا قمت بتشغيل خدمة ويب تتيح للمستخدمين توفير تعبيراتهم العادية. يتمتع الأشخاص الذين لديهم تجربة Little Regex بمهارة مفاجئة في التوصل إلى تعبيرات منتظمة معقدة بشكل كبير.

أفترض أنك ستضطر إلى التعامل معها في الكود. أقترح عليك الاتصال بمؤلف كتاب " regexbuddy واسأل ما هو مطلوب لاكتشاف هذا السيناريو.

Answer 3

بشكل عام ، يمكن أن تستغرق التعبيرات العادية وقتًا أطول مما تتوقع. يجب عليك تجربة التعبير العادي إلى أداة مثل المنظم.

Answer 4

المشكلة هي أن لديك "حلقات" متداخلة في regex ، والتي تجعلها غير فعالة بشكل رهيب (بحيث تستغرق أساسًا إلى الأبد بسبب تعقيد التعبير).

إذا قلت ما ترغب في مطابقة ، يمكنني محاولة اكتشاف Regex أكثر كفاءة لذلك.

Answer 5

يبدو لي أنه مثل حالة regex تنمو بشكل كبير. انظر مدونة BCL.

أفضل حل هو تعيين مهلة على regex ، لا تعبث مع المواضيع.

انظر هنا كيف تجريد الأوتار مع مهلة.