正则表达式的范围和组以DFA的形式实现
我目前正忙于从正则表达式（没有捕获组没有回溯）到表驱动DFA的转换。 我通过从Regex创建NFA然后将NFA转换为DFA来实现此目的。 我目前通过用“（a | b | ... | y | z）”代替组来处理诸如“[az]”之类的组合，这种组合很有效，并且生成的DFA表仍然合理。 除了abc的转义版本之外，“[^ abc]”将被替换为“（ u0000 | u0001 | ...）”，但这会导致巨大的表格。
我如何实现组和范围，以便通过将所有字符放在表中来处理它们“优雅”而不是蛮力？
您正在构建的表具有尽可能多的列，因为有明确的选择可以到达另一个州。 一旦某个字符产生了一个独特的结果，它必须在表中拥有它自己的条目，因此该表是不可减少的。 所以你必须构建整个表并通过分组来删除重复的列。 比如说a和b总是产生相同的过渡，那么你可以将它们分组在[ab] 。
如果您希望更具建设性，请事先标识等效符号。 您可以通过遍历所有状态并最初将不同的组设置为一个包含所有内容的大组来完成此操作。 接下来，对于每个状态，将每个组分割为与当前状态转换相同数量的组。 根据转换对它们进行拆分并删除单例，因为它们是原子的，所以不需要考虑它们。
链接地址: http://www.djcxy.com/p/74799.html