Semelhante aos nossos tópicos para dicas de golfe específicas ao idioma: quais são os truques gerais para encurtar expressões regulares?
Eu posso ver três usos do regex quando se trata de golfe: clássico regex golf ("aqui está uma lista que deve corresponder e aqui está uma lista que deve falhar"), usando o regex para resolver problemas computacionais e expressões regulares usadas como partes de código de golfe maior. Sinta-se à vontade para postar dicas sobre qualquer uma ou todas elas. Se sua dica estiver limitada a um ou mais sabores, indique-os na parte superior.
Como sempre, siga uma dica (ou família de dicas muito relacionadas) por resposta, para que as dicas mais úteis possam subir ao topo por meio de votação.
code-golf
tips
regular-expression
Martin Ender
fonte
fonte
Respostas:
Quando não escapar
Essas regras se aplicam à maioria dos sabores, se não a todos:
]
não precisa escapar quando é incomparável.{
e}
não precisa escapar quando não faz parte de uma repetição, por exemplo,{a}
combina{a}
literalmente. Mesmo se você quiser combinar algo como{2}
, você só precisa escapar de um deles, por exemplo{2\}
.Nas classes de personagens:
]
não precisa escapar quando é o primeiro caractere de um conjunto de caracteres, por exemplo,[]abc]
corresponde a um de]abc
, ou quando é o segundo caractere após a^
, por exemplo,[^]]
corresponde a qualquer coisa, exceto]
. (Exceção notável: sabor ECMAScript!)[
não precisa escapar. Juntamente com a dica acima, isso significa que você pode combinar os dois colchetes com a classe de personagem horrivelmente contra-intuitiva[][]
.^
não precisa escapar quando é não o primeiro caractere em um conjunto de caracteres, por exemplo[ab^c]
.-
não precisa escapar quando é o primeiro (segundo após a^
) ou o último caractere em um conjunto de caracteres, por exemplo[-abc]
,[^-abc]
ou[abc-]
.Nenhum outro personagem precisa escapar dentro de uma classe de caracteres, mesmo que sejam meta caracteres fora das classes de caracteres (exceto a
\
própria barra invertida ).Além disso, em alguns sabores
^
e$
são correspondidos literalmente quando não estão no início ou no final da regex, respectivamente.(Obrigado a @ MartinBüttner por preencher alguns detalhes)
fonte
[.]
). Escapando que normalmente iria salvar 1 byte neste caso\.
[
deve ser escapado em Java. Porém, não tenho certeza sobre o ICU (usado no Android e iOS) ou .NET.Uma expressão regular simples para corresponder a todos os caracteres imprimíveis na tabela ASCII .
fonte
Conheça seus sabores regex
Há uma quantidade surpreendente de pessoas que pensam que expressões regulares são essencialmente independentes da linguagem. No entanto, existem diferenças bastante substanciais entre os sabores e, especialmente para o código de golfe, é bom conhecer alguns deles e seus recursos interessantes, para que você possa escolher o melhor para cada tarefa. Aqui está uma visão geral de vários sabores importantes e o que os diferencia dos outros. (Esta lista não pode realmente estar completa, mas deixe-me saber se eu perdi algo realmente flagrante.)
Perl e PCRE
Estou jogando isso em um único pote, pois não estou muito familiarizado com o sabor Perl e eles são basicamente equivalentes (PCRE é para expressões regulares compatíveis com Perl, afinal). A principal vantagem do sabor Perl é que você pode realmente chamar o código Perl de dentro do regex e da substituição.
(?(group)yes|no)
.\l
,\u
,\L
e\U
.\G
para ancorar uma partida no final da partida anterior.\K
para redefinir o início da partida\Q...\E
para escapar de séries mais longas de caracteres. Útil quando você está tentando combinar uma string que contém muitos meta-caracteres..LÍQUIDO
Este é provavelmente o sabor mais poderoso, com muito poucas deficiências.
[\w-[aeiou]]
\d
são Unicode ciente.Uma falha importante em termos de golfe é que ele não suporta quantificadores possessivos como alguns outros sabores. Em vez de
.?+
ter que escrever(?>.?)
.Java
.*
de onde você pode iniciar uma lookahead, como(?<=(?=lookahead).*)
.\Q...\E
como no Perl / PCRE.Rubi
Nas versões recentes, esse sabor é igualmente poderoso como o PCRE, incluindo o suporte para chamadas de sub-rotina. Como Java, também suporta união e interseção de classes de caracteres. Um recurso especial é a classe de caracteres interna para dígitos hexadecimais:
\h
(e negada\H
).O recurso mais útil para jogar golfe é como Ruby lida com quantificadores. Mais notavelmente, é possível aninhar quantificadores sem parênteses.
.{5,7}+
funciona e o mesmo acontece.{3}?
. Além disso, ao contrário da maioria dos outros sabores, se o limite inferior de um quantificador for,0
ele pode ser omitido, por exemplo,.{,5}
é equivalente a.{0,5}
.Quanto à sub-rotinas, a principal diferença entre sub-rotinas de PCRE e sub-rotinas de Ruby, é que a sintaxe de Ruby é um byte mais
(?n)
vs\g<n>
, mas sub-rotinas de Ruby pode ser usado para capturar, enquanto PCRE redefine capturas após uma sub-rotina acabamentos.Finalmente, Ruby possui semânticas diferentes para modificadores relacionados à linha do que a maioria dos outros tipos. O modificador que geralmente é chamado
m
em outros sabores está sempre ativado no Ruby. Assim,^
e$
sempre coincidir com o início eo fim de uma linha e não apenas o início e fim da cadeia. Isso pode economizar um byte se você precisar desse comportamento, mas custará bytes extras se não precisar, porque você precisará substituir^
e$
por\A
e\z
, respectivamente. Além disso, o modificador que normalmente é chamados
(que faz.
corresponder os feeds de linha) é chamadom
no Ruby. Isso não afeta a contagem de bytes, mas deve-se ter em mente para evitar confusão.Python
O Python tem um sabor sólido, mas não conheço nenhum recurso particularmente útil que você não encontraria em nenhum outro lugar.
No entanto , há um sabor alternativo que se destina a substituir o
re
módulo em algum momento e que contém muitos recursos interessantes. Além de adicionar suporte para recursão, lookbehinds de comprimento variável e operadores de combinação de classes de caracteres, ele também possui o recurso exclusivo de correspondência difusa . Em essência, você pode especificar vários erros (inserções, exclusões, substituições) que são permitidos, e o mecanismo também fornecerá correspondências aproximadas.ECMAScript
O sabor do ECMAScript é muito limitado e, portanto, raramente é muito útil para jogar golfe. A única coisa que ele tem a oferecer é a classe de caracteres vazios negada
[^]
para corresponder a qualquer caractere, bem como a classe de caracteres vazios com falha incondicional[]
(ao contrário do habitual(?!)
). Infelizmente, o sabor não possui nenhum recurso que o torne útil para problemas normais.Lua
Lua tem seu próprio sabor bastante único, que é bastante limitado (por exemplo, você não pode nem quantificar grupos), mas vem com um punhado de recursos úteis e interessantes.
%b
ele, suporta uma sintaxe muito compacta para corresponder a cadeias equilibradas. Por exemplo,%b()
corresponde a(
e então tudo até uma correspondência)
(pulando corretamente os pares correspondentes internos).(
e)
pode haver dois caracteres aqui.Impulso
O sabor regex do Boost é essencialmente do Perl. No entanto, possui alguns recursos novos e agradáveis para a substituição de expressões regulares, incluindo alterações de casos e condicionais . O último é exclusivo do Boost, até onde eu sei.
fonte
.?+
equivalente a.*
?Conheça suas classes de personagens
A maioria dos tipos de expressões regulares tem classes de caracteres predefinidas. Por exemplo,
\d
corresponde a um dígito decimal, que é três bytes menor que[0-9]
. Sim, eles podem ser um pouco diferentes, pois\d
também podem corresponder aos dígitos Unicode em alguns tipos, mas para a maioria dos desafios isso não fará diferença.Aqui estão algumas classes de caracteres encontradas na maioria dos tipos de expressões regulares:
Além disso, também temos:
que são versões negadas do acima.
Certifique-se de verificar o seu sabor para qualquer classe de personagem adicional que possa ter. Por exemplo, o PCRE possui
\R
para novas linhas e Lua ainda possui classes como caracteres minúsculos e maiúsculos.(Obrigado a @HamZa e @ MartinBüttner por apontar isso)
fonte
\R
para novas linhas no PCRE.Não se preocupe com grupos que não capturam (a menos que ...)
Esta dica se aplica a (pelo menos) todos os sabores populares de inspiração Perl.
Isso pode ser óbvio, mas (quando não estiver jogando golfe) é uma boa prática usar grupos
(?:...)
que não capturam sempre que possível. Esses dois personagens extras?:
são um desperdício ao jogar no golfe; portanto, use grupos de captura, mesmo que você não os refaça.Porém, há uma exceção (rara): se você voltar ao grupo de referência
10
pelo menos três vezes, poderá salvar bytes transformando um grupo anterior em um grupo não capturável, de forma que todos eles\10
se tornem\9
s. (Truques semelhantes se aplicam, se você usar o grupo11
pelo menos 5 vezes e assim por diante.)fonte
$9
vez de$10
ou$11
uma vez salva um byte. Transformar$10
em$9
requer um?:
, que é de dois bytes, então você precisará de três$10
s para salvar alguma coisa. Transformar$11
em$9
requer dois?:
s, que são quatro bytes, portanto, você precisará de cinco$11
s para salvar algo (ou cinco$10
e$11
combinados).Recursão para reutilização de padrões
Um punhado de sabores apóia a recursão ( que eu saiba , Perl, PCRE e Ruby). Mesmo quando você não está tentando resolver problemas recursivos, esse recurso pode economizar muitos bytes em padrões mais complicados. Não há necessidade de fazer a chamada para outro grupo (nomeado ou numerado) dentro desse próprio grupo. Se você tem um determinado padrão que aparece várias vezes em sua regex, basta agrupá-lo e consultá-lo fora desse grupo. Isso não é diferente de uma chamada de sub-rotina nas linguagens de programação normais. Então, ao invés de
No Perl / PCRE, você poderia fazer:
ou em Ruby:
desde que seja o primeiro grupo (é claro, você pode usar qualquer número na chamada recursiva).
Observe que isso não é o mesmo que uma referência anterior (
\1
). As referências anteriores correspondem exatamente à mesma string que o grupo encontrou na última vez. Essas chamadas de sub-rotina realmente avaliam o padrão novamente. Como um exemplo parasomeComplexPatternHere
obter uma longa classe de caracteres:Isso corresponderia a algo como
Observe que você não pode usar referências anteriores aqui enquanto preserva o comportamento. Uma referência anterior falharia na sequência acima, porque
B
e0
e!
não são os mesmos. No entanto, com chamadas de sub-rotina, o padrão é realmente reavaliado. O padrão acima é completamente equivalente aCaptura em chamadas de sub-rotina
Uma nota de cautela para Perl e PCRE: se o grupo
1
nos exemplos acima contiver mais grupos, as chamadas de sub-rotina não lembrarão de suas capturas. Considere este exemplo:Isso não corresponde
porque depois que as chamadas de sub-rotina retornam, a nova captura de grupo
2
é descartada. Em vez disso, esse padrão corresponderia a esta sequência:Isto é diferente de Ruby, onde as chamadas de sub-rotinas fazer reter as suas capturas, de modo que o regex Rubi equivalente
(\w(\d):)\2 \g<1>\2 \g<1>\2
iria coincidir com o primeiro dos exemplos acima.fonte
\1
para Javascript. E PHP também (eu acho).(..)\1
, corresponderá,abab
mas falhará,abba
enquanto(..)(?1)
corresponderá ao último. Na verdade, é uma chamada de sub-rotina no sentido de que a expressão é aplicada novamente, em vez de corresponder literalmente ao que correspondeu da última vez.(?=a.b.c)(.[0_B!$]){3}d
Fazendo com que uma correspondência falhe
Ao usar o regex para resolver problemas computacionais ou corresponder a linguagens altamente não regulares, às vezes é necessário fazer com que uma ramificação do padrão falhe, independentemente de onde você estiver na sequência. A abordagem ingênua é usar um lookahead negativo vazio:
O conteúdo (o padrão vazio) sempre corresponde, portanto a aparência negativa sempre falha. Mas, na maioria das vezes, existe uma opção muito mais simples: basta usar um caractere que você sabe que nunca aparecerá na entrada. Por exemplo, se você sabe que sua entrada sempre será composta apenas por dígitos, você pode simplesmente usar
ou qualquer outro caractere não-dígito e não meta para causar falha.
Mesmo que sua entrada possa conter substrings, existem maneiras mais curtas que
(?!)
. Qualquer sabor que permita que as âncoras apareçam dentro de um padrão, em oposição ao final, pode usar uma das seguintes soluções de 2 caracteres:Observe, no entanto, que alguns sabores tratarão
^
e$
como caracteres literais nessas posições, porque obviamente não fazem sentido como âncoras.No sabor ECMAScript, há também a solução de 2 caracteres bastante elegante
Essa é uma classe de caracteres vazia, que tenta garantir que os próximos caracteres sejam um dos da classe - mas não há caracteres na classe, portanto sempre falha. Observe que isso não funcionará em nenhum outro sabor, porque as classes de caracteres geralmente não podem estar vazias.
fonte
Otimize seus ORs
Sempre que você tiver 3 ou mais alternativas em seu RegEx:
Verifique se há um começo comum:
E talvez até um final comum?
Nota: 3 é apenas o começo e representaria a mesma duração, 4 ou mais faria a diferença
Mas e se nem todos eles tiverem um prefixo comum? (espaço em branco adicionado apenas para maior clareza)
Agrupe-os, desde que a regra 3+ faça sentido:
Ou até generalize se a entropia satisfizer o seu caso:
^ neste caso, temos certeza de que não obtemos nenhum
clue
oucrown
slack
Ryan
Isso "de acordo com alguns testes" também melhora o desempenho, pois fornece uma âncora para começar.
fonte
aqua|aquamarine
→aqua(|marine)
ouaqua(marine)?
.Este é bastante simples, mas vale a pena afirmar:
Se você repetir a classe de caracteres,
[a-zA-Z]
provavelmente poderá usar[a-z]
e acrescentar oi
( modificador sensível a maiúsculas e minúsculas) ao seu regex.Por exemplo, no Ruby, as duas regexes a seguir são equivalentes:
/[a-zA-Z]+\d{3}[a-zA-Z]+/
/[a-z]+\d{3}[a-z]/i
- 7 bytes mais curtosNesse caso, os outros modificadores também podem diminuir o seu comprimento total. Em vez de fazer isso:
/(.|\n)/
que corresponde a qualquer caractere (porque ponto não coincide com nova linha), use as s ingle-line modificador
s
, que faz novas linhas jogo de pontos././s
- 3 bytes mais curtoEm Ruby, há uma tonelada de classes de caracteres internas para regex. Veja esta página e procure por "Propriedades dos caracteres".
Um ótimo exemplo é o "Símbolo da moeda". De acordo com a Wikipedia, existem muitos símbolos de moeda possíveis e colocá-los em uma classe de caracteres seria muito caro (
[$฿¢₡Ð₫€.....
]), enquanto você pode corresponder a qualquer um deles em 6 bytes:\p{Sc}
fonte
s
modificador não é suportado. :( Mas lá você pode usar de propriedade da JavaScript/[^]/
truque.(.|\n)
nem funciona em alguns tipos, porque.
geralmente também não corresponde a outros tipos de separadores de linha. No entanto, a maneira usual de fazer isso (sems
) é[\s\S]
com os mesmos bytes que(.|\n)
.Um analisador de idioma simples
Você pode criar um analisador muito simples com um RE
\d+|\w+|".*?"|\n|\S
. Os tokens que você precisa corresponder são separados pelo caractere RE 'ou'.Cada vez que o mecanismo de RE tenta corresponder à posição atual no texto, ele tenta o primeiro padrão, depois o segundo, etc. Se falhar (em um caractere de espaço aqui, por exemplo), ele segue em frente e tenta as correspondências novamente . A ordem é importante. Se colocarmos o
\S
termo antes do\d+
termo,\S
ele corresponderá primeiro a qualquer caractere não espacial que interrompa nosso analisador.O
".*?"
correspondente de seqüência de caracteres usa um modificador não guloso, portanto, correspondemos apenas uma sequência de cada vez. Se o seu ER não possui funções não gananciosas, você pode usar o"[^"]*"
que é equivalente.Exemplo de Python:
Exemplo de Python para golfe:
Você pode ajustar os padrões e a ordem deles para o idioma que você precisa corresponder. Essa técnica funciona bem para JSON, HTML básico e expressões numéricas. Ele foi usado com sucesso várias vezes com o Python 2, mas deve ser geral o suficiente para funcionar em outros ambientes.
fonte
\K
em vez de olhar positivoPCRE e Perl suportam a sequência de escape
\K
, que redefine o início da partida. Ou sejaab\Kcd
, exigirá que sua string de entrada contenha,abcd
mas a correspondência relatada será apenascd
.Se você estiver usando uma observação positiva no início de seu padrão (que provavelmente é o local mais provável), na maioria dos casos, poderá usar
\K
e salvar 3 bytes:Isso é equivalente para a maioria dos propósitos, mas não totalmente. As diferenças trazem vantagens e desvantagens com eles:
(?<=ab*)
. Mas com\K
você pode colocar qualquer tipo de padrão na frente dele! Entãoab*\K
funciona. Isso realmente torna essa técnica muito mais poderosa nos casos em que é aplicável.\K
essa parte do regex, está sendo retornado como todo o resto.Desvantagem: como você provavelmente sabe, várias correspondências de uma regex não podem se sobrepor. Freqüentemente, as pesquisas são usadas para contornar parcialmente essa limitação, pois o pesquisador pode validar uma parte da sequência que já foi consumida por uma correspondência anterior. Portanto, se você quiser combinar todos os caracteres que se seguiram,
ab
poderá usar(?<=ab).
. Dada a entradaisso corresponderia ao segundo
a
e aoc
. Isso não pode ser reproduzido com\K
. Se você usasseab\K.
, obteria apenas a primeira correspondência, porque agora elaab
não está em uma visão geral.fonte
\K
sequência de escape dentro de uma afirmação positiva, o início relatado de uma correspondência bem-sucedida pode ser maior que o final da correspondência.ababc
, dado , não há como combinar o segundoa
e oc
com\K
. Você receberá apenas uma partida.\G
.
a última partida foi realmente uma
.Correspondendo a qualquer caractere
O sabor do ECMAScript não possui os
s
modificadores que fazem a.
correspondência com qualquer caractere (incluindo novas linhas). Isso significa que não há solução de caractere único para corresponder caracteres completamente arbitrários. A solução padrão em outros sabores (quando não se deseja usars
por algum motivo) é[\s\S]
. No entanto, ECMAScript é o único sabor (que eu saiba) que suporta classes de personagens vazias, e, portanto, tem uma alternativa muito mais curto:[^]
. Esta é uma classe de caracteres vazia negada - ou seja, corresponde a qualquer caractere.Mesmo para outros sabores, podemos aprender com esta técnica: se não quisermos usá-lo
s
(por exemplo, porque ainda precisamos do significado usual.
em outros lugares), ainda haverá uma maneira mais curta de corresponder os caracteres de nova linha e de impressão, desde que exista algum caractere que sabemos que não aparece na entrada. Digamos, estamos processando números delimitados por novas linhas. Então podemos combinar qualquer caractere[^!]
, pois sabemos que!
isso nunca fará parte da string. Isso economiza dois bytes sobre o ingênuo[\s\S]
ou[\d\n]
.fonte
\N
significa exatamente o que.
significa fora do/s
modo, exceto que não é afetado por um modo.Use grupos atômicos e quantificadores possessivos
Eu encontrei grupos atômicos (
(?>...)
) e quantificadores possessivo (?+
,*+
,++
,{m,n}+
), por vezes muito úteis para o golfe. Ele corresponde a uma sequência e não permite o retorno posterior. Portanto, ele corresponderá apenas à primeira sequência correspondível encontrada pelo mecanismo de expressão regular.Por exemplo: Para combinar uma sequência com um número ímpar de
a
's no início, que não é seguido por maisa
' s, você pode usar:Isso permite que você use coisas como
.*
livremente e, se houver uma correspondência óbvia, não haverá outra possibilidade de corresponder a muitos ou poucos caracteres, o que pode quebrar seu padrão.No regex do .NET (que não possui quantificadores possessivos), você pode usá-lo para exibir o grupo 1 o maior múltiplo de três (com no máximo 30) vezes (sem jogar muito bem):
fonte
Esqueça um grupo capturado após uma subexpressão (PCRE)
Para esta regex:
Se você deseja limpar o \ 2 após o grupo 1, poderá usar a recursão:
Ele corresponderá
aa
enquanto o anterior não. Às vezes você também pode usar??
ou mesmo?
no lugar de{0}
.Isso pode ser útil se você tiver usado muitas recursões e algumas das referências anteriores ou grupos condicionais aparecerem em locais diferentes no seu regex.
Observe também que grupos atômicos são assumidos para recursões no PCRE. Portanto, isso não corresponde a uma única letra
a
:Ainda não experimentei em outros sabores.
Para lookaheads, você também pode usar negativos duplos para esta finalidade:
fonte
Expressões opcionais
Às vezes é útil lembrar que
é basicamente o mesmo que
Porém, há uma pequena diferença: no primeiro caso, o grupo captura
abc
ou não captura. O último caso faria com que uma referência anterior falhasse incondicionalmente. Na segunda expressão, o grupo capturaráabc
ou uma sequência vazia, onde o último caso faria uma correspondência de referência anterior incondicionalmente. Para emular o último comportamento,?
você precisará cercar tudo em outro grupo que custaria dois bytes:A versão usando
|
também é útil quando você deseja agrupar a expressão em alguma outra forma de grupo e não se importa com a captura:Por fim, esse truque também pode ser aplicado a ungreedy,
?
onde ele salva um byte mesmo em sua forma bruta (e consequentemente 3 bytes quando combinado com outras formas de grupos):fonte
Vários lookaheads que sempre correspondem (.NET)
Se você tiver três ou mais construções de lookahead que sempre correspondem (para capturar subexpressões) ou se houver um quantificador em um lookahead seguido por outra coisa, eles devem estar em um grupo não necessariamente capturado:
Estes são mais curtos:
onde
a
não deve ser o nome de um grupo capturado. Você não pode usar o|
significado usualb
ec
sem adicionar outro par parênteses.Infelizmente, os grupos de equilíbrio nas condicionais pareciam bugs, tornando-os inúteis em muitos casos.
fonte