RE2 (программное обеспечение)
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
| Оригинальный автор(ы) | |
|---|---|
| Первоначальный выпуск | 11 марта 2010 г [1] |
| Стабильная версия | 01.04.2021 / 1 апреля 2021 г [2] |
| Репозиторий | |
| Написано в | С++ |
| Операционная система | Кросс-платформенный |
| Тип | сопоставления шаблонов Библиотека |
| Лицензия | БСД |
| Веб-сайт | github |
RE2 — это программная библиотека , которая реализует механизм регулярных выражений через конечные автоматы с использованием теории автоматов , в отличие от почти всех других библиотек регулярных выражений , которые используют с обратным отслеживанием реализации . Он предоставляет интерфейс C++ .
RE2 был реализован и использован Google . «на лету», Библиотека использует детерминированный алгоритм конечного автомата основанный на Кена Томпсона Plan 9 grep . [3]
Сравнение с PCRE
[ редактировать ]RE2 обычно сравним по производительности с Perl-совместимыми регулярными выражениями (PCRE). Для некоторых операторов регулярных выражений, таких как | (оператор чередования или логической дизъюнкции ) превышает PCRE. С другой стороны, в отличие от PCRE, который поддерживает такие функции, как обратные ссылки , RE2 способен распознавать только обычные языки благодаря своей конструкции с использованием Thompson DFA. [3] алгоритм. Он также немного медленнее, чем PCRE, для операций захвата в скобках.
PCRE может использовать большой рекурсивный стек с соответствующим высоким использованием памяти, что приводит к экспоненциальному времени выполнения определенных шаблонов. Напротив, RE2 использует фиксированный размер стека и гарантирует, что время его выполнения увеличивается линейно (а не экспоненциально) с размером входных данных. Максимальный объем памяти, выделенный с помощью RE2, можно настроить.
RE2 имеет немного меньший набор функций, чем PCRE, но имеет очень предсказуемое время выполнения и максимальное выделение памяти. Это может сделать его более подходящим для использования в серверных приложениях, которые требуют ограничений по использованию памяти и времени вычислений. PCRE, с другой стороны, поддерживает больше функций, таких как обходы, обратные ссылки и рекурсия , но имеет непредсказуемое время выполнения и использование памяти, которое может неограниченно расти.
Принятие
[ редактировать ]Использование в продуктах Google
[ редактировать ]RE2 используется такими Google продуктами , как Gmail , Google Documents и Google Sheets . [4] См. документацию по синтаксису на GitHub: Синтаксис RE2 .
В Google Sheets он используется в функциях RegexMatch() , RegexReplace() , RegexExtract() и функции поиска и замены . RegexExtract() не использует группировку .
Связанные библиотеки
[ редактировать ]Алгоритм RE2 был переписан на Rust как пакет «regex». CloudFlare Брандмауэр веб-приложений использует этот пакет, поскольку алгоритм RE2 невосприимчив к ReDoS . [5]
Расс Кокс также написал RE1, более раннее регулярное выражение, основанное на интерпретаторе байт-кода. [6] OpenResty использует форк RE1 под названием «sregex». [7]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Кокс, Расс (11 марта 2010 г.). «RE2: принципиальный подход к сопоставлению регулярных выражений» . Блог Google с открытым исходным кодом . Проверено 29 мая 2020 г.
- ^ «Выпуски» . Гитхаб . Проверено 3 мая 2021 г.
- ^ Jump up to: а б Кокс, Расс. «Сопоставление регулярных выражений в дикой природе» . swtch.com .
- ^ «Найти и использовать найти и заменить» . Проверено 24 марта 2020 г.
- ^ «Ускорение WAF на 40 %» . Блог Cloudflare . 1 июля 2020 г.
- ^ «Сопоставление регулярных выражений: подход виртуальной машины» . swtch.com .
- ^ «openresty/sregex: Perl-совместимый механизм регулярных выражений на основе NFA/DFA без обратного отслеживания, сопоставляющий большие потоки данных» . OpenResty. 6 февраля 2024 г.