Подобно нашим темам для подсказок по гольфу для конкретных языков: каковы общие приемы сокращения регулярных выражений?

Я могу видеть три применения регулярных выражений, когда дело доходит до игры в гольф: классический регулярное выражение гольфа («вот список, который должен совпадать, и вот список, который должен потерпеть неудачу»), использование регулярного выражения для решения вычислительных проблем и регулярных выражений, используемых как части больший гольф-код. Не стесняйтесь размещать советы по любому или всем из них. Если ваш совет ограничен одним или несколькими ароматизаторами, укажите их в верхней части.

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

Когда не убежать

Эти правила применяются к большинству ароматов, если не ко всем:

• ] не требует побега, когда не имеет себе равных.

• {и }не нужно убегать, когда они не являются частью повторения, например, буквально {a}совпадают {a}. Даже если вы хотите подобрать что-то подобное {2}, вам нужно всего лишь избежать одного из них, например {2\}.

В классах персонажей:

• ]не требует экранирования, когда это первый символ в наборе символов, например, []abc]соответствует одному из ]abc, или когда это второй символ после a ^, например, [^]]соответствует чему-либо, кроме ]. (Заметное исключение: вкус ECMAScript!)

• [не нужно убегать вообще. Вместе с приведенным выше советом это означает, что вы можете сопоставить обе скобки с ужасно нелогичным классом символов [][].

• ^не нуждается в экранировании, когда это не первый символ в наборе символов, например [ab^c].

• -не требует экранирования, когда это первый (второй после a ^) или последний символ в наборе символов, например [-abc], [^-abc]или [abc-].

• Никакие другие символы не нуждаются в экранировании внутри класса символов, даже если они являются метасимволами вне классов символов (за исключением \самой обратной косой черты ).

Кроме того , в некоторых вкусах ^и $подобраны в буквальном смысле , когда они не находятся в начале или в конце регулярного выражения соответственно.

(Спасибо @ MartinBüttner за заполнение нескольких деталей)

Простое регулярное выражение для соответствия всем печатным символам в таблице ASCII .

[ -~]

Знай своего вкуса регулярных выражений

Есть удивительное количество людей, которые думают, что регулярные выражения по существу не зависят от языка. Тем не менее, на самом деле есть довольно существенные различия между разновидностями, и особенно для Code Golf полезно знать некоторые из них и их интересные особенности, так что вы можете выбрать лучшее для каждой задачи. Вот обзор нескольких важных ароматов и того, что отличает их от других. (Этот список не может быть полным, но дайте мне знать, если я пропустил что-то действительно вопиющее.)

Perl и PCRE

Я добавляю их в один банк, так как я не слишком знаком со вкусом Perl, и они в основном эквивалентны (PCRE для Perl-совместимых регулярных выражений в конце концов). Основное преимущество разновидности Perl заключается в том, что вы можете фактически вызывать код Perl из регулярных выражений и подстановок.

• Рекурсия / подпрограммы . Вероятно, самая важная особенность для игры в гольф (которая существует только в нескольких вариантах).
• Условные паттерны (?(group)yes|no).
• Поддерживает изменение в случае замены строки с \l, \u, \Lи \U.
• PCRE допускает чередование во взглядах, где каждая альтернатива может иметь различную (но фиксированную) длину. (Большинство разновидностей, включая Perl, требуют, чтобы внешний вид имел общую фиксированную длину.)
• \G привязать матч к концу предыдущего матча.
• \K сбросить начало матча
• PCRE поддерживает как свойства символов Unicode, так и сценарии .
• \Q...\Eчтобы избежать длинных рядов персонажей. Полезно, когда вы пытаетесь сопоставить строку, которая содержит много метасимволов.

.СЕТЬ

Это, пожалуй, самый мощный аромат, с очень немногими недостатками.

• Поддерживает произвольные длины вид сзади, которые сопоставляются справа налево .
• Имеет уникальную концепцию балансировочных групп - изначально разработанную для сопоставления строк со сбалансированными скобками, их можно использовать для выполнения арифметических операций и сопоставления двухмерных шаблонов .
• Также поддерживает условные паттерны.
• Имеет краткий синтаксис для различия классов символов :[\w-[aeiou]]
• Обычные классы символов, такие \dкак Unicode.
• Поддерживает Unicode категории и блоки .

Один важный недостаток с точки зрения игры в гольф состоит в том, что он не поддерживает квантификаторы притяжения, как некоторые другие ароматы. Вместо того, .?+чтобы вам придется писать (?>.?).

Джава

• Из-за ошибки (см. Приложение) Java поддерживает ограниченный тип просмотра с переменной длиной: вы можете смотреть назад до самого начала строки, .*откуда вы можете теперь начать просмотр, например (?<=(?=lookahead).*).
• Поддерживает объединение и пересечение классов символов.
• Имеет наиболее обширную поддержку Unicode с классами символов для «Unicode-скриптов, блоков, категорий и двоичных свойств» .
• \Q...\E как в Perl / PCRE.

Рубин

В последних версиях этот вариант так же мощен, как и PCRE, включая поддержку вызовов подпрограмм. Как и Java, он также поддерживает объединение и пересечение классов символов. Одна особенность - встроенный класс символов для шестнадцатеричных цифр: \h(и отрицание \H).

Самая полезная функция для игры в гольф - это то, как Ruby обрабатывает квантификаторы. В частности, можно вкладывать квантификаторы без скобок. .{5,7}+работает и так делает .{3}?. Кроме того, в отличие от большинства других ароматов, если нижняя граница квантификатора равна, 0она может быть опущена, например .{,5}, эквивалентна .{0,5}.

Что касается подпрограмм, основное различие между подпрограммами PCRE в подпрограммах и в Ruby, является то , что синтаксис в Ruby является байты больше (?n)против \g<n>, но подпрограммы в Ruby может быть использованы для захвата, в то время как PCRE сбрасывает захваты после того, как подпрограмма заканчивается.

Наконец, в Ruby семантика для модификаторов, связанных с линиями, отличается от большинства других разновидностей. Модификатор, который обычно называют mдругими разновидностями, всегда включен в Ruby. Так ^и $всегда соответствует началу и концу линии не только начало и конец строки. Это может сэкономить вам байт, если вам нужно такое поведение, но это будет стоить вам дополнительных байтов, если вы этого не сделаете, потому что вам придется заменить ^и $на \Aи \z, соответственно. В дополнение к этому, модификатор, который обычно вызывается s(что делает .совпадение с переводами строки), вызывается mв Ruby. Это не влияет на количество байтов, но следует помнить, чтобы избежать путаницы.

питон

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

Тем не менее , есть альтернативный вариант, который предназначен для замены reмодуля в какой-то момент, и который содержит много интересных функций. В дополнение к добавлению поддержки рекурсии, видовых объектов переменной длины и операторов комбинации классов символов, он также обладает уникальной функцией нечеткого сопоставления . По сути, вы можете указать ряд ошибок (вставки, удаления, замены), которые допустимы, и механизм также даст вам приблизительные совпадения.

ECMAScript

Вкус ECMAScript очень ограничен и, следовательно, редко очень полезен для игры в гольф. Единственное, что у него получается, это отрицательный класс пустых символов, [^] соответствующий любому символу, а также безоговорочно провальный класс пустых символов [](в отличие от обычного (?!)). К сожалению, аромат не имеет каких-либо особенностей, которые делают последний полезным для нормальных проблем.

Lua

У Lua есть свой собственный довольно уникальный вкус, который весьма ограничен (например, вы не можете даже количественно определить группы), но имеет несколько полезных и интересных функций.

• Он имеет большое количество сокращений для встроенных классов символов , включая знаки пунктуации, символы верхнего / нижнего регистра и шестнадцатеричные цифры.
• С %bего помощью поддерживается очень компактный синтаксис для сопоставления сбалансированных строк. Например, %b()соответствует a, (а затем все до совпадения )(правильно пропуская внутренние совпадающие пары). (и )может быть любые два символа здесь.

Увеличение

Регулярный вкус Boost по сути Perl. Тем не менее, у него есть несколько приятных новых возможностей для подстановки регулярных выражений, включая изменения регистра и условия . Последнее, насколько я знаю, уникально для Boost.

Знай свои классы персонажей

Большинство разновидностей регулярных выражений имеют предопределенные классы символов. Например, \dсоответствует десятичной цифре, которая на три байта короче, чем [0-9]. Да, они могут немного отличаться, так как \dони также могут совпадать с цифрами Unicode в некоторых вариантах, но для большинства задач это не будет иметь значения.

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

\d      Match a decimal digit character
\s      Match a whitespace character
\w      Match a word character (typically [a-zA-Z0-9_])

Кроме того, у нас также есть:

\D \S \W

которые являются отрицательными версиями выше.

Не забудьте проверить свой вкус на наличие дополнительных классов символов, которые могут у него быть. Например, в PCRE есть \Rсимволы новой строки, а в Lua даже есть классы, такие как строчные и прописные символы.

(Спасибо @HamZa и @ MartinBüttner за указание на это)

Не связывайтесь с группами без захвата (если только ...)

Этот совет относится (по крайней мере) ко всем популярным Perl-вдохновленным вкусам.

Это может быть очевидным, но (когда не игра в гольф) рекомендуется использовать группы без захвата, (?:...)когда это возможно. Эти два дополнительных персонажа ?:расточительны при игре в гольф, поэтому просто используйте группы захвата, даже если вы не собираетесь ссылаться на них.

Однако есть одно (редкое) исключение: если вам случается с группой обратных ссылок 10хотя бы 3 раза, вы можете на самом деле сохранить байты, превратив предыдущую группу в группу без захвата, так что все эти \10s становятся \9s. (Подобные приемы применимы, если вы используете группу 11как минимум 5 раз и т. Д.)

Рекурсия для повторного использования шаблона

Горстка ароматов поддерживает рекурсию ( насколько мне известно , Perl, PCRE и Ruby). Даже если вы не пытаетесь решить рекурсивные проблемы, эта функция может сэкономить много байтов в более сложных шаблонах. Нет необходимости совершать вызов другой (именованной или пронумерованной) группе внутри самой группы. Если у вас есть определенный шаблон, который появляется несколько раз в вашем регулярном выражении, просто сгруппируйте его и обратитесь к нему за пределами этой группы. Это ничем не отличается от вызова подпрограммы в обычных языках программирования. Так что вместо

...someComplexPatternHere...someComplexPatternHere...someComplexPatternHere... 

в Perl / PCRE вы можете сделать:

...(someComplexPatternHere)...(?1)...(?1)...

или в рубине:

...(someComplexPatternHere)...\g<1>...\g<1>...

при условии, что это первая группа (конечно, вы можете использовать любой номер в рекурсивном вызове).

Обратите внимание, что это не то же самое, что backreference ( \1). Обратные ссылки совпадают с той же строкой, что и группа в прошлый раз. Эти вызовы подпрограмм фактически снова оценивают шаблон. В качестве примера для someComplexPatternHereдлинного класса символов:

a[0_B!$]b[0_B!$]c[0_B!$]d

Это будет соответствовать что-то вроде

aBb0c!d

Обратите внимание, что вы не можете использовать обратные ссылки здесь, сохраняя поведение. Обратная ссылка потерпит неудачу в приведенной выше строке, потому что Bи 0и! не то же самое. Однако при вызовах подпрограмм шаблон фактически переоценивается. Вышеуказанный шаблон полностью эквивалентен

a([0_B!$])b(?1)c(?1)d

Захват в вызовах подпрограмм

Одно предостережение для Perl и PCRE: если группа 1в приведенных выше примерах содержит дополнительные группы, то вызовы подпрограмм не запомнят их перехваты. Рассмотрим этот пример:

(\w(\d):)\2 (?1)\2 (?1)\2

Это не будет соответствовать

x1:1 y2:2 z3:3

потому что после возврата вызовов подпрограммы новый захват группы 2отбрасывается. Вместо этого этот шаблон будет соответствовать этой строке:

x1:1 y2:1 z3:1

Это отличается от Ruby, где вызовы подпрограмм делать сохраняют свои снимки, так что эквивалентно Рубиновый регулярное выражение (\w(\d):)\2 \g<1>\2 \g<1>\2будет соответствовать первому из приведенных выше примеров.

Причинение матча провалиться

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

(?!)

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

!

или любой другой нецифровый, не мета-символ, вызывающий сбой.

Даже если ваш ввод может содержать какие-либо подстроки, существуют более короткие пути, чем (?!). Любой вариант, который позволяет якорям появляться в шаблоне, а не в конце, может использовать одно из следующих двухсимвольных решений:

a^
$a

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

Во вкусе ECMAScript также есть довольно элегантное двухсимвольное решение

[]

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

Оптимизируйте свои операционные системы

Всякий раз, когда у вас есть 3 или более альтернатив в вашем RegEx:

/aliceblue|antiquewhite|aquamarine|azure/

Проверьте, есть ли общее начало:

/a(liceblue|ntiquewhite|quamarine|zure)/

А может даже общий финал?

/a(liceblu|ntiquewhit|quamarin|zur)e/

Примечание: 3 - это только начало и будет иметь одинаковую длину, 4+ будет иметь значение

Но что, если не все из них имеют общий префикс? _{(пробелы добавлены только для ясности)}

/aliceblue|antiquewhite|aqua|aquamarine|azure
|beige|bisque|black|blanchedalmond|blue|blueviolet|brown|burlywood
|cadetblue|chartreuse|chocolate|coral|cornflowerblue|cornsilk|crimson|cyan/

Группируйте их, если имеет смысл правило 3+:

/a(liceblue|ntiquewhite|qua|quamarine|zure)
|b(eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood)
|c(adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/

Или даже обобщать если энтропии удовлетворяет ваш USECASE:

/\w(liceblue|ntiquewhite|qua|quamarine|zure
|eige|isque|lack|lanchedalmond|lue|lueviolet|rown|urlywood
|adetblue|hartreuse|hocolate|oral|ornflowerblue|ornsilk|rimson|yan)/

^{^ в этом случае мы уверены, что мы не получаем clueилиcrown slack Ryan}

Это «согласно некоторым тестам» также улучшает производительность, поскольку обеспечивает привязку для начала.

Это довольно просто, но стоит заявить:

Если вы нашли себя повторять класс символов , [a-zA-Z]вероятно , можно просто использовать [a-z]и добавить i( к регистру я nsensitive модификатор) для вашего регулярного выражения.

Например, в Ruby следующие два регулярных выражения эквивалентны:

/[a-zA-Z]+\d{3}[a-zA-Z]+/
/[a-z]+\d{3}[a-z]/i - на 7 байт короче

В этом отношении другие модификаторы также могут сократить вашу общую длину. Вместо этого:

/(.|\n)/

который соответствует ЛЮБОМУ символу (потому что точка не соответствует символу новой строки), используйте модификатор s -lines , который делает точку новой строки.

/./s - на 3 байта короче

В Ruby существует множество встроенных классов символов для регулярных выражений. Смотрите эту страницу и ищите «Свойства персонажа».
Отличным примером является «Символ валюты». Согласно Википедии существует множество возможных символов валюты, и поместить их в класс символов будет очень дорого ( [$฿¢₡Ð₫€.....]), тогда как любой из них можно сопоставить в 6 байтах:\p{Sc}

Простой синтаксический анализатор языка

Вы можете создать очень простой парсер с RE как \d+|\w+|".*?"|\n|\S . Токены, которым вы должны соответствовать, разделены символом RE 'или'.

Каждый раз, когда механизм RE пытается найти совпадение в текущей позиции в тексте, он пробует первый шаблон, затем второй и т. Д. Если он терпит неудачу (например, для пробела здесь), он переходит и снова пытается сопоставить , Порядок важен. Если мы поместили \Sтермин раньше \d+срока,\S он сначала совпадал бы с любым непробельным символом, который сломал бы наш синтаксический анализатор.

Для ".*?"сравнения строк используется не жадный модификатор, поэтому мы сопоставляем только одну строку за раз. Если ваш RE не имеет нежадных функций, вы можете использовать "[^"]*" что эквивалентно.

Пример Python:

text = 'd="dogfinder"\nx=sum(ord(c)*872 for c in "fish"+d[3:])'
pat = r'\d+|\w+|".*?"|\n|\S'
print re.findall(pat, text)

['d', '=', '"dogfinder"', '\n', 'x', '=', 'sum', '(', 'ord', '(', 'c', ')',
    '*', '872', 'for', 'c', 'in', '"fish"', '+', 'd', '[', '3', ':', ']', ')']

Пример игры в гольф на Python:

# assume we have language text in A, and a token processing function P
map(P,findall(r'\d+|\w+|".*?"|\n|\S',A))

Вы можете настроить шаблоны и их порядок для языка, который вам нужен. Этот метод хорошо работает для JSON, базового HTML и числовых выражений. Он успешно использовался много раз с Python 2, но должен быть достаточно общим, чтобы работать в других средах.

\K вместо позитивного взгляда

PCRE и Perl поддерживают escape-последовательность \K, которая сбрасывает начало матча. Это ab\Kcdпотребует, чтобы ваша входная строка содержала, abcdно сообщенное совпадение будет только cd.

Если вы используете позитивный взгляд в начале вашего паттерна (что, вероятно, является наиболее вероятным местом), то в большинстве случаев вы можете использовать \Kвместо этого и сохранить 3 байта:

(?<=abc)def
abc\Kdef

Это эквивалентно для большинства целей, но не полностью. Различия приносят с собой как преимущества, так и недостатки:

• Сверху: PCRE и Perl не поддерживают вид сзади произвольной длины (только .NET поддерживает). То есть нельзя делать что-то подобное (?<=ab*). Но с ним \Kвы можете поставить любой шаблон перед ним! Так ab*\Kработает. Это фактически делает эту технику намного более мощной в тех случаях, когда она применима.
• Перевернутый: Lookarounds не отступают. Это уместно, если вы хотите захватить что-то в представлении для обратной ссылки позже, но есть несколько возможных захватов, которые все приводят к действительным совпадениям. В этом случае движок регулярных выражений будет использовать только одну из этих возможностей. При использовании \Kэтой части регулярное выражение возвращается назад, как и все остальное.

• Недостаток: Как вы, вероятно, знаете, несколько совпадений регулярного выражения не могут перекрываться. Часто обходные пути используются для частичного обхода этого ограничения, поскольку предварительный просмотр может проверять часть строки, которая уже использовалась при предыдущем сопоставлении. Поэтому, если вы хотите сопоставить все последующие символы, abвы можете использовать (?<=ab).. Учитывая вход

  ababc
  

  это будет соответствовать второй aи c. Это не может быть воспроизведено с \K. Если бы вы использовали ab\K., вы бы получили только первый матч, потому что теперь abне в поиске.

Соответствие любому персонажу

В разновидности ECMAScript отсутствуют sмодификаторы, которые бы .соответствовали любому символу (включая символы новой строки). Это означает, что не существует односимвольного решения для сопоставления совершенно произвольных символов. Стандартное решение для других вкусов (когда sпо какой-то причине никто не хочет пользоваться ) есть [\s\S]. Однако, ECMAScript единственный вкус (к моему знанию) , который поддерживает пустые классы символов, и , следовательно , имеет гораздо более короткий вариант: [^]. Это отрицательный пустой класс символов, то есть он соответствует любому символу.

Даже для других вариантов мы можем извлечь уроки из этой техники: если мы не хотим использовать s(например, потому что нам все еще нужно обычное значение .в других местах), все равно может быть более короткий способ сопоставления как символов новой строки, так и печатных символов, при условии, что какой-то символ, который мы знаем, не появляется на входе. Скажем, мы обрабатываем числа, разделенные символами новой строки. Тогда мы можем сопоставить любой символ с [^!], так как мы знаем, что !он никогда не будет частью строки. Это экономит два байта над наивным [\s\S]или [\d\n].

Используйте атомные группы и притяжательные квантификаторы

Я нашел атомные группы ( (?>...)) и притяжательные кванторы ( ?+, *+, ++, {m,n}+) иногда очень полезно для игры в гольф. Он совпадает со строкой и позже запрещает возврат. Таким образом, он будет соответствовать только первой сопоставимой строке, найденной механизмом регулярных выражений.

Например: чтобы сопоставить строку с нечетным числом a's в начале, за которой не следует больше a', вы можете использовать:

^(aa)*+a
^(?>(aa)*)a

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

В .NET регулярных выражениях (которые не имеют притяжательных квантификаторов), вы можете использовать это, чтобы вытолкнуть группу 1 наибольшее кратное 3 (максимум 30) раз (не очень хорошо):

(?>((?<-1>){3}|){10})

Забудьте захваченную группу после подвыражения (PCRE)

Для этого регулярного выражения:

^((a)(?=\2))(?!\2)

Если вы хотите очистить \ 2 после группы 1, вы можете использовать рекурсию:

^((a)(?=\2)){0}(?1)(?!\2)

Это будет соответствовать, в aaто время как предыдущий не будет. Иногда вы также можете использовать ??или даже ?вместо {0}.

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

Также отметим, что атомные группы предполагаются для рекурсий в PCRE. Так что это не будет соответствовать ни одной букве a:

^(a?){0}(?1)a

Я не пробовал это в других ароматах еще.

Для просмотра можно также использовать двойные негативы для этой цели:

^(?!(?!(a)(?=\1))).(?!\1)

Необязательные выражения

Иногда полезно помнить, что

(abc)?

в основном так же, как

(abc|)

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

((abc)?)

Использование версии |также полезно, когда вы все равно хотите обернуть выражение в какую-то другую форму группы и не заботитесь о захвате:

(?=(abc)?)
(?=abc|)

(?>(abc)?)
(?>abc|)

Наконец, этот трюк также может быть применен к неуклюжим, ?когда он сохраняет байт даже в необработанном виде (и, следовательно, 3 байта в сочетании с другими формами групп):

(abc)??
(|abc)

Несколько совпадений, которые всегда совпадают (.NET)

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

(?=a)(?=b)(?=c)
((?=a)b){...}

Это короче:

(?(?(?(a)b)c))
(?(a)b){...}

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

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