Почему моя простая грамматика Ragel использует всю память и сбой

Question

Я пытаюсь преобразовать набор регулярных выражений из правил Adblock Plus в оптимизированную функцию, которую можно вызывать из C++.

Я ожидал, что смогу использовать генератор лексеров, такой как Ragel, чтобы сделать это, но когда я пытаюсь с очень маленьким набором Regex, использование памяти становится очень высоким> 30 ГБ, и Ragel завершает работу без сообщения об ошибке и без создания выходного файла.

Я включил игрушечную грамматику ниже, я пытаюсь понять, делаю ли я что-нибудь глупое, что можно было бы оптимизировать для решения проблемы.

#include <string.h>
namespace xab{
 %%{
machine lexer;
WILDCARD = /[A-Za-z0-9;\/\?:@=&$_\.\+!\*'~#^,%:\-]/*;
SUBDOMAIN = /([A-Za-z]([A-Za-z0-9\-]*[A-Za-z0-9])?\.)+/;
SEPERATOR = /[:\/\?=&]/;
main := 
(WILDCARD '&prvtof=' WILDCARD '&poru=' WILDCARD) |
(WILDCARD '.a3s?n=' WILDCARD '&zone_id=' WILDCARD) |
(WILDCARD '/addyn|' WILDCARD ';adtech;' WILDCARD) |
(WILDCARD '/addyn|' WILDCARD '|adtech;' WILDCARD) |
(WILDCARD '/adiframe|' WILDCARD '|adtech;' WILDCARD) |
(WILDCARD '/adserv|' WILDCARD '|adtech;' WILDCARD) |
(WILDCARD '/affiliates.' WILDCARD '.aspx?' WILDCARD) |
(WILDCARD '/affiliates/' WILDCARD '/show_banner.' WILDCARD) |
(WILDCARD '/banner_js.' WILDCARD '?' WILDCARD) |
(WILDCARD '/bannerframe.' WILDCARD '?' WILDCARD) |
(WILDCARD '/banners.' WILDCARD '&iframe=' WILDCARD) |
(WILDCARD '/bannerview.' WILDCARD '?' WILDCARD) |
(WILDCARD '/bannery/' WILDCARD '?banner=' WILDCARD) |
(WILDCARD '/cdn-cgi/pe/bag?r[]=' WILDCARD 'cpalead.com' WILDCARD) |
(WILDCARD '/delivery/' WILDCARD '?advplaces=' WILDCARD) |
(WILDCARD '/eas?camp=' WILDCARD ';cre=' WILDCARD) |
(WILDCARD '/eas?cu=' WILDCARD ';cre=' WILDCARD) |
(WILDCARD '/eas?cu=' WILDCARD ';ord=' WILDCARD) |
(WILDCARD '/ireel/ad' WILDCARD '.jpg' WILDCARD) |
(WILDCARD '/is.php?ipua_id=' WILDCARD '&search_id=' WILDCARD);
write data; 
}%%
bool matchBlacklist(const char *data) {
const char *p = data;

const char *pe = data + strlen(data);
int cs;
//write init
%% write init; 
// write exec
%% write exec;
if (cs >= lexer_first_final)
return true;
return false;
}
}

Answer 1

AFAIK, вы сталкиваетесь с "космическим взрывом DFA".

DFA должен соответствовать всем вашим правилам за один проход по строке. Для этого каждому состоянию необходим переход 1) в начало каждого правила и 2) в середину каждого правила чередования.

Кроме того, WILDCARD может создавать "недетерминированное поведение", потому что, например, в WILDCARD '&prvtof=' WILDCARD '&poru=' WILDCARD править WILDCARD будет соответствовать &prvtof=, Это и огромное количество вариантов в WILDCARD может еще взорвать ДФА.

В руководстве по Ragel 6.8 приведены инструкции по упрощению DFA в разделах "2.5.5 Конкатенация" и "4. Контроль недетерминизма".

Чтобы избежать "космического взрыва DFA", вы можете захотеть "деоптимизировать" машину Ragel с помощью сканеров, тем самым выборочно переключаясь с DFA без состояния на обратный. И вы можете уменьшить недетерминированность с помощью оператора сильной разницы. И вы можете упростить WILDCARD, заменив его any,

action matched {return true;}
main := |*
  '&prvtof=' (any* -- '&poru=') '&poru=' => matched;
  '.a3s?n=' (any* -- '&zone_id=') '&zone_id=' => matched;
  any;
*|