我目前正在研究掃描程序生成器。 生成器已正常工作。但是當使用字符類時,算法變得非常慢。將字符集轉換爲nfa/dfa的高效算法
掃描儀生成器爲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)
{ ... }
您正在爲_byte_輸入建立一個xFA?在(Utf16)字符上操作會不會更容易(也更可靠)? – 2010-08-21 21:07:39
我不這麼認爲,使用16位字符時,查找表的大小會增加。如果使用utf16(與utf8比較),典型的輸入文件也會更大。 – raisyn 2010-08-22 07:54:48
對不起,我誤解了!接受任何編碼對於將來的版本來說都是不錯的選擇。但爲了簡單起見,我認爲只實現一種編碼更容易,UTF-8對我來說看起來是正確的。 – raisyn 2010-08-22 10:47:24