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

Question

我目前正在尝试解决类似于 Testing intersection of two regular languages 的问题除了我知道如何进行交叉，但有一个额外的要求。

我打算使用的交集逻辑是龙书的将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

我相信反引号会使语言变得非常规，因此您无法将其转换为有限自动机。