¿Cómo obtener la ocurrencia más corta usando expresiones regulares?

Introducción

Alguna vez habrás usado expresiones regulares (regular expression), ya sea programando, en la línea de comandos o en algún editor de texto.

¿No te ha pasado que al usar algún comodín de repetición como el * en vez de obtener la ocurrencia más corta obtienes la más larga (que contiene ocurrencias más cortas)?

Por ejemplo, al analizar la cadena XML:

<a>1111</a><a>2222</a><a>3333</a><a>4444</a>

con la expresión regular siguiente para locazizar los elementos (tags) a:

<a>.*</a>

obtienes toda la cadena en vez de únicamente el primer elemento <a>1111</a>.

Ups, hay ambigüedad: encajan varios trozos de la cadena y además encaja toda la cadena. ¿Qué resultado se elige? 

Greediness vs Laziness

El problema es que al diseñar un motor de expresiones regulares, hay que resolver la ambigüedad. Hay dos comportamientos:

1. Greediness (avaricia, codicia): el comodín se expande consumiento el máximo número de caracteres posible. En la documentación se suele denominar modo greedy.
2. Laziness (pereza): el comodín se expande consumiendo el mínimo número de caracteres posible. En la documentación se suele denominar modo lazy, non-greedy o reluctant.

Algunos motores de búsqueda permiten configurar el comportamiento, otros no.

Si te interesa mucho el tema, en estos enlaces se explica (en inglés) muy bien como funcionan los motores de expresiones regulares y sus comportamientos:

• Regex Tutorial - Repetition with Star and Plus - Greedy
  http://www.regular-expressions.info/repeat.html#greedy
• Regex Tutorial - Repetition with Star and Plus - Lazy
  http://www.regular-expressions.info/repeat.html#lazy
• Greedy vs. Reluctant vs. Possessive Quantifiers (ver la respuesta de Anomie)
  http://stackoverflow.com/questions/5319840/greedy-vs-reluctant-vs-possessive-quantifiers/5319978#5319978

Cómo capturar la ocurrencia más corta (non-greedy)

Algunos motores de expresiones regulares han resuelto la ambigüedad utilizando operadores diferentes para los modos greedy y non-greedy.

El operador para 0 o N ocurrencias más conocido es el greedy * mientras que el non-greedy suele ser una variación suya *? en la mayoría de los casos.

A continuación hay ejemplos del operador non-greedy en varios entornos. Para ello, se utiliza la cadena y la expresión regular de la introducción.

En lenguajes interpretados se muestra la lista de ocurrencias, por ser fácil y muy ilustrativo.

En lenguajes compilados, por simplicidad, se reemplazan todas las ocurencias por la palabra Replaced, de modo que mirando el resultado se sabe si el comportamiento fue greedy (Replaced aparecerá sólo una vez) o non-greedy (Replaced aparecerá varias veces).

grep (hay que activar el modo Perl)

echo "<a>1111</a><a>2222</a><a>3333</a><a>4444</a>" | grep -P -o "<a>.*?</a>"

Vim (este caso difiere mucho del resto)

<a>.\{-}<\/a>

Para detectar tags cuyo contenido incluya saltos de línea:

<a>\_.\{-}<\/a>

Perl (ejecutable en línea de comandos)

perl -e 'my @matches= "<a>1111</a><a>2222</a><a>3333</a><a>4444</a>" =~ /<a>.*?<\/a>/g; print (join("\n", @matches), "\n");'

Ruby (ejecutable en línea de comandos)

ruby -e 'puts "<a>1111</a><a>2222</a><a>3333</a><a>4444</a>".scan( /<a>.*?<\/a>/ ).to_a'

PostgreSQL

SELECT regexp_matches('<a>1111</a><a>2222</a><a>3333</a><a>4444</a>', '<a>.*?<\/a>', 'g');

PHP (ejecutable en línea de comandos)

php -r '$matches= array(); $search= preg_match_all("/<a>.*?<\/a>/", "<a>1111</a><a>2222</a><a>3333</a><a>4444</a>", $matches); print_r($matches);'

Java

"<a>1111</a><a>2222</a><a>3333</a><a>4444</a>".replaceAll("<a>.*?</a>", "Replaced")

Javascript

function doReplace() {
  var str= "<a>1111</a><a>2222</a><a>3333</a><a>4444</a>"
  str= str.replace(new RegExp("<a>.*?</a>", "g"), "Replaced");
  alert(str);
}

C++
Para menejar expresiones regulares en C++ haría falta un compilador que soporte por completo C++11 (GCC 4.9) o bibliotecas alternativa como boost o clang.

sed (este comando siempre es greedy)
http://stackoverflow.com/questions/1103149/non-greedy-regex-matching-in-sed

bash (sus funciones/operadores de expresiones regulares como =~ siempre son greedy)
Al parecer, las expresiones regulares POSIX sólo soportan modo greedy.
http://stackoverflow.com/questions/18738576/regex-in-bash-expression

Prúebalo tu mismo

Aquí hay enlaces a varias paǵinas web para probar algunas de las expresiones anteriores directamente on-line:

• Probador de expresiones regulares en Javascript:
  http://www.regular-expressions.info/javascriptexample.html
• Probador de expresiones regulares en Java:
  http://www.regexplanet.com/advanced/java/index.html
• Probador de expresiones regulares en bash:
  http://regexraptor.net/
• Probador de expresiones regulares en Ruby:
  http://rubular.com/   
• Probador de expresiones regulares en PHP/Javascript/Python:  
  http://regex101.com/ 
• Probador de expresiones regulares en PHP: 
  http://www.phpliveregex.com/
• Coliru: C++ online compiler (g++-4.8 -std=c++11)
  http://coliru.stacked-crooked.com/
• Otros
  http://www.freeformatter.com/regex-tester.html

Enlaces

Enlaces de interés relacionados con este artículo:

• How can I make my match non greedy in vim?
  http://stackoverflow.com/questions/1305853/how-can-i-make-my-match-non-greedy-in-vim
• Non greedy matching using ? with grep
  http://stackoverflow.com/questions/19125173/non-greedy-matching-using-with-grep
• Java - Regular expressions - Quantifiers
  download.oracle.com/javase/tutorial/essential/regex/quant.html
• The Many Degrees of Regex Greed
  http://www.rexegg.com/regex-greed.html
• Regex Tutorial - Repetition with Star and Plus - Greedy
  http://www.regular-expressions.info/repeat.html#greedy
• Regex Tutorial - Repetition with Star and Plus - Lazy
  http://www.regular-expressions.info/repeat.html#lazy
• Greedy vs. Reluctant vs. Possessive Quantifiers (ver la respuesta de Anomie)
  http://stackoverflow.com/questions/5319840/greedy-vs-reluctant-vs-possessive-quantifiers/5319978#5319978
• perlrequick - Perl regular expressions quick start
  http://perldoc.perl.org/perlrequick.html

(Actualizado 10/07/2014)