दोनों अजगर और एसईडी डिफ़ॉल्ट लेकिन द्वारा लालची हैं ... अजगर regex, सभी परिस्थितियों में बाएं से दाएं मूल्यांकन करने के लिए कोशिश करता है के बावजूद यह अगर शाखा मुकदमा चल रहा जारी नहीं रख सकते पहले वाली स्थिति अंततः एक पश्व-अनुरेखन करना चाहिए मिलान करके। रेडिक्स को एक और निर्धारिती रूप में फिर से लिखकर, अनावश्यक बैकट्रैस को रोकने के लिए इसके विपरीत सेड रेगेक्स को अनुकूलित करने से पहले ऑप्टिमाइज़ किया गया है। इसलिए संयुक्त वैकल्पिक पैटर्न "एएबी" शायद सादा "ए" से पहले परीक्षण किया जाता है क्योंकि सबसे विशिष्ट संभव स्ट्रिंग पहले कोशिश की जाती है।
:
अजगर पैटर्न स्ट्रिंग "aabb" दो बार के रूप में "AAB" + "ख" ("< >" के बीच में चिह्नित)
>>> re.sub("a*((ab)*)b", r"<\1>", "aabb")
'<><>'
जबकि sed एक प्रतिस्थापन द्वारा पूरी "aabb" से मेल खाता से मेल खाता है
$ echo "aabb" | sed "s/a*\(\(ab\)*\)b/<\1>/"
<ab>
पायथन रेगेक्स बैकट्र्रेस एल्गोरिदम को regex howto - Repeating Things में "पैरा-दर-चरण उदाहरण ..." शब्दों द्वारा पेश किए गए दो अनुच्छेदों में अच्छा समझाया गया है। यह आईएमओ को वास्तव में regex docs का वर्णन करता है: "चूंकि लक्ष्य स्ट्रिंग स्कैन की जाती है, आरईएस '|' से अलग होती है। बाएं से दाएं से प्रयास किया जाता है। "
प्रदर्शन
के आदेश "(| एक | आ)" btw। "(आ | एक |)" अजगर
>>> re.sub("(?:|a|aa)((ab)*)b", r"<\1>", "aabb")
'<ab>'
>>> re.sub("(?:aa|a|)((ab)*)b", r"<\1>", "aabb")
'<><>'
द्वारा सम्मान किया जाता है, लेकिन इस क्रम क्योंकि sed नियमित अभिव्यक्ति का अनुकूलन sed द्वारा नजरअंदाज कर दिया है। मिलान "एएबी" + "बी" पैटर्न से "ए" विकल्प को पुन: उत्पन्न किया जा सकता है।
$ echo "aabb" | sed "s/\(\|a\|aa\)\(\(ab\)*\)b/<\2>/g"
<ab>
$ echo "aabb" | sed "s/\(aa\|a\|\)\(\(ab\)*\)b/<\2>/g"
<ab>
$ echo "aabb" | sed "s/\(aa\|\)\(\(ab\)*\)b/<\2>/g"
<><>
संपादित: मैं DFA/NFA के बारे में सब कुछ क्योंकि मैं इसे वर्तमान ग्रंथों से साबित नहीं कर सकते हटा दिया।
कहीं मैंने पढ़ा "sed/awk एक DFA का उपयोग करें" और "अजगर/पर्ल/जावा एक NFA का उपयोग करें"। यह alternations (backtracking?) के साथ semantics बदलता है .. क्या यह संबंधित हो सकता है? –
@pst: शायद मैं आपको गलत समझ रहा हूं, लेकिन ऐसा लगता है कि किसी भी बैकट्रैकिंग-आधारित दृष्टिकोण डीएफए का उपयोग करेगा; एनएफए का उपयोग करने का प्रभाव बैकट्रैकिंग की आवश्यकता को खत्म करना होगा, क्योंकि सभी शाखाओं की एक साथ जांच की जाती है। तो, मैं पर्ल/पायथन/जावा/आदि की अपेक्षा करता हूं। एक डीएफए का उपयोग करने के लिए। क्या यह संभव है कि आपने जो लिखा है उसके विपरीत आप पढ़ लें: शायद आप पढ़ सकते हैं कि एक एनएफए और पर्ल/पायथन/जावा इत्यादि का उपयोग करते हुए एक डीएफए का उपयोग करें? – ruakh
@pst: और यह * देखे गए व्यवहार को समझाएगा, अगर sed/awk एक एनएफए का उपयोग करें, और उसके बाद चयन करें कि मिलान के किसी भी तरीके से सबसे लंबा मैच दिया गया है। इस मामले में, '\ (\ (ab \) * \)' match 'ab' एक लंबा समग्र मिलान, 'अब्बा' उत्पन्न करता है, उसके बाद यह खाली स्ट्रिंग से मेल खाता है, क्योंकि बाद वाला मतलब यह होगा कि पूरी तरह से रेगेक्स केवल 'एएबी' से मेल खाएगा। – ruakh