I gruppi atomici di espressioni regolari sono distributivi?

Question

I gruppi di espressioni regolari sono distributivi?

I.e. è (?>A?B?) sempre equivalente a (?>A?)(?>B?)?

In caso contrario, fornire un esempio di contatore.

Answer 1

gruppi atomici in generale

1. Il gruppo atomica (?>regex1|regex2|regex3) considera solo il primo successo di abbinamento all'interno di esso. In altre parole, non consente il backtracking.

2. I regex vengono valutati da sinistra a destra, quindi si esprime l'ordine con cui si intende far coincidere le cose. Il motore parte dalla prima posizione, cercando di fare una partita di successo, tornando indietro se necessario. Se qualsiasi percorso attraverso l'espressione porta a una corrispondenza riuscita, allora corrisponderà in quella posizione.

3. I gruppi atomici non sono distributivi. Considerare questi modelli valutati su ABC: (?>(AB?))(?>(BC)) (nessuna corrispondenza) e (?>(AB?)(BC)) (corrisponde a ABC).

gruppi atomici con tutti i componenti opzionali

Ma, lo scenario in cui entrambe le parti sono opzionali possono essere diversi.

Considerando un gruppo atomico con 2 parti facoltative opzionali A e B ((A)? e (B)?). In qualsiasi posizione, se A corrisponde, può passare a valutare l'opzionale B. Altrimenti, se A non corrisponde, va bene anche perché è opzionale. Pertanto, (A)? corrisponde a qualsiasi posizione. La stessa logica vale per l'opzionale B. La domanda rimanente è se ci possa essere qualche differenza nel backtracking.

Nel caso di tutte le parti opzionali ((?>A?B?)), poiché ogni parte corrisponde sempre, non c'è motivo di tornare indietro nel gruppo atomico, quindi corrisponderà sempre. Quindi, poiché si trova in un gruppo atomico, è vietato il backtracking.

Nel caso di gruppi atomici separati ((?>A?)(?>B?)), ogni parte corrisponde sempre e al motore è vietato il backtracking in entrambi i casi. Ciò significa che i risultati saranno gli stessi.

Per reiterare, il motore può utilizzare solo la prima corrispondenza possibile in (?>A?)(?>B?), che sarà sempre la stessa corrispondenza della prima corrispondenza possibile in (?>A?B?). Pertanto, se il mio ragionamento è corretto, per questo caso speciale , le corrispondenze corrisponderanno allo stesso per più gruppi atomici opzionali come un singolo gruppo atomico con entrambi i componenti facoltativi.

Answer 2

Dato che non è stato specificato, presumo che si riferisca a espressioni regolari Perl, poiché non ho visto l'operatore di raggruppamento (?>) in qualsiasi altra lingua.

Si consideri il seguente:

ra = 'A?' 
rb = 'B?' 

/(?>${ra} ${rb})/x è lo stesso di /(?>${ra})(?>${rb})/x.

In questo caso, sì, funziona in entrambi i casi; tuttavia, poiché (?>) disattiva il backtracking, questo non è il caso con alcuni altri valori di ra e rb.

Ad esempio, dato:

ra = 'A*' 
rb = 'AB*' 

/(?>${ra} ${rb})/x = /(?>${ra})(?>${rb})/x.

Nel secondo caso, rb non potrebbe mai corrispondere, dal momento che ra consumerebbe un'intera sequenza di A, e non consentirebbe il backtracking. Notare che questo dovrebbe funzionare se si utilizza (?:) come operatore di raggruppamento. Si noti inoltre che, se si utilizzavano i gruppi di cattura , corrispondere allo corrispondesse allo stesso modo, ma gli effetti secondari (assegnazione a \1, \2, ...) sarebbero diversi.