簡化正則表達式量化器

Question

我目前正在研究一個簡化創建正則表達式模式的庫。

要生成最清晰的模式，我想盡量簡化量詞。假設以下子模式已經發射：

(?:\d+)? 

上面可以簡化爲\d*，但是它也正確地假設(?:ℝ+)?總是可以被簡化爲ℝ*，其中ℝ是任意（括號，如果必要的話）正則表達式？

如果是的話，下列情況也應該如此，對嗎？

• (?:ℝ+)? =>ℝ*
• (?:ℝ+)* =>ℝ*
• (?:ℝ+)+ =>ℝ+
• (?:ℝ*)? =>ℝ*
• (?:ℝ*)* =>ℝ*
• (?:ℝ*)+ =>ℝ*
• (?:ℝ?)? =>ℝ?
• (?:ℝ?)+ =>ℝ*
• (?:ℝ?)* =>ℝ*

Answer 1

是的，你是正確的。而且您應該始終使用較小的一個，因爲嵌套重複容易出現catastrophic backtracking。因此，除了不同的執行行爲，它們將匹配相同的語言。

Answer 2

我建議轉換成量詞（米，Ñ）重複計數：

• *是（0，∞），
• +爲（1，∞），和
• ?是（0,1）。

然後制定組合量詞的規則。一般來說，什麼是(ℝ{m1, n1}){m2, n2}？關閉我的頭頂，我想你可以簡化到ℝ{m1·m2, n1·n2}如果沒有米 也不米 大於1