計算Swift中正則表達式的最小匹配長度

Question

我想知道是否有人有算法來計算以字符串表示的給定正則表達式的最小可能匹配長度。例如，讓我們稱此算法

其中是正則表達式和函數吐出的整數值。我想在我的應用程序使用這種算法，這樣我就可以計算像

的東西，而不是一個「最小模式長度」件的元數據手動標記到每一個正則表達式。我去之前的任何想法都嘗試重新創建似乎是一個非常複雜的輪子，我自己？儘管如此，我仍將享受挑戰。我認爲我必須使用正則表達式來分析正則表達式本身。先謝謝您的幫助！我正在尋找一個用Swift編寫的解決方案，但通用版本不會受到影響。

Answer 1

你想要做將需要一些工作是什麼。你將需要開發你自己的正則表達式解析器，我不會爲你做這件事（我不知道Swift，但不應該用正則表達式來完成正確的解析器）。但是，我可以幫助使用該算法。

我會想象這種工作的方式是，一步一步地刪除和修改正則表達式，直到可以達到具體的答案。顯然，你不應該在你唯一的正則表達式副本上這樣做，因爲這可能最終會破壞正則表達式。

這裏有一些要採取的步驟：

• 與.替換字符類。您需要小心，您知道Swift的正則表達式如何處理奇怪的語法，例如[]，在某些口味中，]將其視爲文字，因爲語法無效。
• 刪除最多：(regex part){min,max}。
  • 將(regex part){min}替換爲min重複的regex part。
• 刪除*聲明：(regex part)*
• 刪除任何+符號：(regex part)+
• 對於交替，找到最短的交替，並刪除所有其他的人：(regex part is long|but this regex part is super duper long|medium regex|short)
• 用一個.替換char類
• 用.替換所有轉義字面值，即使是\n。請記住，拋開花哨的語法可以更容易地計算最少有多少個字符。

這不是一個詳盡的清單，但它會希望讓你開始。一些謹慎的就是搶先消除括號，這可能會搞亂了操作順序和反向引用。如果Swift的正則表達式具有遞歸功能，這個任務變得更加困難。

另外要記住的是，一些正則表達式可能不會匹配任何東西（但弄清這一點可能很難），以及「最低匹配長度」是在這些情況下沒有意義的。

Answer 2

這是在Ruby中，沒有斯威夫特，但here是一個工具，我寫了可以用來解決這個問題：

/import\s+/.examples.map(&:length).min # => 7 

這個工具將用於所有正則表達式的工作，除了那些其中包含環視。 （預見，後視，字邊界錨等）

如果您只希望它能夠使用正則表達式語言的一小部分，您就可以很容易地編寫一個簡單得多的版本。但是，從經驗來看，創建這樣的「通用解決方案」非常複雜。

Answer 3

這是一項正在進行的工作，但是這是我迄今爲止...

public extension String { 

    public var minRegexMatchLength: Int { 

     let pattern = (self as NSString).mutableCopy() as! NSMutableString 

     if let expr = try? NSRegularExpression(pattern: "((\\(.*?\\))|(\\[.*?\\])|.)[*?]", options: []) { 
      expr.replaceMatchesInString(pattern, options: [], range: NSMakeRange(0, (pattern as String).length), withTemplate: "") 
     } 

     if let expr = try? NSRegularExpression(pattern: "((\\(.*?\\))|(\\[.*?\\])|.)[+]", options: []) { 
      expr.replaceMatchesInString(pattern, options: [], range: NSMakeRange(0, (pattern as String).length), withTemplate: ".") 
     } 

     if let expr = try? NSRegularExpression(pattern: "(\\[bswBSW])", options: []) { 
      expr.replaceMatchesInString(pattern, options: [], range: NSMakeRange(0, (pattern as String).length), withTemplate: ".") 
     } 

     if let expr = try? NSRegularExpression(pattern: "\\(.*?\\)", options: []) { 

      var lengths = [Int]() 

      expr.enumerateMatchesInString(pattern as String, options: [], range: NSMakeRange(0, (pattern as String).length)) 
      { (result: NSTextCheckingResult?, _, _) -> Void in 
       if let result = result { 
        let substring = pattern.substringWithRange(NSMakeRange(result.range.location + 1, result.range.length - 2)) 
        var length = substring.length 
        for word in substring.componentsSeparatedByString("|") { 
         if (word.length < length) { 
          length = word.length 
         } 
        } 
        lengths.append(length) 
       } 
      } 

      var match = expr.firstMatchInString(pattern as String, options: [], range: NSMakeRange(0, (pattern as String).length)) 
      var i = 0 
      while match != nil && i < lengths.count { 
       if let range = match?.range { 
        pattern.replaceCharactersInRange(range, withString: "".stringByPaddingToLength(lengths[i], withString: ".", startingAtIndex: 0)) 
       } 
       match = expr.firstMatchInString(pattern as String, options: [], range: NSMakeRange(0, (pattern as String).length)) 
       i += 1 
      } 

     } 

     return pattern.length 

    } 

}