python - 关于如何将正则表达式转换为状态机图的任何指针

Question

我正在开发一种网络检查工具，该工具允许用户通过网络流匹配正则表达式。它工作正常，现在我想为其添加图形功能。这是为了给用户提供一个表示正则表达式内部状态机的点图。

我发现交互式正则表达式调试器和可视化器非常有用，并且希望具有大部分相似的基于 Python 的功能来生成图形。我有一个接受自定义正则表达式语言并将表达式转换为这样的图形的工具。由于它与 Python re 表达式不兼容，我不能使用它。

关于如何将 Python 正则表达式转换为 FA 状态机的任何指针？

Answer 1

如果您允许 Python 正则表达式的全部范围，则无法做到这一点。原因是 所支持的一些表达式re根本不是正则的，不能用有限自动机来表示。一个简单的例子是r"(a+)b\1"，它匹配一定数量的a's、a和与之前b相同数量的a's（请参阅正则表达式实现细节）。没有 DFA 承认这种表达。