Regular Expressions
नियमित अभिव्यक्ति इंजन प्रकार

NFA

एक NFA (Nondeterministic Finite Automaton) इंजन पैटर्न द्वारा संचालित है ।

सिद्धांत

रेगेक्स पैटर्न एक पेड़ में पार्स किया जाता है।

वर्तमान स्थिति सूचक इनपुट स्ट्रिंग की शुरुआत में सेट है, और इस स्थिति में एक मैच का प्रयास किया जाता है। यदि मैच फिश, स्थिति स्ट्रिंग में अगले चरित्र के लिए बढ़ाई है और इस स्थिति से एक और मैच का प्रयास किया जाता है। यह प्रक्रिया तब तक दोहराई जाती है जब तक कोई मेल नहीं मिलता है या इनपुट स्ट्रिंग का अंत नहीं हो जाता है।

प्रत्येक मैच के प्रयास के लिए

एल्गोरिथ्म एक दिए गए प्रारंभिक स्थिति के लिए पैटर्न ट्री का एक ट्रावेल प्रदर्शन करके काम करता है। जैसा कि यह पेड़ के माध्यम से आगे बढ़ता है, यह मेल खाने वाले पात्रों का उपभोग करके वर्तमान इनपुट स्थिति को अपडेट करता है।

यदि एल्गोरिथ्म एक ट्री नोड का सामना करता है जो वर्तमान स्थिति में इनपुट स्ट्रिंग से मेल नहीं खाता है, तो इसे पीछे करना होगा। यह पेड़ में मूल नोड में वापस जाकर प्रदर्शन किया जाता है, वर्तमान इनपुट स्थिति को उस मूल मान पर रीसेट कर रहा है, जो मूल नोड में प्रवेश करने पर था, और अगली वैकल्पिक शाखा की कोशिश कर रहा था।

यदि एल्गोरिथ्म पेड़ से बाहर निकलने का प्रबंधन करता है, तो यह एक सफल मैच की रिपोर्ट करता है। अन्यथा, जब सभी संभावनाओं की कोशिश की गई है, तो मैच विफल हो जाता है।

अनुकूलन

रेगेक्स इंजन आमतौर पर बेहतर प्रदर्शन के लिए कुछ अनुकूलन करते हैं। उदाहरण के लिए, यदि वे यह निर्धारित करते हैं कि एक मैच किसी दिए गए चरित्र के साथ शुरू होना चाहिए, तो वे इनपुट स्ट्रिंग में उन स्थानों पर एक मैच का प्रयास करेंगे जहां यह चरित्र दिखाई देता है।

उदाहरण

मिलान करें a(b|c)a इनपुट स्ट्रिंग abeacab खिलाफ:

पैटर्न ट्री कुछ इस तरह दिख सकता है:

CONCATENATION
    EXACT: a
    ALTERNATION
        EXACT: b
        EXACT: c
    EXACT: a

मैच की प्रक्रिया निम्नानुसार है:

a(b|c)a      abeacab
^            ^

a इनपुट स्ट्रिंग में पाया जाता है, इसका उपभोग करें और पैटर्न ट्री में अगले आइटम पर जाएं: प्रत्यावर्तन। पहली संभावना का प्रयास करें: एक सटीक b ।

a(b|c)a      abeacab
  ^           ^

b पाया जाता है, इसलिए प्रत्यावर्तन सफल होता है, इसका उपभोग करते हैं और अगले मद में आगे बढ़ते हैं: एक सटीक a :

a(b|c)a      abeacab
      ^        ^

a अपेक्षित स्थिति में नहीं मिला है। प्रत्यावर्तन के लिए बैकट्रैक, इनपुट स्थिति को उस मूल्य पर रीसेट करें जो पहली बार प्रत्यावर्तन में प्रवेश किया था, और दूसरा विकल्प आज़माएं:

a(b|c)a      abeacab
    ^         ^

इस स्थिति में c नहीं मिला है। पश्चाताप करने के लिए पीछे। इस बिंदु पर प्रयास करने के लिए कोई अन्य संभावनाएं नहीं हैं, इसलिए स्ट्रिंग की शुरुआत में कोई मैच नहीं है।

अगले इनपुट स्थिति में एक दूसरे मैच का प्रयास करें:

a(b|c)a      abeacab
^             ^

a वहां मेल नहीं खाता। अगले स्थान पर एक और मैच का प्रयास करें:

a(b|c)a      abeacab
^              ^

भाग्य भी नहीं। अगली स्थिति के लिए अग्रिम।

a(b|c)a      abeacab
^               ^

a मैच, इसलिए इसका उपभोग करें और प्रत्यावर्तन दर्ज करें:

a(b|c)a      abeacab
  ^              ^

b मेल नहीं खाता। दूसरे विकल्प का प्रयास करें:

a(b|c)a      abeacab
    ^            ^

c मेल खाता है, इसलिए इसका उपभोग करें और अगले आइटम के लिए अग्रिम करें:

a(b|c)a      abeacab
      ^           ^

a मैच, और पेड़ के अंत तक पहुँच गया है। एक सफल मैच की रिपोर्ट करें:

a(b|c)a      abeacab
                \_/

DFA

एक DFA (निर्धारक परिमित ऑटोमेटन) इंजन इनपुट द्वारा संचालित होता है ।

सिद्धांत

एल्गोरिथ्म एक बार इनपुट स्ट्रिंग के माध्यम से स्कैन करता है, और रेगेक्स में सभी संभव पथों को याद करता है जो मेल खा सकता है। उदाहरण के लिए, जब एक विकल्प पैटर्न में सामने आता है, तो दो नए रास्ते बनाए जाते हैं और स्वतंत्र रूप से प्रयास किए जाते हैं। जब किसी दिए गए मार्ग का मिलान नहीं होता है, तो इसे संभावनाओं के सेट से हटा दिया जाता है।

निहितार्थ

मिलान समय इनपुट स्ट्रिंग आकार से घिरा हुआ है। कोई बैकट्रैकिंग नहीं है, और इंजन एक साथ कई मैच ढूंढ सकता है, यहां तक कि ओवरलैपिंग मैच भी।

इस पद्धति का मुख्य दोष एनएफए इंजन प्रकार की तुलना में कम सुविधा सेट है जिसे इंजन द्वारा समर्थित किया जा सकता है।

उदाहरण

abadaca खिलाफ मैच a(b|c)a :

abadaca      a(b|c)a
^            ^        Attempt 1      ==> CONTINUE

abadaca      a(b|c)a
 ^           ^        Attempt 2      ==> FAIL
               ^      Attempt 1.1    ==> CONTINUE
                 ^    Attempt 1.2    ==> FAIL

abadaca      a(b|c)a
  ^          ^        Attempt 3      ==> CONTINUE
                   ^  Attempt 1.1    ==> MATCH

abadaca      a(b|c)a
   ^         ^        Attempt 4      ==> FAIL
               ^      Attempt 3.1    ==> FAIL
                 ^    Attempt 3.2    ==> FAIL

abadaca      a(b|c)a
    ^        ^        Attempt 5      ==> CONTINUE

abadaca      a(b|c)a
     ^       ^        Attempt 6      ==> FAIL
               ^      Attempt 5.1    ==> FAIL
                 ^    Attempt 5.2    ==> CONTINUE

abadaca      a(b|c)a
      ^      ^        Attempt 7      ==> CONTINUE
                   ^  Attempt 5.2    ==> MATCH

abadaca      a(b|c)a
       ^       ^      Attempt 7.1    ==> FAIL
                 ^    Attempt 7.2    ==> FAIL