将正则表达式转换为有限状态机

您是否有关于将任何正则表达式转换为有限状态机 (FSM) 的算法的提示。例如，解析正则表达式并适当地将状态添加到 FSM 的算法？有什么参考或更深层次的想法吗？

我正在用 Python 写这个

使用迈克尔·西普瑟的计算理论导论。第 1 章给出了将正则表达式转换为确定性或非确定性有限状态自动机（DFA 或 NFA）的详细算法，在证明它们的等价性的情况下（DFA、NFA 和正则表达式可以匹配完全相同的类）的字符串）。

总体思路是：将正则表达式转换为 NFA，这可以非常简单地完成（*是一个循环，|和字符范围是分支点）。然后，您将 NFA 转换为（更大的）DFA，其中涉及为每个状态创建一个 DFA 状态set替代 NFA 州。 DFA 最多具有与 NFA 状态集的幂集一样多的状态（例如，具有 3 个状态的 NFA 可以转换为最多具有 2^3 = 8 个状态的 DFA），并且可以识别任何目标字符串而无需回溯。阅读本书了解详细信息。