| 1 | <!-- kb_card |
| 2 | id: kb-regex-engines-efficiency-v1 |
| 3 | title: Regex — движки, backtracking, эффективность (L2) |
| 4 | cluster: regex-friedl-mre3 |
| 5 | kb_layer: L2 |
| 6 | book_alignment: Механика NFA/DFA, упорядоченный выбор, катастрофический backtracking — ядро теории Friedl. |
| 7 | last_reviewed_utc: 2026-03-21 |
| 8 | --> |
| 9 | |
| 10 | # Regex: движки и эффективность (L2) |
| 11 | |
| 12 | ## Назначение |
| 13 | |
| 14 | Объяснить **почему** паттерн ведёт себя так, а не иначе: порядок перебора, откаты, асимптотика. Это слой для отладки «зависаний» и тонкой настройки. |
| 15 | |
| 16 | ## Инварианты |
| 17 | |
| 18 | - Теоретический **DFA** и практический **NFA** (с обратным поиском) ведут себя по-разному; большинство «богатых» диалектов — NFA. |
| 19 | - «Линейное» время не гарантируется произвольным regex. |
| 20 | |
| 21 | <!-- section:dfa-vs-nfa --> |
| 22 | ## DFA и NFA (концептуально) |
| 23 | |
| 24 | - **DFA (детерминированный автомат):** из состояния на символ — однозначный переход; классический grep для простых классов regex часто строит DFA-подобное ядро. |
| 25 | - **NFA (недетерминированный):** допускается несколько «активных» путей; **regex-движки общего назначения** обычно симулируют NFA с **backtracking**: при тупике откатываются к последнему выбору. |
| 26 | |
| 27 | **Следствие:** одинаковый на вид паттерн может быть «быстрым» в одном инструменте и «взрывным» в другом из-за различий реализации и оптимизаций. |
| 28 | <!-- /section:dfa-vs-nfa --> |
| 29 | |
| 30 | <!-- section:backtracking --> |
| 31 | ## Backtracking как стек решений |
| 32 | |
| 33 | 1. Движок двигается слева направо. |
| 34 | 2. Квантификаторы и альтернации создают **точки выбора**. |
| 35 | 3. При неудаче дальше по паттерну движок **откатывает** последний жадный выбор и пробует меньшее повторение / другую ветвь `|`. |
| 36 | |
| 37 | **Ordered alternation:** в `a|ab` сначала проверяется `a`; это влияет не только на скорость, но и на то, какая ветвь сработает при перекрытии. |
| 38 | |
| 39 | **Классический риск:** вложенные квантификаторы на подмножествах без жёстких разделителей — экспоненциальное число комбинаций отката. |
| 40 | <!-- /section:backtracking --> |
| 41 | |
| 42 | <!-- section:catastrophic --> |
| 43 | ## Катастрофический backtracking |
| 44 | |
| 45 | Симптом: CPU 100%, «вечный» матч на умеренной длине строки. |
| 46 | |
| 47 | Типичный каркас (идея, не единственный случай): |
| 48 | |
| 49 | - Внешний `(...)*` или `+` на структуру, которая сама содержит неоднозначные повторы. |
| 50 | - Альтернации, дающие много способов разбить одну и ту же подстроку. |
| 51 | |
| 52 | **Стратегии лечения:** |
| 53 | |
| 54 | 1. **Ужесточить** грамматику: явные разделители, более узкие классы символов. |
| 55 | 2. **Атомарная группа** `(?>...)` (где доступно) — запрет отката назад внутрь. |
| 56 | 3. **Владение** `*+`, `++`, `?+` (possessive) — то же на уровне квантификатора. |
| 57 | 4. **Якоря и lookahead** для «отсечения» заведомо неверных позиций раньше. |
| 58 | 5. **Таймаут / лимит шагов** в продакшене (.NET: `Regex.Match(..., TimeSpan)`; в других средах — свои ограничения или не запускать пользовательский regex на длинных строках). |
| 59 | |
| 60 | **Не полагаться** на «оптимизатор сделает быстро» без измерения на репрезентативных входах. |
| 61 | <!-- /section:catastrophic --> |
| 62 | |
| 63 | <!-- section:possessive-atomic --> |
| 64 | ## Атомарные группы и владение |
| 65 | |
| 66 | - **Владение (possessive):** `*+`, `++`, `?+`, `{m,n}+` там, где поддерживается — **не путать** с **ленивыми** `*?`, `+?`, `??`, `{m,n}?`. |
| 67 | - Смысл: после того как квантификатор «съел» символы, **откат количества повторов** для этой группы запрещён. |
| 68 | |
| 69 | Где **нет** владения/атомарности — эмулируй узким lookahead или переписыванием (например, запретить пересечение множеств у вложенных `*`). |
| 70 | <!-- /section:possessive-atomic --> |
| 71 | |
| 72 | ## Связи |
| 73 | |
| 74 | - `kb-regex-syntax-features-v1.md` |
| 75 | - `kb-regex-flavors-practice-v1.md` |
| 76 | - `regex-playbook.md` |
| 77 | |
| 78 | |