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

_{Esta é a segunda parte de uma série de artigos educacionais de regex. Ele mostra como lookaheads e referências aninhadas podem ser usadas para corresponder ao idioma não regular a ⁿ b ⁿ . As referências aninhadas são introduzidas pela primeira vez em: Como este regex encontra números triangulares?}

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

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

Este é o idioma de todas as strings não vazias, consistindo em algum número de a's seguido por um número igual de b' s. Exemplos de cordas nesta língua são ab, aabb, aaabbb.

Essa linguagem pode ser demonstrada como não regular pelo lema do bombeamento . É na verdade uma linguagem livre de contexto arquetípica , que pode ser gerada pela gramática livre de contexto 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. PCRE e Perl oferecem suporte a regex recursivo e .NET oferece suporte à definição de grupos de balanceamento. Mesmo recursos menos "sofisticados", por exemplo, correspondência de referência anterior, significa que regex não é regular.

Mas quão poderosos são esses recursos "básicos"? Podemos reconhecer Lcom Java regex, por exemplo? Talvez possamos combinar lookarounds e referências aninhadas e ter um padrão que funciona com por exemplo, String.matchespara coincidir com cordas 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 equilíbrio
• pcre.org - página de manual do PCRE
• regular-expressions.info - Lookarounds e Grouping and Backreferences
• java.util.regex.Pattern

Questões vinculadas

• A aparência afeta quais idiomas podem ser correspondidos por expressões regulares?
• Grupos de balanceamento .NET Regex vs padrões recursivos PCRE

A resposta é, desnecessário dizer, SIM! Você pode certamente escrever um padrão regex Java para corresponder a ⁿ b ⁿ . Ele usa um lookahead positivo para asserção e uma referência aninhada para "contagem".

Em vez de fornecer imediatamente o padrão, essa resposta guiará os leitores durante o processo de derivá-lo. Várias dicas são fornecidas conforme a solução é construída lentamente. Nesse aspecto, espero que esta resposta contenha muito mais do que apenas outro padrão regex puro. Esperançosamente, os leitores também aprenderão como "pensar em regex" e como colocar várias construções harmoniosamente juntas, para que possam derivar mais padrões por conta própria no futuro.

A linguagem utilizada para desenvolver a solução será o PHP pela sua concisão. O teste final assim que o padrão for finalizado será feito em Java.

Etapa 1: Antecipar a afirmação

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

Aqui está 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);

O resultado é ( conforme 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: correspondemos a+, apenas se estiver no início da string e apenas se for imediatamente seguida por b+.

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

Etapa 2: captura à frente (e modo de espaçamento livre)

Agora, digamos que, embora não desejemos que o b+seja parte da correspondência, queremos capturá- lo de qualquer maneira no grupo 1. Além disso, como prevemos ter um padrão mais complicado, vamos usar o xmodificador para espaçamento livre para que possamos pode tornar nosso regex mais legível.

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

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

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

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

Observe que, por exemplo, aaa|bé o resultado de join-ing com o que cada grupo capturou '|'. Nesse caso, o grupo 0 (ou seja, o que o padrão correspondeu) capturou aaae o grupo 1 capturou b.

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

Etapa 3: Refatorando o lookahead no "loop"

Antes de introduzirmos 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 nós apenas queríamos afirmar que existe um b+seguinte nosso a+, mas o que realmente queremos fazer é afirmar que para cada um aque combinamos dentro do "loop", há um correspondente bpara acompanhar.

Não vamos nos preocupar com o mecanismo de contagem por enquanto e apenas fazer a refatoração da seguinte maneira:

• Primeiro refatorar a+para (?: a )+(observe que (?:…)é um grupo de não captura)
• Em seguida, mova o lookahead dentro deste grupo de não captura
  • Observe que agora devemos "pular" a*antes que possamos "ver" o b+, então modifique o padrão de acordo

Portanto, agora temos o seguinte:

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

A saída é a mesma de antes ( conforme visto em ideone.com ), portanto, não há alteração nesse sentido. O importante é que agora estamos fazendo a afirmação a cada 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 sem captura. Lookarounds podem ser repetidos.

Etapa 4: esta é a etapa em que começamos a contar

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

• No final da primeira iteração do +, quando a primeira afor correspondida, ele deve capturarb
• No final da segunda iteração, quando outra aé correspondida, ela deve capturarbb
• No final da terceira iteração, ele deve capturar bbb
• ...
• No final do n iteração -ésima, grupo 1 deve captar b ⁿ
• Se não houver o suficiente bpara capturar no grupo 1, a afirmação simplesmente falha

Portanto, o grupo 1, que é agora (b+), terá que ser reescrito para algo como (\1 b). Ou seja, tentamos "adicionar" a bao que o grupo 1 capturou na iteração anterior.

Há um pequeno problema aqui, pois esse padrão não tem o "caso base", ou seja, o caso em que pode corresponder sem a auto-referência. Um caso base é necessário porque o grupo 1 começa "não inicializado"; ele ainda não capturou nada (nem mesmo uma string vazia), portanto, uma tentativa de auto-referência sempre falhará.

Há muitas maneiras de contornar isso, mas por enquanto vamos apenas tornar opcional a correspondência de auto-referência , ou seja \1?. Isso pode ou não funcionar perfeitamente, mas vamos ver o que faz e, se houver algum problema, cruzaremos a ponte quando chegarmos a esse ponto. Além disso, adicionaremos mais alguns casos de teste enquanto estamos 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 ( conforme 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 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á programas suficientes be, de alguma forma, contou errado! Examinaremos por que isso aconteceu na próxima etapa.

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

Etapa 4½: Entender o que deu errado

O problema é que, como tornamos a correspondência de auto-referência opcional, o "contador" pode "zerar" de volta para 0 quando não houver bo suficiente . Vamos examinar de perto o que acontece em cada iteração de nosso padrão aaaaabbbcomo 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 4ª iteração, ainda podíamos combinar \1, mas não poderíamos \1b! Como permitimos que a correspondência de auto-referência seja opcional com \1?, o motor retrocede e escolhe a opção "não, obrigado", que nos permite corresponder e capturar apenas b!

Observe, entretanto, que, exceto na primeira iteração, você sempre poderá corresponder apenas à autorreferência \1. Isso é óbvio, é claro, uma vez que é o que acabamos de capturar em nossa iteração anterior, e em nossa configuração podemos sempre combiná-lo novamente (por exemplo, se capturamos da bbbúltima vez, temos a garantia de que ainda haverá bbb, mas pode ou pode não ser bbbbdesta vez).

Lição : cuidado com o retrocesso. O mecanismo de 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.

Etapa 5: Autodomínio para o resgate!

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

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

?+

• (opcional) "Não precisa estar lá,"
  • (possessivo) "mas se estiver aí, você deve pegar e não largar!"

?

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

??

• (opcional) "Não precisa estar lá,"
  • (relutante) "e mesmo que seja, você não precisa tomar ainda,"
    • (retrocedendo) "mas pode ser solicitado que você faça isso mais tarde!"

Em nossa configuração, \1não estará lá na primeira vez, mas sempre estará lá a qualquer momento depois disso, e sempre queremos corresponder a isso. Assim, \1?+realizaríamos exatamente o que desejamos.

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

Agora, a saída é ( conforme 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ção gananciosa, relutante e possessiva. Possessão opcional pode ser uma combinação poderosa.

Etapa 6: toques finais

Portanto, o que temos agora é um padrão que corresponde arepetidamente e para cada aque foi correspondido, há um correspondente bcapturado no grupo 1. O +termina quando não há mais a, ou se a declaração falhou porque não há um correspondente bpara um a.

Para terminar o trabalho, simplesmente precisamos anexar ao nosso padrão \1 $. Esta é agora uma referência anterior ao que o grupo 1 correspondeu, seguido pelo fim da âncora de linha. A âncora garante que não haja nenhum extra bna string; em outras palavras, que de fato temos a ⁿ b ⁿ .

Este é 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 jogos ab, aabb, aaabbbea um ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Leva apenas 0,06s para ser executado em ideone.com .

Etapa 7: o teste de 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 conforme o esperado ( conforme visto em ideone.com ).

E agora chegamos à conclusão ...

É preciso dizer que o a* lookahead e, na verdade, o " +loop principal ", permitem 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 quantificador possessivo obrigatório e não obrigatório no mesmo padrão possa levar a interpretações errôneas).

Também deve ser dito que, embora seja legal, há um padrão regex que corresponderá a ⁿ b ⁿ , essa nem sempre é a "melhor" solução na prática. Uma solução muito melhor é simplesmente corresponder^(a+)(b+)$e, em seguida, comparar o comprimento das strings capturadas pelos grupos 1 e 2 na linguagem de programação de hospedagem.

Em PHP, pode ser parecido com 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 regex pode fazer quase tudo; claramente não pode, e mesmo para as coisas que pode fazer, pelo menos a delegação parcial para a linguagem de hospedagem deve ser considerada se levar a uma solução mais simples.

Conforme mencionado no início, embora este artigo seja necessariamente marcado [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 alguém 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 bônus! Padrão recursivo PCRE!

Uma vez que trouxemos o PHP, é preciso dizer que PCRE oferece suporte a padrões recursivos e sub-rotinas. Assim, o seguinte padrão funciona para preg_match( como visto em ideone.com ):

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

Atualmente o regex do Java não oferece suporte a padrão recursivo.

Ainda mais material de bônus! Correspondendo a ⁿ b ⁿ c ⁿ !!

Então, vimos como combinar a ⁿ b ⁿ que não é regular, mas ainda livre de contexto, mas também podemos combinar a ⁿ b ⁿ c ⁿ , que 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 ao PCRE que suporta padrões recursivos, gostaria apenas de apontar o exemplo mais simples e eficiente de PCRE que descreve a linguagem em questão:

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

Conforme mencionado na pergunta - com o grupo de balanceamento .NET, os padrões do tipo a ⁿ b ⁿ c ⁿ d ⁿ ... z ⁿ podem ser combinados facilmente como

^
  (?<A>a)+
  (?<B-A>b)+  (?(A)(?!))
  (?<C-B>c)+  (?(B)(?!))
  ...
  (?<Z-Y>z)+  (?(Y)(?!))
$

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

Editar:

Também existe um padrão PCRE para a linguagem generalizada com padrão recursivo, mas é necessária uma verificação à frente. 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