Нужна помощь в понимании этого динамического программного решения

Перед исправлением проблемы с StackOverflowError ...

  1. Я хотел бы указать, что ваше текущее regex (\d\*?(;(?=\d))?)+ не может проверить это условие. Каждое значение может включать в себя один * в конце (используется как подстановочный знак для другого соответствия). Он не может отклонить случай 23*4*4*;34*434*34, как показано здесь здесь 1.
  2. Ваше регулярное выражение будет делать ненужный откат на несоответствующем входе.
  3. Java использует один кадр стека для каждого повторения группы (\d\*?(;(?=\d))?) (который повторяется 1 или более раз +).

Правильное регулярное выражение будет:

\d+\*?(?:;\d+\*?)*

Обратите внимание, что это отклонит *, что не слишком ясно из вашего требования, хотите ли вы принять или отклонить это.

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

\d++\*?+(?:;\d++\*?+)*+

Ввод в строковый литерал:

"\\d++\\*?+(?:;\\d++\\*?+)*+"

Я проверил вышеописанное выражение с совпадающим и несоответствующим входом, который имеет более 3600 токенов (разделенных ;).

Сноска

1: regex101 использует аромат PCRE, который немного отличается от аромата Java regex. Однако функции, используемые в вашем регулярном выражении, являются общими между ними, поэтому не должно быть расхождений.

Приложение

  • На самом деле, из моего тестирования с вашим регулярным выражением (\d\*?(;(?=\d))?)+ ( который является неправильным в соответствии с вашим требованием), что делает большинство + притяжательных ++, по-видимому, исправляет проблему StackOverflowError, по крайней мере, в моем тестировании с примерно 3600 токенами (разделенными ;, строка длиной около 20 тыс. символов). Это также, похоже, не приводит к длительному времени выполнения при тестировании на несоответствующую строку.
  • В моем решении сделать квантификатор * для группы (?:;\d+\*?) собственником достаточно, чтобы разрешить StackOverflowError.
    "\\d+\\*?(?:;\\d+\\*?)*+"
    
    Тем не менее, я делаю все притяжательным, чтобы быть в безопасности.

1
задан import_theUser 7 March 2019 в 22:28
поделиться