我目前正在开发一个扫描器生成器。
这个生成器已经可以正常工作了,但是当使用字符集时算法会变得非常慢。
该扫描器生成器用于生成UTF8编码文件的扫描器。应支持完整的字符范围(0x000000至0x10ffff)。
如果我使用大型字符集,例如任意操作符“.”或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[] EncodeCharacter(int character)
{ ... }