Упрощение регулярного выражения, вызывающего исключение Java StackOverflowException - PullRequest
Новая
       9

Упрощение регулярного выражения, вызывающего исключение Java StackOverflowException

1 голос
/ 25 марта 2012

Я пытаюсь извлечь следующие элементы из файла C:

  • Комментарии (одиночные и многострочные)
  • Строковые литералы
  • Десятичные, восьмеричные и шестнадцатеричные литералы.

Я написал следующее регулярное выражение, чтобы попытаться найти эти элементы: 

/\*(?:.|[\r\n])*?\*/|"(?:[^"\\\r\n]|\\.)*"|//.*|\b\d+\b|\b0[xX][\da-fA-F]+\b

Выражение состоит из пяти частей ИЛИ вместе.

  • /\*(?:.|[\r\n])*?\*/ проверка многострочных комментариев.
  • "(?:[^"\\\r\n]|\\.)*" проверяет строковые литералы.
  • //.* проверяет наличие однострочных комментариев.
  • \b\d+\b проверяет десятичные и восьмеричные константы.
  • \b0[xX][\da-fA-F]+\b проверяет шестнадцатеричные константы.

Хотя выражение, кажется, работает нормально при тестировании с использованием regexpal и файла C на 500 строк, моя Java-программа выдает исключение StackOverflowException после нескольких совпадений.

Вот код Java, который использует регулярное выражение: 

Pattern itemsOfInterestPattern = Pattern.compile(
        "/\\*(?:.|[\\r\\n])*?\\*/|\"(?:[^\"\\\\\\r\\n]|\\\\.)*\"|//.*|\\b\\d+\\b|\\b0[xX][\\da-fA-F]+\\b");
// Now, go through the source file and process any tags we find
Matcher itemsOfInterestMatcher = itemsOfInterestPattern.matcher(sourceFile);
int matchNumber = 0;
while (itemsOfInterestMatcher.find()) {
    // We've found a token
    ++matchNumber;
    String token = itemsOfInterestMatcher.group();
    // I then have a switch statement that processes each match depending on its type
}

Трассировка стека при переполнении может быть найдена в http://pastebin.com/7eL6mVd2

Что вызывает переполнение стека и как я могу изменить выражение, чтобы оно работало?

Amr

Ответы [ 2 ]

2 голосов
/ 25 марта 2012

Судя по тому, сколько раз java.util.regex.Pattern$LazyLoop.match(...) появляется в трассировке стека, я держу пари, что проблема заключается в использовании неохотного квантификатора *?: сначала он ничего не пытается сопоставить, затем он возвращается и пытается соответствует одному символу, затем он возвращается и пытается сопоставить два символа и так далее. Поэтому, если у вас есть длинный комментарий, ему придется много откатываться назад, что, по-видимому, включает в себя рекурсию. (Я не знаю, включает ли все обратное отслеживание рекурсию или просто обратное отслеживание с неохотным квантификатором; фактически, до сих пор я даже не осознавал, что обратное отслеживание с неохотным квантификатором имело место.) Если вы измените эту часть : 

/\*(?:.|[\r\n])*?\*/

к этому: 

/\*(?:[^*]|\*(?!/))*+\*/

(используя вместо этого собственнический квантификатор *+ - он пытается сопоставить столько, сколько может, и никогда ничего не возвращает), я думаю, вы обнаружите, что обрабатывать длинные комментарии гораздо лучше. Итак, в целом ваш строковый литерал будет выглядеть так: 

"/\\*(?:[^*]|\\*(?!/))*+\\*/|\"(?:[^\"\\\\\\r\\n]|\\\\.)*\"|//.*|\\b\\d+\\b|\\b0[xX][\\da-fA-F]+\\b"

Отредактировано, чтобы добавить (июль '13): У кого-то в моей компании недавно возникла похожая проблема, из-за которой я немного углубился в причину. Я обнаружил, что проблема не только в возврате, но и в сочетании возврата с подгруппой; например, a* или a*? не будет иметь этой проблемы, но (a)* или (a)*? или (?:a)* или (?:a)*?. Выше я предложил отключить возврат, используя *+ вместо *? (и внеся необходимые изменения в подвыражение); но другой подход состоял бы в том, чтобы устранить подвыражение, изменив это: 

/\*(?:.|[\r\n])*?\*/

на это: 

/\*(?s:.*?)\*/

(где запись (?s:...) эквивалентна ..., за исключением того, что она локально включает режим MULTILINE, что означает, что . будет соответствовать любому символу, даже \n). .*? не требует рекурсии для включения возврата.

Тем не менее, я думаю, что *+ подход лучше в этом случае, и, возможно, в большинстве случаев, поскольку его алгоритмическая временная сложность ниже. (.*? требует постоянной попытки сопоставления и повторного сопоставления с остальной частью шаблона; он может выполнять произвольное обратное отслеживание без переполнения стека, но для этого может потребоваться чрезмерное количество времени.)

0 голосов
/ 25 марта 2012

Учитывая ошибку (мы не видим код :() Важный совет: фактический ответ обычно скрыт где-то в первых десяти строках трассировки стека. Вам нужно прочитать его несколько раз, а затем проверить код Кажется, что большинство ошибок связано с регулярным выражением, кроме первых двух: 

at java.lang.AbstractStringBuilder.charAt(AbstractStringBuilder.java:173)
at java.lang.StringBuilder.charAt(StringBuilder.java:55)

ИМХО, вы должны проверить эти две строки (возможно, с помощью отладчика). В других сообщениях говорится, что такие ошибки могут возникать при нехватке памяти - Как проверить большой XML-файл по схеме xsd? . Для начала попробуйте файл меньшего размера с меньшим количеством комментариев и проверьте, возникает ли эта ошибка.

...