正則表達式範圍和組DFA實現爲表

Question

我目前正忙於從正則表達式（沒有捕獲組沒有回溯）到表驅動DFA轉換。我通過從Regex創建NFA然後將NFA轉換爲DFA來實現此目的。我目前通過用「（a | b | ... | y | z）」代替組來處理諸如「[a-z]」之類的組，並且其工作原理和生成的DFA表仍然合理。除了abc的轉義版本之外，「[^ abc]」將被替換爲「（\ u0000 | \ u0001 | ...）」，但這會導致巨大的表格。

如何實現組和範圍，以便通過將所有字符放在表中來處理它們「優雅」而不是蠻力？

Answer 1

您正在構建的表具有儘可能多的列，因爲有明顯的選擇可以到達另一個狀態。一旦某個字符產生了一個獨特的結果，它必須在表中擁有它自己的條目，因此該表是不可減少的。所以你必須構建整個表並通過分組來刪除重複的列。舉例來說，a和b總是會產生相同的轉換，那麼您可以將它們分組在[ab]中。

如果您希望更有建設性，請事先標識等效符號。您可以通過遍歷所有狀態並最初將不同的組設置爲一個包含所有內容的大組來完成此操作。接下來，對於每個狀態，將每個組分割爲與當前狀態轉換相同數量的組。根據轉換對它們進行拆分並刪除單例，因爲它們是原子的，所以不需要考慮它們。