用于子正则表达式匹配的 TDFA(标记 DFA)中标记转换的标记操作

Question

我是Haskell编程的初学者。我试图使用 Haskell 编程 + TDFA 为正则表达式后端匹配正则表达式的字符串。而且，我确实成功地进行了子正则表达式匹配操作，但没有使用 TDFA 中提出的标签概念。例如，请参阅以下代码。

{-# LANGUAGE MagicHash #-}
import Control.Monad
import Data.Array
import qualified Data.Text as T
import Text.Regex.TDFA
import Text.Regex.TDFA.Common       
str = "bbbb" :: String
regex = "(b|bb|bbb|bbbb)*" :: String

/* 正则表达式 = "(tag1 b|tag2 bb|tag3 bbb|tag4 bbbb)*" ：： 字符串 ---->现在感兴趣 */

main = do
if str =~ regex then putStrLn "matched" else putStrLn "no matches"
let matches = getAllTextMatches (str =~ regex) :: Array Int (Array Int String)
print matches
-- Output: array (0,1) [(0,array (0,1) [(0,"bbbb"),(1,"bbbb")]),(1,array (0,1) [(0,""),(1,"")])]
let matches = getAllTextMatches $ str =~ regex :: [Array Int String]
print matches
-- Output: [array (0,1) [(0,"bbbb"),(1,"bbbb")],array (0,1) [(0,""),(1,"")]]
let matches = getAllTextMatches $ str =~ regex :: Array Int [String]
print matches
-- Output: array (0,1) [(0,["bbbb","bbbb"]),(1,["",""])]
let matches = getAllTextMatches $ str =~ regex :: Array Int String
print matches
-- Output: array (0,1) [(0,"bbbb"),(1,"")]
let matches = getAllTextMatches $ str =~ regex :: [String]
print matches
-- Output: ["bbbb",""]
let matches = str =~ regex :: [[String]]
print matches
-- Output: [["bbbb","bbbb"],["",""]]
let matches = getAllTextMatches $ str =~ regex :: Array Int (MatchText String)
print matches
-- Output: array (0,1) [(0,array (0,1) [(0,("bbbb",(0,4))),(1,("bbbb",(0,4)))]),(1,array (0,1) [(0,("",(4,0))),(1,("",(-1,0)))])]
-- Using getAllMatches
let matches = getAllMatches $ str =~ regex :: Array Int MatchArray
print matches
-- Output: array (0,1) [(0,array (0,1) [(0,(0,4)),(1,(0,4))]),(1,array (0,1) [(0,(4,0)),(1,(-1,0))])]
let matches = getAllMatches $ str =~ regex :: Array Int (MatchOffset,MatchLength)
print matches
-- Output: array (0,1) [(0,(0,4)),(1,(4,0))]
let matches = getAllMatches $ str =~ regex :: [(MatchOffset,MatchLength)]
print matches
-- Output: [(0,4),(4,0)]

无论如何，现在，我实际上非常有兴趣了解 TDFA 上的标签操作在匹配接受的输入字符串的子表达式时如何执行。例如

让我们有一个正则表达式、R = (b|bb|bbb|bbbb)*和输入字符串 ="bbbb"。因此，如果我重写正则表达式R = (tag1 b| tag2 bb | tag3 bbb| tag4 bbbb)*，然后如果我尝试将其与输入字符串 ="bbbb"匹配，那么使用 TDFA 概念，我的兴趣是查看these tags{1,2,3,4}执行了多少次以匹配正则表达式R。如，在给定的输入字符串"bbbb"上，第一个b将是匹配tag1的范围，与输入子串"bb"的"bbbb"将是tag2的范围，依此类推。这就是如何，如果我们现在考虑完整的给定输入字符串"bbbb"那么tag4将给出它的范围，同时将给出结果，使得"bbbb"的"bbb"与tag3的范围相匹配，与"bbbb"的"bb"匹配tag2的范围相同，并且， 最后"b""bbbb"与tag1程度相匹配。因此，我希望看到这些操作using the TDFA module.就是这样。我的意思是，how many times these tags have to be updated in order to match the sub-regex withing the regex for the given accepted input string.就是这样。

因此，任何形式的帮助对我来说都是很多的......:) PS：对于Haskell初学者来说，这是一个挑战，因此正在寻找Haskell黑客。我的意思是睿智的人......无论如何:)，希望最好...:)

Answer 1

不可能将显式标签写入传递给正则表达式-TDFA的正则表达式中。正则表达式-TDFA 支持 POSIX 正则表达式，在 POSIX 子匹配中提取中涉及捕获组(即括号中的子表达式)。您可以将捕获组与正则表达式 TDFA 一起使用，如下所示：

Prelude Text.Regex.TDFA> "bbbb" =~ "((b)|(bb)|(bbb)|(bbbb))*" :: MatchArray
array (0,5) [(0,(0,4)),(1,(0,4)),(2,(-1,0)),(3,(-1,0)),(4,(-1,0)),(5,(0,4))]

在这里你可以看到你的表达式有 6 个捕获组：(b)、(bb)、(bbb)、(bbbb)、((b)|(bb)|(bbb)|(bbbb))和整个正则表达式，在 POSIX 中始终是隐式的第一组。

1. 整个正则表达式在偏移量0处匹配，并跨越4符号
2. ((b)|(bb)|(bbb)|(bbbb))在偏移0和跨度处匹配4符号
3. (b)不匹配 - 因此起始偏移-1和匹配长度0
4. 同样(bb)不匹配
5. 同样(bbb)不匹配
6. 最后，(bbbb)在偏移0处匹配，并跨越4符号。

您也可以将子匹配提取与其他接口一起使用：

Prelude Text.Regex.TDFA> "bbbb" =~ "((b)|(bb)|(bbb)|(bbbb))*" :: [[String]]
[["bbbb","bbbb","","","","bbbb"],["","","","","",""]]

标签由正则表达式-TDFA内部算法隐式添加 - 它们是对用户隐藏的实现细节。如果你想要的是使用 Haskell 正则表达式进行子匹配提取，那么此时你应该停止阅读。但是，如果您对正则表达式-TDFA操作理论感兴趣，那么您问题的答案将更加复杂。

Regex-TDFA基于Ville Laurikari于2000年发明的标记DFA概念。

Regex-TDFA的作者Chris Kuklewicz扩展了Ville的算法以支持POSIX消歧语义。2007年，他在Haskell维基上非正式地描述了他的消歧算法，最近对它的形式化或开发兴趣不大。

Kuklewicz 消歧算法在词法生成器 RE2C 中被采用，并在这篇未发表的论文中正式化(我碰巧是作者)。RE2C 还支持最左边的贪婪消歧语义，并允许您使用显式标记。另请参阅解析 IPv4 地址的简单示例或更复杂的 URI RFC-3986 解析示例以了解。

回到你的问题：

必须更新多少次这些标签才能将给定接受输入字符串的正则表达式与正则表达式中的子正则表达式匹配

答案是，这取决于给定正则表达式的非确定性程度(有关解释，请参阅论文第 16 页)。对于一个简单的标签确定性正则表达式，它是一个微不足道的恒定时间开销。对于有界重复的病理病例，请参阅论文中的示例5(第21页)。另请参阅基准测试(第 27-29 页)，它们表明在实际测试中，子匹配提取的开销相当小。

另请注意，Regex-TDFA 使用惰性真皮化，也就是说，确定化和 POSIX 消除歧义的所有开销都在运行时，因此子匹配提取的总体开销大于 RE2C 情况。

最后，您可以使用/Text/Regex/TDFA/TDFA.hs中定义的调试函数来探索 Regex-TDFA 内部examineDFA并进一步调整它以打印您需要的信息。