3

Когда то давно задавал подобный вопрос на другом форуме, но никто внятно не ответил.

Есть две библиотеки для работы с регулярными выражениями по стандарту PCRE. Это boost::regex (или урезанный вариант std::regex) и библиотека PCRE.

Собственно есть сложное регулярное выражение.

там присутствуют подобные выражения

"+string_open+"(?>(?>(?!"+string_open+"|"+string_close+").)+|(?R))*"+string_close+"

Всё это дело замечательно отрабатывает для небольших входящих строк. но когда входящая строка превышает допустим 1000 символов и условия указанные в регулярном выражении выполняются, то выбрасывается исключение и в boost и в pcre.

Ran out of stack space trying to match the regular expression.

Собственно здесь говорится что происходит выход за пределы некоего стека.

1) Библиотеку pcre можно собрать из исходников, и увеличить там некоторые константы #define , точно не помню что именно там было, то ли указание на использование рекурсивной модели работы то ли еще что то. Но в общем скомпилированная таким образом библиотека pcre стала работать с неограниченными по объему строками и решала поставленную задачу. Сейчас используется именно такая модель.

Однако данный метод увеличил время работы регулярных выражений в 10-20 раз. раньше программа поднималась за 4 секунды, а с использованием такого подхода 40-50 секунд.

2) В boost ни где не смог найти информацию, о том как и где изменять значения этого стека.

Что из себя представляет этот стек? Этот тип формируют сами библиотеки?

Невозможность изменить этот стек, выглядит нелогичным, потому что программа нормально отрабатывается для строки допустим 990 символов. Время выполнения разбора 5 миллисекунд. Занимаемая память 400 кб. Добавляются 20 символов и всё ran out stack.

10
  • Как дела с этой же регуляркой у PIRE Commented 22 окт. 2012 в 11:43
  • А изменение размера стека командой bash не помогает? ulimit -s ulimit -s <new-value>
    – alexlz
    Commented 22 окт. 2012 в 11:59
  • Вообще по поводу PIRE не помню, я её точно не испытывал. Помню, что у yandex была собственная библиотека, наверное это она и есть. И там отсутствовали многие конструкции, вроде опережающих проверок (?<=) или (?=), которые удалили ради производительности. Смотрел разные реализации регулярных выражений для C++(их там более 10). Насколько помню только pcre и boost поддерживают полный стандарт PCRE. У boost есть #define BOOST_REGEX_NON_RECURSIVE #define BOOST_REGEX_BLOCKSIZE #define BOOST_REGEX_MAX_CACHE_BLOCKS в boost/regex/config.hpp Но есть ли возможность без пересборки .lib сделать?
    – manking
    Commented 22 окт. 2012 в 12:00
  • @alexlz это под win.
    – manking
    Commented 22 окт. 2012 в 12:02
  • 4
    @manking Без пересборки нельзя, поскольку BOOST_REGEX_NON_RECURSIVE - это параметр конфига. Мне кажется, что пересборка с BOOST_REGEX_NON_RECURSIVE имеет неплохие шансы решить вашу проблему и это решение, естественно, будет лучше по сравнению с манипуляциями с размером стека (иначе всегда можно будет найти исходные данные, которые радостно свалят ваше приложение). Commented 22 окт. 2012 в 12:08

2 ответа 2

3

Это читали? Что бы сделал я?

  1. Попробовал обе опции: и BOOST_REGEX_RECURSIVE, и BOOST_REGEX_NON_RECURSIVE;
  2. Увеличил бы BOOST_REGEX_BLOCKSIZE и BOOST_REGEX_MAX_BLOCKS.
3
  • Это я читал давно, но правда на русском сайте по boost. И мне тогда казалось, что эти параметры надо указывать перед включением boost в свою программу. Ладно попробую собрать заного. Спасибо.
    – manking
    Commented 22 окт. 2012 в 12:17
  • Поставил BOOST_REGEX_NON_RECURSIVE Увеличил значения в 2 раза. define BOOST_REGEX_BLOCKSIZE 8096 define BOOST_REGEX_MAX_BLOCKS 2096 Заработало. Увеличил входящий текст в два раза снова исключение. Увеличил значения в несколько раз, скорость работы упала. Отсюда еще вопрос. Можно ли в boost самостоятельно указать требуемую .lib не влезая в файлы включения #include <boost\regex.hpp>. Вот как то так ifdef regex_128 pragma comment(lib, "libboost_regex_128.lib") ifdef regex_256 pragma comment(lib, "libboost_regex_256.lib") И насколько это нормально?
    – manking
    Commented 22 окт. 2012 в 14:00
  • В любом случае, эти меры решают проблемы только на половину - на этапе сборки проекта, - а все же лучше не иметь ее в runtime. Думаю, можно найти способ динамический увеличивать размер блока при обнаружении больших входных данных, иначе не сегодня, так завтра проблема может всплыть снова, причем не у вас, а у пользователей вашей системы. Если boost этого не позволяет сделать, ищите другую реализацию RegExp. Commented 23 окт. 2012 в 10:12
0

Для такой задачи лучше использовать более серьёзный парсер, нежели регулярные выражения. Например, boost::spirit. Обе проблемы — стека и быстродействия — решаются сами собой. Из "недостатков" могу отметить большее время компиляции (порядка десятков секунд, частично решаемо с помошью прекомпилированных хэдеров) и достаточно крутая в начале кривая обучения (там активно используются ленивые вычисления, к логике которых надо привыкнуть — но дальше всё проще).

1
  • К недостаткам boost::spirit можно отнести и весьма нетривиальную отладку при возникновении ошибок анализа выражения, т.к. шаблонов там "тьма тьмущая". Commented 24 окт. 2012 в 5:42

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.