घोंसला पैटर्न से मेल खाने के लिए नियमित अभिव्यक्तियों का उपयोग किया जा सकता है?

Question

क्या एक नियमित अभिव्यक्ति लिखना संभव है जो एक नेस्टेड पैटर्न से मेल खाता है जो अज्ञात संख्या में होता है? उदाहरण के लिए, क्या बाहरी अभिव्यक्तियों में निहित खुले/करीबी ब्रेसिज़ की अज्ञात संख्या होने पर नियमित अभिव्यक्ति एक उद्घाटन और समापन ब्रेस से मेल खा सकती है?

उदाहरण के लिए:

public MyMethod() 
{ 
    if (test) 
    { 
    // More { } 
    } 

    // More { } 
} // End 

से मेल खाना चाहिए:

{ 
    if (test) 
    { 
    // More { } 
    } 

    // More { } 
} 

Answer 1

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

आप नेस्टेड/युग्मित तत्वों को एक निश्चित गहराई तक मिलान कर सकते हैं, जहां गहराई केवल आपकी याददाश्त से ही सीमित है, क्योंकि automaton बहुत बड़ा हो जाता है। अभ्यास में, हालांकि, आपको पुश-डाउन automaton का उपयोग करना चाहिए, उदाहरण के लिए एलएल (टॉप-डाउन) या एलआर (नीचे-अप) उदाहरण के लिए, एक संदर्भ-मुक्त व्याकरण के लिए एक पार्सर। आपको खराब रनटाइम व्यवहार को ध्यान में रखना होगा: ओ (एन^3) बनाम ओ (एन), एन = लंबाई (इनपुट) के साथ।

जावा के लिए ANTLR उदाहरण के लिए कई पार्सर जनरेटर उपलब्ध हैं। जावा (या सी) के लिए मौजूदा व्याकरण ढूंढना भी मुश्किल नहीं है।
अधिक पृष्ठभूमि के लिए: Automata Theory विकिपीडिया

पर

Answer 2

नहीं, आप उस बिंदु पर Context Free Grammars के क्षेत्र में हो रही है।

Answer 3

नहीं। इस प्रकार की समस्या के लिए आपको एक पूर्ण उड़ा पार्सर चाहिए।

Answer 4

शायद पर्ल समाधान काम कर रहा है, अगर स्ट्रिंग एक लाइन पर है:

my $NesteD ; 
$NesteD = qr/ \{([^{}] | (??{ $NesteD }))* \} /x ; 

if ($Stringy =~ m/\b(\w+$NesteD)/x) { 
    print "Found: $1\n" ; 
    } 

HTH

संपादित करें: जांच:

• http://dev.perl.org/perl6/rfc/145.html
• माणिक जानकारी: http://www.ruby-forum.com/topic/112084
• अधिक पर्ल: http://www.perlmonks.org/?node_id=660316
• भी अधिक पर्ल: https://metacpan.org/pod/Text::Balanced
• पर्ल, पर्ल, पर्ल: http://perl.plover.com/yak/regex/samples/slide083.html

और एक Torsten Marek से और बात (जो सही ढंग से बताया था, यह एक regex नहीं रह गया है कि):

• http://coding.derkeiler.com/Archive/Perl/comp.lang.perl.misc/2008-03/msg01047.html

Answer 5

Pumping lemma for regular languages यही कारण है कि आप ऐसा नहीं कर सकते हैं।

जेनरेट किए गए automaton में राज्यों की एक सीमित संख्या होगी, कहें, इसलिए के + 1 उद्घाटन ब्रेसिज़ की एक स्ट्रिंग किसी राज्य को कहीं भी दोहराई जाती है (जैसे automaton वर्णों को संसाधित करता है)। एक ही राज्य के बीच स्ट्रिंग का हिस्सा असीमित रूप से कई बार डुप्लिकेट किया जा सकता है और automaton अंतर को नहीं जान पाएगा।

विशेष रूप से, यदि यह के + 1 उद्घाटन ब्रेसिज़ को स्वीकार करता है तो उसके बाद के + 1 समापन ब्रेसिज़ (जो इसे चाहिए) द्वारा स्वीकार किया जाता है, यह अपरिवर्तित के + 1 बंद होने वाली पीतल के बाद पंप की संख्या को भी स्वीकार करेगा (जिसे इसे ' टी)।

Answer 6

उचित रेगुलर एक्सप्रेशन यह ऐसा करने में सक्षम के रूप में आप संदर्भ नि: शुल्क बोली प्रदेशों में देश में नियमित रूप से बोली के दायरे छोड़ना होगा नहीं होगा।

फिर भी "रेगुलर एक्सप्रेशन" संकुल है कि कई भाषाओं की पेशकश सख्ती से अधिक शक्तिशाली हैं।

उदाहरण के लिए, Lua नियमित अभिव्यक्तियों में "%b()" पहचानकर्ता है जो संतुलित कोष्ठक से मेल खाता है। आपके मामले में आप का प्रयोग करेंगे "%b{}"

sed के लिए इसी तरह एक और परिष्कृत उपकरण gema है, जहां आप संतुलित घुंघराले ब्रेसिज़ {#} साथ बहुत आसानी से मेल खाते हैं जाएगा।

तो, अपने निपटान में उपकरणों के आधार पर अपने "रेगुलर एक्सप्रेशन" (एक व्यापक अर्थ में) नेस्टेड कोष्टक मिलान करने में सक्षम हो सकता है।

Answer 7

ज़ोल्ट के रूप में उल्लेख किया है, कुछ regex इंजन समर्थन प्रत्यावर्तन - ज़ाहिर है, इन आम तौर पर जो कि एक बैक ट्रैकिंग एल्गोरिथ्म उपयोग करती हैं इसलिए विशेष रूप से प्रभावी नहीं होगा रहे हैं। उदाहरण: /(?>[^{}]*){(?>[^{}]*)(?R)*(?>[^{}]*)}/sm

Answer 8

हाँ, अगर यह नेट RegEx-इंजन है। नेट इंजन बाहरी स्टैक के साथ आपूर्ति की गई सीमित राज्य मशीन का समर्थन करता है। details

Answer 9

देखना यह काम करने के लिए लगता है: /(\{(?:\{.*\}|[^\{])*\})/m

Answer 10

नेस्टेड पैटर्न की जांच करने के नियमित अभिव्यक्ति का उपयोग करना बहुत आसान है।

'/(\((?>[^()]+|(?1))*\))/' 

Answer 11

PHP रेगेक्स इंजन में रिकर्सिव मिलान का उपयोग ब्रैकेट की प्रक्रियात्मक मिलान से काफी तेज है। विशेष रूप से लंबे तारों के साथ।

http://php.net/manual/en/regexp.reference.recursive.php

उदा

$patt = '!\((?: (?: (?>[^()]+) | (?R))*) \)!x'; 

preg_match_all($patt, $str, $m); 

बनाम

matchBrackets($str); 

function matchBrackets ($str, $offset = 0) { 

    $matches = array(); 

    list($opener, $closer) = array('(', ')'); 

    // Return early if there's no match 
    if (false === ($first_offset = strpos($str, $opener, $offset))) { 
     return $matches; 
    } 

    // Step through the string one character at a time storing offsets 
    $paren_score = -1; 
    $inside_paren = false; 
    $match_start = 0; 
    $offsets = array(); 

    for ($index = $first_offset; $index < strlen($str); $index++) { 
     $char = $str[ $index ]; 

     if ($opener === $char) { 
      if (! $inside_paren) { 
       $paren_score = 1; 
       $match_start = $index; 
      } 
      else { 
       $paren_score++; 
      } 
      $inside_paren = true; 
     } 
     elseif ($closer === $char) { 
      $paren_score--; 
     } 

     if (0 === $paren_score) { 
      $inside_paren = false; 
      $paren_score = -1; 
      $offsets[] = array($match_start, $index + 1); 
     } 
    } 

    while ($offset = array_shift($offsets)) { 

     list($start, $finish) = $offset; 

     $match = substr($str, $start, $finish - $start); 
     $matches[] = $match; 
    } 

    return $matches; 
} 

Answer 12

मेरे question+answer संबंधित है और मैं एक अभिव्यक्ति और मेटा-अभिव्यक्ति है कि मनमाने ढंग से (परिमित) नेस्टिंग के स्तर से मिलान कर सकते हैं। यह बहुत बदसूरत है लेकिन आप और क्या उम्मीद कर सकते हैं? यदि आपका इंजन इसका समर्थन करता है तो मैच में बैकरेरेंस का उपयोग करें। "रेगुलर एक्सप्रेशन":