रेग्युलर ऍक्सप्रैशन

इतिहास

रेग्युलर ऍक्सप्रैशन की जड़ें ऑटोमेटा सिद्धांत एवं औपचारिक भाषा सिद्धांत में निहित हैं, दोनों ही सैद्धांतिक कंप्यूटर विज्ञान के अंग हैं। ये क्षेत्र प्रशिक्षण कंप्यूटेशन (ऑटोमेटा) एवं औपचारिक भाषाओं के वर्णन एवं वर्गीकरण की पद्धतियों के मॉडल हैं। 1950 के दशक में, गणितज्ञ स्टीफेन कोल क्लीन ने अपने गणितीय संकेतन का प्रयोग करते हुए इन मॉडलों का सविस्तार वर्णन किया, जिसे रेगुलर सेट्स कहते हैं। SNOBOL की भाषा पैटर्न मिलान कराने का आरंभिक उपकरण था, लेकिन रेग्युलर ऍक्सप्रैशन के सदृश नहीं. केन थॉम्पसन ने टेक्स्ट फाइल्स में पैटर्न्स के मिलान कराने के माध्यम के रूप में क्लीन के संकेतन का उपयोग संपादक QED के गठन में किया। बाद में उन्होंने Unix संपादक ed में इस क्षमता को जोड़ा, जिसने अंततः रेग्युलर ऍक्सप्रैशन के उपयोग के लिए लोकप्रिय खोजी उपकरण ग्रेप का पता लगाया ("grep" शब्द रेग्युलर ऍक्सप्रैशन ed संपादक की खोज के कमांड से लिया गया है g/re/p जिसमें re रेग्युलर ऍक्सप्रैशन का द्योतक है). समयांतराल से, रेग्युलर ऍक्सप्रैशन के थॉम्पसन के मौलिक रूपांतर में कई बदलाव आए हैं, जिनका व्यापक प्रयोग Unix और Unix जैसी ही प्रयोज्यता, expr, AWK, Emacs, vi और lex सहित हुआ है।
Perl और Tcl रेग्युलर ऍक्सप्रैशन हेनरी स्पेंसर लिखित रिजेक्स लाइब्रेरी से ली गई थीं, हालांकि Perl को स्पेंसर की लाइब्रेरी में अनेक नई विशेषताएं जोड़ने के लिए प्रसारित किया गया।फिलिप हेज़ेल ने PCRE (पर्ल कम्पैटिबल रेग्युलर ऍक्सप्रैशन) को विकसित किया, जो पर्ल की रेग्युलर ऍक्सप्रैशन की कार्यशीलता की लगभग नकल करने की कोशिश करता है, एवं अनेक आधुनिक उपकरणों PHP और Apache HTTP Server के द्वारा प्रयोग में लाया जाता है। Perl 6 की डिज़ाइन की प्रचेष्टा का एक हिस्सा पर्ल के रेग्युलर ऍक्सप्रैशन के एकीकरण में सुधार तथा उनके कार्यक्षेत्र एवं क्षमताओं को बढ़ाना ताकि सूचकों की पदव्याख्या के व्याकरण को परिभाषित करने का मौका दिया जा सके. परिणामस्वरूप एक लघु भाषा Perl 6 नियम बनी, जिसका प्रयोग Perl 6 ग्रामर को परिभाषित करने और साथ ही साथ भाषा में प्रोग्रामर्स के लिए उपकरण मुहैया कराने के लिया होता है। ये नियम पर्ल 5.x रेग्युलर ऍक्सप्रैशन की विशेषताओं को कायम रखते हैं, लेकिन उप-नियमों के द्वारा पुनःप्रवाही सुंदर पद व्याख्या की BNF-शैली की परिभाषा को भी अनुमति प्रदान करते हैं।
दस्तावेज़ और डाटाबेस मॉडलिंग के लिए संरचित सूचना मानकों में रेग्युलर ऍक्सप्रैशन का प्रयोग 1960 के दशक में आरंभ हुआ और 1980 के दशक में फैल गया, जब ISO SGML (ANSI "GCA 101-1983" द्वारा पूर्व आरोपित) उद्योग मानक समेकित हुए. भाषा मानकों में संरचना की सुस्पष्टता के केंद्र में रेग्युलर ऍक्सप्रैशन हैं। समूह वाक्य विन्यास में DTD तत्व का सरल उपयोग स्पष्ट है।
पैटर्न मिलान: इतिहास भी देखें

रेग्युलर ऍक्सप्रैशन की निर्णायक तुल्यता

जैसा कि उदाहरणों को देखने से पता चलता है, विभिन्न रेग्युलर ऍक्सप्रैशन उसी भाषा को अभिव्यक्त कर सकते हैं: रीतिवाद अनावश्यक है।
कलनविधि में लेखन संभव है जो दिए गए रेग्युलर ऍक्सप्रैशन के मध्य यह निर्णय करने के लिए कि उल्लिखित भाषाएं अनिवार्य रूप से एक समान हैं कि नहीं. यह प्रत्येक अभिव्यक्ति को न्यूनतम नियतात्मक परिमित स्थिति मशीन की हद तक कम कर देता है और निर्धारित करता है कि क्या वे समाकृतिक (एक ही आकार के) समकक्ष हैं या नहीं.
इस अनावश्यकता को किस हद तक निकाल दिया जा सकता है? क्या हम रेग्युलर ऍक्सप्रैशन का एक रोचक सबसेट खोज सकते हैं जो पूरी तरह सूचक हो? क्लीन तारा और सेट का गठबंधन स्पष्टतः आवश्यक है, लेकिन शायद हम उनके प्रयोग पर रोक लगा सकते हैं। यह आश्चर्यजनक रूप से कठिन समस्या में बदल सकता है। रेग्युलर ऍक्सप्रैशन इतने सरल हैं कि उन्हें किसी भी रूप में पुनः सुव्यवस्थित ढंग से लिखने की कोई प्रणाली है ही नहीं. अतीत में स्वतः प्रमाणन के अभाव में स्टार हाइट की समस्या खड़ी हो गई। हाल ही में, डेक्सटर कोज़ेन में रेग्युलर ऍक्सप्रैशन को क्लीन के बीजगणित के साथ स्वतः प्रमाणित कर दिया.

Perl-व्युत्पन्न रेग्युलर ऍक्सप्रैशन

POSIX बेसिक (BRE) और विस्तारित रेग्युलर ऍक्सप्रैशन मानकों (ERE) की तुलना में Perl के पास अधिक सुसंगत और समृद्ध वाक्य-विन्यास है। इसकी निरंतरता का एक उदाहरण है कि \ हमेशा गैर-वर्णान्कित अक्षरों से अलग भागता है। क्रियाशीलता का अन्य उदाहरण Perl के साथ तो संभव है, पर POSIX के साथ नहीं - अनुवर्ती रेग्युलर ऍक्सप्रैशन सुस्त परिमाणन की अवधारणा है (अगले अनुभाग में देखें).
व्यापक रूप से अपनी सूचक क्षमता के कारण कई अन्य प्रयोज्यता और प्रोग्रामिंग की भाषाओँ ने वाक्य-विन्यास को Perl की ही तरह अपना लिया है -- उदाहरण के लिए, Java, JavaScript, PCRE, Python, Ruby, Microsoft's .NET Framework और W3C's XML Schema सभी रेग्युलर ऍक्सप्रैशन वाक्य-विन्यास का प्रयोग Perl की ही तरह करते हैं। कुछ भाषाएं एवं उपकरण जैसे कि Boost और PHP बहु रेग्युलर ऍक्सप्रैशन फ्लेवर को सहयोग प्रदान करते हैं। Perl व्युत्पन्न रेग्युलर ऍक्सप्रैशन के कार्यान्वयन में एकरूपता नहीं है और कुछ केवल Perl की विशेषताओं के सबसेट को ही कार्यान्वित करते हैं। Perl 5.10 की प्रक्रिया अपनी पूर्णता और विस्तार के साथ Perl निगमित वाक्य-विन्यास के विस्तार तक पहुंच गई है - मूलतः Python, PCRE, .NET Framework और Java से.

सरल रेग्युलर ऍक्सप्रैशन

सरल रेग्युलर ऍक्सप्रैशन ऐसा वाक्य-विन्यास है, जिनका प्रयोग कंप्यूटर ऍप्लिकेशन प्रोग्राम के ऐतिहासिक संस्करणों में किया जा सकता है एवं अपने अंतर्गत कुछ अनुप्रयोगों के द्वारा सहयोग भी पा सकता है। पिछली अनुरूपता प्रदान करने के उद्देश्य से इसे अनुचित समझा गया है।

सुस्त परिमाणन

रेग्युलर ऍक्सप्रैशन में मानक परिमापक लालची हैं अर्थात् वे जितना मेल खा सकते हैं अधिक से अधिक उतनी बार मेल खाते हैं, बाकी को रिजेक्स के साथ कोई नया मेल खाने के लिए छोड़ देते हैं। उदाहरण के लिए,regexes के लिए कोई नया जो किसी एक आइटम के बीच प्रथम दृष्टान्त खोजना चाहता है, इस उदाहरण में < and > प्रतीक चिह्नों के बीच पा सकता है।
एक और व्हेल एक्स्प्लोज़न <January 26>, को घटित हुआ।
... जो <.*>, पैटर्न के साथ अथवा इसी के समान आना चाहेगा. हालांकि यह पैटर्न वास्तव में "<January 26>, " के बदले "<January 26 >" में वापस जाना चाहेगा, जो अपेक्षित था, क्योंकि * परिमाणन जो लालची है -- अतः यह यथासंभव अधिक से अधिक अक्षरों का उपभोग इनपुट से कर लेना चाहेगा, एवं "January 26>, " के पास "January 26" की तुलना में अधिक अक्षर होंगे.
हालांकि इस समस्या को कई तरीकों से टाला जा सकता है (जैसे कि विषय वस्तु को निर्दिष्ट कर जो मेल खाने योग्य नहीं है: <[^>]*>), आधुनिक रेग्युलर ऍक्सप्रैशन उपकरण एक परिमाणक को सुस्त के रूप में वैशिष्ट्य पाने की अनुमति देते हैं (जिन्हें गैर-लालची, अनिच्छुक, न्यूनतम अथवा अलालची) परिमाणक के बाद एक प्रश्नचिह्न लगाकर किया जाता है (जैसे कि <.*?>), अथवा संशोधक का प्रयोग कर जो परिमाणक के लालच को उलट देता है (यद्यपि मानक परिमाणक के अर्थ में परिवर्तन दुविधा पैदा कर सकता है). सुस्त परिमाणक का प्रयोग कर सूचक सबसे पहले कम से कम मेल खाने की कोशिश करते हैं। हालांकि पूर्ववर्ती उदाहरण में सुस्त मेल का प्रयोग कई मेलों के परिणामों में से किसी एक का चुनाव करने के लिए किया जाता है, कुछ मामलों में इसका प्रयोग बेहतर निष्पादन के लिए भी किया जा सकता है, जब लालची मिलान को अधिक पीछे हटने की जरूरत पड़ेगी.

कार्यान्वयन और चलन समय

कम से कम तीन अलग-अलग कलां विधियां कलनविधि हैं, जो निर्धारित करती हैं कि एक दिया गया रेग्युलर ऍक्सप्रैशन किस प्रकार एक स्ट्रिंग के साथ मेल खता है।
सबसे पुराने और सबसे तेज परिणाम पर निर्भर दो औपचारिक भाषा सिद्धांत जो प्रत्येक गैरनियतात्मक परिमित स्थिति यंत्र (NFA) को नियतात्मक परिमित स्थिति मशीन (DFA) में रूपांतरित करना स्वीकार करता है। DFA का स्पष्ट रूप से निर्माण किया जा सकता है और तब इसके परिणामस्वरूप इनपुट पर एक बार में एक प्रतीक चिन्ह पर परिचालित होता है। एक रेग्युलर ऍक्सप्रैशन के आकार के लिए DFA का निर्माण "O"(2ᵐ) की कीमत पर करने पर समय और स्मृति आ जाती है, लेकिन यह n आकार के string पर ही O (n) समय में चल सकता है। एक वैकल्पिक प्रयास NFA को सीधे अनुकरण करना है, मांग करने पर अनिवार्य रूप से प्रत्येक DFA स्थिति का निर्माण और तब अगले कदम पर संभवतः caching के साथ इसे बाहर निकाल देना. यह DFA को अंतर्निहित रखता है और निर्माण की घातांक लागत से बचा जा सकता है, लेकिन चलन लागत (running cost) O (nm) तक बढ़ जाती है। इस स्पष्ट पदक्षेप को DFA कलनविधि कहते हैं और अंतर्निहित पदक्षेप को NFA कलनविधि. जैसे कि एक समान DFA को क्रियान्वित करने में दोनों को भिन्न तरीकों से देखा जा सकता है, उन्हें भी बिना भेद-भाव के अक्सर कलनविधि कहते हैं। ये कलन विधियां तेज़ हैं लेकिन समूहीकृत उपसूचकों को लौटाने के लिए उनका प्रयोग सुस्त परिमाणन एवं इसी प्रकार की विशेषताएं पेचीदा हैं।
तीसरी कलनविधि बैक ट्रैक के द्वारा पैटर्न के साथ इनपुट स्ट्रिंग के मिलान के लिए है। इस कलनविधि को आमतौर पर NFA कहा जाता है, लेकिन यह शब्दावली अस्पष्ट है। इसका चलन समय घातांकी हो सकता है, जिसका सरल कार्यान्वयन यह उजागर करता है कि जब सूचकों के खिलाफ मिलान जैसे कि (a|aa)*b जिसमे प्रत्यावर्तन और असीमित परिमाणन दोनों ही हैं। कलनविधि पर ज़ोर डालते हैं कि स्थानापन्न मामलों की बढती हुई घातांकी संख्या पर विचार करें. अधिक जटिल कार्यान्वयन अक्सर चिह्नित और गतिशील करते हैं या साधारण मामलों को रद्द कर देती हैं, जब उनका चलन मंद हो जाता है।
हालांकि बैक ट्रैकिंग कार्यान्वयन सबसे खराब स्थिति में एक घातांकी गारंटी देते हैं, वे बहुत अधिक लचीलापन और सूचक शक्ति प्रदान करते हैं। उदाहरण के लिए, किसी भी कार्यान्वयन जो बैकरेफरेन्सेस के प्रयोग की अनुमति देता है या पर्ल द्वारा लागू किये गए विभिन्न एक्सटेंशनस को कार्यान्वित करता है, उसे बैक ट्रैकिंग कार्यान्वयन का अवश्य प्रयोग करना चाहिए।
कुछ कार्यान्वयन सबसे पहले तेज़ DFA को चलाकर दो सबसे अच्छी कलन विधियां उपलब्ध कराते हैं, यह जानने के लिए कि रेग्युलर ऍक्सप्रैशन स्ट्रिंग के साथ थोडा भी मेल खाते हैं या नहीं और केवल इसी स्थिति में संभवतः मंद बैक ट्रैकिंग मिलान होता है।