नियमित अभिव्यक्ति की सच्ची शक्ति

StackOverflow पर PHP टैग के लगातार आगंतुक के रूप में, मैं बहुत बार सवाल करता हूं कि नियमित अभिव्यक्ति का उपयोग करके HTML के कुछ विशिष्ट पहलुओं को पार्स कैसे किया जाए। इसका सबसे आम जवाब है:

“आप HTML को नियमित अभिव्यक्तियों के साथ पार्स नहीं कर सकते क्योंकि HTML नियमित नहीं है। XML पार्सर का उपयोग करें और आप खुश रहेंगे ”

यह कथन - प्रश्न के संदर्भ में - अत्यधिक भ्रामक और पूरी तरह से गलत के बीच कहीं है। मैं इस लेख में यह प्रदर्शित करने का प्रयास करना चाहता हूं कि वास्तव में शक्तिशाली आधुनिक नियमित अभिव्यक्ति कैसे होती है ।

"नियमित" का वास्तव में क्या मतलब है?

औपचारिक भाषा सिद्धांत के संदर्भ में , किसी चीज को "नियमित" कहा जाता है जब उसके पास एक व्याकरण होता है जिसमें किसी भी निष्कर्ष नियम के निम्नलिखित रूपों में से एक होता है:

B -> a
B -> aC
B -> ε

यहां प्रतीक -> को "बाईं ओर दाईं ओर से प्रतिस्थापित किया जा सकता है" के रूप में पढ़ा जा सकता है। यानी पहला नियम इस तरह से ध्वनि करेगा: " B को" से बदला जा सकता है, दूसरे का - " B को aC साथ प्रतिस्थापित किया जा सकता है", और तीसरा - " B को एक रिक्त स्ट्रिंग के साथ बदला जा सकता है" (the एक खाली स्ट्रिंग का चरित्र है)।

लेकिन B , C और a क्या हैं? यह सहमति है कि ऊपरी मामले में पत्र तथाकथित " गैर-टर्मिनलों " (वर्णों को घटकों में विभाजित किया जा सकता है ) को निरूपित करते हैं, और निचले मामले में पत्र "टर्मिनलों" (वर्णों) को इंगित करते हैं जिन्हें और नहीं तोड़ा जा सकता है ।

यह सब कुछ सार लग सकता है, तो आइए एक उदाहरण देखें: व्याकरण के रूप में प्राकृतिक संख्या की परिभाषा।

N -> 0
N -> 1
N -> 2
N -> 3
N -> 4
N -> 5
N -> 6
N -> 7
N -> 8
N -> 9
N -> 0N
N -> 1N
N -> 2N
N -> 3N
N -> 4N
N -> 5N
N -> 6N
N -> 7N
N -> 8N
N -> 9N

यह व्याकरण सुझाव देता है कि:

(N) -
... 0 9

... 0 9, (N)

इस उदाहरण में, 0 से 9 तक की संख्याएं टर्मिनल होंगी (क्योंकि उन्हें घटकों में नहीं तोड़ा जा सकता है), और एन केवल गैर-टर्मिनल होगा (क्योंकि इसे आगे विभाजित किया जा सकता है)।

यदि आप नियमों को एक बार देखते हैं और उनकी तुलना उपर्युक्त नियमित व्याकरणिक रूपों की परिभाषा से करते हैं, तो आप देखेंगे कि वे दिए गए मानदंडों को पूरा करते हैं: पहले दस नियम - फॉर्म B -> a , और दूसरा दस - फॉर्म B -> aC । इसलिए, प्राकृतिक संख्याओं के लिए व्याकरण नियमित है ।

एक और बात जिस पर आप ध्यान दे सकते हैं, वह यह है कि व्याकरण में इतनी सरल चीजों के वर्णन के बावजूद, यह पहले से ही काफी फूला हुआ है। यदि हम एक ही अवधारणा को व्यक्त कर सकते हैं, लेकिन क्या यह अधिक संक्षिप्त रूप में बेहतर नहीं होगा?

और फिर नियमित अभिव्यक्ति दृश्य पर आती है: ऊपर व्याकरण regexp [0-9]+ (जो बहुत आसान है) के बराबर है। और इस प्रकार का एक परिवर्तन किसी भी नियमित व्याकरण के लिए लागू किया जा सकता है: उनमें से प्रत्येक के पास एक समान नियमित अभिव्यक्ति है जो इसके लिए अनुमत सभी पंक्तियों का वर्णन करती है।

क्या नियमित अभिव्यक्ति का वर्णन कर सकते हैं

तो, एक तार्किक प्रश्न उठता है: क्या नियमित अभिव्यक्ति केवल नियमित व्याकरण का वर्णन कर सकती है, या वे अधिक सक्षम हैं? इसका उत्तर हां और नहीं है।

औपचारिक व्याकरण के अर्थ में नियमित अभिव्यक्ति (परिभाषा के अनुसार) केवल नियमित व्याकरण का वर्णन कर सकती है और इससे अधिक कुछ नहीं।

लेकिन जब प्रोग्रामर "नियमित अभिव्यक्तियों" के बारे में बात करते हैं, तो वे औपचारिक व्याकरण से मतलब नहीं रखते हैं। वे अपनी प्रोग्रामिंग भाषाओं में कार्यान्वित व्युत्पन्न नियमित अभिव्यक्तियों के बारे में बात करते हैं। और ये regexp कार्यान्वयन नियमितता की मूल धारणा से बहुत सतही रूप से संबंधित हैं।

रेगेक्स की कोई भी आधुनिक किस्म केवल नियमित भाषाओं की तुलना में बहुत अधिक वर्णन कर सकती है। यह स्पष्ट करना कि और अधिक वर्णन का विषय है।

चीजों को सरल रखने के लिए, मैं केवल regexp के PCRE कार्यान्वयन पर ध्यान केंद्रित करूंगा। सिर्फ इसलिए कि मैं इसे सबसे अच्छा जानता हूं (क्योंकि यह PHP में उपयोग किया जाता है)। कई अन्य कार्यान्वयन इसके समान हैं, इसलिए उनमें से अधिकांश को भी लागू किया जा सकता है।

भाषा पदानुक्रम

यह विश्लेषण करने के लिए कि नियमित अभिव्यक्तियों की मदद से क्या संभव है और क्या वर्णित नहीं किया जा सकता है, हम सबसे पहले विचार करते हैं कि अन्य प्रकार की भाषाएं क्या हैं। इसके लिए एक अच्छा प्रारंभिक बिंदु चॉम्स्की पदानुक्रम होगा :



जैसा कि आप देख सकते हैं, यह औपचारिक भाषाओं को चार प्रकारों में विभाजित करता है: नियमित भाषा (प्रकार 3) - सबसे कम शक्तिशाली, इसके बाद संदर्भ-मुक्त भाषा (टाइप 2), ​​संदर्भ-संवेदनशील भाषा (टाइप 1) और अंत में, सर्वशक्तिमान असीमित भाषाएं (प्रकार) 0)।

चॉम्स्की की पदानुक्रम को कंटेनरीकृत किया जाता है, इसलिए तस्वीर में छोटे बक्से पूरी तरह से बड़े बक्से में संलग्न हैं। यानी कोई भी नियमित भाषा भी संदर्भ-मुक्त है (लेकिन इसके विपरीत नहीं!)।

तो, चलो पदानुक्रम में एक पायदान ऊपर चलते हैं। हम पहले से ही जानते हैं कि एक नियमित अभिव्यक्ति किसी भी नियमित भाषा का वर्णन कर सकती है। क्या यह संदर्भ-मुक्त भाषाओं के लिए संभव है?

(अनुस्मारक: जब मैं "नियमित अभिव्यक्ति" कहता हूं, तो मेरा मतलब है कि वे एक प्रोग्रामेटिक अर्थ में हैं, और औपचारिक भाषाओं के सिद्धांत के अर्थ में नहीं)।

संदर्भ-मुक्त भाषाओं का विवरण

उपरोक्त प्रश्न का उत्तर: हाँ, यह संभव है!

संदर्भ-मुक्त व्याकरण के एक उत्कृष्ट उदाहरण पर विचार करें {a^nb^n, n>0} , जिसका अर्थ है "वर्णों की संख्या, उसके बाद वर्णों की समान संख्या b "। (PCRE) इस भाषा के लिए rexxp होगा:

/^(a(?1)?b)$/

यह नियमित अभिव्यक्ति बहुत सरल है: (?1) पहली उपपट्टी को संदर्भित करता है - (a(?1)?b) । इसलिए, सिद्धांत रूप में, (?1) उपमा को प्रतिस्थापित करना संभव है, इस प्रकार एक पुनरावर्ती निर्भरता का निर्माण होता है:

/^(a(?1)?b)$/
/^(a(a(?1)?b)?b)$/
/^(a(a(a(?1)?b)?b)?b)$/
/^(a(a(a(a(?1)?b)?b)?b)?b)$/
# and so on

उपरोक्त विचारों से, यह स्पष्ट होना चाहिए कि यह अभिव्यक्ति किसी भी स्ट्रिंग को a और b की समान संख्या के साथ वर्णित कर सकती है।

नतीजतन, नियमित अभिव्यक्ति कम से कम कुछ गैर-नियमित, संदर्भ-मुक्त व्याकरण का वर्णन करने में सक्षम हैं। लेकिन क्या वे उन सभी का वर्णन कर सकते हैं? इस प्रश्न का उत्तर देने के लिए, आइए पहले संदर्भ-मुक्त व्याकरण की परिभाषा देखें।

एक संदर्भ-मुक्त व्याकरण में, सभी निष्कर्ष नियमों का रूप है:

A -> β

यहाँ A फिर से एक गैर-प्रतीक चिन्ह है, और als टर्मिनलों और गैर-मध्यस्थों की एक मनमानी स्ट्रिंग है। इस प्रकार, प्रत्येक संदर्भ-मुक्त व्याकरण नियम में बाईं ओर एक अपरिमेय और दाईं ओर मनमाने अक्षरों की एक स्ट्रिंग होती है।

एक उदाहरण के रूप में, निम्नलिखित व्याकरण पर विचार करें:

 function_declaration -> T_FUNCTION is_ref T_STRING '(' parameter_list ')' '{' inner_statement_list '}' is_ref -> '&' is_ref -> ε parameter_list -> non_empty_parameter_list parameter_list -> ε non_empty_parameter_list -> parameter non_empty_parameter_list -> non_empty_parameter_list ',' parameter // ... ... ... 

यह एक PHP व्याकरण (बस कुछ सरल नियम) से एक अंश है। वाक्य-विन्यास जो हम पहले इस्तेमाल करते थे उससे थोड़ा अलग है, लेकिन इसे आसानी से समझा जा सकता है। ध्यान देने योग्य एक पहलू यह है कि यहाँ T_SOMETHING नाम भी टर्मिनल वर्ण हैं। इस तरह के प्रतीकों को आमतौर पर टोकन कहा जाता है, वे अधिक अमूर्त अवधारणाओं को कूटबद्ध करते हैं। उदाहरण के लिए, T_FUNCTION कीवर्ड फ़ंक्शन है, और T_STRING टोकन लेबल है (जैसे getUserById या some_other_name)।

मैं एक उदाहरण को प्रदर्शित करने के लिए इस उदाहरण का उपयोग करता हूं: संदर्भ-मुक्त व्याकरण पहले से ही जटिल भाषाओं को एनकोड करने के लिए पर्याप्त शक्तिशाली हैं। यही कारण है कि लगभग सभी प्रोग्रामिंग भाषाओं में संदर्भ-मुक्त व्याकरण हैं। इस सूची में वाक्यात्मक रूप से सही HTML भी शामिल है।

वास्तविक सवाल पर लौटना: क्या नियमित अभिव्यक्ति इस तरह सभी संदर्भ-मुक्त व्याकरणों को बांध सकती है? फिर से जवाब हाँ है!

यह साबित करना बेहद आसान है, क्योंकि नियमित अभिव्यक्तियाँ (कम से कम पीसीआरई और इसी तरह) व्याकरण के निर्माण के लिए सिंटैक्स प्रदान करती हैं, जो ऊपर दिए गए समान है:

 / (?(DEFINE) (?<addr_spec> (?&local_part) @ (?&domain) ) (?<local_part> (?&dot_atom) | (?"ed_string) | (?&obs_local_part) ) (?<domain> (?&dot_atom) | (?&domain_literal) | (?&obs_domain) ) (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dtext) )* (?&FWS)? \] (?&CFWS)? ) (?<dtext> [\x21-\x5a] | [\x5e-\x7e] | (?&obs_dtext) ) (?<quoted_pair> \\ (?: (?&VCHAR) | (?&WSP) ) | (?&obs_qp) ) (?<dot_atom> (?&CFWS)? (?&dot_atom_text) (?&CFWS)? ) (?<dot_atom_text> (?&atext) (?: \. (?&atext) )* ) (?<atext> [a-zA-Z0-9!#$%&'*+/=?^_`{|}~-]+ ) (?<atom> (?&CFWS)? (?&atext) (?&CFWS)? ) (?<word> (?&atom) | (?"ed_string) ) (?<quoted_string> (?&CFWS)? " (?: (?&FWS)? (?&qcontent) )* (?&FWS)? " (?&CFWS)? ) (?<qcontent> (?&qtext) | (?"ed_pair) ) (?<qtext> \x21 | [\x23-\x5b] | [\x5d-\x7e] | (?&obs_qtext) ) # comments and whitespace (?<FWS> (?: (?&WSP)* \r\n )? (?&WSP)+ | (?&obs_FWS) ) (?<CFWS> (?: (?&FWS)? (?&comment) )+ (?&FWS)? | (?&FWS) ) (?<comment> \( (?: (?&FWS)? (?&ccontent) )* (?&FWS)? \) ) (?<ccontent> (?&ctext) | (?"ed_pair) | (?&comment) ) (?<ctext> [\x21-\x27] | [\x2a-\x5b] | [\x5d-\x7e] | (?&obs_ctext) ) # obsolete tokens (?<obs_domain> (?&atom) (?: \. (?&atom) )* ) (?<obs_local_part> (?&word) (?: \. (?&word) )* ) (?<obs_dtext> (?&obs_NO_WS_CTL) | (?"ed_pair) ) (?<obs_qp> \\ (?: \x00 | (?&obs_NO_WS_CTL) | \n | \r ) ) (?<obs_FWS> (?&WSP)+ (?: \r\n (?&WSP)+ )* ) (?<obs_ctext> (?&obs_NO_WS_CTL) ) (?<obs_qtext> (?&obs_NO_WS_CTL) ) (?<obs_NO_WS_CTL> [\x01-\x08] | \x0b | \x0c | [\x0e-\x1f] | \x7f ) # character class definitions (?<VCHAR> [\x21-\x7E] ) (?<WSP> [ \t] ) ) ^(?&addr_spec)$ /x 

आप जो देखते हैं, वह RFC 5322 का उपयोग कर एक ईमेल पते का वर्णन करने के लिए एक नियमित अभिव्यक्ति है। यह RFC से बीएनएफ नियमों के एक साधारण रूपांतरण का उपयोग करके बनाया गया है, जिसे पीसीआरई समझता है।

वाक्य-विन्यास अत्यंत सरल है: सभी नियम परिभाषाएँ DEFINE कथन में लिपटी हुई हैं, जिसका मूल अर्थ यह है कि इन सभी नियमों का किसी चीज़ से सीधा मेल नहीं है, उन्हें बस घोषित करने की आवश्यकता है। केवल ^(?&addr_spec)$ हिस्सा बहुत ही अंत में निर्धारित करता है कि आखिर यहाँ क्या वर्णित है।

नियमों की परिभाषा, वास्तव में, वास्तविक "नियम" नहीं हैं, बल्कि उप-समूह हैं। पहले उदाहरण में (a(?1)?b) 1 को प्रथम उप-समूह के रूप में संदर्भित किया जाता है। इस तरह के कई उपमाओं के साथ, नामकरण अव्यवहारिक है, इसलिए उन्हें सार्थक नाम दिए गए हैं। तो (?<xyz> ...) xyz नामक टेम्पलेट को परिभाषित करता है। (?&xyz) - इससे लिंक करें।

निम्नलिखित तथ्य पर ध्यान दें: ऊपर दी गई नियमित अभिव्यक्ति x संशोधक का उपयोग करती है। उन्होंने इंजन को रिक्त स्थान की अनदेखी करने और # -स्टाइल टिप्पणियों का पालन करने का निर्देश दिया। इस तरह से आप अपने regexp को बेहतर प्रारूपित कर सकते हैं ताकि अन्य लोग इसे सामान्य रूप से समझ सकें। (ई-मेल पते के लिए इस regexp RFC 822 के विपरीत ...)

इस प्रकार, उपरोक्त वाक्यविन्यास आपको व्याकरण को नियमित अभिव्यक्ति के लिए बस मानचित्रित करने की अनुमति देता है:

A -> BC
A -> CD
// becomes
(?<A> (?&B) (?&C)
| (?&C) (?&D)
)

एकमात्र पकड़ यह है कि नियमित अभिव्यक्तियाँ बाईं ओर की पुनरावृत्ति का समर्थन नहीं करती हैं। अगर हम मापदंडों की सूची की उपरोक्त परिभाषा लेते हैं:

 non_empty_parameter_list -> parameter non_empty_parameter_list -> non_empty_parameter_list ',' parameter 

आप इसे सटीक रूप से व्याकरण-आधारित regexp में परिवर्तित करने में सक्षम नहीं होंगे । निम्नलिखित काम नहीं करेगा:

(?<non_empty_parameter_list>
(?¶meter)
| (?&non_empty_parameter_list) , (?¶meter)
)

इसका कारण यह है क्योंकि non_empty_parameter_list अपनी परिभाषा के बाईं ओर दिखाई देता है। इसे बाएं हाथ की पुनरावृत्ति कहा जाता है और व्याकरण की परिभाषाओं में बहुत आम है। कारण यह है कि एलएएलआर (1) पार्सर्स, जो सबसे अधिक बार पार्सिंग के लिए उपयोग किए जाते हैं, आमतौर पर दाएं तरफा से बेहतर बाईं ओर की पुनरावृत्ति को संभालते हैं।

लेकिन चिंतित मत हो, यह किसी भी तरह से नियमित अभिव्यक्ति की शक्ति को प्रभावित नहीं करता है। प्रत्येक बाएं पुनरावर्ती व्याकरण को एक सही पुनरावर्ती में परिवर्तित किया जा सकता है। ऊपर के उदाहरण में, बस दो भाग स्वैप करें:

 non_empty_parameter_list -> parameter non_empty_parameter_list -> parameter ',' non_empty_parameter_list 

अब यह बिल्कुल स्पष्ट होना चाहिए कि नियमित अभिव्यक्ति किसी भी संदर्भ-मुक्त भाषा का वर्णन कर सकती है (और, इसलिए, लगभग सभी भाषाएं जो प्रोग्रामर मुठभेड़ करती हैं)। एकमात्र समस्या: हालांकि नियमित अभिव्यक्तियाँ संदर्भ-मुक्त व्याकरण का वर्णन कर सकती हैं, वे आमतौर पर उन्हें पार्स नहीं कर सकते। पार्सिंग में एक स्ट्रिंग को एक सार सिंटैक्स ट्री में परिवर्तित करना शामिल है। इसके लिए नियमित अभिव्यक्ति का उपयोग करना असंभव है, कम से कम पीसीआरई (हालांकि, निश्चित रूप से, पर्ल में, जहां नियमित अभिव्यक्ति में मनमाना कोड डालना संभव है, आप लगभग कुछ भी कर सकते हैं ...)।

फिर भी, उपरोक्त DEFINE regexp मेरे लिए बहुत उपयोगी निकला। अंत में, आमतौर पर आपको पार्सिंग के लिए पूर्ण समर्थन की आवश्यकता नहीं होती है, आप बस कुछ का वर्णन करना चाहते हैं (उदाहरण के लिए, एक ई-मेल पता) या डेटा के छोटे टुकड़े निकालें (और पूरे पार्स ट्री का निर्माण न करें)। जटिल प्रसंस्करण कार्यों में से अधिकांश को regexp- आधारित व्याकरणों का उपयोग करके बहुत सरल बनाया जा सकता है :)

अब मुझे फिर से उस पर ध्यान केंद्रित करने दें जो मैंने पहले पारित करने में उल्लेख किया था: वाक्यात्मक रूप से सही HTML संदर्भ-मुक्त है। इसलिए, आप इसे नियमित अभिव्यक्ति का उपयोग करके वर्णन कर सकते हैं , जैसा कि लोकप्रिय विश्वास के विपरीत है। बस दो चीजों के बारे में मत भूलना: सबसे पहले, आपके द्वारा जो भी HTML आता है, उनमें से अधिकांश वाक्य-रचना सही नहीं है (आमतौर पर, यह बंद भी नहीं है)। और दूसरी बात, बस जो आप नहीं कर सकते उसका मतलब यह नहीं है कि आपको होना चाहिए । आप अपने सॉफ्टवेयर को ब्रेनफक पर लिख सकते हैं, लेकिन ऐसे कारण हैं जो आप नहीं करते हैं, है ना?

विषय पर मेरी राय यह है: जहां भी आपको सामान्य HTML प्रसंस्करण की आवश्यकता होती है, अपने स्वाद के लिए DOM लाइब्रेरी का उपयोग करें। यह गलत HTML को सही ढंग से प्रोसेस करेगा और पार्सिंग के पूरे बोझ को उठाएगा। दूसरी ओर, यदि आप विशिष्ट मामलों से निपट रहे हैं, तो तेज नियमित अभिव्यक्ति अक्सर सबसे अच्छा तरीका है। और मुझे स्वीकार करना होगा: हालांकि मैं आमतौर पर लोगों से कहता हूं कि नियमित अभिव्यक्ति का उपयोग करके HTML को पार्स न करें, मैं खुद जानता हूं कि यह अक्सर कैसे करना है। सिर्फ इसलिए कि मैं अक्सर विशिष्ट स्थितियों का सामना करता हूं जब regexps का उपयोग सरल होता है।

प्रसंग व्याकरण

अब जब हमने संदर्भ-मुक्त भाषाओं पर करीब से नज़र डाली है, तो चलिए चॉम्स्की पदानुक्रम: संदर्भ-संवेदनशील भाषाओं में एक और कदम बढ़ाते हैं।

उनके लिए, संरचनात्मक नियम निम्नलिखित रूप लेंगे:

αAβ → αγβ

पहले पात्रों का यह मिश्रण काफी जटिल लगता है, लेकिन वास्तव में यहां सब कुछ सरल है। कोर अभी भी A → γ that पैटर्न है जिसे हमने संदर्भ-मुक्त व्याकरण के लिए परिभाषित किया है। यह बस दोनों दिशाओं में α और β जोड़ा गया। ये दोनों एक संदर्भ बनाते हैं (जिसने व्याकरण के इस वर्ग को एक नाम भी दिया है)। तो, A को अब γ बदला जा सकता है, यदि इसके बाईं ओर α और दाईं ओर be हो।

पूर्वगामी को अधिक समझने योग्य बनाने के लिए, निम्नलिखित नियमों की व्याख्या करने का प्रयास करें:

ab A -> abc
a B c -> a QH c
HB -> HC

रूसी में, यह इस तरह से ध्वनि करेगा:

`A` `c`, , `ab` .
`B` `QH`, , `a` `c` .
`B` `C`, `H` .

संदर्भ-संवेदनशील भाषाएं कुछ ऐसी हैं जिन्हें आप शायद ही कभी "सामान्य" प्रोग्रामिंग में पाते हैं। वे प्राकृतिक भाषा प्रसंस्करण में अधिक महत्वपूर्ण हैं (क्योंकि प्राकृतिक भाषा निश्चित रूप से संदर्भ-मुक्त नहीं हैं। शब्दों के संदर्भ के आधार पर अलग-अलग अर्थ हैं)। लेकिन यहां तक ​​कि प्राकृतिक भाषाओं को संसाधित करने वाले लोग तथाकथित "नरम संदर्भ-संवेदनशील भाषाओं" के साथ काम करते हैं, क्योंकि वे मॉडलिंग के लिए पर्याप्त हैं, और पार्सिंग बहुत तेज है।

यह समझने के लिए कि संदर्भ के प्रति संवेदनशील व्याकरण कितने शक्तिशाली हैं, आइए उन व्याकरणों के एक अन्य वर्ग को देखें, जिसमें संदर्भ-संवेदनशील व्याकरणों के समान ही अभिव्यंजक शक्ति है: गैर-लघु व्याकरण।

गैर-लघु व्याकरण के लिए, प्रत्येक निष्कर्ष नियम में α ->β , जहां α और character केवल प्रतिबंध के साथ मनमाना चरित्र तार होते हैं: दाईं ओर वर्णों की संख्या बाईं ओर वर्णों की संख्या से कम नहीं होनी चाहिए। औपचारिक रूप से, यह सूत्र द्वारा व्यक्त किया जाता है |α| <= |β| |α| <= |β| कहाँ |x| वर्णों की एक स्ट्रिंग की लंबाई को दर्शाता है।

इसलिए गैर-शॉर्टहैंड व्याकरण किसी भी नियम की अनुमति देते हैं जब तक कि वे इनपुट लाइन को छोटा करना शुरू न करें। यानी ABC -> HQ एक अमान्य नियम होगा, क्योंकि इसके बाएं हिस्से में तीन अक्षर हैं, और दाएं - केवल दो हैं। इसलिए, यह नियम छोटा होगा। दूसरी ओर, काफिला नियम HQ -> ABC उपयुक्त है, क्योंकि इसमें बाईं ओर दाईं ओर अधिक वर्ण हैं, जो स्ट्रिंग का विस्तार करता है।

ये रिश्ते (संदर्भ-संवेदी और गैर-लम्बे व्याकरण के लिए समान) यह बिल्कुल स्पष्ट करते हैं कि संदर्भ-संवेदनशील व्याकरण के साथ आप लगभग कुछ भी कर सकते हैं। बस छोटा मत करो :)

यह समझने के लिए कि दोनों व्याकरणों में समान अभिव्यंजक शक्ति क्यों है, निम्नलिखित परिवर्तन उदाहरण को देखें:

//
AB -> CD
// -
AB -> AX
AX -> YX
YX -> YD
YD -> CD

ठीक है, वापस नियमित अभिव्यक्तियों के लिए। क्या वे संदर्भ-संवेदनशील भाषाओं का भी वर्णन कर सकते हैं?

इस बार मैं आपको एक निश्चित उत्तर नहीं दे सकता। बेशक, वे कुछ संदर्भ-संवेदनशील भाषाओं का वर्णन कर सकते हैं, लेकिन मुझे नहीं पता कि क्या वे उन सभी का वर्णन कर सकते हैं।

संदर्भ-संवेदी भाषा के उदाहरण के रूप में जिसे आसानी से regexps का उपयोग करके वर्णित किया जा सकता है, हम संदर्भ-मुक्त भाषा {a^nb^n, n>0} संशोधन लेते हैं, जिसके बारे में हमने ऊपर बात की थी। जब आप इसे {a^nb^nc^n, n>0} , अर्थात् में बदल देते हैं यदि b और c की समान मात्रा के पूर्व की मात्रा है, तो यह संदर्भ-संवेदनशील हो जाएगा।

इस भाषा के लिए PCRE regexp इस प्रकार है:

 /^ (?=(a(?-1)?b)c) a+(b(?-1)?c) $/x 

यदि हम कथन को अनदेखा करते हैं (?=...) , तो केवल a+(b(?-1)?c) हमारे बाईं ओर रहता है। यह जांचता है कि एक मनमाना मात्रा a ही मात्रा b और c द्वारा पीछा किया जाता है। (?-1) - सबपैटर्न के सापेक्ष संदर्भ, जिसका अर्थ है "अंतिम परिभाषित सबपैटर्न"। इस मामले में, यह है (b(?-1)?c) ।

हमारे लिए एक नई इकाई है (?=...) । इसे "शून्य चौड़ाई की सशर्त अभिव्यक्ति" कहा जाता है और यह जांचता है कि निम्नलिखित पाठ का वर्णन एक मुखौटा द्वारा किया गया है, लेकिन चेक स्वयं ही इसके उपसंचालन द्वारा किया जाता है। इस प्रकार, एक ही समय में दोनों पैटर्न के अनुपालन के लिए एक चेक है। भाग a+(b(?-1)?) c a+(b(?-1)?) जाँचता है कि b और c की संख्या समान है, और (a(?-1)?b)c - कि a और b की मात्रा समान है। दोनों मुखौटे एक साथ पुष्टि करते हैं कि सभी तीन वर्ण एक ही राशि में निहित हैं।

ऊपर दिए गए regexp में, आप यह भी देख सकते हैं कि कैसे बयानों का उपयोग करके नियमित अभिव्यक्तियों में संदर्भ की अवधारणा को लागू किया जाता है। यदि हम अब संदर्भ-संवेदनशील व्याकरण की परिभाषा पर लौटते हैं, तो आप कह सकते हैं कि प्रपत्र का एक निष्कर्ष नियम

αAβ → αγβ

निम्नलिखित DEFINE regexp नियम में परिवर्तित किया जा सकता है:

(?<A> (?<= α ) γ (?= β ) )

यह कहने के लिए समान है कि A saying है, लेकिन केवल अगर इसके α बाएं और। β दाईं ओर α ।

उपरोक्त को देखते हुए, आप सोच सकते हैं कि अब आप एक संदर्भ-संवेदनशील व्याकरण को आसानी से एक नियमित अभिव्यक्ति में बदल सकते हैं, लेकिन वास्तव में ऐसा नहीं है। कारण यह है कि पूर्वव्यापी कथन ((?<= ... )) में एक महत्वपूर्ण सीमा है: यह निश्चित लंबाई का होना चाहिए। इसका अर्थ है कि कथन द्वारा वर्णित पाठ की लंबाई पहले से ज्ञात होनी चाहिए। यानी आप लिख सकते हैं (?<= a(bc|cd) ) , लेकिन आप नहीं लिख सकते हैं (?<= ab+) । पहले मामले में, बयान किसी भी मामले में ठीक तीन वर्णों को जोड़ता है और, इसलिए, एक निश्चित लंबाई है। दूसरे मामले में, कथन ab , abb , abbbb इत्यादि को बांध सकता है। उन सभी की लंबाई अलग-अलग है, और इंजन को नहीं पता है कि उन्हें कब मिलान करना शुरू करना चाहिए। इसलिए वे बस निषिद्ध हैं।

यह संदर्भ-संवेदनशील व्याकरणों को regexps में परिवर्तित करने में आसानी के लिए एक बड़ा झटका है। लगभग सभी ऐसे व्याकरणों में पूर्वव्यापी कथनों के लिए परिवर्तनशील चौड़ाई की आवश्यकता होती है।

लेकिन यह तथ्य कि संदर्भ-संवेदी व्याकरण को सीधे regexp में बदलना असंभव है, इसका मतलब यह नहीं है कि नियमित अभिव्यक्ति उन सभी का वर्णन नहीं कर सकती है।उदाहरण के लिए, उपरोक्त भाषा {a^nb^nc^n, n>0}में एक व्याकरण भी है जिसमें चर चौड़ाई के पूर्वव्यापी कथन की आवश्यकता होती है। शायद ऐसा ही कुछ अन्य संदर्भ-संवेदनशील व्याकरणों के लिए भी संभव है। मैं ईमानदारी से नहीं जानता।

तो आखिर हम क्या कह सकते हैं? Regexps कम से कम कुछ संदर्भ-संवेदनशील भाषाओं का वर्णन कर सकता है, लेकिन यह ज्ञात नहीं है कि क्या वे उन सभी का वर्णन कर सकते हैं ।

असीमित व्याकरण

चॉम्स्की पदानुक्रम में व्याकरणों का अगला वर्ग असीमित व्याकरण है। उनकी मदद से बनाई जा सकने वाली भाषाओं के सेट में सभी पुनरावर्ती भाषाएं शामिल हैं।

असीमित व्याकरण के बारे में बहुत कम कहा जा सकता है, क्योंकि वे, उह, असीमित हैं। उनके अनुमान नियम α -> β, जहां αऔर जहां βकोई प्रतिबंध नहीं के साथ वर्ण के तार हैं।

इसलिए, असीमित व्याकरण केवल गैर-लघु व्याकरण से "गैर-छोटा" भाग निकालते हैं। इसलिए, उनके लिए यह ABC -> HQएक वैध नियम होगा, हालांकि पहले यह नहीं था।

असीमित व्याकरण कितने सही हैं? इतना कि वे मजबूत नहीं हो सकते: वे ट्यूरिंग-पूर्ण हैं। यहां तक ​​कि असीमित व्याकरण पर आधारित "प्रोग्रामिंग भाषा" भी है: थू। चूंकि यह ट्यूरिंग-पूर्ण है, इसलिए यह सब कुछ कर सकता है जो अन्य प्रोग्रामिंग भाषाएं सक्षम हैं।

ट्यूरिंग पूर्णता के परिणामों में से एक यह है कि एक निश्चित व्याकरण से संबंधित एक निश्चित रेखा सामान्य स्थिति में जाँच करने की समस्या है या नहीं।

दुर्भाग्य से, मैं आपको कुछ और नहीं बता सकता कि नियमित अभिव्यक्ति और असीमित व्याकरण कैसे संबंधित हैं। नरक, मैं पर्याप्त असीमित व्याकरण (जो गैर-छोटा नहीं होगा) का एक उदाहरण भी नहीं मिला।

लेकिन अब, जब हम ट्यूरिंग पूर्णता के बारे में बात कर रहे हैं, तो अगले बिंदु पर चलते हैं:

बैकलिंक्स के साथ नियमित अभिव्यक्ति एनपी-पूर्ण हैं

यहाँ एक और बहुत शक्तिशाली नियमित अभिव्यक्ति सुविधा है जिसका मैंने पहले उल्लेख नहीं किया है: बैकलिंक्स।

यानीइस तरह के एक बहुत सरल regexp युक्त:

/^(.+)\1$/

(.+)और \1एक ही मनमाना पाठ का वर्णन करें। आम तौर पर \nइसका अर्थ है "वहाँ कुछ, जो nth उपपट्ट द्वारा वर्णित है।" यानीअगर यह (.+)वर्णन करता है foo, यह भी अधिक कुछ नहीं का \1वर्णन करेगा foo। इसलिए, अभिव्यक्ति का (.+)\1अर्थ है "कुछ पाठ, इसके बाद इसकी एक प्रति।"

इस regexp का वर्णन "प्रतिलिपि भाषा" कहा जाता है और संदर्भ-संवेदनशील भाषाओं का एक और विशिष्ट उदाहरण है।

इसी प्रकार, आप ऊपर दिए गए अन्य व्याकरण के उदाहरणों का वर्णन करने के लिए अन्य लिंक का उपयोग कर सकते हैं:

 # {a^nb^n, n>0} (context-free) /^ (?: a (?= a* (\1?+ b) ) )+ \1 $/x # {a^nb^nc^n, n>0} (context-sensitive) /^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $/x 

यह कैसे काम करता है इसका स्पष्टीकरण इस लेख के दायरे से बाहर है, लेकिन आप स्टैकऑवरफ्लो पर इस महान विषय के बारे में पढ़ सकते हैं ।

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

एनपी-पूर्ण का क्या अर्थ है? एनपी-पूर्णता समस्याओं को हल करने के लिए कम्प्यूटेशनल जटिलता के सिद्धांत में एक वर्ग है, जिसमें कई "मुश्किल" समस्याएं आती हैं। एनपी-पूर्ण समस्याओं के उदाहरण हैं ट्रैवलिंग सेल्समैन प्रॉब्लम (टीएसपी), बूलियन फॉर्मूला सैटिस्फैक्शन प्रॉब्लम (सैट) और द नैकपैक प्रॉब्लम (बीकेपी)।

एक समस्या एनपी-पूर्ण को कॉल करने के लिए एक और महत्वपूर्ण शर्त किसी अन्य एनपी-समस्या को कम करने की क्षमता है। इस प्रकार, सभी एनपी-पूर्ण समस्याएं मूल रूप से विनिमेय हैं। यदि आप उनमें से किसी एक का त्वरित समाधान पाते हैं, तो आपके पास उन सभी का त्वरित समाधान होगा।

इसलिए अगर कोई एनपी-पूर्ण समस्या का त्वरित समाधान पाता है, तो मानवता के लगभग सभी जटिल कम्प्यूटेशनल समस्याओं को एक झपट्टा में हल किया जाएगा। क्या, जैसा कि हम जानते हैं, का अर्थ होगा सभ्यता का अंत।

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

3-CNF SAT का अर्थ है "3-संयोजी सामान्य रूप में बूलियन फ़ार्मुलों के लिए व्यवहार्यता समस्या" और समझने के लिए पर्याप्त सरल है। निम्नलिखित फार्म का एक बूलियन फार्मूला है:

(!$a || $b || $d)
&& ( $a || !$c || $d)
&& ( $a || !$b || !$d)
&& ( $b || !$c || !$d)
&& (!$a || $c || !$d)
&& ( $a || $b || $c)
&& (!$a || !$b || !$c)

इसमें AND ऑपरेटरों द्वारा अलग की गई स्थितियों की एक श्रृंखला शामिल है। इनमें से प्रत्येक स्थिति में OR ऑपरेटरों द्वारा अलग किए गए तीन चर (या उनके निषेध) शामिल हैं। 3-CNF SAT पूछता है: क्या इस बूलियन फॉर्मूला का समाधान है (जैसे, सच)?

उपरोक्त बूलियन सूत्र को निम्न नियमित अभिव्यक्ति में बदला जा सकता है:

 <?php $regex = '/^ (x?)(x?)(x?)(x?) .* ; (?: x\1 | \2 | \4 ), (?: \1 | x\3 | \4 ), (?: \1 | x\2 | x\4 ), (?: \2 | x\3 | x\4 ), (?: x\1 | \3 | x\4 ), (?: \1 | \2 | \3 ), (?: x\1 | x\2 | x\3 ), $/x'; $string = 'xxxx;x,x,x,x,x,x,x,'; var_dump(preg_match($regex, $string, $matches)); var_dump($matches); 

आप इस कोड को चलाते हैं, तो आपको निम्न परिणाम मिलेगा $matches:

array(5) {
[0]=> string(19) "xxxx;x,x,x,x,x,x,x,"
[1]=> string(1) "x"
[2]=> string(1) "x"
[3]=> string(0) ""
[4]=> string(0) ""
}

इसका मतलब है कि उपरोक्त सूत्र संतुष्ट हो जाता है, तो $a = true, $b = true, $c = falseऔर $d = false।

नियमित अभिव्यक्ति एक बहुत ही सरल चाल का उपयोग करती है: किसी भी तीन स्थितियों के लिए, स्ट्रिंग में xवर्णन किया जाना चाहिए। तो अगर आप की तरह कुछ है (?: \1 | x\3 | \4 )regexps में है, तो स्ट्रिंग केवल वर्णित किया जा सकता है, तो \1- यह है x(सही), या \3- एक खाली स्ट्रिंग (गलत), या \4- एक x(सही)।

अब यह इंजन पर निर्भर है। यह स्ट्रिंग बाइंडिंग के लिए विभिन्न रास्तों की जाँच करता है जब तक या तो कोई समाधान नहीं निकलता है या यह आत्मसमर्पण कर देता है।

संक्षेप में देना

चूंकि लेख थोड़ा लंबा था, यहाँ मुख्य बिंदुओं का सारांश दिया गया है:

• , , .
• ( PCRE) - . HTML, .
• - .
• NP . NP , .

लेकिन यह मत भूलो: जो आप नहीं कर सकते हैं उससे आपको क्या करना चाहिए । नियमित भावों के साथ HTML को संसाधित करना कुछ मामलों में वास्तव में बुरा विचार है। और दूसरों में, यह शायद सबसे अच्छी बात है।

बस यह पता लगाएँ कि आपके विशिष्ट कार्य के लिए सबसे सरल उपाय क्या है, और इसका उपयोग करें। यदि आप नियमित अभिव्यक्तियों का उपयोग करके समस्या को हल करने के लिए चुनते हैं, तो एक्स-संशोधक के बारे में मत भूलना, जो आपको अपने regexp के प्रारूप को और अधिक सुंदर बनाने की अनुमति देता है। जटिल नियमित अभिव्यक्तियों के लिए, अपने कोड को साफ और पठनीय रखने के लिए DEFINE कथनों और नामित उपपट्टों का उपयोग करना भी याद रखें।

वह सब है।

अनुवादक से: अनुवाद के संबंध में संभावित टिप्पणियां, कृपया एक व्यक्तिगत में लिखें। मैं उनके लिए बहुत आभारी रहूंगा।