Регулярное выражение, которое соответствует только самому себе

Есть несколько довольно крутых проблем, связанных с регулярным выражением ( Саморегулирующее регулярное выражение , регулярное выражение , проверяющее регулярное выражение )

Это вполне может быть невозможно, но есть ли регулярное выражение, которое будет соответствовать ТОЛЬКО самому себе?

ПРИМЕЧАНИЕ, разделители должны быть включены:

например /thing/должен совпадать /thing/а не thing. Единственным возможным соответствием для вашего выражения должно быть само выражение. Многие языки допускают реализацию строки вместо регулярного выражения. Например в Go

package main

import "fmt"
import "regexp"

func main() {

    var foo = regexp.MustCompile("bar")
    fmt.Println(foo.MatchString("foobar"))
}

но ради задачи, пусть выражение будет разделено (начальный символ, выражение, конечный символ ex: /fancypantpattern/или @[^2048]@), если вы хотите аргументировать кавычки как разделитель, пусть будет так. Я думаю, учитывая очевидную сложность этой проблемы, это не будет иметь большого значения.

Чтобы помочь вам в этом:

Быстрый взлом, который я собрал для rubular.com (веб-страница для редактирования ruby regex):

var test = document.getElementById("test")
,regex = document.getElementById("regex")
,delimiter="/"
,options = document.getElementById("options")
,delay = function(){test.value = delimiter + regex.value + delimiter + options.value}
,update = function(e){
    // without delay value = not updated value
    window.setTimeout(delay,0);
}
regex.onkeydown = update;
options.onkeydown = update;

Хотя это технически «код-гольф», я буду очень впечатлен, если кто-нибудь сможет найти ответ / доказать, что это невозможно.

Ссылка теперь исправлена. Извините всех

Победный ответ пока: jimmy23013 с 40 символами

code-golf string decision-problem regular-expression pattern-matching Дилан Мадисетти
источник

Очевидно, что любое регулярное выражение, которое включает в себя только литералы, будет работать: //, / a /, / xyz / и т. Д. Было бы хорошо потребовать, чтобы регулярное выражение включало нелитеральную операцию.

хлебница

литералы не будут работать, потому что вы должны сопоставить обратную косую черту, например, / aaa / будет соответствовать, aaaно не / aaa /

Дилан Мадисетти

@DylanMadisetti Нужно ли использовать //разделители или мы можем выбрать другие разделители (PCRE поддерживает практически любой символ, и, в частности, вы можете использовать соответствующие скобки / скобки / скобки в качестве разделителей).

Мартин Эндер

Я думаю, что это довольно хорошая математическая / вычислительная проблема, и доказательство может быть непростым ... Многие важные теоремы начинались как простой вопрос, с которым можно поиграть, так что, возможно, через 5 лет появится статья в Википедии "Проблема Мадисетти";)

Павел Токарз

Да, точно. В некоторых языках (например, grep в bash) разделитель по сути является пустой строкой. Поэтому предполагать, что регулярное выражение требует разделителей, уже неправильно. Действительно, поскольку grep является одной из самых ранних реализаций регулярного выражения, каноническое определение регулярного выражения не имеет разделителей. Самым ярким проявлением этого предположения является PHP, для которого требуется два разделителя: "/и/"

slebetman

PCRE аромат, 261 289 210 184 127 109 71 53 51 44 40 байт

Да, это возможно!

<^<()(?R){2}>\z|\1\Q^<()(?R){2}>\z|\1\Q>

Попробуй это здесь. (Но /показано, что это разделитель на Regex101.)

^{Пожалуйста, воздержитесь от внесения ненужных правок (обновлений) на странице Regex101. Если ваше редактирование на самом деле не предполагает улучшения, попытки или тестирования этого регулярного выражения, вы можете создать его или создать новые на их домашней странице .}

Версия работает более корректно на Regex101 (44 байта):

/^\/()(?R){2}\/\z|\1\Q^\/()(?R){2}\/\z|\1\Q/

Попробуй это здесь.

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

Пояснения:

\Q^\/()(?R){2}\/\z|\1\Qсоответствует строке ^\/()(?R){2}\/\z|\1\Q. Это использует причуду, которую \Q...\Eне нужно закрывать, и работают неэкранированные разделители \Q. Это заставило некоторые предыдущие версии работать только на Regex101, а не локально. Но, к счастью, последняя версия сработала, и я использовал для этого еще несколько байтов.
\1до \Qсопоставления с захваченной группой 1. Поскольку группа 1 не существует в этой опции, она может совпадать только в рекурсивных вызовах. В рекурсивных вызовах это соответствует пустым строкам.
(?R){2}вызывает целое регулярное выражение дважды, что соответствует ^\/()(?R){2}\/\z|\1\Qкаждому разу.
() ничего не делает, кроме как захватывает пустую строку в группу 1, которая включает другую опцию в рекурсивных вызовах.
^\/()(?R){2}\/\z(?R){2}добавлены совпадения с разделителями, от начала до конца. \/До того , как рекурсивные вызовы также удостоверился сам этот вариант не соответствует в рекурсивных вызовах, так как он не будет в начале строки.

51 байт с закрытым \Q...\E:

/\QE\1|^\/(\\)Q(?R){2}z\/\E\1|^\/(\\)Q(?R){2}z\/\z/

Попробуй это здесь.

Оригинальная версия, 188 байт

Спасибо Мартину Бюттнеру за отыгрывание около 100 байтов!

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.\2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{11}$/

Попробуй это здесь.

Или 210 байтов без \Q...\E:

/^(?=.{194}\\2\\.\)\{2}\.\{12}\$\/D$)((?=(.2.|))\2\/\2\^\2\(\2\?=\2\.\2\{194}\2\\\2\\2\2\\\2\\\2\.\2\\\2\)\2\\\2\{2}\2\\\2\.\2\\\2\{12}\2\\\2\$\2\\\2\/D\2\$\2\)\2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\)){2}.{12}$/D

Попробуй это здесь.

Расширенная версия:

/^(?=.{173}\Q\2\)){2}.{11}$\E\/\z)        # Match things near the end.
((?=(.2.|))                               # Capture an empty string or \2\ into group 2.
   \2\/\2\^\2\(\2\?=\2\.\2\{173}\2\\Q\2\\2\2\\\2\)\2\)\2\{2}\2\.
   \2\{11}\2\$\2\\E\2\\\2\/\2\\z\2\)      # 1st line escaped.
   \2\(\2\(\2\?=\2\(\2\.2\2\.\2\|\2\)\2\) # 2nd line escaped.
){2}
.{11}$/x

Расширения, подобные (?=и \1делающие так называемые «регулярные» выражения, перестали быть регулярными, что также делает возможным использование кавычек. Обратные ссылки не регулярны, но предвкушают.

Объяснение:

Я использую \2\вместо \экранирования специальные символы. Если \2соответствует пустой строке, \2\x(где xспециальный символ) соответствует xсамому себе. Если \2совпадает \2\, \2\xсоответствует сбежавшему. \2в двух матчах группы 1 могут отличаться в регулярных выражениях. В первый раз \2должна совпадать пустая строка, а во второй раз \2\.
\Q\2\)){2}.{11}$\E\/\z(строка 1) соответствует 15 символам с конца. И .{11}$(строка 7) соответствует 11 символам с конца (или перед завершающим переводом строки). Таким образом, шаблон непосредственно перед вторым шаблоном должен соответствовать первым 4 или 3 символам в первом шаблоне, поэтому \2\.\2\|\2\)\2\)должен соответствовать ...\2\)или ...\2\. Не может быть завершающего символа новой строки, потому что последний символ должен быть ). И сопоставляемый текст не содержит другого )перед самым правым, поэтому все остальные символы должны быть в \2. \2определяется как (.2.|), так что это может быть только \2\.
В первой строке все выражение соответствует точно 188 символам, поскольку все имеет фиксированную длину. Два раза группы 1 соответствуют 45 * 2 символам плюс 29 раз \2. И вещи после группы 1 соответствуют 11 символам. Таким образом, общая длина двух времен \2должна составлять ровно 3 символа. Знание \2во второй раз длиной 3 символа, оно должно быть пустым в первый раз.
Все, кроме заглядывания и \2литералов в группе 1. С двумя \2известными временами и последними несколькими символами, известными из первой строки, это регулярное выражение соответствует ровно одной строке.
Мартину Бюттнеру пришла в голову идея использовать lookahead для захвата группы 2 и наложения ее на часть quine. Это убрало символы, которые не были экранированы обычным образом между двумя временами группы 1, и помогло избежать шаблона, соответствующего им в моей исходной версии, и значительно упростило регулярное выражение.

Regex без рекурсий и обратных ссылок, 85 байт

Кто-то может возразить, что выражения с рекурсиями или обратными ссылками не являются настоящими «регулярными» выражениями. Но выражения только с заглядыванием могут все еще соответствовать только обычным языкам, хотя они могут быть намного длиннее, если выражены традиционными регулярными выражениями.

/(?=.*(\QE\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\E\\){2}z\/\z)^\/\(\?\=\.\*\(\\Q.{76}\z/

Попробуй это здесь.

610 байтов без \Q...\E(для игры в гольф):

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}(.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\(.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}(.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}(.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

Попробуй это здесь.

Идея похожа.

/^(?=.{610}$)(?=.{71}(\(\.\{8\}\)\?\\.[^(]*){57}\)\{2\}\.\{12\}\$\/D$)
((.{8})?\/(.{8})?\^(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{610(.{8})?\}(.{8})?\$(.{8})?\)
(.{8})?\((.{8})?\?=(.{8})?\.(.{8})?\{71(.{8})?\}
  (.{8})?\((.{8})?\\(.{8})?\((.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{8(.{8})?\\(.{8})?\}
    (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\?(.{8})?\\(.{8})?\\
    (.{8})?\.(.{8})?\[(.{8})?\^(.{8})?\((.{8})?\](.{8})?\*(.{8})?\)(.{8})?\{57(.{8})?\}
  (.{8})?\\(.{8})?\)(.{8})?\\(.{8})?\{2(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\.(.{8})?\\(.{8})?\{12(.{8})?\\(.{8})?\}
  (.{8})?\\(.{8})?\$(.{8})?\\(.{8})?\/D(.{8})?\$(.{8})?\)(.{8})?\(){2}.{12}$/D

Основное регулярное выражение

Если предвидение не разрешено, лучшее, что я могу сейчас сделать, это:

/\\(\\\(\\\\){2}/

который соответствует

\\(\\\(\\

Если {m,n}квантификатор не разрешен, это невозможно, потому что ничто, которое может соответствовать только одной строке, не может соответствовать строке длиннее самой себя. Конечно, можно по-прежнему придумывать что-то вроде того, \qчто только соответствует /\q/, и при этом говорить выражения с этим регулярным. Но, очевидно, ничего подобного не поддерживается основными реализациями.

jimmy23013
источник

Впечатляет. Я потратил некоторое время, пытаясь заставить его соответствовать чему-то другому, но безуспешно.

Примо

как, черт возьми, человек может произвести такую вещь?

xem

Это заслуживает того, чтобы быть самым высоко оцененным ответом на этом сайте.

Cruncher

Это самая абсурдная, невероятная вещь, которую я когда-либо видел.

Алекс А.

Кто-то написал в Твиттере этот пост, так что я получил 49 голосов за день ...

jimmy23013

Регулярное выражение, которое соответствует только самому себе

Чтобы помочь вам в этом:

Ответы:

PCRE аромат, 261 289 210 184 127 109 71 53 51 44 40 байт

Оригинальная версия, 188 байт

Regex без рекурсий и обратных ссылок, 85 байт

Основное регулярное выражение