Aydin Schwartz
Студент магистратуры Data Science Университета Сан-Франциско
Регулярные выражения заслужили плохую репутацию. Кажется, при каждом упоминании они вызывают в воображении простыни текста, которые выглядят абсолютно бессмысленно. Вот, к примеру, известное выражение проверки корректности электронной почты:
(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])Угу… Не претендую на то, что к концу статьи вы его поймёте, но покажу, что регулярки построены на простых правилах, понять которые не так уж сложно.
Почему нас вообще должно волновать, как они работают? Думаю, пара причин тому есть, и вот первая: когда вы поймёте фундаментальные основы регулярных выражений, писать хорошие регулярки станет проще.
Бывало, я писал регулярку и не возвращался к ней несколько месяцев, а потом всё забывал и переучивался заново. Избежать этой проблемы поможет понимание идей в основе регулярных выражений, а не только их синтаксиса.
Может, как программист-самоучка я лезу на рожон, но заглянуть в теорию Сomputer Science будет полезно, а разбор движка регулярок — хорошая возможность познакомиться с понятием «конечный автомат».
И, по-моему, лучший способ разобраться — визуализация, поэтому на Python и Graphviz я написал движок регулярок, который анимирует поиск по тексту. Если хотите попробовать свои примеры, загляните на Github. Ниже я показываю анимацию поиска S+NAKE по тексту SSSSNAKE.
Вводная часть
В основе регулярных выражений лежит много теории, но я постараюсь разъяснить только самое необходимое для нашего движка.
Wikipedia определяет регулярное выражение как «последовательность символов, определяющая шаблон поиска по тексту». Большая часть символов регулярного выражения — это обычные символы, но есть несколько специальных метасимволов — это (*, +, ? , |) с уникальными функциями, о которых поговорим позже.
Ядро движка регулярок — детерминированный конечный автомат (далее — ДКА). Звучит затейливо, но это просто направленный граф с начальным и конечным узлами. Он работает, изменяя свои состояния согласно некоторому вводу:
Единственный способ этого ДКА перейти из начального состояния в заключительное — пройти последовательность «BAT». Этот пример кажется простым, но он расширяется до произвольных входных данных и сложных последовательностей символов, поэтому в идеале хотелось бы найти способ превратить регулярное выражение в ДКА.
И здесь нас спасает теория! Теорема Клина утверждает, что для любого регулярного выражения существует ДКА, способный задать тот же набор строк, и наоборот. Иными словами, существует алгоритм, преобразующий ту самую безумную проверку e-mail в ДКА — и в форме ДКА компьютер легко обработает его.
До начала разработки алгоритма я должен предостеречь вас: преобразование регулярного выражения в ДКА может оказаться очень затратным вычислением.
Вместо этого превратим выражение в недетерминированный конечный автомат (далее — НКА). Основное отличие НКА от ДКА состоит в том, что он может находиться в нескольких состояних одновременно и переходить в разные состояния без сканирования очередной буквы ввода [такой переход называется эпсилон-переходом. — прим. ред.].
Регулярное выражение → НКА
Вот краткий обзор метасимволов движка:
(
*) соответствует символу ноль или более раз.(
+) соответствует символу один или несколько раз.(
?) соответствует символу ноль или один раз.(
.) соответствует любому символу.(
()) инкапсулирует подвыражения.(
|),or— логическое "ИЛИ".
Если вы работали с регулярками, наверное, вы заметили, что метасимволов ([]) и ({}) в движке нет. Тем не менее, движок имеет все возможности реализации операций, выполняемых этими символами:
Выражение
[ABC]не поддерживается; его эквивалент —(A|B|C).A{2, 3}— эквивалентAAA?. Добавить эти метасисволы возможно, но их сложно выразить графически.
Преобразование регулярного выражения в НКА я покажу на примере (A*B|AC)D. Сначала нужно немного обработать выражение — заключить его в круглые скобки. Затем — создать узлы для каждого символа, а ещё последний, пустой узел, означающий заключительное состояние автомата:
Добавляем рёбра перехода от одной точки к другой. Представить их можно как рёбра к узлам с буквами. Они выполняются, только когда сканируемая в тексте буква совпадает с буквой узла. Логика добавления рёбер перехода соответствия проста: переход соответствия от текущего узла к следующему добавляется, когда узел не содержит метасимвола.
Сложнее всего добавить рёбра эпсилон-перехода. Представить их можно как рёбра, идущие к узлам с метасимволами. Для каждого метасимвола эти рёбра будут разными, а ещё на них влияет расположение скобок: если в выражении есть оператор *, он требует трёх отдельных рёбер эпсилон-перехода:
К состоянию после эпсилон-перехода.
К состоянию до эпсилон-перехода.
От состояния до перехода — к *.
После добавления всех этих рёбер НКА завершается:
Сопоставление шаблонов НКА
Теперь, когда НКА построен, можно запустить его на тексте и наблюдать переходы от состояния к состоянию:
Если НКА достигает заключительного состояния, значит, совпадение найдено.
Если мы закончили сканирование текста и не достигли этого состояния, совпадение не найдено.
Базовый шаблон запуска НКА выглядит так:
До сканирования первой буквы создаётся список активных состояний и в него добавляется первый узел НКА.
Берутся эпсилон-переходы от каждого узла в активном состоянии к каждому достижимому состоянию. Все достижимые состояния помещаются в список состояний-кандидатов.
Сканируется следующая буква текста.
Список активных состояний очищается. Если какое-либо состояние в кандидатах совпадает с буквой в тексте, берётся его переход соответствия в следующее состояние и добавляется в новый список активных состояний.
Шаги 2–4 повторяются до конца текста или до заключительного состояния автомата.
Python-код этой процедуры — ниже:
def recognize(text, regex, match_transitions, epsilon_transitions):
active_states = [0]
# get candidate states before scanning first character
candidate_states = digraph_dfs(epsilon_transitions, active_states[0])
candidate_chars = [regex[state] for state in epsilon_states]
for i, letter in enumerate(text):
# get epsilon transition states that match letter of input text
matched_states = []
[matched_states.append(state) for state, char in zip(candidate_states, candidate_chars) if
char == letter or char == "."]
# take match transition from matched state to next state
active_states = []
[active_states.extend(match_transitions[node]) for node in matched_states]
# get next epsilon transitions
candidate_states = []
[candidate_states.extend(digraph_dfs(epsilon_transitions, node)) for node in active_states]
candidate_chars = [regex[state] for state in candidate_states]
# check if nfa has reached the accepting state
if len(regex) in candidate_states:
return True
# if we've processed all text and haven't reached accepting state, return False
return FalseПрогоним НКА через текст AABD. Первый шаг — взять все возможные эпсилон-переходы до сканирования первой буквы AABD, вот так:
На самом первом шаге НКА уже находится в 6 состояних-кандидатах! Далее сканируем до первой буквы текста:
Переход соответствия из A имеют два узла: 4 и 8. Следующий шаг — взять переход соответствия из этих узлов.
Отсюда процесс повторяется так же. Из активных состояний берётся каждый доступный эпсилон-переход, сканируется следующая буква, затем берём следующий переход состояния:
И последнее
Надеюсь, вы лучше поняли внутреннюю работу механизма регулярных выражений. Для разъяснений настоятельно рекомендую эти видеолекции профессора Роберта Седжвика.
Трудно полностью понять что-то, не поработав с этим, поэтому я призываю всех читателей создать свои анимации регулярок или просто повозиться с их отладчиком.
А мы поможем прокачать ваши навыки или с самого начала освоить профессию, актуальную в любое время:
Выбрать другую востребованную профессию.
