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

Question

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

• Комментарии (одиночных и множественных линий)
• строковых литералов
• Decimal, восьмеричные и шестнадцатеричные литералы.

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

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

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

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

Хотя выражение, похоже, отлично работает при тестировании с использованием regexpal и файла с 500 строками C, моя 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

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

Амр

Answer 1

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

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

к этому:

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

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

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

---

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

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

к этому:

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

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

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

Answer 2

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

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

ИМХО вы должны проверить эти две строки (возможно, с помощью отладчика) Другие сообщения говорят, что такие ошибки может быть брошен, когда у вас заканчивается память - How to validate big xml against xsd schema?. Попробуйте уменьшить размер файла с меньшим количеством комментариев для начала и проверьте, RS.