將字符集轉換爲nfa/dfa的高效算法

我目前正在研究掃描程序生成器。生成器已正常工作。但是當使用字符類時，算法變得非常慢。將字符集轉換爲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) 
{ ... }

來源

2010-08-21 raisyn

您正在爲_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

看看像Google RE2和TRE這樣的正則表達式庫在做什麼。

來源

2010-08-22 20:03:34 jilles

我認爲Google RE2能處理我需要的東西，但它非常複雜......我在http://code.google.com/p/re2/source/browse/re2/compile.cc找到了一些互動代碼（從559行開始） – raisyn 2010-08-23 16:08:42

有很多方法可以處理它。它們都歸結爲在數據結構中一次處理一組字符，而不是一次枚舉整個字母表。這也是你如何在合理數量的內存中爲Unicode製作掃描儀。

關於如何表示和處理字符集有很多選擇。目前，我正在使用一種解決方案，該解決方案可以保留有序的邊界條件列表和相應的目標狀態。如果您必須在每個關鍵點掃描整個字母表，則可以比這更快地處理這些列表中的操作。事實上，它以足夠快的速度運行在Python上。

來源

2010-08-24 16:04:35 Ian

我與我的掃描儀發生器有同樣的問題，所以我想出了用間隔樹確定的用它們的ID替換間隔的想法。例如，dfa中的a..z範圍可以表示爲：97,98,99，...，122，而我將範圍表示爲[97,122]，然後在它們之外構建區間樹結構，因此最後它們被表示爲引用區間樹的ID。鑑於以下RE：a ..Z +，我們最終得到這樣的DFA：

0 -> a -> 1 
0 -> b -> 1 
0 -> c -> 1 
0 -> ... -> 1 
0 -> z -> 1 

1 -> a -> 1 
1 -> b -> 1 
1 -> c -> 1 
1 -> ... -> 1 
1 -> z -> 1 
1 -> E -> ACCEPT

現在壓縮間隔：

0 -> a..z -> 1 

1 -> a..z -> 1 
1 -> E -> ACCEPT

提取從DFA的所有區間和建立間隔樹了出來：

{ 
    "left": null, 
    "middle": { 
     id: 0, 
     interval: [a, z], 
    }, 
    "right": null 
}

更換實際間隔到他們的ID：

0 -> 0 -> 1 
1 -> 0 -> 1 
1 -> E -> ACCEPT

來源

2013-05-16 08:04:04 Ruslan

在這個庫（http://mtimmerm.github.io/dfalex/）中，我通過在每個轉換上放置一系列連續字符來代替單個字符。這貫穿了NFA構建，NFA-> DFA轉換，DFA最小化和優化的所有步驟。

它非常緊湊，但它增加了代碼複雜性的每一步。

來源

2016-07-23 21:31:22

將字符集轉換爲nfa/dfa的高效算法

回答

相關問題