Come possiamo abbinare un ^ nb ^ n con la regex di Java?

Questa è la seconda parte di una serie di articoli di regex educativo. Mostra come possono essere usati lookheadhead e riferimenti annidati per abbinare il languge non regolare a n b n . I riferimenti annidati vengono introdotti per la prima volta in: In che modo questa espressione regolare trova i numeri triangolari?

Una delle lingue non regolari archetipiche è:

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

Questa è la lingua di tutte le stringhe non vuote che consistono in un numero di a seguito da un numero uguale di b . Esempi di stringhe in questa lingua sono ab , aabb , aaabbb .

Questa lingua può essere mostrata non regolare dal lemma del pompaggio . È infatti un linguaggio archetipico privo di contesto , che può essere generato dalla grammatica S → aSb | ab context-free S → aSb | ab S → aSb | ab .

Nondimeno, le implementazioni regex dei giorni nostri riconoscono chiaramente più delle semplici lingue. Cioè, non sono “regolari” dalla definizione formale della teoria del linguaggio. PCRE e Perl supportano la regex ricorsiva e .NET supporta la definizione dei gruppi di bilanciamento. Anche meno caratteristiche “fantasiose”, ad es. Corrispondenza backreference, significa che l’espressione regolare non è regolare.

Ma quanto sono potenti queste caratteristiche “di base”? Possiamo riconoscere L con regex di Java, ad esempio? Possiamo forse combinare accostamenti e riferimenti annidati e avere un modello che funziona con eg String.matches per abbinare stringhe come ab , aabb , aaabbb , ecc.?

Riferimenti

  • perlfaq6: Posso usare le espressioni regolari di Perl per far corrispondere il testo bilanciato?
  • MSDN – Elementi di linguaggio delle espressioni regolari – Definizioni di gruppi di bilanciamento
  • pcre.org – Pagina man di PCRE
  • regular-expressions.info – Lookarounds e Grouping e Backreferences
  • java.util.regex.Pattern

Domande collegate

  • Il lookaround influenza quali lingue possono essere abbinate dalle espressioni regolari?
  • .NET Regex Balancing Group vs Pattern ricorsivi PCRE

La risposta è, inutile dirlo, SÌ! Puoi sicuramente scrivere un modello regex Java per abbinare un n b n . Utilizza un lookahead positivo per l’asserzione e un riferimento annidato per “contare”.

Piuttosto che dare immediatamente il modello, questa risposta guiderà i lettori nel processo di derivazione. Vengono forniti vari suggerimenti mentre la soluzione viene lentamente costruita. In questo aspetto, si spera che questa risposta contenga molto più di un semplice modello regolare di espressioni regolari. Speriamo che i lettori imparino anche come “pensare in regex” e come mettere insieme vari costrutti in modo armonioso, in modo che possano ricavare più schemi da soli in futuro.

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


Passo 1: guarda avanti per asserzione

Iniziamo con un problema più semplice: vogliamo abbinare a+ all’inizio di una stringa, ma solo se è seguito immediatamente da b+ . Possiamo usare ^ per ancorare la nostra corrispondenza, e dal momento che vogliamo solo abbinare il a+ senza il b+ , possiamo usare l’asserzione lookahead (?=…) .

Ecco il nostro modello con un semplice cablaggio di prova:

 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’output è ( come visto su 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 : puoi usare i pattern in lookaround per fare asserzioni.


Passaggio 2: acquisizione in modalità lookahead (e modalità spaziatura libera)

Ora diciamo che anche se non vogliamo che il b+ faccia parte della partita, vogliamo comunque catturarlo nel gruppo 1. Inoltre, poiché prevediamo un pattern più complicato, usiamo il modificatore x per la spaziatura libera quindi possiamo rendere più leggibile la nostra regex.

Basandoci sul nostro precedente frammento PHP, ora abbiamo il seguente schema:

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

L’output è ora ( come visto su ideone.com ):

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

Nota che ad esempio aaa|b è il risultato del join -ing di ciò che ciascun gruppo ha catturato con '|' . In questo caso, il gruppo 0 (ovvero il modello corrispondente) ha catturato aaa e il gruppo 1 catturato b .

Lezione : puoi catturare all’interno di un lookaround. È ansible utilizzare la spaziatura libera per migliorare la leggibilità.


Passaggio 3: Refactoring del lookahead nel “loop”

Prima di poter introdurre il nostro meccanismo di conteggio, è necessario apportare una modifica al nostro modello. Attualmente, il lookahead è al di fuori del “ciclo” di ripetizione + . Questo va bene perché volevamo solo affermare che c’è un b+ segue il nostro a+ , ma quello che vogliamo veramente fare è affermare che per ogni a che abbiniamo all’interno del “loop”, c’è un corrispondente b che lo accompagna .

Non preoccupiamoci del meccanismo di conteggio per ora e facciamo il refactoring come segue:

  • Primo refattatore a+ a (?: a )+ (notare che (?:…) è un gruppo non catturante)
  • Quindi sposta il lookahead all’interno di questo gruppo non catturante
    • Nota che ora dobbiamo “saltare” a* prima di poter “vedere” il b+ , quindi modificare il modello di conseguenza

Quindi ora abbiamo il seguente:

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

L’output è lo stesso di prima ( come visto su ideone.com ), quindi non c’è alcun cambiamento in tal senso. La cosa importante è che ora stiamo facendo l’asserzione ad ogni iterazione del + “loop”. Con il nostro schema attuale, questo non è necessario, ma dopo faremo il gruppo 1 “contare” per noi usando l’auto-riferimento.

Lezione : puoi catturare all’interno di un gruppo non catturante. I lookaround possono essere ripetuti.


Step 4: Questo è il passo in cui iniziamo a contare

Ecco cosa faremo: riscriveremo il gruppo 1 in modo che:

  • Alla fine della prima iterazione del + , quando il primo a è abbinato, dovrebbe catturare b
  • Alla fine della seconda iterazione, quando a altro a è abbinato, dovrebbe catturare bb
  • Alla fine della terza iterazione, dovrebbe acquisire bbb
  • Alla fine della n -esima iterazione, il gruppo 1 dovrebbe acquisire b n
  • Se non ci sono abbastanza b da catturare nel gruppo 1, l’asserzione fallisce semplicemente

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

C’è un piccolo problema qui in quanto a questo modello manca il “caso base”, vale a dire il caso in cui può corrispondere senza l’autoreferenzialità. È necessario un caso base perché il gruppo 1 inizia “non inizializzato”; non ha ancora catturato nulla (nemmeno una stringa vuota), quindi un tentativo di autoreferenzialità fallirà sempre.

Ci sono molti modi per aggirare questo problema, ma per ora facciamo solo la corrispondenza di riferimento automatico opzionale , cioè \1? . Questo potrebbe non funzionare perfettamente, ma vediamo solo che cosa fa, e se c’è qualche problema allora attraverseremo quel ponte quando ci arriveremo. Inoltre, aggiungeremo altri casi di test mentre ci siamo.

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

L’output è ora ( come visto su 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 far “contare” il gruppo 1 usando l’auto-referenza! Ma aspetta … c’è qualcosa di sbagliato nel secondo e negli ultimi casi di test !! Non ce ne sono abbastanza, e in qualche modo ha contato male! Esamineremo perché questo è accaduto nel passaggio successivo.

Lezione : un modo per “inizializzare” un gruppo autoreferenziale è rendere opzionale la corrispondenza autoreferenziale.


Step 4½: Capire cosa è andato storto

Il problema è che, poiché abbiamo reso opzionale la corrispondenza del riferimento automatico, il “contatore” può “resettare” nuovamente a 0 quando non ci sono abbastanza b . Esaminiamo attentamente cosa succede ad ogni iterazione del nostro modello con aaaaabbb come 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! Nella nostra quarta iterazione, potremmo comunque corrispondere a \1 , ma non potremmo corrispondere a \1b ! Dal momento che consentiamo che la corrispondenza autoreferenziale sia facoltativa con \1? , il motore torna indietro e ha scelto l’opzione “no grazie”, che ci consente di abbinare e catturare solo b !

Si noti, tuttavia, che, tranne che per la prima iterazione, è sempre ansible associare solo l’autoreferenziale \1 . Ovviamente, è ovvio, visto che è ciò che abbiamo appena catturato nella nostra iterazione precedente, e nel nostro setup possiamo sempre abbinarlo di nuovo (ad es. Se abbiamo catturato il bbb ultima volta, ci è garantito che ci sarà ancora il bbb , ma lì potrebbe essere o non essere bbbb questa volta).

Lezione : attenzione al backtracking. Il motore regex farà il backtracking che permetti fino a quando il pattern specificato non coincide. Ciò potrebbe influire sulle prestazioni (es. Backtrack catastrofici ) e / o sulla correttezza.


Step 5: Auto-possesso in soccorso!

La “correzione” dovrebbe ora essere ovvia: combinare la ripetizione facoltativa con il quantificatore possessivo . Cioè, invece di semplicemente ? , usa ?+ invece (ricorda che una ripetizione quantificata come possessiva non torna indietro, anche se tale “cooperazione” può risultare in una corrispondenza del modello generale).

In termini molto informali, questo è cosa ?+ ? e ?? dice:

?+

  • (facoltativo) “Non deve essere lì”
    • (possessivo) “ma se è lì, devi prenderlo e non lasciarlo andare!”

?

  • (facoltativo) “Non deve essere lì”
    • (goloso) “ma se è così puoi prenderlo per ora”
      • (backtracking) “ma potrebbe esserti chiesto di lasciarlo andare più tardi!”

??

  • (facoltativo) “Non deve essere lì”
    • (riluttante) “e anche se non lo si deve ancora prendere”
      • (backtracking) “ma potrebbe esserti chiesto di prenderlo più tardi!”

Nel nostro setup, \1 non ci sarà la prima volta, ma ci sarà sempre in qualsiasi momento e vogliamo sempre abbinarlo. Quindi, \1?+ Otterrebbe esattamente ciò che vogliamo.

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

Ora l’output è ( come visto su 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!!! 

Ecco!!! Problema risolto!!! Ora contiamo correttamente, esattamente nel modo in cui lo vogliamo!

Lezione : impara la differenza tra la ripetizione avida, riluttante e possessiva. Opzionale-possessivo può essere una combinazione potente.


Passaggio 6: tocchi finali

Quindi quello che abbiamo adesso è un modello che corrisponde a a ripetutamente, e per ogni a che è stato abbinato, c’è un corrispondente b catturato nel gruppo 1. Il + termina quando non ci sono più a , o se l’asserzione fallisce perché non c’è è un b corrispondente per un a .

Per completare il lavoro, abbiamo semplicemente bisogno di aggiungere al nostro modello \1 $ . Questo è ora un riferimento all’indietro a quale gruppo 1 corrisponde, seguito dalla fine dell’ancora di riga. L’ancora assicura che non ci siano b extra nella stringa; in altre parole, che in effetti abbiamo un n b n .

Ecco il modello definitivo, con casi di test aggiuntivi, incluso uno 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 

Trova 4 corrispondenze: ab , aabb , aaabbb e il 5000 b 5000 . Ci vogliono solo 0,06 secondi per funzionare su ideone.com .


Passaggio 7: il test Java

Quindi il pattern funziona in PHP, ma l’objective finale è scrivere un pattern che funzioni 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 su ideone.com ).


E ora arriviamo alla conclusione …

Bisogna dire che l’ a* nel lookahead, e in effetti il ​​”main + loop”, permettono entrambi di tornare indietro. I lettori sono incoraggiati a confermare perché questo non è un problema in termini di correttezza, e perché allo stesso tempo rendere entrambi possessivi funzionerebbe anche (anche se forse mescolare quantificatori possessivi obbligatori e non obbligatori nello stesso schema potrebbe portare a percezioni errate).

Va anche detto che mentre è chiaro che esiste un modello regex che corrisponderà a n b n , questa non è sempre la soluzione “migliore” nella pratica. Una soluzione molto migliore è semplicemente abbinare ^(a+)(b+)$ , e quindi confrontare la lunghezza delle stringhe catturate dai gruppi 1 e 2 nel linguaggio di programmazione dell’hosting.

In PHP, può sembrare qualcosa del genere ( come visto in 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 è quello di convincere i lettori che regex può fare quasi tutto; chiaramente non può, e anche per le cose che può fare, prendere in considerazione almeno una parziale delega alla lingua di hosting se porta a una soluzione più semplice.

Come accennato in alto, mentre questo articolo è necessariamente contrassegnato [regex] per StackOverflow, è forse più di questo. Mentre certamente c’è valore nell’apprendere asserzioni, riferimenti annidati, quantificatori possessivi, ecc., Forse la lezione più grande qui è il processo creativo con cui si può provare a risolvere i problemi, la determinazione e il duro lavoro che spesso richiede quando si è soggetti a vari vincoli, la composizione sistematica da varie parti per build una soluzione di lavoro, ecc.


Materiale bonus! Pattern ricorsivo PCRE!

Dato che abbiamo introdotto PHP, è necessario dire che PCRE supporta pattern e subroutine ricorsivi. Quindi, seguendo il modello funziona per preg_match ( come visto su ideone.com ):

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

Attualmente la regex di Java non supporta pattern ricorsivi.


Ancora più materiale bonus! Abbinamento a n b n c n !!

Quindi abbiamo visto come abbinare un n b n che non è regolare, ma è comunque privo di contesto, ma possiamo anche abbinare un n b n c n , che non è nemmeno privo di contesto?

La risposta è, ovviamente, SÌ! I lettori sono incoraggiati a provare a risolverlo da soli, ma la soluzione è fornita di seguito (con implementazione in Java su ideone.com ).

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

Dato che non è stata fatta alcuna menzione di PCRE a supporto dei pattern ricorsivi, vorrei solo sottolineare l’esempio più semplice ed efficiente di PCRE che descrive la lingua in questione:

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

Come menzionato nella domanda – con il gruppo di bilanciamento .NET, i pattern del tipo a n b n c n d n … z n possono essere abbinati facilmente come

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

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


Modificare:

Esiste anche un pattern PCRE per la lingua generalizzata con pattern ricorsivo, ma è necessario un look ahead. Non penso che questa sia 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