domingo, 27 de abril de 2014

¿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:

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>

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:

Enlaces


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


(Actualizado 10/07/2014)