ti-enxame.com

Como podemos combinar a ^ n b ^ n com Java regex?

Esta é a segunda parte de uma série de artigos sobre regex educacional. Ele mostra como lookaheads e referências aninhadas podem ser usadas para corresponder ao idioma não regularnbn. As referências aninhadas são introduzidas pela primeira vez em: Como esse regex encontra números triangulares?

Um dos não arquetípicos - idiomas regulares é:

L = { anbn: n > 0 }

Esse é o idioma de todas as strings não vazias que consistem em um número de a 's seguido por um número igual de b' s. Exemplos de strings nesse idioma são ab, aabb, aaabbb.

Pode-se mostrar que esse idioma não é regular pelo lema de bombeamento . Na verdade, é um arquetípico linguagem livre de contexto , que pode ser gerado pela gramática livre de contextoS → aSb | ab.

No entanto, as implementações modernas de expressões regulares reconhecem claramente mais do que apenas idiomas comuns. Ou seja, eles não são "regulares" por definição formal da teoria da linguagem. O PCRE e o Perl suportam regex recursivo e o .NET suporta a definição de grupos de balanceamento. Recursos menos sofisticados, por exemplo, p. correspondência de referência anterior, significa que a regex não é regular.

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

Referências

Perguntas vinculadas

95
polygenelubricants

A resposta é, escusado será dizer, SIM ! Você certamente pode escrever um Java para corresponder anbn. Ele usa um lookahead positivo para asserção e uma referência aninhada para "contagem".

Em vez de fornecer imediatamente o padrão, esta resposta guiará os leitores através de o processo de derivá-lo. Várias dicas são dadas quando a solução é construída lentamente. Nesse aspecto, espero que essa resposta contenha muito mais do que apenas outro padrão de regex puro. Esperamos que os leitores também aprendam como "pensar em regex" e como reunir várias construções de maneira harmoniosa, para que possam derivar mais padrões por conta própria no futuro.

A linguagem usada para desenvolver a solução será PHP por sua concisão. O teste final após a finalização do padrão será realizado em Java.


Etapa 1: Lookahead para asserção

Vamos começar com um problema mais simples: queremos combinar a+ No início de uma string, mas apenas se for seguido imediatamente por b+. Podemos usar ^ Para anchor nossa correspondência e, como queremos combinar apenas a+ Sem o b+, Podemos usar lookahead afirmação (?=…).

Aqui está o nosso padrão com um equipamento 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+, Apenas se estiver no início da string e somente se for imediatamente seguido por b+.

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


Etapa 2: Capturando em um lookahead (e nos modos a p e c a n iç ã o)

Agora, digamos que, embora não desejemos que o b+ Faça parte da partida, queremos capturar de qualquer maneira no grupo 1. Além disso, como prevemos ter um Para 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 anterior PHP, 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

Observe que p. aaa|b É o resultado de join- o que cada grupo capturou com '|'. Nesse caso, o grupo 0 (ou seja, qual o padrão correspondente) capturou aaa e o grupo 1 capturou b.

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


Etapa 3: Refatorar a cabeça de impressão 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á bom até agora, porque queríamos apenas afirmar que há um b+ Seguindo nosso a+, Mas o que nós realmente queremos fazer eventualmente é afirmar que, para cada a que combinamos dentro do "loop", existe um b correspondente.

Não vamos nos preocupar com o mecanismo de contagem no momento e apenas refatorando da seguinte maneira:

  • Primeiro refatorar a+ Para (?: a )+ (Observe que (?:…) É um grupo que não captura)
  • Em seguida, mova a cabeça de impressão para dentro desse grupo que não captura.
    • Observe que agora precisamos "pular" a* Antes de podermos "ver" o b+, Portanto, modifique o padrão adequadamente

Portanto, agora temos o seguinte:

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

A saída é a mesma de antes ( como visto em ideone.com ), portanto não há mudanças nesse sentido. O importante é que agora estamos fazendo a afirmação em toda iteração do + "Loop". Com nosso padrão atual, isso não é necessário, mas a seguir faremos o grupo 1 "contar" para nós usando a auto-referência.

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


Etapa 4: este é o passo em que começamos a contar

Aqui está o que vamos fazer: reescreveremos o grupo 1 de modo que:

  • No final da primeira iteração do +, Quando o primeiro a for correspondido, ele deverá capturar b
  • No final da segunda iteração, quando outro a for correspondido, ele deverá capturar bb
  • No final da terceira iteração, ele deve capturar bbb
  • ...
  • No final da n - a iteração, o grupo 1 deve capturar bn
  • Se não houver b suficiente para capturar no grupo 1, a asserção simplesmente falha

Portanto, 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, pois esse padrão está ausente no "caso base", ou seja, no caso em que ele pode corresponder sem a auto-referência. Um caso base é necessário porque o grupo 1 começa "não inicializado"; ainda não capturou nada (nem mesmo uma sequência vazia), portanto, uma tentativa de auto-referência sempre falha.

Há muitas maneiras de contornar isso, mas por enquanto vamos apenas fazer a correspondência de auto-referência opcional , ou seja, \1?. Isso pode ou não funcionar perfeitamente, mas vamos apenas ver o que isso faz e, se houver algum problema, atravessaremos a ponte quando chegarmos a ela. Além disso, adicionaremos mais 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 próximos da solução agora! Conseguimos fazer o grupo 1 "contar" usando a auto-referência! Mas espere ... algo está errado com o segundo e o último caso de teste !! Não há bs suficientes e, de alguma forma, isso contou errado! Examinaremos por que isso aconteceu na próxima etapa.

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


Etapa 4½: Entendendo o que deu errado

O problema é que, como tornamos a correspondência de auto-referência opcional, o "contador" pode "redefinir" de volta para 0 quando não há b 's suficientes. Vamos examinar atentamente o que acontece a cada iteração do nosso padrão com aaaaabbb como entrada.

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

A-ha! Em nossa quarta iteração, ainda poderíamos combinar \1, Mas não poderíamos combinar \1b! Como permitimos que a correspondência de auto-referência seja opcional com \1?, O mecanismo retrocede e pega a opção "no thanks", que permite combinar e capturar apenas b!

Observe, no entanto, que, exceto na primeira iteração, você sempre pode 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 correspondê-lo novamente (por exemplo, se capturamos bbb da última vez, temos a garantia de que ainda haverá pode ser bbb, mas pode ou não haver bbbb desta vez).

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


Passo 5: Auto-posse para o resgate!

A "correção" agora deve ser óbvia: combine repetição opcional com possessivo quantificador. Ou seja, em vez de simplesmente ?, Use ?+ (Lembre-se de que uma repetição quantificada como possessiva não retrocede, mesmo que essa "cooperação" possa resultar em uma correspondência do padrão geral ).

Em termos muito informais, é isso que ?+, ? E ?? Dizem:

?+

  • (opcional) "Não precisa estar lá",
    • (possessivo) "mas se estiver lá, você deve pegá-lo e não deixar ir!"

?

  • (opcional) "Não precisa estar lá",
    • (ganancioso) "mas se for, você pode aguentar por enquanto",
      • (retrocedendo) "mas pode ser solicitado que você solte mais tarde!"

??

  • (opcional) "Não precisa estar lá",
    • (relutante) "e, mesmo que seja, você não precisa tomá-lo ainda",
      • (retrocedendo) "mas você pode ser solicitado a levá-lo mais tarde!"

Em nossa configuração, \1 Não estará presente na primeira vez, mas estará sempre estará presente a qualquer momento depois disso, e nós sempre = deseja combiná-lo então. 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 da maneira que queremos!

Lição: Aprenda a diferença entre repetições gananciosas, relutantes e possessivas. Opcional-possessivo pode ser uma combinação poderosa.


Etapa 6: retoques finais

Portanto, o que temos agora é um padrão que corresponde a a repetidamente, e para cada a que correspondeu, existe 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 concluir o trabalho, basta anexar ao nosso padrão \1 $. Agora, essa é uma referência anterior ao grupo 1 que correspondeu, seguido pelo final da âncora da linha. A âncora garante que não haja b 'extras na string; em outras palavras, que de fato temos umnbn.

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

Ele encontra 4 correspondências: ab, aabb, aaabbb e o a5000b5000. Demora apenas 0,06s para rodar em ideone.com .


Etapa 7: o teste Java

Portanto, o padrão funciona em PHP, mas o objetivo 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* No lookahead e, de fato, o "loop principal +", Ambos permitem retroceder. 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 quantificador possessivo obrigatório e não obrigatório no mesmo padrão possa levar a percepções errôneas).

Também deve-se dizer que, embora seja elegante, há um padrão de expressão regular que corresponderá a anbn, essa nem sempre é a "melhor" solução na prática. Uma solução muito melhor é simplesmente combinar ^(a+)(b+)$ e comparar o comprimento das seqüências capturadas pelos grupos 1 e 2 na linguagem de programação de hospedagem.

No PHP, pode ser algo como isto ( como visto em ideone.com ):

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

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

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


Material bônus! Padrão recursivo PCRE!

Desde que criamos o PHP, é preciso dizer que o PCRE suporta padrões e sub-rotinas recursivas. Assim, o seguinte padrão funciona para preg_match ( como visto em ideone.com ):

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

Atualmente, a regex de Java não suporta padrão recursivo.


Ainda mais material bônus! Correspondência anbncn !!

Então, vimos como combinar umnbn que não é regular, mas ainda sem contexto, mas também podemos corresponder anbncn, que nem sequer é livre de contexto?

A resposta é, é claro, SIM ! Os leitores são incentivados a tentar resolver isso sozinhos, mas a solução é fornecida abaixo (com implementação em Java no ideone.com ).

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

136
polygenelubricants

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

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

Conforme mencionado na pergunta - com o grupo de balanceamento .NET, os padrões do tipo anbncndn… Zn pode ser correspondido facilmente como

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>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ário um lookahead. Não acho que seja uma tradução direta do que foi dito acima.

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

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

11
kennytm