Como podemos combinar um ^ nb ^ n com o Java regex?

Esta é a segunda parte de uma série de artigos de regex educacionais. Ela mostra como lookaheads e referências aninhadas podem ser usadas para combinar com o idioma não regular a n b n . As referências aninhadas são introduzidas pela primeira vez em: Como esta regex encontra números triangulares?

Uma das linguagens não regulares arquetípicas é:

L = { a n b n : n > 0 }

Esta é a linguagem de todas as cadeias não vazias que consistem em alguns números de a seguidos por um número igual de b . Exemplos de strings nessa linguagem são ab , aabb , aaabbb .

Esta linguagem pode ser mostrada como não regular pelo lema do bombeamento . É de fato uma linguagem arquetípica livre de contexto , que pode ser gerada pela gramática livre de contexto S → aSb | ab S → aSb | ab .

No entanto, as implementações de regex modernas reconhecem claramente mais do que apenas linguagens regulares. Ou seja, eles não são “regulares” pela definição formal da teoria da linguagem. O PCRE e o Perl suportam o regex recursivo, e o .NET suporta a definição de grupos de equilíbrio. Mesmo características menos “extravagantes”, por exemplo, correspondência de retro-referência, significam que a regex não é regular.

Mas quão poderosos são esses resources “básicos”? Podemos reconhecer L com regex Java, por exemplo? Podemos talvez combinar lookarounds e referências aninhadas e ter um padrão que funcione com eg String.matches para combinar strings como ab , aabb , aaabbb , etc?

Referências

  • perlfaq6: Posso usar expressões regulares Perl para corresponder ao texto balanceado?
  • MSDN – Elementos de linguagem de expressão regular – Definições de grupo de balanceamento
  • pcre.org – página de manual do PCRE
  • regular-expressions.info – Lookarounds e Agrupamento e Backreferences
  • java.util.regex.Pattern

Perguntas vinculadas

  • A aparência afeta quais idiomas podem ser correspondidos por expressões regulares?
  • Grupos Regulares de Balanceamento .NET Regex vs Padrões Recursivos PCRE

A resposta é, desnecessário dizer, sim! Você pode certamente escrever um padrão de regex Java para corresponder a um n b n . Ele usa uma antecipação positiva para asserção e uma referência aninhada para “contagem”.

Em vez de dar imediatamente o padrão, essa resposta guiará os leitores pelo processo de derivação. Várias dicas são dadas como a solução é construída lentamente. Neste aspecto, espero que esta resposta contenha muito mais do que apenas outro padrão regular de regex. Espero que os leitores também aprendam como “pensar em regex” e como colocar vários construtos harmoniosamente juntos, para que possam derivar mais padrões sozinhos no futuro.

A linguagem usada para desenvolver a solução será PHP por sua concisão. O teste final, uma vez finalizado o padrão, será feito em Java.


Passo 1: Lookahead para afirmação

Vamos começar com um problema mais simples: queremos combinar a+ no início de uma string, mas somente se for seguido imediatamente por b+ . Podemos usar ^ para ancorar a nossa correspondência e, como só queremos corresponder ao a+ sem o b+ , podemos usar a asserção lookahead (?=…) .

Aqui está o nosso padrão com um arnês de teste simples:

 function testAll($r, $tests) { foreach ($tests as $test) { $isMatch = preg_match($r, $test, $groups); $groupsJoined = join('|', $groups); print("$test $isMatch $groupsJoined\n"); } } $tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb'); $r1 = '/^a+(?=b+)/'; # └────┘ # lookahead testAll($r1, $tests); 

A saída é ( como visto em ideone.com ):

 aaa 0 aaab 1 aaa aaaxb 0 xaaab 0 b 0 abbb 1 a 

Esta é exatamente a saída que queremos: combinamos a+ , somente se estiver no início da string, e somente se for imediatamente seguido por b+ .

Lição : Você pode usar padrões em lookarounds para fazer asserções.


Etapa 2: Capturando em um lookahead (e no modo de espaçamento livre)

Agora digamos que, embora não queiramos que o b+ parte do jogo, queremos capturá- lo de qualquer maneira no grupo 1. Além disso, como esperamos ter um padrão mais complicado, vamos usar o modificador x para espaçamento livre. para que possamos tornar nosso regex mais legível.

Com base no nosso snippet PHP anterior, agora temos o seguinte padrão:

 $r2 = '/ ^ a+ (?= (b+) ) /x'; # │ └──┘ │ # │ 1 │ # └────────┘ # lookahead testAll($r2, $tests); 

A saída é agora ( como visto em ideone.com ):

 aaa 0 aaab 1 aaa|b aaaxb 0 xaaab 0 b 0 abbb 1 a|bbb 

Note que, por exemplo, aaa|b é o resultado de join que cada grupo capturou com '|' . Neste caso, o grupo 0 (isto é, o que corresponde ao padrão) capturou aaa e o grupo 1 capturou b .

Lição : Você pode capturar dentro de um lookaround. Você pode usar o espaçamento livre para melhorar a legibilidade.


Etapa 3: Refatorando o lookahead no “loop”

Antes de podermos introduzir nosso mecanismo de contagem, precisamos fazer uma modificação em nosso padrão. Atualmente, o lookahead está fora do “loop” de repetição. Isso está bem até agora porque nós apenas queríamos afirmar que há um b+ seguindo o nosso a+ , mas o que realmente queremos fazer é afirmar que para cada a que combinamos dentro do “loop”, há um b correspondente para ele .

Não nos preocupemos com o mecanismo de contagem por enquanto e façamos a refatoração da seguinte forma:

  • Primeiro refator a+ para (?: a )+ (note que (?:…) É um grupo que não captura)
  • Em seguida, mova o lookahead dentro desse grupo que não captura
    • Note que agora devemos “pular” a* antes que possamos “ver” o b+ , então modifique o padrão de acordo

Então agora temos o seguinte:

 $r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x'; # │ │ └──┘ │ │ # │ │ 1 │ │ # │ └───────────┘ │ # │ lookahead │ # └───────────────────┘ # non-capturing group 

A saída é a mesma de antes ( como visto no ideone.com ), então não há mudanças nesse sentido. O importante é que agora estamos fazendo a afirmação em cada iteração do “loop”. Com o nosso padrão atual, isso não é necessário, mas em seguida faremos o grupo 1 “count” para nós usando auto-referência.

Lição : Você pode capturar dentro de um grupo sem captura. Lookarounds podem ser repetidos.


Passo 4: Este é o passo em que começamos a contar

Aqui está o que vamos fazer: vamos rewrite o grupo 1 de tal forma que:

  • No final da primeira iteração do + , quando o primeiro a é correspondido, ele deve capturar b
  • No final da segunda iteração, quando outro é combinado, ele deve capturar bb
  • No final da terceira iteração, ele deve capturar bbb
  • No final da n- ésima iteração, o grupo 1 deve capturar b n
  • Se não houver b suficiente para capturar no grupo 1, a afirmação simplesmente falhará

Então, o grupo 1, que agora é (b+) , terá que ser reescrito para algo como (\1 b) . Ou seja, tentamos “adicionar” a b ao grupo 1 capturado na iteração anterior.

Há um pequeno problema aqui em que este padrão está faltando o “caso base”, ou seja, o caso em que ele pode coincidir sem a auto-referência. Um caso base é necessário porque o grupo 1 inicia “não inicializado”; não capturou nada ainda (nem mesmo uma string vazia), então uma tentativa de auto-referência sempre falhará.

Há muitas maneiras de contornar isso, mas, por enquanto, vamos apenas tornar a auto-referência correspondente opcional , ou seja, \1? . Isso pode ou não funcionar perfeitamente, mas vamos ver o que isso faz, e se houver algum problema, então atravessaremos essa ponte quando chegarmos a ela. Além disso, adicionaremos mais alguns casos de teste enquanto estivermos nisso.

 $tests = array( 'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb' ); $r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x'; # │ │ └─────┘ | │ # │ │ 1 | │ # │ └──────────────┘ │ # │ lookahead │ # └──────────────────────┘ # non-capturing group 

A saída é agora ( como visto em ideone.com ):

 aaa 0 aaab 1 aaa|b # (*gasp!*) aaaxb 0 xaaab 0 b 0 abbb 1 a|b # yes! aabb 1 aa|bb # YES!! aaabbbbb 1 aaa|bbb # YESS!!! aaaaabbb 1 aaaaa|bb # NOOOOOoooooo.... 

A-ha! Parece que estamos realmente perto da solução agora! Conseguimos fazer com que o grupo 1 “contasse” usando auto-referência! Mas espere … algo está errado com o segundo e último teste! Não há bs suficientes e, de alguma forma, isso conta errado! Vamos examinar por que isso aconteceu na próxima etapa.

Lição : Uma maneira de “inicializar” um grupo de auto-referência é tornar a correspondência de auto-referência opcional.


Etapa 4½: Entendendo o que deu errado

O problema é que, como fizemos a correspondência de auto-referência opcional, o “contador” pode “redefinir” de volta para 0 quando não há bs suficientes. Vamos examinar atentamente o que acontece em cada iteração do nosso padrão com aaaaabbb como input.

  aaaaabbb ↑ # Initial state: Group 1 is "uninitialized". _ aaaaabbb ↑ # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized", # so it matched and captured just b ___ aaaaabbb ↑ # 2nd iteration: Group 1 matched \1b and captured bb _____ aaaaabbb ↑ # 3rd iteration: Group 1 matched \1b and captured bbb _ aaaaabbb ↑ # 4th iteration: Group 1 could still match \1, but not \1b, # (!!!) so it matched and captured just b ___ aaaaabbb ↑ # 5th iteration: Group 1 matched \1b and captured bb # # No more a, + "loop" terminates 

A-ha! Na nossa quarta iteração, ainda poderíamos igualar \1 , mas não conseguimos igualar \1b ! Já que permitimos que a correspondência de auto-referência seja opcional com \1? , o motor recua e levou a opção “não, obrigado”, que então nos permite combinar e capturar apenas b !

Observe, no entanto, que, exceto na primeira iteração, você poderia sempre corresponder apenas à auto-referência \1 . Isso é óbvio, claro, já que é o que acabamos de capturar em nossa iteração anterior e, em nossa configuração, sempre podemos fazer a correspondência novamente (por exemplo, se capturamos bbb última vez, garantimos que ainda haverá bbb , mas pode ou não ser bbbb desta vez).

Lição : Cuidado com o retrocesso. O mecanismo regex fará tanto retrocesso quanto você permitir até que o padrão fornecido corresponda. Isso pode afetar o desempenho (ou seja, retrocesso catastrófico ) e / ou correção.


Passo 5: Auto-possession para o resgate!

A “correção” agora deve ser óbvia: combine a repetição opcional com o quantificador possessivo . Isto é, em vez de simplesmente ? , use ?+ vez disso (lembre-se de que uma repetição quantificada como possessiva não recua, mesmo que essa “cooperação” possa resultar em uma correspondência com o padrão geral).

Em termos muito informais, isso é o que ? e ?? diz:

?+

  • (opcional) “Não precisa estar lá”
    • (possessivo) “mas se estiver lá, você deve pegar e não soltar!”

?

  • (opcional) “Não precisa estar lá”
    • (ganancioso) “mas se é que você pode tomar por agora”
      • (retrocesso) “mas você pode ser solicitado a deixar isso para depois!”

??

  • (opcional) “Não precisa estar lá”
    • (relutante) “e mesmo que seja você não tem que fazer isso ainda”
      • (backtracking) “mas você pode ser convidado a levá-lo mais tarde!”

Em nossa configuração, \1 não estará lá na primeira vez, mas sempre estará lá a qualquer momento depois disso e sempre queremos combiná-lo. Assim, \1?+ Realizaria exatamente o que queremos.

 $r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x'; # │ │ └──────┘ │ │ # │ │ 1 │ │ # │ └───────────────┘ │ # │ lookahead │ # └───────────────────────┘ # non-capturing group 

Agora a saída é ( como visto em ideone.com ):

 aaa 0 aaab 1 a|b # Yay! Fixed! aaaxb 0 xaaab 0 b 0 abbb 1 a|b aabb 1 aa|bb aaabbbbb 1 aaa|bbb aaaaabbb 1 aaa|bbb # Hurrahh!!! 

Voilà !!! Problema resolvido!!! Agora estamos contando corretamente, exatamente do jeito que queremos!

Lição : Aprenda a diferença entre a repetição gananciosa, relutante e possessiva. Opcional-possessivo pode ser uma combinação poderosa.


Etapa 6: toques finais

Então, o que temos agora é um padrão que corresponde a a repetidamente, e para cada a que foi correspondido, há um b correspondente capturado no grupo 1. O + termina quando não há mais a , ou se a afirmação falhou porque não há é um b correspondente para um a .

Para terminar o trabalho, basta acrescentar ao nosso padrão \1 $ . Agora, essa é uma referência anterior ao grupo 1, seguido do final da âncora de linha. A âncora garante que não haja nenhum b extra na corda; em outras palavras, que na verdade nós temos um n b n .

Aqui está o padrão finalizado, com casos de teste adicionais, incluindo um com 10.000 caracteres:

 $tests = array( 'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb', '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc', str_repeat('a', 5000).str_repeat('b', 5000) ); $r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x'; # │ │ └──────┘ │ │ # │ │ 1 │ │ # │ └───────────────┘ │ # │ lookahead │ # └───────────────────────┘ # non-capturing group 

Encontra 4 correspondências: ab , aabb , aaabbb e a 5000 b 5000 . São necessários apenas 0.06s para serem executados no ideone.com .


Etapa 7: o teste de Java

Então o padrão funciona em PHP, mas o objective final é escrever um padrão que funcione em Java.

 public static void main(String[] args) { String aNbN = "(?x) (?: a (?= a* (\\1?+ b)) )+ \\1"; String[] tests = { "", // false "ab", // true "abb", // false "aab", // false "aabb", // true "abab", // false "abc", // false repeat('a', 5000) + repeat('b', 4999), // false repeat('a', 5000) + repeat('b', 5000), // true repeat('a', 5000) + repeat('b', 5001), // false }; for (String test : tests) { System.out.printf("[%s]%n %s%n%n", test, test.matches(aNbN)); } } static String repeat(char ch, int n) { return new String(new char[n]).replace('\0', ch); } 

O padrão funciona como esperado ( como visto em ideone.com ).


E agora chegamos à conclusão …

É preciso dizer que o a* em antecipação e, de fato, o “main + loop”, ambos permitem o retrocesso. Os leitores são encorajados a confirmar por que isso não é um problema em termos de correção, e por que ao mesmo tempo tornar ambos possessivos também funcionaria (embora talvez misturar quantificadores possessivos obrigatórios e não obrigatórios no mesmo padrão possa levar a equívocos).

Também deve ser dito que, embora seja legal que haja um padrão de regex que corresponda a um n b n , essa nem sempre é a “melhor” solução na prática. Uma solução muito melhor é simplesmente combinar ^(a+)(b+)$ e, em seguida, comparar o comprimento das seqüências de caracteres capturadas pelos grupos 1 e 2 na linguagem de programação de hospedagem.

No PHP, pode parecer algo assim ( como visto em ideone.com ):

 function is_anbn($s) { return (preg_match('/^(a+)(b+)$/', $s, $groups)) && (strlen($groups[1]) == strlen($groups[2])); } 

O objective deste artigo não é convencer os leitores de que o regex pode fazer quase qualquer coisa; claramente, não pode, e até mesmo para as coisas que pode fazer, pelo menos a delegação parcial para o idioma de hospedagem deve ser considerada se levar a uma solução mais simples.

Como mencionado na parte superior, embora este artigo seja necessariamente marcado como [regex] para stackoverflow, talvez seja mais do que isso. Embora certamente haja valor em aprender sobre asserções, referências aninhadas, quantificador possessivo, etc, talvez a maior lição aqui seja o processo criativo pelo qual se pode tentar resolver problemas, a determinação e o trabalho árduo que muitas vezes requer quando você está sujeito a várias restrições, a composição sistemática de várias partes para construir uma solução de trabalho, etc.


Material de bônus! Padrão recursivo PCRE!

Desde que trouxemos o PHP, é necessário dizer que o PCRE suporta padrões e sub-rotinas recursivas. Assim, seguindo o padrão funciona para preg_match ( como visto em ideone.com ):

 $rRecursive = '/ ^ (a (?1)? b) $ /x'; 

Atualmente, o regex do Java não suporta padrão recursivo.


Ainda mais material bônus! Correspondendo a n b n c n !!

Então, vimos como combinar um n b n que é não-regular, mas ainda sem contexto, mas podemos também corresponder a um n b n c n , que não é nem mesmo livre de contexto?

A resposta é, claro, sim! Os leitores são encorajados a tentar resolver isso por conta própria, mas a solução é fornecida abaixo (com implementação em Java em ideone.com ).

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $

Dado que nenhuma menção foi feita do PCRE suportando padrões recursivos, eu gostaria apenas de apontar o exemplo mais simples e mais eficiente do PCRE que descreve a linguagem em questão:

 /^(a(?1)?b)$/ 

Como mencionado na pergunta – com o grupo de balanceamento .NET, os padrões do tipo a n b n c n d n … z n podem ser correspondidos facilmente

 ^ (?a)+ (?b)+ (?(A)(?!)) (?c)+ (?(B)(?!)) ... (?z)+ (?(Y)(?!)) $ 

Por exemplo: http://www.ideone.com/usuOE


Editar:

Há também um padrão PCRE para a linguagem generalizada com padrão recursivo, mas é necessária uma visão antecipada. Eu não acho que isso seja uma tradução direta do acima.

 ^ (?=(a(?-1)?b)) a+ (?=(b(?-1)?c)) b+ ... (?=(x(?-1)?y)) x+ (y(?-1)?z) $ 

Por exemplo: http://www.ideone.com/9gUwF

    Intereting Posts