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

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

Источник:Все о Google на Хабрахабре