DFA 的正则表达式范围和组实现为 table
Regex ranges and groups to DFA implemented as table
我目前正在尝试从正则表达式（无捕获组，无回溯）到 table 驱动的 DFA 的转换。我通过从 Regex 创建 NFA 然后将 NFA 转换为 DFA 来实现这一点。我目前通过将组替换为“(a|b|...|y|z)”来简单地处理诸如“[a-z]”之类的组，这很有效，并且生成的 DFA table 仍然是合理的尺寸。否定组如“[^abc]”也是如此，它将被替换为“(\u0000|\u0001|...)”，不包括 abc 的转义版本，但这会导致巨大的 tables。
如何实现组和范围，以便 table 处理它们 "elegant" 而不是通过将所有字符放入 table 中的蛮力？
您正在构建的 table 的列数与到达另一个状态的不同选择数一样多。一旦某个字符产生了唯一的结果，它就必须在 table 中有自己的条目，因此 table 是不可约的。因此，您必须构建整个 table 并通过对它们进行分组来删除重复的列。例如说 a 和 b 总是产生相同的转换，那么你可以将它们分组在 [ab].
中
如果您希望更具建设性，请事先确定等效符号。您可以通过遍历所有状态并将不同的组设置为一个包含所有内容的大组来实现这一点。接下来，对于每个状态，将每个组分成与当前状态的转换一样多的组。根据转换拆分它们并删除单例，不需要考虑它们，因为它们是原子的。
我目前正在尝试从正则表达式（无捕获组，无回溯）到 table 驱动的 DFA 的转换。我通过从 Regex 创建 NFA 然后将 NFA 转换为 DFA 来实现这一点。我目前通过将组替换为“(a|b|...|y|z)”来简单地处理诸如“[a-z]”之类的组，这很有效，并且生成的 DFA table 仍然是合理的尺寸。否定组如“[^abc]”也是如此，它将被替换为“(\u0000|\u0001|...)”，不包括 abc 的转义版本，但这会导致巨大的 tables。
如何实现组和范围，以便 table 处理它们 "elegant" 而不是通过将所有字符放入 table 中的蛮力？
您正在构建的 table 的列数与到达另一个状态的不同选择数一样多。一旦某个字符产生了唯一的结果，它就必须在 table 中有自己的条目，因此 table 是不可约的。因此，您必须构建整个 table 并通过对它们进行分组来删除重复的列。例如说 a 和 b 总是产生相同的转换，那么你可以将它们分组在 [ab].
如果您希望更具建设性，请事先确定等效符号。您可以通过遍历所有状态并将不同的组设置为一个包含所有内容的大组来实现这一点。接下来，对于每个状态，将每个组分成与当前状态的转换一样多的组。根据转换拆分它们并删除单例，不需要考虑它们，因为它们是原子的。