48
क्या कोई ऐसा उपकरण है जो एक विशेष नियमित अभिव्यक्ति लेता है और नियमित अभिव्यक्तियों के साथ मिलान की एक निश्चित संख्या के लिए आवश्यक संचालन की संख्या के मामले में सबसे खराब स्थिति परिदृश्य लौटाता है?नियमित अभिव्यक्तियों के लिए सबसे खराब केस विश्लेषण
इसलिए उदाहरण के लिए, एक (f|a)oo.*[ ]baz को देखते हुए, कितने कदम इंजन संभवतः हालांकि जा सकता के माध्यम से 100 अक्षरों मैच के लिए?
मैं भी दिलचस्पी होगी अगर वहाँ एक उपकरण है कि पाठ के नमूने का एक समूह लेने के लिए और प्रत्येक रन के लिए औसत संचालन दिखा सकते हैं।
मुझे पता है इस इंजन का इस्तेमाल किया और कार्यान्वयन पर एक बहुत निर्भर करेगा - लेकिन मैं कैसे आम यह है के रूप में अज्ञानी हूँ। तो अगर यह कई भाषाओं के लिए आम है (मेरा प्रश्न बहुत अस्पष्ट बना रहा है) तो मुझे विशेष रूप से पर्ल और पायथन में दिलचस्पी होगी।
उत्कृष्ट सवाल! जाहिर है यह रेगेक्स पर निर्भर करेगा। यह अच्छी तरह से ज्ञात है कि शुद्ध regexes (यहां तक कि नीचे संदर्भित '(x + x +) + y' उदाहरण की तरह) एक शुद्ध परिमित-राज्य मशीन ऑटोमाटा स्वीकार करते हैं, लेकिन आम रेगेक्स पुस्तकालय वास्तव में बैकट्रैकिंग के साथ उन लोगों को लागू करते हैं, बड़े हिस्से में फैंसी का समर्थन करने के लिए संदर्भ की तरह सामान। आपके जैसे टूल का वर्णन http://en.wikipedia.org/wiki/Regular_expression_Denial_of_Service_-_ReDoS –