RE2 — новая библиотека регулярных выражений / C++ / Хабрахабр

RE2 — новая библиотека регулярных выражений

Вчера Google выпустил новую библиотеку регулярных выражений — RE2. Библиотека написана на C++.

Существует два подхода к реализации регулярных выражений: недетерминированные конечные автоматы (NFA) и детерминированные конечные автоматы (DFA). Первый механизм регулярных выражений используется, например, в Perl, Python, Ruby и .NET. К сожалению, в этом случае время работы программы может расти экспоненциально, а также может неограниченно расти использование стека. Такое поведение оказалось неприемлемым для таких проектов Google, как Code Search, Sawzall и Bigtable, поэтому программисты компании написали библиотеку на основе детерминированных конечных автоматов. RE2 гарантирует линейную скорость выполнения поиска и ограниченное использование стека. DFA также используется, например, в lex и egrep. В отличие от большинства подобных реализаций RE2 поддерживает почти все основные возможности PCRE.

Библиотека распространяется под BSD лицензией.

UPD: Убрал Tcl из примеров NFA, сейчас там используются DFA.

+39

12 марта 2010, 18:16

kureimoru

комментарии (23)

НЛО прилетело и опубликовало эту надпись здесь

kureimoru 12 марта 2010, 23:41 # ↑

Если я правильно понял документацию (под рукой нет ни библиотеки, ни даже компилятора C++), то как-то так:

std::string text("multiline\ntext");
int lineno = 2;
std::ostringstream replacement;
replacement << "sprintf '%05d ', " << lineno++;
re2::RE2::GlobalReplace(&text, "^", replacement.str());

НЛО прилетело и опубликовало эту надпись здесь

kureimoru 13 марта 2010, 00:08 # ↑

А, тьфу ты, не выполнит, конечно. В любом случае, это отличие плюсов от перла, регекспы не меняются в обоих случаях. Вот:

replacement << setfill('0') << setw(5) << lineno++;

НЛО прилетело и опубликовало эту надпись здесь

kureimoru 13 марта 2010, 00:22 # ↑

Да, этого с ней сделать не получится. Все функции замены (и проверки) в библиотеке принимают фиксированные строковые значения и вызов сторонних функций или callback'и на каждую замену не поддерживают.

Bonart 13 марта 2010, 11:03 #

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

–8

tpolm 13 марта 2010, 15:30 # ↑

спасибо, Кэп!

impwx 13 марта 2010, 11:09 #

В TCL гибридный механизм, который работает скорее как DFA, нежели NFA.

kureimoru 13 марта 2010, 11:21 # ↑

Да, вы правы, в той же статье Tcl вспоминают в контексте DFA, а не NFA. Я поправил пост.

Bonart 13 марта 2010, 11:43 # ↑

ЕМНИП там DFA ищет образец целиком, а потом на него натравливается NFA. Т.е. с точки зрения расхода ресурсов это все-таки NFA, в котором DFA-дополнение используется в целях оптимизации

impwx 13 марта 2010, 13:56 # ↑

Но работает он с DFA-скоростью, т.е. в любом случае, есть ли совпадение или нет, он требует одинаковое время для поиска.

Bonart 13 марта 2010, 19:40 # ↑

Нет — DFA-скорость при возможности достигается, но в общем случае не гарантируется. Главное преимущество чистого DFA для гугла (не надо думать об оптимизации самого регэкспа) в этом случае не реализуется.

–19

rev 13 марта 2010, 12:15 #

Вау! 2010 год, а плюс-плюсники открыли для себя регулярные выражения

NeonMercury 13 марта 2010, 12:18 # ↑

Вы, как я понял, не пишите на плюсах, не понимаете о чём идёт речь, так зачем холиварить?!
Просто появилась ещё одна либа для регэкспов, не более

–12

rev 13 марта 2010, 12:21 # ↑

Ваша логическая цепочка обрывается на первой половине предложения. Писал, теперь вот по таким постам не жалею, что слез. Спасибу автору.

stab 13 марта 2010, 12:53 #

Странно, что в сырцах есть как файл nfa.cc так и dfa.cc, таки решение гибридное, если судить по коду в re2.cc.

Bonart 13 марта 2010, 13:26 # ↑

Тогда нужны точные критерии, когда подрубается NFA (подозреваю, что при использовании сохраняющих скобок), иначе слова о линейном потреблении ресурсов останутся только словами.

impwx 13 марта 2010, 14:04 #

Почитал только что список возможностей — подожду использовать, пока не сделают обратные ссылки и опережающую \ ретроспективную проверки. Никто не тестил на скорость относительно PCRE?

tpolm 13 марта 2010, 15:48 # ↑

вы статью читали? Там по ссылкам есть тестирование скорости относитлеьно PCRE

impwx 13 марта 2010, 16:14 # ↑

Прошу прощенья, не нашел с первого раза :)
Если кому-то интересно — сравнение тут.

Bonart 13 марта 2010, 19:33 # ↑

Обе эти фичи на DFA нереализуемы принципиально. С ними о линейности требований к ресурсам можно забыть.

impwx 13 марта 2010, 21:57 # ↑

А жаль!

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Языки программирования ↓

C++