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

Question

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

我正在用 Python 写这个

Answer 1

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

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