我目前正在做一个扫描仪生成器。这个生成器已经工作得很好了。但是当使用字符类的时候，算法变得很慢。
扫描程序生成器生成一个用于UTF8编码文件的扫描程序。应该支持所有字符范围（0x 000000到0x 10 ffff）。
如果我使用大字符集，比如any操作符'.'或unicode属性{L}，nfa（以及dfa）包含很多状态（〉10000）。因此，将nfa转换为dfa并创建最小dfa需要很长时间（即使输出的最小dfa只包含几个状态）。
下面是我当前创建nfa字符集部分的实现。
void CreateNfaPart(int startStateIndex, int endStateIndex, Set<int> characters)
{
transitions[startStateIndex] = CreateEmptyTransitionsArray();
foreach (int character in characters) {
// get the utf8 encoded bytes for the character
byte[] encoded = EncodingHelper.EncodeCharacter(character);
int tStartStateIndex = startStateIndex;
for (int i = 0; i < encoded.Length - 1; i++) {
int tEndStateIndex = transitions[tStartStateIndex][encoded[i]];
if (tEndStateIndex == -1) {
tEndStateIndex = CreateState();
transitions[tEndStateIndex] = CreateEmptyTransitionsArray();
}
transitions[tStartStateIndex][encoded[i]] = tEndStateIndex;
tStartStateIndex = tEndStateIndex;
}
transitions[tStartStateIndex][encoded[encoded.Length - 1]] = endStateIndex;
}有谁知道如何更有效地实现函数以只创建必要的状态吗？
编辑：
更具体地说，我需要一个类似于以下的函数：
List<Set<byte>[]> Convert(Set<int> characters)
{
???????
}将字符（int）转换为UTF8编码byte[]的辅助函数定义为：
byte[] EncodeCharacter(int character)
{ ... }
6条答案
按热度按时间t3irkdon1#
有很多方法可以处理它。它们都可以归结为在数据结构中一次处理字符集，而不是枚举整个字母表。这也是如何在合理的内存量中为Unicode扫描器。
关于如何表示和处理字符集，你有很多选择。我目前正在使用一个解决方案，它保留了一个有序的边界条件和相应的目标状态列表。你可以在这些列表上处理操作，比你必须在每个节点扫描整个字母表要快得多。事实上，它足够快，可以在Python中以可接受的速度运行。
z5btuh9x2#
我来解释一下你的要求联合一组Unicode代码点，以便生成状态最小的DFA，其中转换表示这些代码点的UTF8编码序列。
当你说“更有效”时，这可能适用于运行时、内存使用或最终结果的紧凑性。有限自动机中“最小”的通常含义是使用最少的状态来描述任何给定的语言，这就是你通过“只创建必要的状态”得到的。
每个有限自动机都有一个等价的 state minimal DFA（参见 Myhill-Nerode 定理[1]，或Hopcroft & Ullman [2]）。为了您的目的，我们可以直接使用Aho-Corasick算法[3]构造这个最小DFA。
要做到这一点，我们需要一个从Unicode代码点到它们对应的UTF8编码的Map。UTF8编码算法是有据可查的，我在这里就不重复了。
Aho-Corasick的工作原理是首先构造一个 trie。在你的例子中，这将是依次添加的每个UTF8序列的trie。然后，该trie被注解为转换，将其转换为算法的其余部分的DAG。有一个很好的overview of the algorithm here，但我建议阅读论文本身。
此方法的伪代码：
这种方法（形成UTF8编码序列的trie，然后Aho-Corasick，然后渲染出DFA）是在我的regexp和有限状态机库的实现中采用的方法，我在构建Unicode字符类时正是这样做的。这里你可以看到代码：
其他方法（如对这个问题的其他回答中所提到的）包括处理代码点和表达代码点的范围，而不是拼写出每个字节序列。
[1]Myhill-Nerode：陈文辉（1998），线性自动机转换，国立台湾大学机械工程研究所硕士论文
[2]Hopcroft & Ullman（1979），Section 3.4，Theorem 3.10，p.67
[3]阿霍，阿尔弗雷德五;Corasick，Margaret J.（June 1975）. Efficient string matching：An aid to bibliographic search. Communications of the ACM. 18（6）：333-340.
carvr3hs3#
看看像Google RE2和TRE这样的正则表达式库在做什么。
txu3uszq4#
我的扫描器生成器也遇到了同样的问题，所以我想出了用区间树确定的id替换区间的想法。例如，dfa中的..z范围可以表示为：97，98，99，...，122，相反，我将范围表示为[97，122]，然后从它们中构建区间树结构，因此在最后，它们被表示为引用区间树的id。a..z+，我们最终得到这样的DFA：
现在压缩间隔：
从DFA中提取所有区间，并从中构建区间树：
将实际间隔替换为它们的ID：
uqjltbpv5#
在这个库（http://mtimmerm.github.io/dfalex/）中，我通过在每个转换上放置一系列连续字符而不是单个字符来实现这一点。这贯穿了NFA构造，NFA-〉DFA转换，DFA最小化和优化的所有步骤。
它非常紧凑，但它增加了每一步的代码复杂性。
ni65a41a6#
我的https://metacpan.org/pod/Unicode::SetAutomaton模块实现了这一点。如果
\w的DFA很大，那么您可能不想制作它的多个副本。因此，我的模块对Unicode标量值集进行分区，使得每个标量值都属于一个分区，然后它计算DFA，其中每个接受状态对应于这样的分区。您可以使用DFA将输入字节转换为分区，然后在这些分区上定义更高级别的转换，节省了高级自动机中的大量空间。