java - 从正则表达式生成图灵机的算法

Question

我正在开发一个软件来从正则表达式生成图灵机。

[ 编辑:澄清一下，OP 希望将正则表达式作为输入，并以编程方式生成图灵机来执行相同的任务。 OP 正在寻求执行从正则表达式创建 TM 的任务，而不是使用正则表达式。 ]

首先我会解释一下我做了什么，然后我的具体问题是什么:

我将正则表达式建模如下:

RegularExpression(接口(interface)):下面的类实现了这个接口(interface)

简单(即:“aaa”，“bbb”，“abcde”):这是一个叶类，它没有任何子表达式

ComplexWithoutOr (ie: "a(ab)*","(a(ab)c(b))*"):这个类包含一个RegularExpression列表。

ComplexWithOr(即:"a(a|b)","(a((ab)|c(b))"):此类包含一个Or操作，其中包含一个RegularExpression列表。它表示第一个示例的“a|b”部分和第二个示例的“(ab)|c(b)”。

变量(即:“awcw”，其中 w E {a,b}*):这尚未实现，但其想法是将其建模为具有与 Simple 不同逻辑的叶类。它代表示例的“w”部分。

请务必理解并同意上述模型。如果您有任何问题，请发表评论，然后再继续阅读...

谈到 MT 生成，我有不同程度的复杂性:

简单:这种类型的表达式已经在起作用了。为每个字母生成一个新状态并向右移动。如果在任何状态下，读取的字母不是预期的，它会启动一个“回滚电路”，以 MT 头处于初始位置结束并停止在非最终状态。

ComplexWithoutOr:我的问题来了。在这里，算法为每个子表达式生成一个 MT 并将它们连接起来。这适用于一些简单的情况，但我对回滚机制有疑问。

这是一个不适用于我的算法的示例:

“(ab)abac”:这是一个 ComplexWithoutOr 表达式，包含一个 ComplexWithOr 表达式“(ab)”(在“ab”中有一个简单表达式)和一个简单表达式“abac”

我的算法首先为“ab”生成一个 MT1。此 MT1 被 MT2 用于“(ab)*”，因此如果 MT1 成功，它会再次进入 MT1，否则 MT1 回滚，MT2 正确结束。换句话说，MT2 不能失败。

然后，它会为“abac”生成一个 MT3。 MT2的输出就是MT3的输入。 MT3的输出就是执行的结果

现在，假设这个输入字符串:“abac”。如您所见，它与正则表达式相匹配。那么让我们看看执行 MT 时会发生什么。

MT1 在第一次“ab”时正确执行。 MT1 第二次“ac”失败并回滚，将 MT 头置于第 3 个位置“a”。 MT2 正确完成，输入被转发到 MT3。 MT3 失败，因为 "ac"!="abac"。所以MT不认识“abac”。

你明白这个问题了吗？你知道解决这个问题的方法吗？

我是用Java开发的，但是语言不重要，我想讨论一下算法。

Answer 1

我不完全清楚你到底想实现什么。看起来您想制作一个图灵机(或一般的任何 FSM)，它只接受那些也被正则表达式接受的字符串。实际上，您想将正则表达式转换为 FSM。

实际上，这正是真正的正则表达式匹配器在幕后所做的事情。我想this Russ Cox 的系列文章涵盖了很多您想做的事情。