javascript - 从解析树到 NFA

Question

我正在寻找将正则表达式转换为 NFA 的方法。我知道我们需要将正则表达式转换为解析树，然后将其转换为 NFA。我正在使用 java 脚本。有没有js工具可以直接根据给定的正则表达式生成解析树？

此外，我对解析树到 NFA 部分的转换感到困惑。

Answer 1

为什么要构建一个解析树呢？将正则表达式直接转换为 NFA 相对简单。

基本案例的数量是有限的。知道了这些，我们就可以从这些案例的某种组合中构建完整的 NFA。考虑可以构建某些正则表达式 R 的所有可能方式。

前三个很简单，但并集、串联和 Kleene 闭包需要一点思考。

我在这里找到了最后 3 张相当不错的照片: http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser/Thompson.jpg

R = Ø(什么都不接受):

将平凡地成为不接受状态的路径。 (令 O 为非接受状态，X 为接受状态。)

(->O)

R = ϵ(接受空字符串):

通往接受状态的路径。

(->X)

R = a(接受字符串 'a'):

一个起始状态，在字符串 'a' 上有一条通往接受状态的路径。

(->O-a>X)

R = R1 ∘ R2(2 个正则表达式的串联):

起始状态成为 R1 的起始状态，在 R1 的接受状态和 R2 的起始状态之间添加了 epsilon 转换，R1 的接受状态被移除。图中第二种状态是accepting但不应该。

R = R1 U R2(2 个正则表达式的并集):

R1 和 R2 的 epsilon 转换到 NFA 的起始状态——如果可能，机器将“猜测”进入哪个状态。图中R1和R2分别用R和S表示。

R = R1*(R1 的 Kleene 闭包):

添加一个 epsilon 转换，使 R1 可以永远循环!

---

现在我们有了所有初始可能性的公式，可以将它们组合成一个大型 NFA。例如，对于 (A U B) ∘ C*

1. 为 A U B 构建 NFA“x”。
2. 为 C* 构建 NFA“y”。
3. 构建 NFA x ∘ y
4. 大功告成!

可以证明任何 NFA 都可以像这样归纳构造，并且我提供的所有初始构造都是正确的。嗯。

遗憾的是，我不熟悉任何可以满足您要求的 js 工具，但根据上述信息，如果您使用某种合理的表示形式存储基本案例，代码应该相当简单。

要获得更彻底、更少 sleep 不足的解释，请尝试 http://www.codeproject.com/Articles/5412/Writing-own-regular-expression-parser在深入研究编码之前，您需要真正理解 Thompson 的算法(我所描述的)。该网站看起来比我在这里更深入地了解实现。

祝你好运!