问

模式匹配导致长输入上的Stackoverflow

WE艺家人-千乐发布于 2023-02-04 14:35

regex

我知道有关于此主题的几个主题,但找到的解决方案特定于特定问题,并且基于改进Regex字符串.

无论如何,我需要处理一个文本输入文件,其中包含的数据将图形结构建模为相邻列表.每行n包含与n相邻的顶点列表(每个都标记为整数),由一个或多个空格字符分隔.我决定在解析之前使用正则表达式字符串检查每一行,而不是NumberFormatExceptions在数据不良的情况下抛出和捕获.

所以这就是代码在这一点上松散的样子:

line = line.trim(); //Remove whitespace in the beginning and in the end of line
if (Pattern.matches("(\\d+\\s*)*", line)){
    //split string and parse vertices
}

一行也可能为空,这意味着它的度数为0.

它适用于大多数实例,但是当解析具有~1000个相邻顶点的线(StackOverflow)时失败.我想知道我可以解决这个问题的各种方法.我不想增加JVM堆栈大小,因为程序应保持可移植性.此外,我想继续使用RegEx模式匹配,因为嘿,这就是它的用途!所以希望有人有个好主意.

1 个回答

已经提供了替代解决方案,所以我不会涉及这些解决方案.我将解释为什么你的模式导致StackOverflowError¹,以及你的正则表达式如何也受到灾难性的回溯.

^{StackOverflowError如果您的JVM使用OpenJDK Java类库,则会出现¹.对于其类库使用其他内容的JVM可能不会发生.但是,由于Oracle的JRE(最常见的JRE)使用OpenJDK Java类库(Oracle实际上维护OpenJDK),因此在编写正则表达式时必须考虑此错误.在相关的说明中,过去曾多次报告过这个错误 - 这是其中之一,并且仍然没有修复.}

不要接受这个答案,因为它无法解决问题

的StackOverflowError

为了匹配由量词重复的子模式(除了占有量词),Pattern该类可以递归地调用内部函数来匹配,因此每次迭代使用一些堆栈.

它通常会对子模式进行一些分析,以避免对简单模式(如\w+or)(?:df)+进行递归调用,但是它被强制执行递归调用(?:gd?f)*或(?:g|d|f).注意前一种情况没有选择点,但后一种情况有选择点.具有选择点的常见模式是量词(占有率排除)或替代|.

如果输入字符串足够长,以便子模式重复数千次,您将得到StackOverflowError您的模式,因为它包含选择点.

占有量词没有选择点,因为它不允许回溯.引擎无需回溯,因此不需要递归调用以在堆栈上存储信息.

灾难性的回溯

您的模式会受到灾难性的回溯,因为您可以在不同的迭代次数中找到可由您的正则表达式匹配的字符串.在匹配的输入中,通常会探索一个或两个分支,但是当输入字符串是失败的输入时,将探索所有这些分支.

作为一个例子,让我们使用1234正则表达式的简单输入(\\d+\\s*)*.它可以通过上面的正则表达式以几种不同的方式匹配.
```
1/2/3/4    (4 iterations)
1/2/34     (3 iterations)
12/34      (2 iterations)
1234       (1 iteration)
1/23/4     (3 iterations)
```
在输入失败的情况下1234 5678 x,引擎将回溯所有分割数字的方式.下面的曲目显示了引擎尝试的前几次尝试:
```
1234 /5678 /x
1234 /567/8 /x
1234 /56/78 /x
1234 /56/7/8 /x
1234 /5/678 /x
1234 /5/67/8 /x
1234 /5/6/78 /x
1234 /5/6/7/8 /x

123/4 /5678 /x
123/4 /567/8 /x
123/4 /56/78 /x
123/4 /56/7/8 /x
123/4 /5/678 /x
...
```
如果输入由一个长数字和许多这样的数字组成,那么你将进入一个回溯地狱.
2023-02-04 14:38 回答

xeyuxing369

撰写答案

今天，你开发时遇到什么问题呢？

立即提问

热门标签

模式匹配导致长输入上的Stackoverflow

的StackOverflowError

灾难性的回溯