दो regular expressions के अंतर और intersection की गणना

 (phylactery.org)
2 पॉइंट द्वारा GN⁺ 2023-09-12 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • जब regular expressions की तुलना string sets की तरह करनी हो, antimirov एक ही स्क्रीन पर दो expressions α और β के inclusion relation, equivalence, intersection और difference की गणना करके दिखाता है
  • परिणाम क्षेत्र complement और relation expressions को साथ में दिखाता है, और ~α, α < β, α = β, α & β, α ^ β, α - β जैसे operations देखे जा सकते हैं
  • अलग से string s डालने पर s ∈ α, s ∈ β के रूप में हर regular expression का match होना तुरंत जाँचा जा सकता है
  • syntax में ., concatenation, alternation |, repetition *·+·?·{n}·{m,n}, character groups, negated character groups, escape, UTF-16 Unicode escape का समर्थन है
  • anchors, zero-width assertions, backreferences, subgroup extraction, search·partial matching, case-insensitive जैसे behavior-changing features समर्थित नहीं हैं

regular expression तुलना और set operations

  • input क्षेत्र दो regular expressions α और β लेता है
  • output दो regular expressions के complement और relation·set operations को साथ में दिखाता है
    • ~α, ~β: हर regular expression का complement
    • α < β, α = β, α > β: दो regular expressions का inclusion relation और equivalence
    • α & β: intersection
    • α ^ β: symmetric difference
    • α - β: difference
  • string s इनपुट करने पर s ∈ α, s ∈ β के रूप में यह जाँचा जा सकता है कि वह हर regular expression में शामिल है या नहीं
  • हर regular expression का size और DFA state count भी दिखाया जाता है
    • उदाहरण स्क्रीन में |α| = 1, |β| = 1
    • उदाहरण स्क्रीन में dfa(α) और dfa(β) दोनों में 1-1 state है

समर्थित regular expression syntax

  • basic operators single character, concatenation, alternation और repetition को संभालते हैं
    • .: किसी भी एक character से match
    • xy: x के बाद y से match होने वाला concatenation
    • x|y: x या y से match
    • x*: 0 या अधिक बार repetition
    • (xyz): grouping
    • (): empty string से match होने वाला empty regular expression
  • अक्सर इस्तेमाल होने वाले repetition shorthand syntax का भी समर्थन है
    • x+: 1 या अधिक बार repetition, xx* के बराबर
    • x?: optional matching, (x|) के बराबर
    • x{n}: x को n बार concatenate करना
    • x{m,n}: x को कम से कम m बार और अधिकतम n बार concatenate करना
  • character sets और escape के लिए नीचे दिए गए रूप इस्तेमाल किए जा सकते हैं
    • [a-z0-9]: group के अंदर के किसी एक character से match
    • [^a-z0-9]: group में न होने वाले किसी एक character से match
    • \c: special character c को escape करना
    • \u001a: संबंधित UTF-16 character से match
    • इसके अलावा a, b, c जैसे characters स्वयं से match करते हैं

असमर्थित features

  • antimirov का फोकस regular expressions को set operations के target के रूप में संभालने पर है, इसलिए नीचे दिए गए features शामिल नहीं हैं
    • anchors ^, $
      • हालांकि ^ और $ को फिर भी escape करना होगा
    • zero-width assertions, उदाहरण: (?=...), (?<=...)
    • backreferences, उदाहरण: \1, \2
    • subgroup extraction
    • search या partial matching
    • case-insensitive जैसे behavior बदलने वाले अन्य flags
  • अधिक जानकारी non/antimirov में देखी जा सकती है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-09-12
Hacker News की राय

  • मैंने ऐसा ही एक web demo बनाया था, जो दिखाता है कि regex कैसे parsing → NFA → DFA → minimal DFA में बदलता है, और minimal DFA से LLVM IR/Javascript/WebAssembly तक output करता है
    http://compiler.org/reason-re-nfa/src/index.html

    • हालांकि NFA से explicit DFA में जाना हमेशा अच्छा विकल्प नहीं होता
      संदर्भ के लिए, regex matching के वैकल्पिक तरीके के रूप में इस्तेमाल हो सकने वाला Brzozowski derivative भी दिलचस्प हो सकता है: https://en.wikipedia.org/wiki/Brzozowski_derivative

  • इस library का इस्तेमाल string class hierarchy बनाने के लिए किया जा सकता है, और इसके नतीजे में typed strings का ज़्यादा सक्रिय रूप से उपयोग किया जा सकता है
    उदाहरण के लिए email और URL की अपनी खास grammar होती है, और उनके values का space सभी non-empty strings का subset है, जबकि non-empty strings सभी strings का subset हैं
    अगर type system को पता हो कि email string, non-empty string का subtype है, तो email address को non-empty string मांगने वाले function में पास करना valid माना जा सकता है
    इस library का इस्तेमाल ऐसे string types की definition और hierarchy को verify करने में किया जा सकता है, और hierarchy implementation भाषा के हिसाब से subclassing, trait bounds वगैरह में अलग-अलग होगी

    • जिन languages में tagged union types होते हैं, उनमें यह तरीका अक्सर इस्तेमाल होता है। Haskell-style pseudocode मोटे तौर पर ऐसा लगेगा
      Address constructor export नहीं किया जाता, केवल type export किया जाता है, और fromString :: Text -> Maybe Address के अंदर validation करके गलत address होने पर Nothing लौटाया जाता है
      validity को data के अंदर न मिलाएं, बल्कि अलग path से signal भेजें, और जब output चाहिए हो तो toText :: Address -> Text से wrapped value को फिर निकालें
    • email address validation के लिए regex का इस्तेमाल न करना बेहतर है
      https://news.ycombinator.com/item?id=31092912
    • देर-गर्मियों की सुबह @ के बाईं ओर email address में क्या allow है और क्या नहीं, इसमें गहराई तक उतरने जितनी अजीब चीज़ें कम ही होती हैं
      “valid email address” को व्यक्त करने की कोशिश करने वाला हर regex गलत है—यह सरल heuristic काफी सुरक्षित है, लेकिन सारा मज़ा बिगाड़ देता है
    • “value space” का मतलब क्या है, यह जानने की उत्सुकता है

  • regex, काफी शानदार और जटिल mathematical theory को एक उपयोगी interface में बांध देने का अच्छा उदाहरण है
    linear algebra भी कुछ ऐसा ही लगता है

    • कोई उपयुक्त field मिल जाए तो बहुत सारी mathematics का linear algebra में बदल जाना हमेशा हैरान करता है
      complex plane का Möbius transformation w=(az+b)/(cz+d) तक linear algebra में बदला जा सकता है
    • आम तौर पर ऐसे मामलों में इसका मतलब होता है कि representation सच्चाई के ज्यादा करीब जा रही है
      अच्छे interface का अपना intrinsic value होता है, जिसे result-focused बहुत से लोग ठीक से स्वीकार नहीं करते
    • अगर मेरी याद सही है, तो Conway की https://store.doverpublications.com/0486485838.html में linear algebra से connection आया था। मैंने बस सरसरी तौर पर देखा था

  • यह शानदार page regex pairs के बीच binary relation calculate करता है और DFA को graph के रूप में दिखाता है
    regex पर किए जाने वाले काफी non-trivial operations का यह सचमुच प्रभावशाली demonstration है

    • बहुत बढ़िया है, लेकिन सख्ती से कहें तो यह उन features को support नहीं करता जो regex को अब regular expression नहीं रहने देते, यह हैरानी की बात नहीं है
      फिर भी लगा था कि ^ और $ anchors तो समस्या नहीं होंगे

  • “regex filter numbers divisible by 3” paste करके देखा तो page पूरी तरह freeze हो गया: https://stackoverflow.com/q/10992279/41948
    ^(?:[0369]+|[147](?:[0369]*[147][0369]*[258])*(?:[0369]*[258]|[0369]*[147][0369]*[147])|[258](?:[0369]*[258][0369]*[147])*(?:[0369]*[147]|[0369]*[258][0369]*[258]))+$
    ^([0369]|[147][0369]*[258]|(([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]\*[258])))+$
    उत्सुकता है कि कोई छोटा expression है या नहीं

    • यह webpage उन regex पर freeze हो जाता है जो बहुत ज्यादा states वाला DFA बनाते हैं
      उदाहरण के लिए (ab+c+)+, (abc){100}, a.*quick brown fox jumps over the lazy dog जैसी चीज़ें
    • वैसे भी page के description में लिखा है कि anchors support नहीं हैं

  • मैं syntactically valid URL और email address का intersection देखना चाहता था, लेकिन नीचे वाला URL regex डालने भर से ही page को process करने में बहुत ज्यादा समय लगने लगा
    [\-a-zA-Z0-9@:%._+~#=]{1,256}\.[a-zA-Z0-9()]{1,6}\b([\-a-zA-Z0-9()@:%_+.~#?&//=]*)
    स्रोत: https://stackoverflow.com/a/3809435/623763

    • (...){1,256} जैसे expressions बहुत भारी होते हैं, और Scala JS code आखिरकार timeout हो जाता है या browser को मार देता है
      उसे (...)+ में बदल दें तो कम-से-कम मेरे environment में चलता है। (...){1,6} जैसे छोटे expressions शायद ठीक होंगे

  • union और intersection से generate होने वाले regex खास compact नहीं होते, यह देखकर पहले हैरानी हुई और फिर बात समझ आ गई
    उदाहरण के लिए "y.+" और ".+z" का intersection "y.*z" जैसे बहुत सरल expression से लिखा जा सकता है, और page से equivalence भी confirm हो जाती है। लेकिन tool yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz* output करता है
    ऐसा result आने की कोई वजह होगी, लेकिन character count जैसे criterion पर minimal regex निकालना शायद कहीं ज्यादा कठिन है

    • एक वजह शायद यह है कि ".+z" को deterministic automaton में convert करने के बाद वह बड़ा और गंदा हो जाता है

  • पहले मैंने इसी concept का इस्तेमाल करके “IP RegEx filter” setting का validation logic लिखा था
    लक्ष्य था कि users regex के जरिए IP filter सेट कर सकें। Marketing team CIDR नहीं समझती थी, और Google Analytics की वजह से regex जानती थी
    valid regex को कैसे define किया जा सकता था? “सभी IPv4 addresses” वाले regex के साथ उसका intersection खाली नहीं होना चाहिए था, और साथ ही वह “सभी IPv4 addresses” वाले regex के बराबर भी नहीं होना चाहिए था
    इससे filter के कुछ न करने वाली शिकायतें काफी रोकी गईं, लेकिन गलत filter input को खुद रोक नहीं पाया

    • क्या इससे ज़्यादा simple solution संभव नहीं था? filter regex को validate करने की कोशिश करने के बजाय, sample IP addresses दिखाए जा सकते हैं, या user से addresses का एक set डालवाकर दिखाया जा सकता है कि कौन से addresses match होते हैं और कौन से नहीं
      यह गलत filter की समस्या से निपटने में भी मदद करता है

  • Mobile पर इसे ज़्यादा usable बनाने के लिए regex input field में auto-suggestion बंद करना बेहतर होगा
    https://stackoverflow.com/questions/35513968/disable-autocor...

  • मैंने पेज को 3 से विभाज्य संख्याओं के लिए दो मिलते-जुलते regex से test किया, और दोनों सिरों के ^ और $ हटाने पर भी यह hang हो गया
    Regex 1: ([0369]|([258]|[147][0369]*[147])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([147]|[258][0369]*[258])|([147]|[258][0369]*[258])([0369]|([147][0369]*[258]|[258][0369]*[147]))*([258]|[147][0369]*[147]))*
    Regex 2: ([0369]|[258][0369]*[147]|(([147]|[258][0369]*[258])([0369]|[147][0369]*[258])*([258]|[147][0369]*[147])))*
    आखिरी * से ठीक पहले तक सब parse हो जाता है, लेकिन जैसे ही * जोड़ते हैं, पूरा page hang हो जाता है
    * के बिना, इसने अंकों के योग के 3 से विभाज्य होने वाले number fragments को parse करने वाला एक valid validator बना दिया था