algorithms · advanced · 7d
Движок регулярных выражений
Собери движок регулярных выражений с нуля через конструкцию Томпсона и симуляцию подмножества состояний — тот же метод, что делает grep и re2 иммунными к катастрофическому обратному ходу.
Результат
Движок регулярных выражений, который компилирует паттерны в NFA Томпсона и матчит через симуляцию множества состояний, поддерживает конкатенацию, альтернацию `|`, `*`, `+`, `?`, группировку `()` и `.`, работает в O(m·n) по всей строке и гарантированно не зависает на патологических входах вроде `(a*)*b` против длинной строки из 'a'.
Этапы
0/6 · 0%- 01Разбери паттерн в AST
До любого автомата нужно конкретное синтаксическое дерево. Паттерн регулярного выражения — это контекстно-свободная грамматика: альтернация (`a|b`) связывает слабее всего, затем конкатенация (соположение), затем постфиксные кванторы (`*`, `+`, `?`), затем атомы (литерал, `.` или группа `(...)`). Чистый рекурсивно-нисходящий парсер справляется с этим в четырёх взаимно рекурсивных функциях — parseAlternation, parseConcatenation, parseQuantifier, parseAtom — с приоритетом, зашитым в стек вызовов, а не в таблицу приоритетов. Почему не Pratt? Потому что эта грамматика достаточно мала, чтобы рекурсивный спуск был самодокументирующимся, а глубина вызовов точно отражает иерархию приоритетов. Узлы AST: Literal(char), AnyChar, Concat(left, right), Alter(left, right), Star(child), Plus(child), Optional(child). Храни дерево чисто структурным без логики NFA — это принадлежит строителю автомата, а не парсеру.
Критерии готовности- Парсер корректно обрабатывает вложенные группы, все кванторы, альтернацию с несколькими ветками и `.`; отклоняет незакрытые скобки и неизвестные токены с понятным сообщением об ошибке.
- AST для `(ab|cd)*` проверяем в тесте: Star, оборачивающий Alter из двух Concat-ов, без идентификаторов NFA-состояний или переходов на этом слое.
Самопроверка
Проведи парсер через `a?b|c+` и проследи, какая рекурсивная функция обрабатывает каждый символ; senior-ревьюер проверяет корректность приоритета (квантор связывает теснее конкатенации, конкатенация — теснее альтернации) и что грамматика не использует глобальную таблицу приоритетов.
- 02Построй NFA Томпсона из AST
Конструкция Томпсона 1968 года преобразует AST регулярного выражения в NFA, компонуя небольшие, чётко определённые фрагменты NFA: каждый тип узла даёт фрагмент ровно с одним начальным состоянием и одним принимающим, соединёнными помеченными переходами (символ или epsilon). Правила компоновки: Literal — один переход по этому символу; Concat(A, B) — epsilon из принимающего A в начало B; Alter(A, B) — новое начало с epsilon-переходами в оба начала A и B и epsilon-переходами из обоих принимающих в новое принимающее; Star(A) — новые начало/принимающее плюс epsilon-переходы для пропуска A целиком или возврата; Plus(A) = Concat(A, Star(A)); Optional(A) = Alter(A, epsilon-фрагмент). Результат — NFA с O(m) состояниями и O(m) переходами для паттерна длиной m. Никогда не генерируй более 2 состояний на узел AST — конструкция Томпсона гарантирует эту границу. Конструкция должна быть чистыми данными (состояния + переходы); симулятор — следующий шаг.
Критерии готовности- Каждый тип узла AST отображается в фрагмент NFA не более чем с 2 новыми состояниями; ты можешь вывести таблицу состояний/переходов для малого паттерна и вручную проследить каждое epsilon- и символьное ребро.
- NFA для `(ab|cd)*` содержит не более 18 состояний (2 на символ, 2 на Alter, 2 на Star) — подтверди счёт в тесте.
Самопроверка
Нарисуй фрагмент NFA для `a|b` — два символьных перехода, общее начало, общее принимающее — и объясни, почему конструкция Томпсона никогда не требует более 2 новых состояний на оператор; senior-ревьюер проверяет, что состояния не переиспользуются между фрагментами (только свежие идентификаторы).
- 03Симуляция: epsilon-замыкание и множество состояний
Симуляция — это выплата за конструкцию Томпсона. Вместо того чтобы следовать по одному пути за раз (рекурсивный backtracking), ты поддерживаешь множество всех состояний, в которых сейчас может находиться NFA, и продвигаешь всё множество вместе на каждом входном символе. Алгоритм: (1) вычисли epsilon-замыкание начального состояния — все состояния, достижимые за ноль или более epsilon-переходов; (2) для каждого символа входа найди все состояния, достижимые символьным переходом из любого состояния текущего множества, затем возьми epsilon-замыкание результата; (3) после потребления всего входа прими тогда и только тогда, когда принимающее состояние есть в финальном множестве. Представление в виде множества состояний и обеспечивает линейное время: каждое состояние посещается не более одного раза на входной символ, так что суммарная работа O(m·n), где m — количество состояний NFA, n — длина входа. Без рекурсии, без backtracking, без стека — только BFS по epsilon-рёбрам и битовое множество или Set идентификаторов состояний. Матч всей строки означает, что нужно потребить все символы и закончить в принимающем состоянии; не принимай префикс.
Критерии готовности- Литеральные паттерны матчат точно и отклоняют похожие строки; `.` матчит любой один символ; пустая строка корректно обрабатывается (принимается или отклоняется в зависимости от паттерна).
- `a*` матчит пустую строку и любую последовательность 'a'; `a+` отклоняет пустую строку и матчит одну или более 'a'; `a?b` матчит и 'b', и 'ab'.
Самопроверка
Проследи эволюцию множества состояний при матче 'ab' против паттерна `(a|b)*` — перечисли точное множество после каждого символа; senior-ревьюер проверяет, что epsilon-замыкание вычисляется после каждого шага по символу, а не только в начале.
- 04Кванторы: `*`, `+`, `?` и их граничные случаи
Каждый квантор имеет тонко различающуюся форму NFA и свой набор входов, которые должны быть доказаны корректными. `*` (ноль и более) должен принимать пустую строку, 'a', 'aaa' и отклонять 'aaabbb' против `(ab)*` — последний должен отклоняться, потому что 'aaabbb' не является последовательностью пар 'ab'. `+` (один и более) — это Concat(A, Star(A)) в NFA: должен отклонять пустую строку, но принимать 'a' и 'aaa'. `?` (ноль или один) — это Alter(A, empty): должен матчить 'b' и 'ab' против `a?b`, но отклонять 'aab'. Граничные случаи, выявляющие ошибки: квантор над группой, например `(ab)+`, где фрагмент NFA группы используется ровно один раз в Plus, но цикл оборачивает всю группу; вложенные кванторы, например `(a+)*`; и случай пустого паттерна. Проработай каждый квантор минимум с тремя входами для принятия и тремя для отклонения до объявления готовности.
Критерии готовности- `(ab|cd)*` матчит пустую строку, 'ab', 'cdab', 'abcdab'; отклоняет 'abc', 'a', 'abcd' (не полная последовательность пар).
- Вложенный квантор `(a+)*` обрабатывается без ошибок — NFA строится, симуляция завершается, и входы матчатся корректно.
Самопроверка
Покажи фрагмент NFA Томпсона для `a+` в виде диаграммы состояний — объясни, как Plus переиспользует фрагмент для `a`, а не копирует его, и почему это важно для линейности числа состояний; senior-ревьюер проверяет, что Plus — это Concat(фрагмент, Star(фрагмент)) с теми же физическими состояниями, а не копией.
- 05Альтернация `|` и группировка `()`
Альтернация — это оператор, который наиболее наглядно демонстрирует превосходство NFA Томпсона над backtracking. Движок с backtracking, вычисляющий `(a|a)*b` против длинной строки из 'a' без 'b', перебирает каждую экспоненциальную комбинацию веток перед тем как провалиться. NFA Томпсона схлопывает все ветки в одно множество состояний: когда текущее множество расширяется через epsilon-переходы узла Alter, обе ветки добавляются одновременно — движок никогда не фиксируется на одной ветке и никогда не возвращается назад. Реализация Alter: одно новое начальное состояние с epsilon-переходами в оба начала A и B, и одно новое принимающее состояние с epsilon-переходами из обоих принимающих A и B. Группы `(...)` прозрачны для построения NFA: разбери их в поддерево и передай строителю рекурсивно; специальный узел 'group' не нужен (захватывающие группы — это отдельная задача, которую ты явно не реализуешь). Протестируй, что `(cat|dog)` матчит 'cat' и 'dog', отклоняет 'ca' и 'cats', и что глубоко вложенная альтернация типа `((a|b)|(c|d))` обрабатывается.
Критерии готовности- `(cat|dog)` матчит 'cat' и 'dog'; отклоняет 'ca', 'cats', 'do', 'dogs'.
- Альтернация внутри Star, например `(ab|cd)*`, корректно работает для входов из смешанных пар — доказывая, что подход с множеством состояний обрабатывает декартово произведение вариантов веток без их перечисления.
Самопроверка
Объясни, почему `(a|b)*` против 'abba' выполняет ровно 4 · (состояния NFA) операций, а не 2^4 — проследи, какие состояния есть в множестве после каждого символа; senior-ревьюер проверяет, что множество никогда не содержит дублирующихся идентификаторов состояний и что ветки альтернации сосуществуют в одном множестве, а не исследуются последовательно.
- 06Гарантия линейного времени: без катастрофического обратного хода
Последний этап — доказать то, что ты построил: не только что оно работает на типичных входах, но что его нельзя заставить зависнуть. Катастрофический backtracking поражает движки, отслеживающие один путь за раз: `(a*)*b` против 'aaaa...a' (без b) вызывает экспоненциальный перебор, потому что движок должен попробовать каждый способ распределить 'a' между вложенными звёздочками, прежде чем признать отказ. Твой NFA Томпсона иммунен: симуляция множества состояний посещает каждое состояние не более одного раза на входной символ, поэтому худший случай для паттерна из m состояний и входа длиной n — ровно m·n посещений состояний. Докажи это тестом на время или подсчёт шагов: скомпилируй `(a*)*b` (или `(a|a)*b`) и примени к строке из 30+ 'a' без 'b'; матч должен завершиться и вернуть false без зависания, за линейное время, а не экспоненциальное. Добавь комментарий к циклу симуляции, объясняющий, почему добавление состояния в текущее множество, уже там присутствующего, является no-op — именно этот механизм ограничивает размер множества числом m и делает линейное время возможным. Явно сравни это с тем, как PCRE или JS RegExp `/((a*)*b)/` зависает на том же входе.
Критерии готовности- Тест компилирует `(a*)*b` (или `(a|a)*b`) и вызывает `match(nfa, 'a'.repeat(30))` — он возвращает `false` за 100 мс на любой разумной машине, доказывая поведение линейного времени.
- Цикл симуляции содержит проверку, пропускающую добавление состояния, уже присутствующего в текущем множестве, и комментарий объясняет, что именно этот предел предотвращает экспоненциальный взрыв.
Самопроверка
Покажи результат теста на время для `(a*)*b` против 'a'.repeat(30) и объясни в одном абзаце, почему движок с backtracking в стиле PCRE экспоненциален на этом входе, а твоя симуляция NFA — нет; senior-ревьюер проверяет, что объяснение называет дедупликацию множества состояний как механизм, а не просто «NFA лучше».
Стартер
- README.md
- src/regex.ts
- test/regex.test.ts
Распакуй, реализуй заглушки, затем гоняй тесты, пока не позеленеют: bun test
Рубрика
| Джуниор | Миддл | Сеньор | |
|---|---|---|---|
| Парсер и построение NFA | Захардкоженный или ad-hoc парсер обрабатывает несколько случаев; NFA строится вручную или без чётких правил компоновки фрагментов — конструкция не обобщается на новые операторы. | Рекурсивно-нисходящий парсер строит корректный AST с правильным приоритетом операторов; строитель NFA применяет правила фрагментов Томпсона для всех необходимых операторов и генерирует не более 2 состояний на узел AST. | Ты можешь назвать границу O(m) числа состояний и O(m) числа переходов для паттерна длиной m, подтвердить это тестом подсчёта состояний и объяснить, почему Plus переиспользует подфрагмент, а не копирует его (копия удвоила бы число состояний и нарушила гарантию линейности). |
| Корректность симуляции | Матч работает для простых литеральных паттернов; даёт сбои или неверные результаты для паттернов с кванторами или альтернацией, применённой к группам. | Epsilon-замыкание корректно вычисляется до и после каждого шага по символу; все операторы (`*`, `+`, `?`, `|`, `.`, группировка) принимают допустимые входы и отклоняют почти-совпадения в тестовом наборе. | Матч всей строки соблюдается (не матч префикса): симуляция потребляет весь вход и проверяет принадлежность принимающему состоянию только в конце. Ты можешь проследить множество состояний для среднего паттерна символ за символом и предсказать результат принятия/отклонения до запуска кода. |
| Гарантия линейного времени (без катастрофического обратного хода) | Движок использует рекурсивный backtracking или DFS по NFA — даёт корректные результаты на типичных входах, но зависает или работает очень медленно на `(a*)*b` против 30+ символов 'a'. | Симуляция поддерживает дедуплицированное множество состояний и продвигает полное множество на каждом символе; `(a*)*b` против 30+ символов 'a' быстро возвращает false. | Ты предоставляешь тест на время или счёт шагов, демонстрирующий завершение за доли миллисекунды для `(a*)*b` на 30+ символах 'a', называешь проверку дедупликации как механизм и объясняешь, почему движок в стиле PCRE экспоненциален на том же входе — называя конкретный коэффициент ветвления (количество способов распределить n 'a' по k уровням вложенных звёзд). |
| Ясность кода и расширяемость | Парсер, строитель NFA и симулятор перемешаны в одной функции или модуле без чёткого разделения ответственности. | Парсер, типы AST, строитель NFA и симулятор находятся в отдельных, чётко именованных функциях или классах; публичный API — `compile(pattern) → NFA` и `match(nfa, input) → boolean`. | Добавление нового оператора (например, классов символов) требует изменения только парсера и строителя NFA, но не симулятора; симулятор является универсальным по типу перехода и представлению состояния. Ты можешь продемонстрировать это, набросав изменения для поддержки `[a-z]` менее чем в 20 строках. |
Эталонный разбор (спойлер)
Конструкция Томпсона 1968 года гарантирует O(m) состояний и O(m) переходов для паттерна длиной m, компонуя фрагменты NFA не более чем с 2 новыми состояниями на оператор. Именно эта граница делает последующую симуляцию O(m·n), а не экспоненциальной: множество активных состояний всегда является подмножеством этих m состояний, поэтому его размер ограничен m независимо от глубины вложенности кванторов.
Epsilon-замыкание — это множество всех NFA-состояний, достижимых из данного состояния через ноль или более epsilon-переходов. Его корректное вычисление — через BFS или DFS по epsilon-рёбрам — является наиболее распространённым источником ошибок в симуляции NFA. Замыкание должно пересчитываться после каждого шага по символу, а не только в начале, потому что символьные переходы могут приводить в состояния с исходящими epsilon-рёбрами.
Катастрофический backtracking в движках стиля PCRE возникает потому, что они фиксируются на одном пути NFA за раз. Для `(a*)*b` против 'aaaa' (без b) движок должен перебрать каждый способ распределить 'a' между внешней и внутренней звёздочками, прежде чем признать отказ — число разделений экспоненциально зависит от длины входа. Симуляция Томпсона полностью избегает этого: когда обе ветки Alter или цикла Star являются допустимыми продолжениями, они добавляются в текущее множество одновременно, поэтому ни один путь никогда не исследуется повторно.
Матч всей строки (весь вход должен совпасть, а не подстрока) соблюдается проверкой того, находится ли принимающее состояние в финальном множестве после потребления всех входных символов. Поиск подстроки — другая семантика: инициализируй симуляцию epsilon-замыканием всех состояний, достижимых из начала с неявным префиксом 'любое количество символов до паттерна' — эквивалентно добавлению `.*` в начало паттерна, но без фактического добавления этих состояний.
Конструкция подмножества (конвертация NFA в DFA) кэширует каждое достижимое множество NFA-состояний как единственное DFA-состояние. После построения переход DFA — O(1) на символ (epsilon-замыкание не нужно), что делает его быстрее для многократного матча одного паттерна против множества входов. Компромисс: построение DFA может занять O(2^m) времени и состояний в худшем случае (хотя на практике это редко), тогда как симуляция Томпсона всегда использует O(m) состояний и не требует предварительных вычислений помимо построения NFA.
Сделай по-сеньорски
- Добавь якоря `^` и `$`: вместо матча всей строки реализуй поиск подстроки, где `^` заставляет матч начинаться с позиции 0, а `$` — заканчиваться на последнем символе — и докажи, что симуляция всё ещё работает за O(m·n).
- Конвертируй NFA в DFA через конструкцию подмножества, кэшируй построенные DFA-состояния и измерь ускорение на regex, требующем посещения многих NFA-состояний на входной символ — затем объясни, когда симуляция NFA выигрывает у DFA (большой паттерн, короткий вход) и когда побеждает DFA (малый паттерн, длинный вход).
- Реализуй классы символов `[a-z]`, `[^abc]` (инвертированный) и сокращения `\d`, `\w`, `\s` — расширь AST узлом CharClass и обработай переход как в построении NFA, так и в симуляции, не увеличивая взрывообразно число состояний.
- Добавь захватывающие группы `(...)`, пометив epsilon-переходы слотами сохранения, реализуй параллельную симуляцию, отслеживающую назначения тегов вместе с множествами состояний (алгоритм Лаурикари), и возвращай захваченные подстроки вместе с результатом матча.