Здравствуйте, Alexander G, Вы писали:
AG>Здравствуйте, jazzer, Вы писали:
J>>У тебя реально файлы такие? Т.е. все эти скобки еще миллион раз закроются же? Если не секрет, что ты за задачу решаешь, что тебе нужно парсить миллион раз вложенные скобки?
AG>Какой файл — не знаю, в дампе кучи нет, из стекового бектрейса извлекать сложно. Да, миллион скобок — это не реально, но и реальная грамматика сложнее. Я верю, что это не ошибка в моём коде, а патологический случай входных данных.
Ну на этот случай можно и защиту поставить.
Данные могут быть патологическими по-разному, может быть просто тупой огромный файл, результат разбора которого всю память забьет безо всякой рекурсии.
AG>Кстати, boost::regex имеет макрос BOOST_REGEX_NON_RECURSIVE для тех, кто хочет обрабатывать любые входные данные без переполнения стека.
Ну так то ж регэкспы, а Спирит — это парсер, реализующий рекурсивный спуск, трудно требовать от него нерекурсивности
Здравствуйте, ., Вы писали:
.>jazzer wrote:
>> У тебя реально файлы такие? Т.е. все эти скобки еще миллион раз >> закроются же? Если не секрет, что ты за задачу решаешь, что тебе нужно >> парсить миллион раз вложенные скобки? .>Хм... а это реально может быть проблемой, если есть возможность DoS-аттак. Нехорошо, если какой-нибудь сервис будет падать по переполнению стека при специально сформированных входных данных.
Ну так защиту надо поставить, ограничить глубину рекурсии, на спирите это делается в две строчки.
Здравствуйте, jazzer, Вы писали:
J>Ну на этот случай можно и защиту поставить. J>Данные могут быть патологическими по-разному, может быть просто тупой огромный файл, результат разбора которого всю память забьет безо всякой рекурсии.
Можно. Просто тупо огромный файл просто кинет std::bad_alloc, оно покажется пользователю как "Недостаточно памяти для обработки команды". А к stack overflow я не был готов. Более того, глобально его обрабатывать и не собираюсь, пусть лучше крешдампы приходят для переполнений в других местах. Конечно, теперь, когда я знаю, что в спирите может быть stack overflow, я могу обернуть его в SEH обработку с восстановлением.
J>Ну так то ж регэкспы, а Спирит — это парсер, реализующий рекурсивный спуск, трудно требовать от него нерекурсивности
Ну так в моём случае нужно пересмотреть метод разбора. Например, если бы нужно было было просто проверить балланс скобок, то хватило бы одного цикла и двух переменных
jazzer wrote:
> Ну на этот случай можно и защиту поставить.
Интересно как.
> Ну так то ж регэкспы, а Спирит — это парсер, реализующий рекурсивный > спуск, трудно требовать от него нерекурсивности
Рекурсивный спуск не означает, что должен использоваться системный стек и падать по его переполнению. Можно использовать банальный массив, никто не отменял std::stack, который честно вернёт out of memory в худшем случае.
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, ., Вы писали:
.>jazzer wrote:
>> Ну на этот случай можно и защиту поставить. .>Интересно как.
ну как-то так:
int i = 0;
group = ch_p( '(' )[ increment_or_throw_a(i,10000) ]
>> +element
>> ch_p( ')' )[ decrement_a(i) ];
increment_a и decrement_a есть в стандартной поставке, сделать increment_or_throw_a из increment_a, думаю, не составит труда.
>> Ну так то ж регэкспы, а Спирит — это парсер, реализующий рекурсивный >> спуск, трудно требовать от него нерекурсивности .>Рекурсивный спуск не означает, что должен использоваться системный стек и падать по его переполнению. Можно использовать банальный массив, никто не отменял std::stack, который честно вернёт out of memory в худшем случае.
тоже верно, хотя рекурсивные вызовы все равно будут, даже если все данные вынести на внешний стек в куче, и системный стек будет расходоваться.
Не уверен, что можно сделать так, чтоб системный стек не расходовался совсем, сохранив способ описания грамматики через expression templates.
jazzer wrote:
> increment_a и decrement_a есть в стандартной поставке, сделать > increment_or_throw_a из increment_a, думаю, не составит труда.
Так-то понятно, ведь это тривиальный пример. Но далеко не очевидно, в каком месте какой-нибудь реальной, сложной грамматики нужно будет такие штуки расставить.
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Re[12]: Какой уровень допустим ? 640 хватит всем ?
Здравствуйте, ., Вы писали:
.>Так-то понятно, ведь это тривиальный пример. Но далеко не очевидно, в каком месте какой-нибудь реальной, сложной грамматики нужно будет такие штуки расставить.
А ещё, если мы таки хотим обрабатывать большие файлы, как мы можем знать ограничение имплементации ?
В моём примере, 10 K скобок валят релиз. В дебаге, естественно, намного меньше. Разумеется, сильно зависит от опций. У более сложной граматики ограничение может быть существенно ближе.
Русский военный корабль идёт ко дну!
Re[13]: Какой уровень допустим ? 640 хватит всем ?
Здравствуйте, Alexander G, Вы писали:
AG>Здравствуйте, ., Вы писали:
.>>Так-то понятно, ведь это тривиальный пример. Но далеко не очевидно, в каком месте какой-нибудь реальной, сложной грамматики нужно будет такие штуки расставить.
AG>А ещё, если мы таки хотим обрабатывать большие файлы, как мы можем знать ограничение имплементации ?
AG>В моём примере, 10 K скобок валят релиз. В дебаге, естественно, намного меньше. Разумеется, сильно зависит от опций. У более сложной граматики ограничение может быть существенно ближе.
практически всегда можно разумное ограничение поставить, просто исходя из смысла задачи, а не из возможностей имплементации.
А если действительно по смыслу задачи надо поддерживать огромную вложенность, то можно просто в настройках компилятора соответствующий объем стека установить и не волноваться более на его счет.
Ну либо сменить движок парсинга на такой, которой не задействует стек процесса.
Но, имхо, это экзотическая задача и нужно такое очень редко.
Здравствуйте, jazzer, Вы писали:
J>практически всегда можно разумное ограничение поставить, просто исходя из смысла задачи, а не из возможностей имплементации.
Понятно что надо исходить из задачи, я к тому, что для экзотической задачи таки не хватает возможностей имплементации.
J>А если действительно по смыслу задачи надо поддерживать огромную вложенность, то можно просто в настройках компилятора соответствующий объем стека установить и не волноваться более на его счет.
Ну поставлю я 80 МБ стека, и сколько тредов я после этого смогу создать ?
Хотя поставить большой стек для отдельно взятого треда со спиритом — вариант.
J>Ну либо сменить движок парсинга на такой, которой не задействует стек процесса. J>Но, имхо, это экзотическая задача и нужно такое очень редко.
Я думаю ещё можно попробовать выделить нерекурсивную часть грамматики и оставить её на спирите, а вложенные скобки разрулить вручную.
Русский военный корабль идёт ко дну!
Re[15]: Какой уровень допустим ? 640 хватит всем ?
Здравствуйте, Alexander G, Вы писали:
AG>Здравствуйте, jazzer, Вы писали:
J>>практически всегда можно разумное ограничение поставить, просто исходя из смысла задачи, а не из возможностей имплементации.
AG>Понятно что надо исходить из задачи, я к тому, что для экзотической задачи таки не хватает возможностей имплементации.
Для экзотических задач обычно не подходят средства для широкого применения Это общее правило
Иначе бы всем хватало вижуал бейсика
J>>А если действительно по смыслу задачи надо поддерживать огромную вложенность, то можно просто в настройках компилятора соответствующий объем стека установить и не волноваться более на его счет.
AG>Ну поставлю я 80 МБ стека, и сколько тредов я после этого смогу создать ? AG>Хотя поставить большой стек для отдельно взятого треда со спиритом — вариант.
либо отдельный процесс. Грохнется — не жалко.
J>>Ну либо сменить движок парсинга на такой, которой не задействует стек процесса. J>>Но, имхо, это экзотическая задача и нужно такое очень редко.
AG>Я думаю ещё можно попробовать выделить нерекурсивную часть грамматики и оставить её на спирите, а вложенные скобки разрулить вручную.
Ну там еще есть то, что между скобками, с ним, я думаю, самая возня...
