文件名称：DFA:使用乐观线程识别硬编码正则表达式的 DFA
文件大小：90KB
文件格式：ZIP
更新时间：2024-08-02 20:27:49
C++
RE2DFA 为了匹配正则表达式（RE），它可能首先被转换为确定性有限自动机（DFA）。 将 RE 与输入字符串匹配则是处理输入字符串的每个字符，根据字符进行状态转换。 如果在到达字符串末尾时 DFA 处于接受状态，则 RE 匹配。 例如，正则表达式ˆ(a+b+(c|d)+)+$可以由以下自动机表示，假设字符串字母表为{a, b, c, d} 。 匹配过程本质上是顺序的，因为我们需要一次处理一个字符的字符串。 然而，它可以通过使用乐观方法并行化。 假设我们有1普通线程和 n 个乐观线程。 我们将输入字符串分成n + 1部分。 普通线程获取字符串的第一部分，并执行如上匹配。 n 个乐观线程各自对自己的字符串部分执行匹配，但由于它们不确定 DFA 将处于什么状态，因此它们同时模拟每个可能状态的匹配。 例如，在上面的例子中，一个乐观线程会检查它的片段 4 次，假设它从状态0 、 1 、
【文件预览】：
DFA-master
----src()
--------dfa.hpp(1KB)
--------stringBuilder.cpp(1KB)
--------main.cpp(3KB)
----benchmark.csv(90B)
----stat.sh(113B)
----CMakeLists.txt(176B)
----assets()
--------speedup.png(9KB)
--------example_dfa.png(83KB)
----README.md(4KB)