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. Сначала нужно немного обработать выражение — заключить его в круглые скобки. Затем — создать узлы для каждого символа, а ещё последний, пустой узел, означающий заключительное состояние автомата:

Добавляем рёбра перехода от одной точки к другой. Представить их можно как рёбра к узлам с буквами. Они выполняются, только когда сканируемая в тексте буква совпадает с буквой узла. Логика добавления рёбер перехода соответствия проста: переход соответствия от текущего узла к следующему добавляется, когда узел не содержит метасимвола.

Сложнее всего добавить рёбра эпсилон-перехода. Представить их можно как рёбра, идущие к узлам с метасимволами. Для каждого метасимвола эти рёбра будут разными, а ещё на них влияет расположение скобок: если в выражении есть оператор *, он требует трёх отдельных рёбер эпсилон-перехода:

  1. К состоянию после эпсилон-перехода.

  2. К состоянию до эпсилон-перехода.

  3. От состояния до перехода — к *.

После добавления всех этих рёбер НКА завершается:

Сопоставление шаблонов НКА

Теперь, когда НКА построен, можно запустить его на тексте и наблюдать переходы от состояния к состоянию:

  • Если НКА достигает заключительного состояния, значит, совпадение найдено.

  • Если мы закончили сканирование текста и не достигли этого состояния, совпадение не найдено.

Базовый шаблон запуска НКА выглядит так:

  1. До сканирования первой буквы создаётся список активных состояний и добавьте в него первый узел в НКА.

  2. Берутся эпсилон-переходы от каждого узла в активном состоянии к каждому достижимому состоянию. Все достижимые состояния помещаются в список состояний-кандидатов.

  3. Сканируется следующая буква текста.

  4. Список активных состояний очищается. Если какое-либо состояние в кандидатах совпадает с буквой в тексте, берётся его переход соответствия в следующее состояние и добавляется в новый список активных состояний.

  5. Шаги 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. Следующий шаг — взять переход соответствия из этих узлов.

Переходы соответствия A → * и A → C
Переходы соответствия A → * и A → C

Отсюда процесс повторяется так же. Из активных состояний берётся каждый доступный эпсилон-переход, сканируется следующая буква, затем берём следующий переход состояния:

Весь процесс поиска НКА заканчивается в заключительном состоянии автомата
Весь процесс поиска НКА заканчивается в заключительном состоянии автомата

И последнее

Надеюсь, вы лучше поняли внутреннюю работу механизма регулярных выражений. Для разъяснений настоятельно рекомендую эти видеолекции профессора Роберта Седжвика.

Трудно полностью понять что-то, не поработав с этим, поэтому я призываю всех читателей создать свои анимации регулярок или просто повозиться с их отладчиком.

А мы поможем прокачать ваши навыки или с самого начала освоить профессию, актуальную в любое время:

Выбрать другую востребованную профессию.

Комментарии (16)


  1. aamonster
    21.07.2022 01:23
    +1

    А потом приходят Perl-style regular expressions (с back referencing – по большому счёту это уже и не регэкспы) и всё ломается (с заменой линейного алгоритма работы с регэкспами на экспоненциальный)


  1. mc2
    21.07.2022 02:44

    Исправьте пожалуйста, автор не студент университета Южной Флориды, а университета Сан-Франциско.


    1. vagon333
      21.07.2022 09:02

      University of South Florida (Тампа)


      1. mc2
        21.07.2022 12:36

        Открыть Гугл сложно: (

        https://www.linkedin.com/in/aydin-schwartz


        1. mc2
          21.07.2022 15:07
          +1

          1. stranger777
            23.07.2022 14:42

            Поправили, спасибо! Проверка автора и упомянутых в тексте людей на IN попадёт в чек-лист контроля качества переводов :)


  1. Z55
    21.07.2022 06:59
    +2

    Регулярные выражения заслужили плохую репутацию.

    Чего??


    1. funca
      21.07.2022 09:52
      +1

      Видимо отсылка к классике:

      Some people, when confronted with a problem think “I know, I'll use regular expressions.” Now they have two problems.

      (историки утверждают, что фраза была высказана в ответ на идею интегрировать Perl в Emacs)


  1. Funny_Meerkat
    21.07.2022 10:56

    с регулярными выражениями очень приятно парсить всякие XML в Notepad++. В этой публикации что-то готовое через PHP было, но мне было привычнее сделать вручную


    1. wataru
      21.07.2022 12:11
      +2

      XML, ровно как и HTML — это не регулярные языки. парсить их регулярными выражениями, даже с референсами — плохая идея.


  1. codecity
    21.07.2022 16:34

    Есть ли тулуза, которая по регулярному выражению выдаст несколько наборов данных, которым оно соответствует? Желательно как-то осмысленно.


    1. Alexandroppolus
      22.07.2022 08:58
      +1

      Кстати, для регулярок с несколькими наслаивающимися lookahead (часть из которых отрицательные) это может быть весьма нетривиальная задача


    1. Tsimur_S
      22.07.2022 12:12
      +1

      1. codecity
        22.07.2022 13:05
        +1

        Благодарю. Мне одному так намного нагляднее? Просто тупо вбиваешь регулярку, смотришь примеры - и сразу понятно о чем речь.



  1. QtRoS
    22.07.2022 15:01

    Вопрос: как давно в состояниях конечных автоматов рисуют инпуты? Не проще ли обозначать состояния, а инпуты рисовать над стрелками? Я как ни старался, не смог понять вашу нотацию эпсилон-переходов. Обычно это просто e над стрелочкой между состояниями, демонстрирующее отсутствие необходимости в инпуте для перехода.