正则表达式的部分匹配

Question

在NFA中，很容易使所有以前非终止状态变为接受状态，从而使其匹配给定语言的所有子串。

在Java正则表达式引擎中，有没有一种方法可以找出一个字符串是否是与给定正则表达式匹配的字符串的起始子串？

表达式regexX ~“任何开始于”，regexA = 任何普通正则表达式

结果表达式“regexXregexA”匹配所有“regexA”的所有匹配项的起始子串：

例如：

regexA = a*b, matches "ab" and not "a"
  
"regexXa*b", matches "a" because it is a start of "ab" (and "aab")  

编辑：

由于有些人仍然无法理解，这里提供一个程序测试来解答此问题：

import java.util.regex.*;
public class Test1 {
    public static void main(String args[]){
       String regex = "a*b";
       System.out.println(
       partialMatch(regex, "aaa");
       );
     }
public boolean partialMatch(String regex, String begining){
//return true if there is a string which matches the regex and    
//startsWith(but not equal) begining, false otherwise 
}
}

必须返回真。

- iantonuk

---

如果您用其他语言回答，我也没问题。 - iantonuk

“very clearly” 是主观的，以我个人看来。至少有另一个用户不理解你的问题是关于什么的。 - Eric Duminil

你的评论是不合逻辑的。我非常确定，即使问题被清楚地解释了，仍然有不止一个人不理解甚至连微积分都不理解。 - iantonuk

以下是一个完全“非主观”的示例：import java.util.regex.; public class Test1 { public static void main(String args[]){ String regex = "ab"; System.out.println( Pattern.matches(regexX+regex, "aaa") ); } } - iantonuk

什么是 regexX？这是一个用于测试第二部分是否存在并查找模式的条件吗？ - Shakiba Moshiri

Answer 1

你要找的是称为“部分匹配”的功能，这在Java正则表达式API中得到了本地支持（记录一下，提供此功能的其他引擎包括PCRE和boost :: regex）。

您可以通过检查Matcher.hitEnd函数的结果来确定输入字符串是否部分匹配，该函数告诉您匹配是否失败，因为已达到输入字符串的末尾。

Pattern pattern = Pattern.compile("a*b");
Matcher matcher = pattern.matcher("aaa");
System.out.println("Matches: " + matcher.matches());
System.out.println("Partial match: " + matcher.hitEnd());

这会输出：

Matches: false
Partial match: true

- Lucas Trzesniewski

---

谢谢，实际上这是NFA概念的一对一映射。您能详细说明一下matches()是如何实现的吗？如果在非终止状态（既不接受也不拒绝）中命中输入结尾，那么“hitEnd”标志就会被设置，这只是一个底层的NFA吗？ - iantonuk

@bedbad 我不知道具体的实现细节，但其背后的思想就像你所描述的那样：如果你处于一个非最终状态，并且没有更多可能的转换（因为没有更多的输入），那么 hitEnd 将返回 true。 - Lucas Trzesniewski

@bedbad 顺便说一下，我最近在JavaScript方面回答了一个非常类似的问题这里，你可能会感兴趣，因为JS没有提供这个功能，解决方法是（大致上）将模式重写为在正则表达式中的每个“点”处包括$，这相当于标记所有可能的NFA状态为最终状态，如果到达输入的结尾。 - Lucas Trzesniewski

这是您的悬赏奖金，先生。我找不到那个问题，我认为这个问题相当被低估了。 在Java和C/C++中是否也可以实现？您能否提供boost:regex源链接？ - iantonuk

是的，您可以在C和C++中使用PCRE，以及在C++中使用boost::regex。这里是boost部分匹配文档，以及这里是关于部分匹配的PCRE2文档。 - Lucas Trzesniewski

Answer 2

在NFA中，可以轻松地使所有以前的非终止状态接受，以匹配给定语言的所有子字符串。实际上，可以通过添加一个新的终止状态和从每个状态（终止或非终止）到新终止状态的ε移动来完成。据我所知，没有等效于此操作的正则表达式。可能一些正则表达式库提供了一种验证字符串是否是正则表达式的部分匹配的方法，但我不知道。我不懂Java，主要使用PHP工作，并且它不提供这样的功能。也许有库可以做到这一点，但我从未需要过。对于一个小而特定的正则表达式，您可以尝试构建一个新的正则表达式，通过结合这些简单的规则来匹配部分匹配原始正则表达式的字符串：a->a？, ab->ab？, a*->a*, a+->a*, a|b->(a|b)? 等等。上述的a和b是原始正则表达式的子正则表达式。根据需要使用括号。

- axiac

---

感谢您的尝试，axiac！不幸的是，我不能使用小型和/或特定的正则表达式：我正在构建解析器生成器（这部分是用于词法分析器生成器）（因此我不知道语法输入将是什么）。我需要知道到目前为止字符串是否与任何正则表达式匹配。（因为最终完全匹配它的字符串可能是“无限”长（或非常长））。 - iantonuk

如果你正在构建一个词法分析器，那么你应该比我更清楚如何将非确定有限状态自动机转换为正则表达式，反之亦然。 - axiac

是的，这是一个解决方案：将所有运行时正则表达式转换为NFA，执行该操作，然后再转换回来进行匹配。我完全意外地遇到了这个问题，并觉得它应该不需要超过3行代码。我不知道Java标准包中是否有完整的NFA实现。我只是觉得为了这个场合而这样做不太合适，所以我在这里问了一下。总之，我认为Java正则表达式应该可以处理任何FAs，这就是我问的原因。 - iantonuk

我没有标记你的答案，因为它实际上是不正确的。如果你试图推断它（“a和b是原始正则表达式的子正则表达式”），你会发现在第二条规则中，我们将我们的正则表达式分成了两个子正则表达式：a和b。 然后按顺序应用第一条规则到a-> a？将导致a？b？这是不正确的，因为它匹配了“b”，而它不应该。所以a和b不能是其他正则表达式。（即集合不起作用）。规则应该做的是找到所有可能的后缀并将它们标记为“？” - iantonuk

我同意你对我的答案的看法。你可以注意到最后一个项目是"etc"；我没有花太多精力写它，而且我知道它对你没有什么帮助。特别是因为你没有一个可以轻松转换的小型已知正则表达式。第二个转换规则应该是：Ab -> Ab?，其中b是一个字符，A是一个子表达式。其他规则也应该被重新制定为可用。最初我并不打算写一个答案，但这太长了，不能作为评论。 - axiac

我的反例仍然成立：Ab -> Ab? ->(A)b?->(a)b?->a?b? 不适用。你需要给出一组规则，确切地做到所有后缀都是可选的，而不多做任何事情。 - iantonuk