Confusión con la agrupación atómica: ¿en qué se diferencia de la agrupación en la expresión regular de Ruby?

regex ruby-1.9.3

Question

Acabo de rubyinfo los documentos de Atomic Grouping y rubyinfo y me rubyinfo algunas preguntas rápidas de la siguiente manera:

1. ¿Por qué el nombre vino como "agrupación atómica" ? Qué "atomicidad" tiene esa agrupación general que no tiene.
2. ¿En qué se diferencia la agrupación atómica de la agrupación general ?
3. ¿Por qué los grupos atómicos se llaman grupos no capturadores ?

Intenté entender el siguiente código, pero tenía confusión sobre la salida y qué tan diferente funcionan en la misma cadena también.

irb(main):001:0> /a(?>bc|b)c/ =~ "abbcdabcc"
=> 5
irb(main):004:0> $~
=> #<MatchData "abcc">
irb(main):005:0> /a(bc|b)c/ =~ "abcdabcc"
=> 0
irb(main):006:0> $~
=> #<MatchData "abc" 1:"b">

Answer 1

A () tiene algunas propiedades (incluyen aquellas como (?!pattern) , (?=pattern) , etc. y el plano (pattern) ), pero la propiedad común entre todas ellas es la agrupación , lo que hace que el patrón arbitrario sea un unidad única (la unidad es mi propia terminología), que es útil en la repetición.

La captura normal (pattern) tiene la propiedad de captura y grupo . Capturar significa que el texto que coincida con el patrón en el interior se capturará para que pueda usarlo como referencia, en la coincidencia o el reemplazo. El grupo que no captura (?:pattern) no tiene la propiedad de captura, por lo que ahorrará un poco de espacio y acelerará un poco en comparación con (pattern) ya que no almacena el índice inicial y final de la cadena haciendo coincidir el patrón en el interior.

La agrupación atómica (?>pattern) también tiene la propiedad de no captura, por lo que la posición del texto que coincide no se capturará.

La agrupación atómica agrega la propiedad de atómico en comparación con el grupo de captura o no captura. Aquí, significa atómico: en la posición actual, encuentre la primera secuencia (la primera se define por la forma en que el motor coincide de acuerdo con el patrón dado) que coincida con el patrón dentro de la agrupación atómica y manténgala (por lo tanto, no se permite el retroceso).

Un grupo sin atomicidad permitirá el retroceso: seguirá encontrando la primera secuencia, luego, si la coincidencia anticipada falla, retrocederá y encontrará la siguiente secuencia, hasta que se encuentre una coincidencia para toda la expresión regex o se agoten todas las posibilidades.

Ejemplo

Cadena de entrada: bbabbbabbbbc
Patrón: /(?>.*)c/

La primera coincidencia de .* Es bbabbbabbbbc debido al cuantificador codicioso * . Se mantendrá en esta coincidencia, impidiendo que c coincida. El emparejador volverá a intentarlo en la siguiente posición hasta el final de la cadena, y sucederá lo mismo. Así que nada coincide con el regex en absoluto.

Cadena de entrada: bbabbbabbbbc
Patrón: /((?>.*)|b*)[ac]/ , para probar /(((?>.*))|(b*))[ac]/

Hay 3 coincidencias para este regex, que son bba , bbba , bbbbc . Si usa la segunda expresión regular, que es la misma pero con los grupos de captura agregados para fines de depuración, puede ver que todas las coincidencias son el resultado de la coincidencia de b* interior.

Puedes ver el comportamiento de retroceso aquí.

• Sin la agrupación atómica /(.*|b*)[ac]/ , la cadena tendrá una única coincidencia, que es toda la cadena, debido a que el seguimiento al final para coincidir con [ac] . Tenga en cuenta que el motor volverá a .* Para retroceder por 1 carácter, ya que todavía tiene otras posibilidades.

  Pattern: /(.*|b*)[ac]/
  bbabbbabbbbc
  ^             -- Start matching. Look at first item in alternation: .*
  bbabbbabbbbc
              ^ -- First match of .*, due to greedy quantifier
  bbabbbabbbbc
              X -- [ac] cannot match
                -- Backtrack to ()      
  bbabbbabbbbc
             ^  -- Continue explore other possibility with .*
                -- Step back 1 character
  bbabbbabbbbc
              ^ -- [ac] matches, end of regex, a match is found

• Con la agrupación atómica, todas las posibilidades de .* Se cortan y se limitan a la primera coincidencia. Entonces, después de comerse con avidez toda la cadena y no coincidir, el motor tiene que ir por el patrón b* , donde encuentra una coincidencia con la expresión regular.

  Pattern: /((?>.*)|b*)[ac]/
  bbabbbabbbbc
  ^             -- Start matching. Look at first item in alternation: (?>.*)
  bbabbbabbbbc
              ^ -- First match of .*, due to greedy quantifier
                -- The atomic grouping will disallow .* to be backtracked and rematched
  bbabbbabbbbc
              X -- [ac] cannot match
                -- Backtrack to ()
                -- (?>.*) is atomic, check the next possibility by alternation: b*
  bbabbbabbbbc
  ^             -- Starting to rematch with b*
  bbabbbabbbbc
    ^           -- First match with b*, due to greedy quantifier
  bbabbbabbbbc
     ^          -- [ac] matches, end of regex, a match is found

  Los siguientes partidos continuarán desde aquí.

Answer 2

Hace poco tuve que explicar los Grupos atómicos a otra persona y pensé que me gustaría modificar y compartir el ejemplo aquí.

Considere the (big|small|biggest) (cat|dog|bird) .

Partidos en negrita

• El Perro grande
• el pajarito
• el perro mas grande
• el gato pequeño

Para la primera línea, un motor de expresiones regulares encontraría the . Luego continuaría con nuestros adjetivos ( big , small , biggest ), se encuentra big . Habiendo emparejado "grande", procede y encuentra el espacio. Luego mira a nuestras mascotas ( cat , dog , bird ) y encuentra al cat , lo salta y encuentra al dog .

Para la segunda línea, nuestra expresión regular encontraría the . Procedería y miraría a lo big , saltéelo, miraría y encontraría lo small . Luego encuentra "". Mira al "gato", lo salta, mira al "perro", lo salta y encuentra el "pájaro".

Para la tercera línea, nuestra expresión regular encontraría the , Continúa y encuentra un big que coincida con el requisito inmediato , y continúa. No puede encontrar el espacio, por lo que retrocede (rebobina la posición hasta la última elección que hizo). Se salta big , se ve small y se salta. Encuentra más grande que también coincide con el requisito inmediato . Luego encuentra "". Mira al cat y lo salta, y empareja al dog .

Para la cuarta línea, nuestra expresión regular encontraría the . Se procederá a mirar a lo big , saltarlo, mirar y encontrar lo small . Luego encuentra "". Mira y coincide con el cat .

Ahora considere the (?>big|small|biggest) (cat|dog|bird) Observe el grupo atómico ?> los adjetivos.

Partidos en negrita

• El Perro grande
• el pajarito
• el perro mas grande
• el gato pequeño

Para la primera línea, la segunda línea y la cuarta línea, nuestro motor funciona de la misma manera.

Para la tercera línea, nuestra expresión regular encontraría, Continúa y encuentra "grande" que coincida con el requisito inmediato , y continúa. No puede encontrar el espacio, pero el grupo atómico, al ser la última elección hecha por el motor, no permitirá que esa elección sea reexaminada (prohíbe el retroceso). Ya que no puede hacer una nueva elección, la coincidencia tiene que fallar, ya que nuestra expresión simple no tiene otras opciones.

Esto es sólo un resumen básico. Un motor no tendría que mirar a la totalidad del cat para saber que no encaja con el dog , simplemente mirar la c es suficiente. Cuando se trata de hacer coincidir un pájaro, la c en cat y la d en dog son suficientes para decirle al motor que examine otras opciones.

Sin embargo, si tuviera ... ((cat|snake)|dog|bird) , el motor también tendría que examinar, por supuesto, la serpiente antes de pasar al grupo anterior y examinar el perro y el pájaro.

También hay muchas opciones que un motor no puede decidir sin pasar por lo que puede no parecer una coincidencia. Si tiene ((red)?cat|dog|bird) , el motor mirará "r", retroceda, observe el ? cuantificador, ignore el subgrupo (red) y busque una coincidencia.

Answer 3

Un "grupo atómico" es uno en el que la expresión regular nunca retrocederá. Entonces, en su primer ejemplo /a(?>bc|b)c/ si la alternancia bc en el grupo coincide, entonces nunca retrocederá y probará la alternancia b . Si modifica ligeramente su primer ejemplo para que coincida con "abcdabcc" , verá que aún coincide con "abcc" al final de la cadena en lugar de con "abc" al comienzo. Si no usa un grupo atómico, puede retroceder más allá del bc y probar la alternancia b y terminar coincidiendo con el "abc" al comienzo.

En cuanto a la pregunta dos, en qué se diferencia, es solo una reformulación de su primera pregunta.

Y, por último, los grupos atómicos no son "llamados" grupos no capturadores. Ese no es un nombre alternativo para ellos. Los grupos que no capturan son grupos que no capturan su contenido. Por lo general, cuando compara una expresión regular con una cadena, puede recuperar todos los grupos emparejados y, si usa una sustitución, puede usar referencias inversas en la sustitución como /1 para insertar los grupos capturados allí. Pero un grupo que no captura no proporciona esto. El grupo clásico que no captura es (?:pattern) . Un grupo atómico también tiene la propiedad que no captura, por lo que se llama un grupo que no captura.