Similar a nuestros hilos para consejos de golf específicos del idioma: ¿cuáles son los trucos generales para acortar las expresiones regulares?
Puedo ver tres usos de regex cuando se trata de jugar al golf: el clásico regex golf ("aquí hay una lista que debería coincidir, y aquí hay una lista que debería fallar"), usando regex para resolver problemas computacionales y expresiones regulares usadas como partes de Código de golf más grande. Siéntase libre de publicar consejos que aborden cualquiera o todos estos. Si su punta está limitada a uno o más sabores, indique estos sabores en la parte superior.
Como de costumbre, siga una sugerencia (o una familia de sugerencias muy relacionadas) por respuesta, de modo que las sugerencias más útiles puedan llegar a la cima mediante la votación.
fuente
Respuestas:
Cuando no escapar
Estas reglas se aplican a la mayoría de los sabores, si no a todos:
]
no necesita escapar cuando no tiene comparación.{
y}
no necesitan escapar cuando no son parte de una repetición, por ejemplo,{a}
coincide{a}
literalmente. Incluso si desea hacer coincidir algo como{2}
, solo necesita escapar de uno de ellos, por ejemplo{2\}
.En clases de personajes:
]
no necesita escapar cuando es el primer carácter de un conjunto de caracteres, por ejemplo,[]abc]
coincide con uno de]abc
, o cuando es el segundo carácter después de un^
, por ejemplo,[^]]
coincide con cualquier cosa menos]
. (Excepción notable: ¡sabor ECMAScript!)[
no necesita escapar en absoluto. Junto con el consejo anterior, esto significa que puedes combinar ambos corchetes con la clase de personaje terriblemente contra-intuitiva[][]
.^
no necesita escapar cuando es no el primer carácter de un conjunto de caracteres, por ejemplo[ab^c]
.-
no necesita escapar cuando es el primer (segundo después de a^
) o el último carácter en un conjunto de caracteres, por ejemplo[-abc]
,[^-abc]
o[abc-]
.No es necesario que otros caracteres escapen dentro de una clase de caracteres, incluso si son metacaracteres fuera de las clases de caracteres (excepto la barra diagonal inversa
\
).Además, en algunos sabores
^
y$
se combinan literalmente cuando no están al principio o al final de la expresión regular respectivamente.(Gracias a @ MartinBüttner por completar algunos detalles)
fuente
[.]
). Escaparlo normalmente ahorraría 1 byte en este caso\.
[
debe escapar en Java. Sin embargo, no estoy seguro sobre ICU (utilizado en Android e iOS) o .NET.Una expresión regular simple para unir todos los caracteres imprimibles en la tabla ASCII .
fuente
Conoce tus sabores regex
Hay una cantidad sorprendente de personas que piensan que las expresiones regulares son esencialmente agnósticas al lenguaje. Sin embargo, en realidad hay diferencias bastante sustanciales entre los sabores, y especialmente para el golf de código es bueno conocer algunos de ellos y sus características interesantes, para que pueda elegir el mejor para cada tarea. Aquí hay una descripción general de varios sabores importantes y lo que los distingue de los demás. (Esta lista no puede estar realmente completa, pero avíseme si me perdí algo realmente deslumbrante).
Perl y PCRE
Los estoy tirando en una sola olla, ya que no estoy demasiado familiarizado con el sabor de Perl y son en su mayoría equivalentes (PCRE es para expresiones regulares compatibles con Perl después de todo). La principal ventaja del sabor Perl es que en realidad se puede llamar al código Perl desde el interior de la expresión regular y la sustitución.
(?(group)yes|no)
.\l
,\u
,\L
y\U
.\G
para anclar una partida al final de la partida anterior.\K
para reiniciar el comienzo del partido\Q...\E
para escapar de series más largas de personajes. Es útil cuando intenta hacer coincidir una cadena que contiene muchos metacaracteres..RED
Este es probablemente el sabor más poderoso, con muy pocas deficiencias.
[\w-[aeiou]]
\d
son compatibles con Unicode.Una deficiencia importante en términos de golf es que no admite cuantificadores posesivos como algunos otros sabores. En lugar de
.?+
tendrás que escribir(?>.?)
.Java
.*
desde donde ahora puede comenzar una búsqueda hacia adelante, como(?<=(?=lookahead).*)
.\Q...\E
como en Perl / PCRE.Rubí
En versiones recientes, este sabor es igualmente poderoso que PCRE, incluido el soporte para llamadas de subrutina. Al igual que Java, también admite la unión e intersección de clases de caracteres. Una característica especial es la clase de caracteres incorporada para dígitos hexadecimales:
\h
(y el negado\H
).Sin embargo, la característica más útil para el golf es cómo Ruby maneja los cuantificadores. En particular, es posible anidar cuantificadores sin paréntesis.
.{5,7}+
funciona y también lo hace.{3}?
. Además, a diferencia de la mayoría de los otros sabores, si0
se puede omitir el límite inferior de un cuantificador , por ejemplo,.{,5}
es equivalente a.{0,5}
.En cuanto a las subrutinas, la principal diferencia entre las subrutinas de PCRE y las subrutinas de Ruby es que la sintaxis de Ruby es un byte más larga
(?n)
vs\g<n>
, pero las subrutinas de Ruby se pueden usar para capturar, mientras que PCRE restablece las capturas después de que finaliza una subrutina.Finalmente, Ruby tiene una semántica diferente para los modificadores relacionados con la línea que la mayoría de los otros sabores. El modificador que generalmente se llama
m
en otros sabores siempre está activado en Ruby. Así^
, y$
siempre que coincida con el comienzo y el final de una línea no sólo el principio y el final de la cadena. Esto puede ahorrarle un byte si necesita este comportamiento, pero le costará bytes adicionales si no lo hace, ya que tendrá que reemplazar^
y$
con\A
y\z
, respectivamente. Además de eso, el modificador que generalmente se llamas
(que hace que los.
avances de línea coincidan) se llamam
en Ruby. Esto no afecta el recuento de bytes, pero debe tenerse en cuenta para evitar confusiones.Pitón
Python tiene un sabor sólido, pero no conozco ninguna característica particularmente útil que no encontrarías en ningún otro lado.
Sin embargo , hay un sabor alternativo que está destinado a reemplazar el
re
módulo en algún momento y que contiene muchas características interesantes. Además de agregar compatibilidad para operadores de combinación de recursión, lookbehinds de longitud variable y clase de caracteres, también tiene la característica única de coincidencia difusa . En esencia, puede especificar una serie de errores (inserciones, eliminaciones, sustituciones) que están permitidos, y el motor también le dará coincidencias aproximadas.ECMAScript
El sabor ECMAScript es muy limitado y, por lo tanto, rara vez es muy útil para el golf. Lo único que tiene que hacer es que la clase de caracteres vacía negada
[^]
coincida con cualquier carácter, así como la clase de caracteres vacía que falla incondicionalmente[]
(a diferencia de lo habitual(?!)
). Desafortunadamente, el sabor no tiene ninguna característica que lo haga útil para problemas normales.Lua
Lua tiene su propio sabor bastante único, que es bastante limitado (por ejemplo, ni siquiera puede cuantificar grupos) pero viene con un puñado de características útiles e interesantes.
%b
él admite una sintaxis muy compacta para que coincida con cadenas equilibradas. Por ejemplo,%b()
coincide con ay(
luego todo hasta una coincidencia)
(omitiendo correctamente los pares coincidentes internos).(
y)
pueden ser dos caracteres cualquiera aquí.Aumentar
El sabor regex de Boost es esencialmente el de Perl. Sin embargo, tiene algunas características nuevas y agradables para la sustitución de expresiones regulares, que incluyen cambios de casos y condicionales . Este último es exclusivo de Boost, que yo sepa.
fuente
.?+
equivalente a.*
?Conoce tus clases de personajes
La mayoría de los sabores regex tienen clases de caracteres predefinidas. Por ejemplo,
\d
coincide con un dígito decimal, que es tres bytes más corto que[0-9]
. Sí, pueden ser ligeramente diferentes, ya\d
que también pueden coincidir con los dígitos Unicode en algunos sabores, pero para la mayoría de los desafíos esto no hará la diferencia.Aquí hay algunas clases de caracteres que se encuentran en la mayoría de los sabores regex:
Además, también tenemos:
que son versiones negadas de lo anterior.
Asegúrese de verificar su sabor para cualquier clase de personaje adicional que pueda tener. Por ejemplo, PCRE tiene
\R
para nuevas líneas y Lua incluso tiene clases como minúsculas y mayúsculas.(Gracias a @HamZa y @ MartinBüttner por señalarlos)
fuente
\R
para nuevas líneas en PCRE.No te molestes con los grupos que no capturan (a menos que ...)
Este consejo se aplica a (al menos) todos los sabores populares inspirados en Perl.
Esto puede ser obvio, pero (cuando no se juega al golf) es una buena práctica usar grupos
(?:...)
que no capturan siempre que sea posible. Sin?:
embargo, estos dos personajes adicionales son un desperdicio cuando juegas al golf, así que solo usa grupos de captura, incluso si no vas a hacer referencia a ellos.Sin embargo, hay una excepción (rara): si sucede que el grupo de referencia retrocede
10
al menos 3 veces, en realidad puede guardar bytes convirtiendo un grupo anterior en un grupo sin captura, de modo que todos esos\10
s se conviertan en\9
s. (Se aplican trucos similares, si usa el grupo11
al menos 5 veces, etc.)fuente
$9
lugar de$10
o$11
una vez guarda un byte. Volviendo$10
a$9
requiere una?:
, que es de dos bytes, por lo que tendrá tres$10
s para salvar algo. Volviendo$11
a$9
requiere dos?:
s que es cuatro bytes, por lo que tendrá cinco$11
s para ahorrar algo (o cinco$10
y$11
combinado).Recursión por reutilización de patrones
Un puñado de sabores respaldan la recursividad ( que yo sepa , Perl, PCRE y Ruby). Incluso cuando no intente resolver problemas recursivos, esta función puede ahorrar muchos bytes en patrones más complicados. No es necesario hacer la llamada a otro grupo (con nombre o numerado) dentro de ese grupo. Si tiene un cierto patrón que aparece varias veces en su expresión regular, simplemente agrúpelo y consúltelo fuera de ese grupo. Esto no es diferente de una llamada de subrutina en lenguajes de programación normales. Entonces en lugar de
en Perl / PCRE puedes hacer:
o en Ruby:
siempre que sea el primer grupo (por supuesto, puede usar cualquier número en la llamada recursiva).
Tenga en cuenta que esto no es lo mismo que una referencia inversa (
\1
). Las referencias posteriores coinciden exactamente con la misma cadena que el grupo coincidió la última vez. Estas llamadas de subrutina en realidad evalúan el patrón nuevamente. Como ejemplo parasomeComplexPatternHere
tomar una clase de caracteres larga:Esto coincidiría con algo como
Tenga en cuenta que no puede usar referencias anteriores aquí mientras se preserva el comportamiento. Una referencia inversa fallaría en la cadena anterior, porque
B
y0
y!
no son lo mismo. Sin embargo, con las llamadas de subrutina, el patrón se vuelve a evaluar. El patrón anterior es completamente equivalente aCaptura en llamadas de subrutina
Una nota de precaución para Perl y PCRE: si el grupo
1
en los ejemplos anteriores contiene más grupos, entonces las llamadas de subrutina no recordarán sus capturas. Considere este ejemplo:Esto no coincidirá
porque después de que regresan las llamadas de la subrutina,
2
se descarta la nueva captura de grupo . En cambio, este patrón coincidiría con esta cadena:Esto es diferente de Rubí, donde las llamadas a subrutinas hacen conservar sus capturas, así, el texto equivalente de Ruby
(\w(\d):)\2 \g<1>\2 \g<1>\2
se correspondería con el primero de los ejemplos anteriores.fuente
\1
para Javascript. Y PHP también (supongo).(..)\1
, coincidiríaabab
pero fallaríaabba
mientras(..)(?1)
que coincidirá con el último. En realidad, es una llamada de subrutina en el sentido de que la expresión se aplica nuevamente, en lugar de coincidir literalmente con lo que coincidió la última vez.(?=a.b.c)(.[0_B!$]){3}d
Hacer que un partido falle
Cuando se usa la expresión regular para resolver problemas computacionales o hacer coincidir lenguajes altamente no regulares, a veces es necesario hacer que una rama del patrón falle independientemente de dónde se encuentre en la cadena. El enfoque ingenuo es utilizar una búsqueda anticipada negativa vacía:
El contenido (el patrón vacío) siempre coincide, por lo que la búsqueda anticipada negativa siempre falla. Pero la mayoría de las veces, hay una opción mucho más simple: simplemente use un carácter que sabe que nunca aparecerá en la entrada. Por ejemplo, si sabe que su entrada siempre constará solo de dígitos, simplemente puede usar
o cualquier otro carácter que no sea un dígito ni un metadato para causar un error.
Incluso si su entrada podría contener alguna subcadena, existen formas más cortas que
(?!)
. Cualquier sabor que permita que las anclas aparezcan dentro de un patrón en lugar del final, podría usar cualquiera de las siguientes soluciones de 2 caracteres:Sin embargo, tenga en cuenta que algunos sabores se tratarán
^
y$
como caracteres literales en estas posiciones, porque obviamente no tienen sentido como anclas.En el sabor ECMAScript también existe la solución elegante de 2 caracteres
Esta es una clase de caracteres vacía, que intenta asegurarse de que los siguientes caracteres sean uno de los de la clase, pero no hay caracteres en la clase, por lo que esto siempre falla. Tenga en cuenta que esto no funcionará en ningún otro sabor, porque las clases de caracteres generalmente no pueden estar vacías.
fuente
Optimiza tus quirófanos
Siempre que tenga 3 o más alternativas en su RegEx:
Verifique si hay un comienzo común:
¿Y tal vez incluso un final común?
Nota: 3 es solo el comienzo y representaría la misma longitud, 4+ marcaría la diferencia
Pero, ¿qué pasa si no todos tienen un prefijo común? (espacio en blanco solo agregado para mayor claridad)
Agrúpelos, siempre que la regla 3+ tenga sentido:
O incluso generalice si la entropía satisface su caso de uso:
^ en este caso estamos seguros de que no obtenemos ninguno
clue
ocrown
slack
Ryan
Esto "según algunas pruebas" también mejora el rendimiento, ya que proporciona un ancla para comenzar.
fuente
aqua|aquamarine
→aqua(|marine)
oaqua(marine)?
.Este es bastante simple, pero vale la pena declararlo:
Si te encuentras repitiendo la clase de caracteres,
[a-zA-Z]
probablemente solo puedas usar[a-z]
y agregar eli
( modificador de mayúsculas y minúsculas) a tu expresión regular.Por ejemplo, en Ruby, las siguientes dos expresiones regulares son equivalentes:
/[a-zA-Z]+\d{3}[a-zA-Z]+/
/[a-z]+\d{3}[a-z]/i
- 7 bytes más cortosPara el caso, los otros modificadores también pueden acortar su longitud total. En lugar de hacer esto:
/(.|\n)/
lo que coincide con cualquier carácter (porque de puntos no coincide nueva línea), utilice los s ingle modificador de línea
s
, lo que hace que las nuevas líneas de concordancia de puntos././s
- 3 bytes más cortosEn Ruby, hay un montón de clases de personajes incorporadas para expresiones regulares. Vea esta página y busque "Propiedades del personaje".
Un gran ejemplo es el "símbolo de moneda". Según Wikipedia, hay un montón de posibles símbolos de moneda, y ponerlos en una clase de caracteres sería muy costoso (
[$฿¢₡Ð₫€.....
]), mientras que puede hacer coincidir cualquiera de ellos en 6 bytes:\p{Sc}
fuente
s
modificador no es compatible. :( Pero allí puedes usar el/[^]/
truco patentado de JavaScript .(.|\n)
ni siquiera funciona en algunos sabores, porque a.
menudo tampoco coincide con otros tipos de separadores de línea. Sin embargo, la forma habitual de hacer esto (sins
)[\s\S]
es con los mismos bytes que(.|\n)
.Un analizador de lenguaje simple
Puede construir un analizador muy simple con un RE como
\d+|\w+|".*?"|\n|\S
. Los tokens que necesitas hacer coincidir se separan con el carácter RE 'o'.Cada vez que el motor RE intenta hacer coincidir en la posición actual en el texto, intentará el primer patrón, luego el segundo, etc. Si falla (en un carácter de espacio aquí, por ejemplo), continúa y vuelve a intentar las coincidencias . El orden es importante. Si colocamos el
\S
término antes del\d+
término, el\S
primero coincidiría con cualquier carácter no espacial que rompería nuestro analizador.El
".*?"
emparejador de cadenas utiliza un modificador no codicioso, por lo que solo hacemos coincidir una cadena a la vez. Si su RE no tiene funciones no codiciosas, puede usar"[^"]*"
cuál es equivalente.Ejemplo de Python:
Golfed Python Ejemplo:
Puede ajustar los patrones y su orden para el idioma que necesita hacer coincidir. Esta técnica funciona bien para JSON, HTML básico y expresiones numéricas. Se ha utilizado con éxito muchas veces con Python 2, pero debería ser lo suficientemente general como para funcionar en otros entornos.
fuente
\K
en lugar de mirar hacia atrás positivoPCRE y Perl admiten la secuencia de escape
\K
, que restablece el comienzo del partido. Esoab\Kcd
requerirá que su cadena de entrada contenga,abcd
pero la coincidencia informada solo serácd
.Si está utilizando una retrospectiva positiva al comienzo de su patrón (que probablemente sea el lugar más probable), en la mayoría de los casos, puede usar
\K
en su lugar y guardar 3 bytes:Esto es equivalente para la mayoría de los propósitos, pero no del todo. Las diferencias traen ventajas y desventajas con ellos:
(?<=ab*)
. ¡Pero con\K
usted puede poner cualquier tipo de patrón frente a él! Asíab*\K
funciona En realidad, esto hace que esta técnica sea mucho más poderosa en los casos en que sea aplicable.\K
esa parte de la expresión regular, se retrocede como todo lo demás.Desventaja: Como probablemente sepa, varias coincidencias de una expresión regular no pueden superponerse. A menudo, las búsquedas alternativas se utilizan para evitar esta limitación, ya que la búsqueda anticipada puede validar una parte de la cadena que ya se consumió en una coincidencia anterior. Entonces, si desea hacer coincidir todos los caracteres que siguen
ab
, puede usar(?<=ab).
. Dada la entradaesto coincidiría con el segundo
a
y elc
. Esto no se puede reproducir con\K
. Si lo usóab\K.
, solo obtendría la primera coincidencia, porque ahoraab
no está en una búsqueda.fuente
\K
secuencia de escape dentro de una afirmación positiva, el inicio informado de una coincidencia exitosa puede ser mayor que el final de la coincidencia.ababc
, dado , no hay forma de igualar tanto el segundoa
como elc
con\K
. Solo obtendrás una coincidencia.\G
.
del último partido fuera realmente una
.Emparejar cualquier personaje
El sabor ECMAScript carece de
s
modificadores, lo que hace que.
coincida con cualquier carácter (incluidas las nuevas líneas). Esto significa que no hay una solución de un solo carácter para hacer coincidir caracteres completamente arbitrarios. La solución estándar en otros sabores (cuando uno no quiere usars
por alguna razón) es[\s\S]
. Sin embargo, ECMAScript es el único sabor (que yo sepa) que apoya las clases de caracteres vacíos, y por lo tanto tiene una alternativa mucho más corto:[^]
. Esta es una clase de caracteres vacía negada, es decir, coincide con cualquier carácter.Incluso para otros sabores, podemos aprender de esta técnica: si no queremos usar
s
(por ejemplo, porque todavía necesitamos el significado habitual.
en otros lugares), todavía puede haber una forma más corta de combinar los caracteres imprimibles y de nueva línea, siempre que haya algún carácter que sepamos que no aparece en la entrada. Digamos que estamos procesando números delimitados por nuevas líneas. Entonces podemos unir cualquier carácter[^!]
, ya que sabemos que!
nunca será parte de la cadena. Esto ahorra dos bytes sobre el ingenuo[\s\S]
o[\d\n]
.fuente
\N
significa exactamente lo que.
significa fuera del/s
modo, excepto que no se ve afectado por un modo.Utilice grupos atómicos y cuantificadores posesivos.
He encontrado grupos atómicos (
(?>...)
) y cuantificadores posesivos (?+
,*+
,++
,{m,n}+
) a veces muy útiles para jugar al golf. Coincide con una cadena y no permite retroceder más tarde. Por lo tanto, solo coincidirá con la primera cadena compatible que encuentre el motor regex.Por ejemplo: para hacer coincidir una cadena con un número impar de
a
's al principio, que no es seguida por mása
' s, puede usar:Esto le permite usar cosas como
.*
libremente, y si hay una coincidencia obvia, no habrá otra posibilidad que combine demasiados caracteres o muy pocos, lo que puede romper su patrón.En .NET regex (que no tiene cuantificadores posesivos), puede usar esto para hacer estallar el grupo 1 el mayor múltiplo de 3 (con un máximo de 30) veces (no se juega muy bien):
fuente
Olvídese de un grupo capturado después de una subexpresión (PCRE)
Para esta expresión regular:
Si desea borrar el \ 2 después del grupo 1, puede usar la recursividad:
Coincidirá
aa
mientras que el anterior no. A veces también puede usar??
o incluso?
en lugar de{0}
.Esto puede ser útil si usa mucho las recursiones, y algunas de las referencias o grupos condicionales aparecieron en diferentes lugares en su expresión regular.
También tenga en cuenta que se suponen grupos atómicos para las recursiones en PCRE. Entonces esto no coincidirá con una sola letra
a
:No lo probé en otros sabores todavía.
Para lookaheads, también puede usar negativos dobles para este propósito:
fuente
Expresiones opcionales
A veces es útil recordar que
es casi lo mismo que
Sin embargo, hay una pequeña diferencia: en el primer caso, el grupo captura
abc
o no captura en absoluto. El último caso haría que una referencia inversa fallara incondicionalmente. En la segunda expresión, el grupo capturaráabc
o una cadena vacía, donde el último caso haría una coincidencia de referencia incondicional. Para emular este último comportamiento?
, necesitaría rodear todo en otro grupo que costaría dos bytes:La versión que usa
|
también es útil cuando desea ajustar la expresión en alguna otra forma de grupo de todos modos y no le importa la captura:Finalmente, este truco también se puede aplicar a ungreedy
?
donde guarda un byte incluso en su forma sin procesar (y, en consecuencia, 3 bytes cuando se combina con otras formas de grupos):fuente
Múltiples lookaheads que siempre coinciden (.NET)
Si tiene 3 o más construcciones anticipadas que siempre coinciden (para capturar subexpresiones), o hay un cuantificador en una búsqueda anticipada seguido de otra cosa, por lo que deberían estar en un grupo no necesariamente capturado:
Estos son más cortos:
donde
a
no debe ser el nombre de un grupo capturado. No se puede usar|
para decir lo habitual dentrob
yc
sin agregar otro par de paréntesis.Desafortunadamente, los grupos de equilibrio en los condicionales parecían tener errores, haciéndolo inútil en muchos casos.
fuente