"आधुनिक" regexes की पहचान शक्ति

Question

वास्तविक आधुनिक regexes वास्तव में किस वर्ग की भाषाएं पहचानते हैं?

जब भी बैक-रेफरेंस (उदा। (.*)_\1) के साथ एक असंबद्ध लंबाई कैप्चरिंग समूह होता है तो एक रेगेक्स अब एक गैर-नियमित भाषा से मेल खाता है। लेकिन यह, अपने आप पर, S ::= '(' S ')' | ε जैसे कुछ मिलान करने के लिए पर्याप्त नहीं है - माता-पिता के मिलान करने वाले जोड़े की संदर्भ-मुक्त भाषा।

रिकर्सिव रेगेक्स (जो मेरे लिए नए हैं, लेकिन मुझे पर्ल और पीसीआरई में मौजूद आश्वासन दिया गया है) कम से कम अधिकांश सीएफएल पहचानने लगते हैं।

क्या किसी ने इस क्षेत्र में कोई शोध किया है या पढ़ा है? इन "आधुनिक" regexes की सीमाएं क्या हैं? क्या वे एलएल या एलआर व्याकरण के सीएफजी से कड़ाई से अधिक या कड़ाई से कम पहचानते हैं? या क्या ऐसी दोनों भाषाएं मौजूद हैं जिन्हें रेगेक्स द्वारा पहचाना जा सकता है लेकिन एक CFG और विपरीत नहीं है?

प्रासंगिक कागजात के लिंक की बहुत सराहना की जाएगी।

Answer 1

पैटर्न Recursion

पुनरावर्ती पैटर्न के साथ, आप पुनरावर्ती वंश मिलान का एक रूप है।

यह समस्याओं की एक किस्म के लिए ठीक है, लेकिन एक बार आप वास्तव में पुनरावर्ती वंश पार्स करने करना चाहते हैं, आप यहाँ और वहाँ कैप्चर समूहों डालने की आवश्यकता है, और यह इस तरह से पूर्ण पार्स संरचना ठीक करने के लिए अजीब है। पर्ल के लिए डैमियन कॉनवे का Regexp::Grammars मॉड्यूल सरल पैटर्न को एक समकक्ष रूप में बदल देता है जो स्वचालित रूप से एक पुनरावर्ती डेटा संरचना में कैप्चरिंग नामित करता है, जो पार्सेड संरचना के बहुत आसान पुनर्प्राप्ति के लिए बनाता है। मेरे पास इस पोस्टिंग के अंत में इन दो दृष्टिकोणों की तुलना में एक नमूना है। Recursion

पर

प्रतिबंध सवाल क्या व्याकरण के प्रकार है कि पुनरावर्ती पैटर्न मिलान कर सकते हैं था। खैर, वे निश्चित रूप से recursive descent प्रकार matchhers हैं। दिमाग में आने वाली एकमात्र चीज यह है कि रिकर्सिव पैटर्न left recursion को संभाल नहीं सकते हैं। यह व्याकरण के प्रकार पर एक बाधा डालता है जिसे आप उन्हें लागू कर सकते हैं। कभी-कभी आप बाएं रिकर्सन को खत्म करने के लिए अपने प्रोडक्शंस को पुन: व्यवस्थित कर सकते हैं।

बीटीडब्ल्यू, पीसीआरई और पर्ल थोड़ा अलग है कि आपको रिकर्सन वाक्यांश कैसे दिया जाता है। पिक्चरपटर मैनपेज में "रिक्वेस्टिव पैटर्न" और "पर्ल से रिकर्सन अंतर" पर अनुभाग देखें। उदाहरण: पर्ल ^(.|(.)(?1)\2)$ को संभाल सकता है जहां पीसीआरई को इसके बजाय ^((.)(?1)\2|.)$ की आवश्यकता होती है।

Recursion प्रदर्शन

पुनरावर्ती पैटर्न के लिए की जरूरत आश्चर्यजनक रूप से अक्सर उठता है। एक अच्छी तरह से विज़िट किया गया उदाहरण तब होता है जब आपको घोंसला कर सकते हैं, जैसे कि संतुलित ब्रांड्स, उद्धरण, या यहां तक ​​कि HTML/XML टैग भी। यहां बाध्य माता-पिता के लिए मिलान है:

\((?:[^()]*+|(?0))*\) 

मुझे लगता है कि इसकी कॉम्पैक्ट प्रकृति की वजह से पढ़ने के लिए यह चालक है।

‘ (?: [^‘’] *+ | (?0))* ’ 

:, एक स्पष्ट उदाहरण नेस्टेड एकल उद्धरण मिलान किया जाएगा

\((?: [^()] *+ | (?0))* \) 

फिर, के बाद से हम अपने प्रत्यावर्तन के लिए कोष्ठक का उपयोग कर रहे: इस खाली स्थान के नहीं रह गया है महत्वपूर्ण बनाने के लिए /x मोड के साथ आसानी से इलाज संभव है

एक और पुनरावर्ती परिभाषित चीज जिसे आप मिलान करना चाहते हैं वह एक पालिंड्रोम होगा। यह सरल पैटर्न पर्ल में काम करता है:

^((.)(?1)\2|.?)$ 

जो आप कुछ इस तरह का उपयोग कर सबसे सिस्टम पर परीक्षण कर सकते हैं:

$ perl -nle 'print if /^((.)(?1)\2|.?)$/i' /usr/share/dict/words 

नोट प्रत्यावर्तन के PCRE के कार्यान्वयन की आवश्यकता है कि और अधिक व्यापक

^(?:((.)(?1)\2|)|((.)(?3)\4|.)) 

यह पीसीआरई रिकर्सन कैसे काम करता है इस पर प्रतिबंधों के कारण है।

उचित पार्सिंग

मेरे लिए, ऊपर के उदाहरण ज्यादातर खिलौना मैचों सभी कि दिलचस्प नहीं, वास्तव में कर रहे हैं। जब यह दिलचस्प हो जाता है तब जब आपके पास असली व्याकरण होता है तो आप पार्स करने की कोशिश कर रहे हैं। उदाहरण के लिए, आरएफसी 5322 बल्कि मेल पते को विस्तृत रूप से परिभाषित करता है। यहां मिलान करने के लिए "व्याकरणिक" पैटर्न है:

$rfc5322 = qr{ 

    (?(DEFINE) 

    (?<address>   (?&mailbox) | (?&group)) 
    (?<mailbox>   (?&name_addr) | (?&addr_spec)) 
    (?<name_addr>  (?&display_name)? (?&angle_addr)) 
    (?<angle_addr>  (?&CFWS)? < (?&addr_spec) > (?&CFWS)?) 
    (?<group>   (?&display_name) : (?:(?&mailbox_list) | (?&CFWS))? ; (?&CFWS)?) 
    (?<display_name> (?&phrase)) 
    (?<mailbox_list> (?&mailbox) (?: , (?&mailbox))*) 

    (?<addr_spec>  (?&local_part) \@ (?&domain)) 
    (?<local_part>  (?&dot_atom) | (?&quoted_string)) 
    (?<domain>   (?&dot_atom) | (?&domain_literal)) 
    (?<domain_literal> (?&CFWS)? \[ (?: (?&FWS)? (?&dcontent))* (?&FWS)? 
            \] (?&CFWS)?) 
    (?<dcontent>  (?&dtext) | (?&quoted_pair)) 
    (?<dtext>   (?&NO_WS_CTL) | [\x21-\x5a\x5e-\x7e]) 

    (?<atext>   (?&ALPHA) | (?&DIGIT) | [!#\$%&'*+-/=?^_`{|}~]) 
    (?<atom>   (?&CFWS)? (?&atext)+ (?&CFWS)?) 
    (?<dot_atom>  (?&CFWS)? (?&dot_atom_text) (?&CFWS)?) 
    (?<dot_atom_text> (?&atext)+ (?: \. (?&atext)+)*) 

    (?<text>   [\x01-\x09\x0b\x0c\x0e-\x7f]) 
    (?<quoted_pair>  \\ (?&text)) 

    (?<qtext>   (?&NO_WS_CTL) | [\x21\x23-\x5b\x5d-\x7e]) 
    (?<qcontent>  (?&qtext) | (?&quoted_pair)) 
    (?<quoted_string> (?&CFWS)? (?&DQUOTE) (?:(?&FWS)? (?&qcontent))* 
          (?&FWS)? (?&DQUOTE) (?&CFWS)?) 

    (?<word>   (?&atom) | (?&quoted_string)) 
    (?<phrase>   (?&word)+) 

    # Folding white space 
    (?<FWS>    (?: (?&WSP)* (?&CRLF))? (?&WSP)+) 
    (?<ctext>   (?&NO_WS_CTL) | [\x21-\x27\x2a-\x5b\x5d-\x7e]) 
    (?<ccontent>  (?&ctext) | (?&quoted_pair) | (?&comment)) 
    (?<comment>   \((?: (?&FWS)? (?&ccontent))* (?&FWS)? \)) 
    (?<CFWS>   (?: (?&FWS)? (?&comment))* 
         (?: (?:(?&FWS)? (?&comment)) | (?&FWS))) 

    # No whitespace control 
    (?<NO_WS_CTL>  [\x01-\x08\x0b\x0c\x0e-\x1f\x7f]) 

    (?<ALPHA>   [A-Za-z]) 
    (?<DIGIT>   [0-9]) 
    (?<CRLF>   \x0d \x0a) 
    (?<DQUOTE>   ") 
    (?<WSP>    [\x20\x09]) 
    ) 

    (?&address) 

}x; 

जैसा कि आप देखते हैं, यह बहुत बीएनएफ-जैसा है। समस्या यह है कि यह सिर्फ एक मैच है, कैप्चर नहीं। और आप वास्तव में माता-पिता को पकड़ने के साथ पूरी चीज को घेरना नहीं चाहते हैं क्योंकि यह आपको नहीं बताता कि कौन सा उत्पादन किस भाग से मेल खाता है। पहले उल्लिखित Regexp :: ग्रामर मॉड्यूल का उपयोग करके, हम कर सकते हैं।

#!/usr/bin/env perl 

use strict; 
use warnings; 
use 5.010; 
use Data::Dumper "Dumper"; 

my $rfc5322 = do { 
    use Regexp::Grammars; # ...the magic is lexically scoped 
    qr{ 

    # Keep the big stick handy, just in case... 
    # <debug:on> 

    # Match this... 
    <address> 

    # As defined by these... 
    <token: address>   <mailbox> | <group> 
    <token: mailbox>   <name_addr> | <addr_spec> 
    <token: name_addr>  <display_name>? <angle_addr> 
    <token: angle_addr>  <CFWS>? \< <addr_spec> \> <CFWS>? 
    <token: group>   <display_name> : (?:<mailbox_list> | <CFWS>)? ; <CFWS>? 
    <token: display_name> <phrase> 
    <token: mailbox_list> <[mailbox]> ** (,) 

    <token: addr_spec>  <local_part> \@ <domain> 
    <token: local_part>  <dot_atom> | <quoted_string> 
    <token: domain>   <dot_atom> | <domain_literal> 
    <token: domain_literal> <CFWS>? \[ (?: <FWS>? <[dcontent]>)* <FWS>? 

    <token: dcontent>  <dtext> | <quoted_pair> 
    <token: dtext>   <.NO_WS_CTL> | [\x21-\x5a\x5e-\x7e] 

    <token: atext>   <.ALPHA> | <.DIGIT> | [!#\$%&'*+-/=?^_`{|}~] 
    <token: atom>   <.CFWS>? <.atext>+ <.CFWS>? 
    <token: dot_atom>  <.CFWS>? <.dot_atom_text> <.CFWS>? 
    <token: dot_atom_text> <.atext>+ (?: \. <.atext>+)* 

    <token: text>   [\x01-\x09\x0b\x0c\x0e-\x7f] 
    <token: quoted_pair>  \\ <.text> 

    <token: qtext>   <.NO_WS_CTL> | [\x21\x23-\x5b\x5d-\x7e] 
    <token: qcontent>  <.qtext> | <.quoted_pair> 
    <token: quoted_string> <.CFWS>? <.DQUOTE> (?:<.FWS>? <.qcontent>)* 
          <.FWS>? <.DQUOTE> <.CFWS>? 

    <token: word>   <.atom> | <.quoted_string> 
    <token: phrase>   <.word>+ 

    # Folding white space 
    <token: FWS>    (?: <.WSP>* <.CRLF>)? <.WSP>+ 
    <token: ctext>   <.NO_WS_CTL> | [\x21-\x27\x2a-\x5b\x5d-\x7e] 
    <token: ccontent>  <.ctext> | <.quoted_pair> | <.comment> 
    <token: comment>   \((?: <.FWS>? <.ccontent>)* <.FWS>? \) 
    <token: CFWS>   (?: <.FWS>? <.comment>)* 
          (?: (?:<.FWS>? <.comment>) | <.FWS>) 

    # No whitespace control 
    <token: NO_WS_CTL>  [\x01-\x08\x0b\x0c\x0e-\x1f\x7f] 
    <token: ALPHA>   [A-Za-z] 
    <token: DIGIT>   [0-9] 
    <token: CRLF>   \x0d \x0a 
    <token: DQUOTE>   " 
    <token: WSP>    [\x20\x09] 
    }x; 
}; 

while (my $input = <>) { 
    if ($input =~ $rfc5322) { 
     say Dumper \%/;  # ...the parse tree of any successful match 
           # appears in this punctuation variable 
    } 
} 

जैसा कि आप देख, पैटर्न में एक बहुत ही थोड़ा अलग संकेतन का उपयोग करके, आप अब जो कुछ %/ चर में आप के लिए दूर पूरे पार्स पेड़ संग्रहीत करता है, सब कुछ बड़े करीने से लेबल के साथ मिलता है। परिवर्तन का नतीजा अभी भी एक पैटर्न है, जैसा कि आप =~ ऑपरेटर द्वारा देख सकते हैं। यह सिर्फ थोड़ा जादुई है।