Come possiamo abbinare a ^ n b ^ n con Java regex?

Question

  

_{Questa è la seconda parte di una serie di articoli regex educativi. Essa mostra come lookaheads e riferimenti annidati possono essere utilizzati per abbinare il languge non regolare un ⁿ b ⁿ . riferimenti annidati vengono introdotti in: Come funziona questo regex trovare i numeri triangolari}

Una delle archetipo non linguaggi regolari è:

  

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

Questo è il linguaggio di tutte le stringhe non vuoti costituiti da un numero di a di seguito da un numero uguale di b di. Esempi di stringhe in questa lingua sono ab, aabb, aaabbb.

Questa lingua può essere spettacolo di essere non regolare da parte del pompaggio lemma . Si tratta infatti di un archetipo context-free linguaggio, che può essere generata dal grammatica context-free S → aSb | ab.

Tuttavia, le moderne implementazioni giorno regex riconoscono chiaramente più lingue solo normali. Vale a dire, non sono "regolari" dalla definizione formale teoria del linguaggio. PCRE e Perl supporta regex ricorsivo, e supporti .NET bilanciamento Definizione gruppi. Anche i meno caratteristiche "fantasia", ad esempio, backreference corrispondenza, significa che regex non è regolare.

Ma quanto sia potente è questa funzionalità "di base"? Possiamo riconoscere L con Java espressione regolare, per esempio? forse possiamo combinare lookarounds e riferimenti annidati e hanno un modello che funziona con per esempio String.matches per abbinare stringhe come ab, aabb, aaabbb, etc?

Bibliografia

• perlfaq6:? Posso usare espressioni regolari Perl per abbinare testo equilibrato
• MSDN - Regular Expression Language Elements - Balancing Group Definizioni
• pcre.org - pagina man PCRE
• regular-expressions.info - Lookarounds e Raggruppare e backreference
• java.util.regex.Pattern

questioni legate

• fa Lookaround influenzano quali lingue possono essere di pari passo con le espressioni regolari?
• .NET Regex Balancing Gruppi vs Patterns PCRE ricorsive

Answer 1

La risposta è, manco a dirlo, YES si può certamente scrivere un modello Java regex per partita un ⁿ b ⁿ . Esso utilizza un lookahead positivo per affermazione, e uno riferimento annidato per "conteggio".

Piuttosto che immediatamente dando fuori il modello, questa risposta vi guiderà lettori attraverso il processo di derivare esso. Vari suggerimenti sono dati come la soluzione è costruito lentamente. In questo aspetto, si spera questa risposta conterrà molto di più di un altro modello regex pulito. Speriamo che i lettori potranno anche imparare a "pensare in regex", e come mettere i vari costrutti insieme in armonia, in modo che possano derivare ulteriori motivi per conto proprio in futuro.

Il linguaggio utilizzato per sviluppare la soluzione sarà PHP per la sua concisione. La prova finale una volta che il modello è finalizzato sarà fatto in Java.

---

Passaggio 1: Lookahead per asserzione

La partenza di Let con un problema semplice: vogliamo abbinare a+ all'inizio di una stringa, ma solo se è seguito immediatamente da b+. Possiamo usare ^ per href="http://www.regular-expressions.info/anchors.html" la nostra partita, e dal momento che vogliamo solo per abbinare il a+ senza il b+, possiamo usare lookahead affermazione (?=…).

Ecco il nostro modello con un semplice test harness:

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);

L'uscita è ( come visto in ideone.com ):

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

Questo è esattamente l'output che vogliamo:. Abbiniamo a+, solo se è all'inizio della stringa, e solo se è immediatamente seguito da b+

Lezione :. È possibile utilizzare i modelli in lookarounds a fare asserzioni

---

Passaggio 2: Cattura in un lookahead (e f r e e - p a c i n modo g s)

Ora diciamo che, anche se non vogliamo che la b+ a far parte della partita, noi vogliamo cattura comunque in gruppo 1. Inoltre, come ci aspettiamo avere un modello più complicato, usiamo modificatore x per senza spaziatura in modo che possiamo rendere la nostra espressione regolare più leggibile.

Sulla nostra precedente frammento di codice PHP, ora abbiamo il seguente schema:

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

testAll($r2, $tests);

L'uscita è ora ( come visto in ideone.com ):

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

Si noti che per esempio aaa|b è il risultato di join-zione quanto ogni gruppo catturato con '|'. In questo caso, gruppo 0 (cioè quello del modello corrispondente) aaa b catturata, e il gruppo 1 catturati.

Lezione : È possibile acquisire all'interno di un Lookaround. È possibile utilizzare senza spaziatura per migliorare la leggibilità.

---

Fase 3: Rifattorizzare il lookahead nel "loop"

Prima di poter introdurre il nostro meccanismo di conteggio, abbiamo bisogno di fare una modifica al nostro modello. Attualmente, il lookahead è al di fuori della + ripetizione "loop". Questo va bene fino ad ora perché volevamo solo di affermare che c'è un b+ seguendo la nostra a+, ma quello che davvero vogliono fare alla fine è affermare che per ogni a che abbiniamo all'interno del "loop", c'è un b corrispondente per andare con esso.

Non preoccuparti di Let circa il meccanismo di conteggio per ora e solo fare il refactoring come segue:

• Prima refactoring a+ a (?: a )+ (nota che (?:…) è un non-gruppo di cattura)
• quindi spostare l'ins lookaheadide questo non-gruppo di cattura
  • Si noti che ora dobbiamo "saltare" a* prima di poter "vedere" il b+, in modo da modificare il modello di conseguenza

Così ora abbiamo la seguente:

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

L'uscita è la stessa di prima ( come visto in ideone.com ), quindi non c'è nessun cambiamento in quel considerare. La cosa importante è che ora stiamo facendo l'affermazione a ad ogni iterazione del "loop" +. Con la nostra attuale modello, questo non è necessario, ma la prossima faremo gruppo 1 "contano" per noi usando autoreferenzialità.

Lezione : È possibile catturare all'interno di un gruppo non-cattura. Lookarounds possono essere ripetuti.

---

Passo 4: Questa è la fase in cui iniziamo il conteggio

Ecco quello che andremo a fare: dovremo riscrivere gruppo 1 tale che:

• Al termine della prima iterazione del +, quando il primo a corrisponde, dovrebbe catturare b
• Al termine della seconda iterazione, quando un altro a è abbinato, dovrebbe catturare bb
• Al termine della terza iterazione, dovrebbe catturare bbb
• ...
• Al termine del n -esima iterazione, gruppo 1 deve acquisire b ⁿ
• Se non ci sono abbastanza b alla cattura nel gruppo 1, quindi l'asserzione non riesce semplicemente

Quindi gruppo 1, che ora è (b+), dovrà essere riscritto a qualcosa di simile (\1 b). Cioè, cerchiamo di "aggiungere" un b a quale gruppo 1 ha catturato nella precedente iterazione.

C'è un piccolo problema qui in questo schema che manca il "caso base", cioè il caso in cui si può abbinare senza l'auto-riferimento. Un caso base è richiesto perché gruppo 1 inizia "inizializzata"; non ha ancora (nemmeno una stringa vuota) catturato niente, quindi un tentativo di auto-riferimento sarà sempre sicuro.

Ci sono molti modi per aggirare questo, ma per ora limitiamoci a fare l'abbinamento autoreferenzialità opzionale , vale a dire \1?. Questo può o non può funzionare perfettamente, ma facciamo solo vedere che cosa che fa, e se c'è qualche problema, allora dovremo attraversare quel ponte quando sarà il momento. Inoltre, aggiungeremo qualche altro casi di test, mentre siamo a questo.

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);

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

L'uscita è ora ( come visto in 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! Sembra che siamo davvero vicini alla soluzione ora! Siamo riusciti a ottenere 1 gruppi di "contare" con auto-riferimento! Ma attesa ... qualcosa non va con il secondo e gli ultimi casi di test !! Non ci sono abbastanza bs, e in qualche modo contati sbagliato! Esamineremo perché questo è accaduto nella fase successiva.

Lezione :. Un modo per "inizializzare" un gruppo di auto-riferimento è quello di rendere la ricerca opzionale di auto-riferimento

---

Passo 4½: capire cosa è andato storto

Il problema è che da quando abbiamo fatto l'abbinamento opzionale di auto-riferimento, il "contatore" in grado di "reset" di nuovo a 0 quando non ci sono abbastanza b di. Cerchiamo di esaminare attentamente ciò che accade ad ogni iterazione del nostro modello con aaaaabbb come input.

 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! Sul nostro 4 ° iterazione, potevamo ancora corrispondere \1, ma non siamo riusciti a corrispondere \1b! Dal momento che consentano l'abbinamento autoreferenzialità di essere facoltativa con \1?, i Backtracks motore e preso l'opzione "no grazie", che poi ci permette di abbinare e cattura solo b!

Do nota, tuttavia, che, ad eccezione proprio alla prima iterazione, si può sempre corrispondere solo il \1 autoreferenzialità. Questo è ovvio, naturalmente, dal momento che è ciò cheabbiamo appena catturato sul nostro precedente iterazione, e nella nostra messa a punto siamo in grado di corrispondere sempre di nuovo (ad esempio se abbiamo catturato bbb ultima volta, abbiamo la garanzia che ci saranno ancora bbb, ma ci può essere o non essere bbbb questa volta).

Lezione : Attenzione alle backtracking. Il motore regex farà tanto backtracking come si permettono fino a quando i dati corrispondenze di pattern. Questo può influire sulle prestazioni (cioè catastrofica backtracking ) e / o correttezza.

---

Fase 5: padronanza di sé in soccorso

La "correzione" dovrebbe essere ovvio: combinare opzionale ripetizione con possessivo quantifier. Cioè, invece di semplicemente ?, uso ?+ invece (ricordiamo che una ripetizione che viene quantificata come possessivo non backtrack, anche se tale "cooperazione" può tradursi in una partita del modello generale).

In termini molto informali, questo è ciò che dice ?+, ? e ??:

  

?+

     

  
• (opzionale) "Non deve essere lì"      
    
  • (possessivo) "ma se è lì, è necessario prendere e non mollare!"
    
  

     

?

     

  
• (opzionale) "Non deve essere lì"      
    
  • (greedy) "ma se è si può prendere per il momento,"      
      
    • (backtracking) "ma è possibile che venga chiesto di lasciarlo andare dopo!"
      
    
  

     

??

     

  
• (opzionale) "Non deve essere lì"      
    
  • (riluttante) "e, anche se è che non c'è bisogno di prenderlo appena ancora,"      
      
    • (backtracking) "ma è possibile che venga chiesto di prendere in un secondo momento!"
      
    
  

Nella nostra configurazione, \1 non sarà lì la prima volta, ma sarà sempre c'è qualche tempo dopo, e abbiamo sempre vogliono abbinarlo poi . Così, \1?+ avrebbe compiuto esattamente quello che vogliamo.

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

Ora l'uscita è ( come visto in 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 risolto!!! Ora stiamo contando correttamente, esattamente il modo in cui vogliamo che!

Lezione : imparare la differenza tra ripetizione avido, riluttante, e possessivo. Opzionale-possessivo può essere una combinazione potente.

---

Passo 6: Ultimi ritocchi

Quindi quello che abbiamo in questo momento è un modello che le partite a più volte, e per ogni a che è stato abbinato, v'è un corrispondente b catturato nel gruppo 1. Le termina + quando non ci sono più a, o se l'affermazione non è riuscito perché non v'è un corrispondente b un a.

Per finire il lavoro, abbiamo semplicemente bisogno di aggiungere al nostro modello \1 $. Questo è ora un riferimento di quanto gruppo 1 corrisponde, seguita dalla fine della linea di ancoraggio. Le assicura di ancoraggio che non ci sono nessun di b aggiuntivi nella stringa; in altre parole, che in realtà abbiamo un ⁿ b ⁿ .

Ecco il modello finalizzato, con casi di test aggiuntivi, tra cui uno che è di 10.000 caratteri:

$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

Si trova 4 partite: ab, aabb, aaabbb, e il un ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . Ci vuole solo 0.06s per l'esecuzione su ideone.com .

---

Passo 7: Il test Java

Quindi, il modello funziona in PHP, ma l'obiettivo finale è quello di scrivere un modello che works in 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);
}

Il modello funziona come previsto ( come visto in ideone.com ).

---

Ed ora arriviamo alla conclusione ...

Si deve essere detto che la a* nel lookahead, e in effetti il ??"loop + principale", sia permesso di backtracking. I lettori sono incoraggiati a confermare perché questo non è un problema in termini di correttezza, e perché allo stesso tempo rendendo sia possessivo inoltre lavoro (anche se forse miscelazione quantificatore possessivo obbligatoria e non obbligatoria nello stesso modello può portare ad errori di percezione).

Va anche detto che, mentre è pulito che ci sia un'espressione regolare che abbinerà un ⁿ b ⁿ , questo è in non sempre la soluzione "migliore", in pratica. Una soluzione molto migliore è quello di abbinare semplicemente ^(a+)(b+)$, e quindi confrontare la lunghezza delle stringhe catturate dai gruppi 1 e 2 nel linguaggio di programmazione di hosting.

In PHP, può sembrare qualcosa di simile ( come si vede nella ideone.com ):

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

Lo scopo di questo articolo è non per convincere i lettori che regex può fare quasi tutto; chiaramente non può, e anche per le cose che può fare, almeno delega parziale alla lingua di hosting dovrebbe essere considerata se porta a una soluzione più semplice.

Come menzionato in alto, mentre questo articolo è necessariamente etichettato [regex] per StackOverflow, è forse circa più. Mentre certamente non c'è valore nel conoscere asserzioni, riferimenti annidati, quantificatore possessivo, ecc, forse la più grande lezione qui è il processo creativo attraverso il quale si può tentare di risolvere i problemi, la determinazione e il duro lavoro che spesso richiede quando si è sottoposti a vari vincoli, la composizione sistematica da varie parti per costruire una soluzione di lavoro, ecc.

---

Materiale Bonus! PCRE modello ricorsivo!

Dato che abbiamo fatto portare fino PHP, ha bisogno di essere detto che PCRE supporta modello ricorsivo e subroutine. Così, a seguito modello funziona per preg_match ( come visto in ideone.com ):

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

regex del Attualmente Java non supporta modello ricorsivo.

---

Ancora più materiale bonus! Abbinamento un ⁿ b ⁿ c ⁿ !!

Quindi, abbiamo visto come abbinare un ⁿ b ⁿ che non è regolare, ma ancora priva di contesto, ma può abbiamo anche abbinare un ⁿ b ⁿ c ⁿ , che non è nemmeno context-free?

La risposta è, ovviamente, YES I lettori sono invitati a cercare di risolvere questo da soli, ma la soluzione si riportano di seguito (con implementazione in Java su ideone.com ).

  

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

Answer 2

Dato che nessuna menzione è stata fatta di PCRE sostenere modelli ricorsivi, Vorrei solo far notare l'esempio più semplice e più efficiente di PCRE che descrive la lingua in questione:

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

Answer 3

Come indicato nella domanda - con .NET gruppo, i modelli di tipo bilanciamento un ⁿ b ⁿ c ⁿ d ⁿ ... z ⁿ può essere abbinato facilmente come

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

Ad esempio: http://www.ideone.com/usuOE

---

Modifica

C'è anche un modello di PCRE per la lingua generalizzata con il modello ricorsivo, ma è necessario un lookahead. Non credo che questa è una traduzione diretta di quanto sopra.

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

Ad esempio: http://www.ideone.com/9gUwF