为什么Java正则表达式需要编译？

Question

我了解到Java正则表达式需要编译才能在字符串上进行任何类型的正则表达式匹配，但我不明白为什么需要编译。

正则表达式字符串编译后会生成更高效的表示方式，比String类型更高效。那编译后的表示方式是什么？它是如何比String类型更高效的？

- johnnyodonnell

---

衍生出一种最优解析语法。由于模式可以在文本文件的行上重复数千次，因此这似乎值得努力。但是，由于回溯等原因，正则表达式可能会很慢。这是声明式编程的典型特征：您告诉您想要什么，但过程留给实现。 - Joop Eggen

正则表达式引擎不使用字符串，模式仅提供搜索指令，几乎所有引擎都会将该模式转换为不同的表示形式。通常是一个状态机。 - VLAZ

@VLAZ 那个不同的表示是什么？它如何比普通字符串更高效？ - johnnyodonnell

如果您构建了一个状态机来定义通过消耗字符的转换，那么您可以极大地简化匹配过程。/\d\s_/变成状态和转换，然后开始消耗字符：“1_”->抓取“1”->好的，匹配\d->移动到下一个状态->抓取空格->好的，匹配\s->移动到下一个状态->抓取“_”->好的，匹配_ ->完成。如果提供“1a_”，则抓取“1”->好的，匹配\d->移动到下一个状态->抓取“a”->不匹配\s->结束。 - VLAZ

@VLAZ 我想这就是我要找的答案。虽然我对状态机还不是很了解，但听起来它比字符串表示更有效。感谢您的帮助！ - johnnyodonnell

Answer 1

通常，正则表达式引擎使用一组指令来遍历目标文本并匹配其中的部分内容。我们作为开发人员编写的高级（易读）模式就像Java（或任何其他语言）中的源代码。计算机不会运行您的源代码，它将其编译成计算机可以理解的指令。同样，您的正则表达式模式会被编译成一组指令，正则表达式引擎（无论编程语言如何）可以处理。

我个人认为Regular-Expressions.info网站非常有帮助，其中包含很多解释，尽管他们对引擎内部工作原理的解释有点简略。这条SO答案还不错，还提供了其他链接。

如果您想要更详细的答案，请查看此页面，其中讨论了正则表达式引擎的本质，即它们是有限状态机。

引用： 正则表达式引擎实现为有限状态机（FSM）。您提供的模式将编译为表示此状态机的数据结构。 当您将字符串与此模式匹配时，正则表达式引擎会接受每个字符并决定FSM内的状态转换。如果输入字符没有有效的状态转换，则匹配失败。 FSM中的状态之一是终止/结束状态。如果正则表达式引擎到达此状态，则报告成功。

回答您的“它与字符串相比如何更有效”问题，它不能是字符串...您必须获取引擎的低级指令。字符串类型不是一组指令！

- Jordan Kasper

---

这非常有帮助！虽然我仍然感觉自己并不完全知道这个问题的答案，但这确实让我更接近了一步。而且我可能还没有达到100%的原因之一是我对有限状态机知之甚少。所以，你提供的链接将非常有价值。谢谢！ - johnnyodonnell

Answer 2

你的问题不太明确，我猜你是在问正则表达式字符串编译后的更高效表示方式是什么？以及这种表示方式如何比字符串更高效？

正则表达式本质上只是一种描述（对于计算机而言）你想匹配什么的语言。

把正则表达式字符串看作代码，计算机在使用之前必须先将其翻译成可用的形式。

因此，“编译”正则表达式就是将该字符串转换为机器指令。

它比字符串“更高效”，因为当你存储模式时，你可以保留那些匹配指令，以便在不重新翻译相同正则表达式字符串的情况下高效地重复使用。

例如，以下是我理解的编译与字符串表示的区别：

public static void main(String[] args){
    // using "string representation"
    System.out.println("some string".matches("myRegex"));


    // using "compiled representation"
    Pattern myPattern = Pattern.compile("myRegex");

    Matcher myMatcher1 = myPattern.matcher("some string 1");
    Matcher myMatcher2 = myPattern.matcher("some string 2");

    System.out.println(myMatcher1.matches());
    System.out.println(myMatcher2.matches());
}

但是如果你看一下"some string".matches("myRegex")所使用的方法，你会发现它也调用了Pattern.compile()来翻译正则表达式指令：

String.java

public boolean matches(String regex) {
    // return Pattern.matches(regex, this);
    Pattern p = Pattern.compile(regex);
    Matcher m = p.matcher(input);
    return m.matches();
}

因此，使用“字符串表示法”仍会编译RegEx，只是不会缓存模式以供重复使用。

- xtratic

---

我理解了很多。你说，“在将其翻译成计算机可以使用的内容之前，计算机无法对其进行任何操作。”我的问题是，RegEx被翻译成什么？以上一些答案提到，RegEx被翻译成有限状态机。这正是我想要了解的。 - johnnyodonnell