正则表达式功能如何作为 NFA 实现

Question

我了解简单的正则表达式功能是如何在*、|和()等NFA实现的。

我想知道更复杂的功能，如^、$、[]、[-]等是如何实现的。它们看起来很简单，但我想知道这些表达式是如何转换为NFA的。

以这个正则表达式为例：^k[a-z0-9]{9}$ .这将如何转换为NFA？

Answer 1

好的，让我们使用相同的表达式：

^k[a-z0-9]{9}$

集

NFA中用于表示正则表达式的每个转换通常表示为一个集合，而不是单个字符。

因此，"k"字符的转换表示为包含单个字符的集合

，而"[a-z0-9]"表示为包含这些字符的集合。

正则表达式NFA的特定实现可能具有单个字符的替代的、传统的、简化的过渡，这就是它的样子，但这可能被描述为优化细节。

锚

请注意，在具有显式锚定字符的正则表达式中，表单的正则表达式

k[a-z0-9]{9}

将等效于

（.）[A-Z0-9]{9}(.)

因为事实就是如此。但是，当正则表达式被锚定时，NFA就是它的真实面目。换句话说，NFA 始终锚定到搜索空间的开头和结尾，如果锚定字符不存在，（.*） 会在后台自动拍打正则表达式的开头或结尾。

重复

表达式{N}

这通常只需在内部复制正则表达式 N 次即可完成。明确地将其扩展。

以上是正则表达式 NFA 的典型实现。

Answer 2

我想

你可能想看看汤普森的构造算法。