Поедание красных вишен дает вам возможность есть синих призраков. Идея о том, что производные можно использовать для создания алгоритма сопоставления регулярных выражений, почти столь же нелепа. Позвольте мне объяснить, как работает этот алгоритм и как он связан с Pac-Man.

В 1964 году Бжозовский опубликовал первую статью о производных регулярных выражений . Это, безусловно, один из моих любимых алгоритмов. Используя производные от регулярных выражений, мы можем реализовать алгоритм для сопоставления регулярных выражений. Этот алгоритм очень:

• просто
• функциональный
• легко расширяется вашими операторами

В этой статье я покажу вам, как мы можем сопоставить строку с регулярным выражением, используя только две чистые функции и некоторые аналогии с Pac-Man. Если вы предпочитаете, вы можете посмотреть следующее видео вместо чтения статьи, поскольку она охватывает тот же материал:

Резюме регулярных выражений

Во-первых, давайте кратко рассмотрим регулярные выражения, чтобы убедиться, что мы находимся на одной странице. Выражение a(a|b)*соответствует строке, которая начинается с a, за которой следует любое количество a's и b's.

• Строка abсовпадет a(a|b)*. Мы укажем это с помощью съедобного синего призрака.
• Строка aabbbaтакже совпадает a(a|b)*, так как она начинается с aи сопровождается несколькими a'и b'.
• Затем строка acне соответствует a(a|b)*, так как регулярное выражение не соответствует никаким c, а наше регулярное выражение не выполняет сопоставление подстрок. Мы укажем это с помощью красного призрака, преследующего Pac-Man.
• Наконец, строка baтакже не совпадает a(a|b)*, потому что она не начинается с a.

Обзор алгоритма

Прежде чем углубляться в детали, давайте рассмотрим, как работает этот алгоритм. Я придумал странную игру Pac-Man, в которой вы можете есть призраков только в том случае, если едите фрукты в последовательности, соответствующей регулярному выражению. Наш Pac-Man представляет регулярное выражение aba*. У него есть следующая последовательность фруктов: яблоко, затем банан, а затем яблоко: aba.

1. Когда мы начинаем, призрак преследует нас, и регулярное выражение, которое у нас осталось для сопоставления, — это aba*.
2. Мы едим первое яблоко, и регулярное выражение, которое у нас осталось для сопоставления, имеет вид ba*. Призрак все еще преследует нас, так как фрукт, который мы съели до сих пор, яблоко, не соответствует регулярному выражению.
3. Далее едим банан. Регулярное выражение, которое мы оставили для сопоставления, равно a*. Теперь призрак начинает убегать, потому что технически он abуже соответствует aba*.
4. Мы можем попробовать съесть привидение или съесть другое яблоко, и в этом случае регулярное выражение, которое у нас осталось для сопоставления, будет все еще a*. Призрак все еще убегает, так как abaтакже соответствует регулярному выражению aba*.

Здесь работает еще одна функция. Функция проверяет, гонится ли призрак за Pac-Man или Pac-Man уже совпал с регулярным выражением и гонится за призраком. Эта функция называется функцией, допускающей значение NULL; он проверяет, соответствует ли оставшееся регулярное выражение пустой строке. Он может это сделать, потому что если регулярное выражение, которое осталось для сопоставления, соответствует пустой строке, съеденных им фруктов уже должно быть достаточно, чтобы удовлетворить регулярное выражение.

Алгоритм сопоставления производных

Это означает, что нам нужны только две функции для написания алгоритма сопоставления производных:

1. производная функция
2. обнуляемая функция

Один на Голанге для императивных программистов:

и еще один на Haskell для функциональных программистов:

Эти две функции эквивалентны и просто написаны в разных стилях программирования. В коде Haskell, foldlтакже называемый fold left или reduce в других языках, выполняет работу цикла for за вас. Кроме того, в Haskell нам не нужны запятые для передачи параметров функциям; поскольку применение функции является наиболее распространенной операцией в функциональном языке программирования, мы используем пробел для разделения параметров.

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

Отступление от истории происхождения Pac-Man

Но прежде чем мы это сделаем, я не знаю, задумывались ли вы когда-нибудь об истории происхождения Pac-Man. Я утверждаю, что не было никакой бочки с ядерными отходами, в которую упал Пакман, в результате чего Пакман получил способность поедать призраков. Логика намного проще.

Pac-Man — это фрукт! Когда Pac-Man ест другие фрукты, Pac-Man становится каннибалом. Так что, если вас когда-нибудь преследует призрак, вы должны съесть немного человеческого мяса, и призрак должен, по крайней мере временно, начать убегать от вас. Теперь я не пробовал это сам, но логика кажется здравой.

Это объясняет, почему зомби всегда преследуют людей. Как однажды сказал Дэвид Аттенборо:

«Зомби, которые преследуют нас, сами преследуются призраками, которых мы не можем видеть. После того, как зомби съедят часть нашей человеческой плоти, вы увидите, как они демонстрируют странное поведение, жуя воздух, это зомби, поедающий призрака, который преследовал его раньше».

Основные операторы

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

Мы можем думать о регулярном выражении как описывающем набор строк.

• Это означает, что пустой набор представляет оператор, который не соответствует ни одной строке.
• Пустая строка представляет собой одноэлементный набор из одной строки, которая соответствует только пустой строке.
• Символ также представляет собой одноэлементный набор, который соответствует только одному символу a.
• Затем мы можем комбинировать эти базовые регулярные выражения, используя такие операторы, как: or, concatenationи Kleene star, где rи sпредставляет собой два регулярных выражения, которые мы комбинируем.

Обнуляемая функция

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

• a*соответствует пустой строке, поскольку ноль или более включают ноль.
• (a*|b)соответствует пустой строке, начиная с левой части или соответствует пустой строке.
• abне соответствует пустой строке, так как соответствует только строкеab
• ab*также не соответствует пустой строке, так как ab*требуется строка, начинающаяся сa
• (a|b)не соответствует пустой строке, так как ни левая, ни правая часть не orсоответствует пустой строке.

Вот реализация функции, допускающей значение null. Левая сторона представляет значения, которые передаются в функцию, а правая сторона представляет реализацию функции в этом случае. Красные призраки представляют ложь, а синие призраки - правду:

• Пустой набор не соответствует пустой строке, поскольку он не соответствует ни одной строке.
• Пустая строка соответствует пустой строке, потому что она соответствует только пустой строке.
• Символ aне соответствует пустой строке, потому что он соответствует только символу a.
• Если у нас есть логический or, мы должны проверить обе стороны. Если любой из них соответствует пустой строке, то логическое orсоответствует пустой строке.
• Чтобы concatenationдва регулярных выражения соответствовали пустой строке, они оба должны соответствовать пустой строке.
• И, наконец, если у нас есть zero or moreчто-то, то оно включает ноль, что означает, что оно всегда соответствует пустой строке.

1. Наш главный оператор — orэто означает, что мы должны проверить допустимость значений NULL для левой и правой сторон: bи a*.
2. Проверяем и видим, что символ bс левой стороны не обнуляемый: false.
3. Затем мы проверяем и видим, что a*с правой стороны можно обнулить: true.
4. Теперь мы вернулись falseи trueможем orих достать true.

Обнуляемые упражнения

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

1. а
2. а*(б*|∅)
3. еа
4. ∅*
5. (∅|b)*(abc|ε)

Прежде чем мы рассмотрим реализацию функции, давайте рассмотрим примеры производной. Здесь мы возьмем производную от нескольких регулярных выражений, все относительно символа a:

• Регулярное выражение, которое остается для сопоставления после того , как a*он съел aяблоко, все еще равно a*.
• Производная по ab*отношению к aравна b*, так как мы уже сопоставили префикс a.
• Производная (a|b)bпо . a_b
• Производная b|(a*b)по . a_ a*bЛевый bне совпадал, поэтому мы могли его выбросить, и он aбыл поглощен zero or more aправым.
• Далее у нас есть ab*, это немного сложно. После того, как он съест яблоко, останется найти регулярное выражение b(ab)*. Так как мы только сопоставили a, мы ожидаем увидеть по крайней мере еще один b.

• Производная пустого множества всегда является пустым множеством. Восстановить невозможно, так как пустой набор ничему не соответствует.
• Производная пустой строки относительно любого символа является пустым множеством. Он не ожидал совпадения с персонажем. Он будет соответствовать только пустой строке.
• Производным от одного символа к подобному символу (в данном случае apple) является пустая строка, поскольку после того, как он совпал с самим собой, все, что осталось для сопоставления, — это пустая строка.
• Производная символа по отношению к другому символу, который не равен, в данном случае bанане, является пустым набором, поскольку мы не сопоставили конкретный символ.
• Производная orвыражения есть orпроизводная. Он просто перекладывает проблему на своих потомков.
• Производная concatвыражения должна учитывать, может ли она пропустить первое выражение. Он может пропустить первое выражение только в том случае, если первое выражение соответствует пустой строке и допускает значение NULL. Итак, первое, что мы делаем, это проверяем это. Давайте подумаем о случае, когда он не может пропустить первое выражение, если выражение rне допускает значение NULL. Тогда производная является производной первого выражения concatenatedсо вторым выражением s. Если мы можем пропустить первое регулярное выражение, мы должны рассмотреть альтернативу, которая является только производной от второго выражения. Затем мы можем выбрать orдве альтернативы: пропустить rи не пропустить rи вернуть это в результате.
• Наконец, у нас есть starоператор. Соответствует выражению ноль или более раз. Поскольку нам передается символ, это не нулевой случай. Так что надо рассматривать one or moreдело. Это означает, что мы должны взять производную выражения внутри starи concatenateснова с zero or moreвыражением.

Производный пример 1

Возьмем производную (ab)*по a.

(ab)*является zero or moreвыражением, поэтому мы смотрим на zero or moreправило. Мы видим, что для этого требуется взять производную от выражения внутри star.

Это concatenationиз aи b. Итак, мы проверяем, может ли левая сторона обнуляться, а символ aне может быть обнуляемым. Это означает, что мы не можем пропустить это. Мы должны взять производную aпо a. Но это пустая строка, поэтому, если мы возьмем concatenateпустую строку с правой стороной, которая была b, мы получим b.

Теперь вернемся к zero or more, помните, что мы взяли производную по abотношению к aи получили обратно b. Теперь мы можем соединить это (ab)*снова, и мы получим b(ab)*.

Производный пример 2

Возьмем производную (a*ba)по b.

• a*объединяется с ba, поэтому мы рассмотрим правило конкатенации.
• Мы проверяем, допускает ли левая часть a*значение NULL, что так и есть. Это означает, что мы можем его пропустить, что также означает, что мы должны создать orиз двух производных.
• Левая сторона оказывается несоответствующей, так a*как не соответствует b.
• К счастью, у нас есть альтернатива ba. Производная baпо bесть и a.

Здесь я пропустил некоторые детали. Считайте это упражнением, чтобы проверить мою работу, пройдясь по функции самостоятельно.

Производные упражнения

Попробуйте пройтись по реализации и проверить, каковы производные следующих регулярных выражений по отношению к b. Вы можете нажать на них, чтобы проверить свой ответ:

1. εb
2. б*(б|в)
3. а*(б|в)
4. bεb
5. ∅*б

Надеюсь, теперь вы понимаете, почему поедание красных вишен дает вам возможность есть синих призраков и как реализовать сопоставление регулярных выражений с использованием производного алгоритма.

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

Мы также можем легко расширить алгоритм, включив в него новые операторы, такие как , notи interleaveдаже поддерживая контекстно-свободные грамматики. Я буду обсуждать некоторые из этих тем в следующей статье .

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

Спасибо

• Brink van der Merwe за то, что нашли время объяснить мне этот алгоритм.

• Бжозовский, Януш А. «Производные регулярных выражений». Журнал ACM (JACM) 11.4 (1964): 481–494.
• Оуэнс, Скотт, Джон Реппи и Аарон Турон. «Пересмотр производных регулярных выражений». Журнал функционального программирования 19.2 (2009): 173–190.