c++ - 与组的交集正则表达式，如何推导分组位的交集？

Question

我目前正在尝试解决类似于测试两种常规语言的交集的问题，但我知道如何进行交集，但有一个额外的要求。

我打算使用的交集逻辑是 Dragon Book 用于将 NFA 转换为 DFA 的算法，但同时在两个 NFA 上执行。由于所有 DFA 都是 NFA（但几乎没有不确定性），因此您可以根据需要对更多交叉点重复此操作。

我的问题是我的一个正则表达式具有可以作为新正则表达式的一部分进一步使用的组。具体来说：

bin/x86/a.out: obj/x86/.*\.o

obj/{[a-zA-Z0-9]+}/{.*}.o: src/\2.c

在第一行的末尾，我有一个匹配 x86 目标的所有对象的正则表达式。在第二行中，我有一个正则表达式，它指定了一个可能的构建行，它应该与第一个组与固定的“x86”匹配，第二个组与它后面的任何给定字符串匹配。在示例中，第一个匹配项尚未使用，但它应该是可检索的。为了确保匹配结束（并允许递归规则），我想使用从第一个正则表达式获得的信息来匹配第二个。通过从第一行获取第二个正则表达式和从第二行获取第一个正则表达式来选择规则，并确定两者的交集（由交集产生的 DFA）是否具有接受状态。如果是这样，则有两个都可以解析的句子，因此该组可以采用一些值。

一般来说，是否有可能从第一个正则表达式中提取信息以用于匹配第二个正则表达式的组？

如果不是一般情况，我需要添加哪些限制？

Answer 1

为什么您的示例看起来像 Makefile 规则，即使 Makefile 不支持正则表达式？

因为这就是我想做的事情（没有双关语）。

您使用哪个正则表达式库？

没有，目前还没有。我正在考虑根据这个问题的输出编写我自己的。如果这是不可能的，我可以用一个支持这个的现有的。如果这在理论上是可能的，我将开发自己的来完全做到这一点并按照我的意图制作应用程序。

有些支持前瞻表达式，这是表达式交叉的另一种方式

交集背后的想法是定义通用规则，并且可以包含多个不同的左侧部分（在通常的 makefile 中使用 %，但如果您确实有多个变体点，则不需要执行某种递归 make - 例如平台、构建类型或文件名）。如果我不能为组考虑第二个正则表达式，我就不能递归地使用这样的规则，因为递归在每个步骤/级别之间不会有任何变化。这会降低通用性，但仍然可以接受。尽管如此，知道答案是一个有趣的问题（IE，它可以通用地完成），它将决定我对正则表达式库的要求。

（未作为原始作者发布，因为我丢失了我的 cookie 并且正在等待合并帐户）。

Answer 2

我相信反引号使语言不规则，因此您将无法将其转换为有限自动机。