martes, 3 de febrero de 2009

HAL y los trabalenguas (II)

[... continuación de la entrega anterior]

La expresión regular que vamos a diseñar debe ajustarse a todos los fragmentos del flujo de texto entrante que tengan la siguientes formas [Utilizo el signo ¶ para hacer visible los espacios entre las palabras]:

  • {palabra} [caso 1]

  • {palabra¶palabra} [caso 2]

  • {palabra¶palabra¶palabra} [caso 3]

  • etc. [caso n]


El primer caso es muy simple y es muy fácil construir una expresión regular para él. Tal expresión constaría de una llave de apertura, (el carácter '{'), seguida de una palabra, seguida de una llave de cierre (el carácter '}'). Por su parte, una palabra es un conjunto cualquiera de caracteres alfabéticos y/o numéricos ("hola", "HAL", "HAL9000", "2001", etc. son ejemplos de palabras) Un conjunto de caracteres de esta clase se designa mediante la expresión regular [[:alnum:]], donde [:alnum:] es la clase de caracteres alfanuméricos y los corchetes que la engloban ---aquí, en rojo--- [[:alpha:]] designan un conjunto cualquiera de caracteres de la clase englobada por ellos, en este caso, de la clase de los caracteres alfanuméricos. Por tanto, nuestra expresión regular sería:

{[[:alnum:]]}

Para ponerla a prueba vamos a utilizar la propia salida de dict -d jargon para el término hacker. Antes de hacerlo, copiamos esa salida a un fichero, que llamaremos jargon_hacker, con el fin de no sobrecargar el servidor de dict.org con nuestras pruebas.

dict -d jargon hacker >jargon_hacker

El autor ha condescendido en realizar las verificaciones de nuestras expresiones regulares mediante este simple fichero. En realidad, tales verificaciones deberían ser más exhaustivas. En general, un paso fundamental en la solución de un problema es elaborar pruebas exhaustivas de su validez, concretamente, baterías de ejemplos que incluyan todas las posibilidades de manifestación del problema. No obstante, puesto que hacerlo de este modo para el asunto que tenemos entre manos complicaría la exposición, hemos convencido al autor para que haga la vista gorda, en la promesa de que el lector será menos perezoso en el futuro cuando le toque diseñar pruebas semejantes.

Probemos, pues, la expresión regular recién creada [Las comillas que rodean la expresión regular son opcionales, pero convenientes, dado que en otro tipo de expresiones resultan necesarias]:

grep -E -o '{[[:alnum:]]}' jargon_hacker

Antes de ejecutarla, nótese que hemos añadido otra opción a grep, la opción -E (Extended Regular Expression). Con esta opción podemos hacer que nuestra expresión regular se ajuste a las normas modernas para escritura de expresiones regulares, que contiene más opciones que las opciones básicas y obsoletas, las cuales se mantiene por compatibilidad con programas existentes. Aunque esto va a complicar en un aspecto nuestra expresión regular de hoy, merece la pena trabajar, salvo casos excepcionales, con la forma moderna de escritura. Lo que significa que siempre que hablemos a partir de ahora de expresiones regulares nos referiremos a expresiones regulares extendidas en lugar de a expresiones regulares básicas.

La ejecución de la orden no nos devuelve más que una letra y la llave de cierre:

e}
r}
k}
s}
c}
s}
k}
e}

Nuestra expresión regular es evidentemente inválida. No acierta a dar con los fragmentos de texto que nos interesa rescatar del flujo entrante. La explicación precedente parece, pues, errónea en algún punto.

En realidad, la expresión es correcta, pero incompleta. Y eso que le falta no es deducible sin más, requiere una explicación aparte.

Vayamos al primer detalle fundamental. Las expresiones regulares pueden recibir, y frecuentemente lo hacen, un especificador numérico. En nuestra expresión anterior hemos indicado a grep que busque algo con un único carácter alfanumérico entre llaves. Para indicar que queremos que busque uno o más de un carácter alfanumérico añadimos al conjunto de caracteres alfanuméricos el signo '+'.

El segundo problema es que el carácter de llave de apertura ('{') no aparece en la respuesta, aunque forma parte de la expresión regular. Da la sensación de que grep no lo tiene en cuenta, de que es invisible para él. La causa de ello es que la implementación de grep que nuestra distribución ha instalado (GNU grep) requiere que este signo se enmarque entre corchetes ([{]) cuando forma parte de la expresión regular y carece de un significado especial, como sucede en nuestro caso. [El lector curioso puede leer la página de manual grep(1), subsección Basic vs Extended Regular Expressions si desea mayor información sobre este abstruso tema].

Debemos, en consecuencia, reconstruir nuestra expresión de esta forma [los añadidos van en rojo]:

# Modelo final para el caso 1
[{][[:alnum:]]+}

El modelo se puede verificar como antes:

grep -E -o '[{][[:alnum:]]+}' jargon_hacker

Que nos devuelve un resultado satisfactorio:

{cracker}
{bogus}
{geek}
{wannabee}

Bien. Acabamos de crear una expresión regular para que grep nos devuelva las expresiones del tipo {palabra}, el caso básico de las que pueden aparecer en el artículo del Jargon File.

El verdadero problema surge con los casos en que el numero de palabras entre llaves es indeterminado.

Podemos comenzar a hacernos una idea de lo que en tales casos sucede, tomando como punto de partida {palabra¶palabra}.

La expresión regular para un caso como éste debe contar también con el espacio que hay entre las palabras. Conviene ser precavido y pensar que el tipógrafo del artículo del Jargon pudo introducir por error tabuladores en lugar de espacios. O sea, que nos conviene pensar que lo que separa las dos palabras puede ser un espacio (o varios espacios) o un tabulador (o varios, si el tipógrafo estaba dormido). La forma de designar en una expresión regular la clase de estos "espacios" en blanco es [:blank:]. Un conjunto de caracteres de tal clase, análogamente a lo que sucedía con la clase [:alnum:], se designa mediante la expresión [[:blank:]].

En consecuencia, una expresión regular para el caso {palabra¶palabra} se escribiría así:

[{][[:alnum:]]+[[:blank:]]+[[:alnum:]]+}

Y una prueba de verificación de su resultado sería:

grep -E -o '[{][[:alnum:]]+[[:blank:]]+[[:alnum:]]+}' jargon_hacker

La cual nos devuelve lo que esperamos:

{hack value}
{the network}
{Internet address}
{hacker ethic}

Ahora bien, con el nuevo modelo hemos perdido lo que el primer modelo nos proporcionaba: quedan fuera los fragmentos de una sola palabra entre llaves.

Si analizamos la situación con mayor atención, veremos que es posible considerar el caso 1 ({palabra}) como un tipo especial del caso 2 ({palabra¶palabra}), justamente aquél en que el conjunto formado por la última palabra y su espacio precedente (¶palabra) ocurre 0 veces.

Con un poco más de reflexión llegaremos a la conclusión de que tanto los casos vistos como cualesquiera otros más complejos no son sino casos particulares de un caso genérico {palabra¶palabra} donde ¶palabra puede suceder de 0 a n veces.

Para escribir mediante una expresión regular el conocimiento alcanzado sobre esta estructura textual necesitamos un nuevo constructo lingüístico, a saber, una forma de agrupar conjuntos de caracteres pertenecientes a clases diferentes, en nuestro caso los conjuntos [[:blank:]] y [[:alnum:]]. La forma de conseguirlo es bastante natural: encerrar entre paréntesis el grupo en cuestión:

([[:blank:]]+[[:alnum:]]+)

Sobre este conjunto ---en el encajará el fragmento de texto ¶palabra--- se debe finalmente establecer la especificación numérica correspondiente (cero o más de cero veces). El signo para especificar cero o más de cero es '*'. Por tanto, la expresión regular completa sería la siguiente:

# Modelo para todo caso
[{][[:alnum:]]+([[:blank:]]+[[:alnum:]]+)*}

Pidamos a HAL que realice la prueba final:

grep -E -o '[{][[:alnum:]]+([[:blank:]]+[[:alnum:]]+)*}' jargon_hacker

¡Bingo! El resultado es exactamente el que queremos:

{hack value}
{cracker}
{the network}
{Internet address}
{hacker ethic}
{bogus}
{geek}
{wannabee}

Y naturalmente también cazará fragmentos con más y más palabras entre llaves. El curioso puede comprobarlo si le apetece:

echo 'esto es {una prueba más dura}, HAL' \
| grep -E -o '[{][[:alnum:]]+([[:blank:]]+[[:alnum:]]+)*}'

¿Hemos llegado al final del camino en nuestra tarea con las monstruosas REs? Sí y no. Sí, porque la solución es correcta. No, porque es demasiado complicada para un caso tan simple. ¿Es necesario llegar a tal extremo de complejidad para algo aparentemente trivial como extraer una o varias palabras entre llaves? Cualquier lector con un sentido estético pensará que no, que tiene que haber otro medio más sencillo. Una solución excesivamente compleja puede funcionar, puede ser más que suficiente para HAL, pero no para el ser humano sensible, que estima la sencillez y la belleza en un grado muy alto. Al fin y al cabo otros seres humanos pueden tener que leer esta clase de monstruos y no vamos a ser tan crueles con sus ojos como para contentarnos tan fácilmente.

Volvamos a empezar por el principio. Cuestionemos la forma misma de concebir inicialmente el problema. Un fragmento de texto entre llaves es algo más sencillo que una serie de palabras entre llaves. ¿Por qué no intentar pensar que es simplemente eso, un fragmento de texto entre llaves y nada más, un conjunto de cualquier clase de caracteres, caracteres alfabéticos o numéricos o espacios o lo que sea? La forma de designar un clase de caracteres de cualquier tipo en una expresión regular es [[:print:]] (= cualquier conjunto de caracteres imprimibles).

Probemos con esta expresión del nuevo concepto:

grep -E -o '[{][[:print:]]+}' jargon_hacker

Pero HAL, implacable, quiere devolvernos a la dura realidad:

{hack value}
{cracker}
{the network} and {Internet address}
{hacker ethic}
{bogus}). See also {geek}, {wannabee}

No podía ser tan fácil, evidentemente. Pero no hemos estado tan lejos. Si dedicamos un tiempo a mirar el resultado, quizá surja la idea feliz, que no es otra que la de darse cuenta de que, por ejemplo, en la línea de la respuesta

{the network} and {Internet address}

las llaves delimitadoras de nuestro molde [marcadas en rojo] han encajado con la primera y la última de la línea y que todo lo demás [también las llaves marcadas en azul] han encajado con el conjunto de cualesquiera caracteres imprimibles que indicamos en el centro de nuestra expresión regular.

Si tuviésemos un modo de conseguir que grep "cace" el carácter de llave de cierre ('}') que hay entre las llaves inicial y final de la línea citada, es decir, que no lo considere como un carácter más del conjunto de los que puede haber entre dichas llaves, obtendríamos la expresión anhelada.

Existe una forma de indicárselo: construir una expresión regular con un conjunto complementario. Lo que nos interesa en concreto es construir un molde que empiece por '{', siga con cualquier carácter menos la llave de cierre (o, en general cualquier signo de puntuación) y termine por '}'. Cualquier carácter excepto signos de puntuación se designa en una expresión regular mediante [^[:punct:]], donde el signo '^' inmediatamente después del corchete de apertura significa todo excepto lo que sigue a continuación y [:punct:] designa la clase de caracteres de los signos de puntuación, entre los que está nuestra famosa llave.

La solución está a un paso mínimo, el de introducir el especificador numérico oportuno:

# Modelo final
[{][^[:punct:]]+}

Naturalmente siempre podemos limitarnos al caso único de la llave de cierre y no utilizar ninguna clase mayor que lo contenga:

# Modelo final alternativo
[{][^}]+}

Cualquiera de las dos opciones vale.

Ya podemos disfrutar con la respuesta de HAL a nuestra orden definitiva, eficaz y bella:

grep -E -o '[{][^[:punct:]]+}' jargon_hacker


Resumen de HAL y los trabalenguas I y II

  • Una expresión regular (regular expression o RE) es un molde que usan determinadas órdenes para buscar qué fragmentos de texto encajan con él. Mediante ellas es posible localizar fragmentos de texto que correspondan a ciertas estructuras textuales abstractas.

  • Cuando se trata de resolver un problema y no sabemos qué orden puede resultar conveniente para hacerlo, conviene investigar todas las opciones en las órdenes conocidas relacionadas con el asunto del problema antes de lanzarse a la busca y captura de una orden nueva.

  • La solución de un problema debe verificarse para todos los casos posibles mediantes baterías exhaustivas de ejemplos que contemplen todos los casos posibles y que deben diseñarse antes de proceder a la solución del problema.

  • grep -o devuelve los fragmentos del flujo entrante que encajan con la expresión regular que se le da como primer argumento, en lugar de la línea completa en que dichos fragmentos se encuentran.

  • Hay, al menos, dos tipos de expresiones regulares: expresiones regulares extendidas (abreviado, ERE), que es la forma moderna de escribir expresiones regulares y expresiones regulares básicas (abreviado, BRE).

  • grep -E hace que grep interprete las expresiones regulares que le damos como primer argumento como expresiones regulares extendidas.

  • Algunos elementos sintácticos básicos de las expresiones regulares son:

    • Un carácter se representa a sí mismo, salvo que tenga un significado sintáctico especial en la expresión regular. A este tipo de caracteres que se representan a sí mismos se les denomina literales

    • Las clases de caracteres se representan mediante expresiones del tipo [:clase:]. Por ejemplo: [:print:] representa la clase de todos los caracteres imprimibles (casi todos); [:alnum:], las letras y los números; [:punct:], los signos de puntuación, incluidos paréntesis, corchetes y llaves; [:blank:], el espacio y el tabulador.

    • Los conjuntos de elementos se representan enmarcando entre corchetes tales elementos. Por ejemplo, [[:alnum:]] representa un conjunto de caracteres alfanuméricos.

    • Un conjunto complementario de elementos se representa mediante el signo '^' justo después del corchete de apertura que designa el comienzo de la expresión para un conjunto. Por ejemplo, [^[:punct:]] representa el conjunto de caracteres que no son signos de puntuación.

    • Se pueden y se suelen añadir especificaciones numéricas para indicar cuántas veces puede aparecer un elemento de la expresión regular en el texto que debe encajar con ella. Por ejemplo: '+' especifica que el elemento precedente ocurre una o más de una vez; '*' especifica que el elemento precedente ocurre cero o más de cero veces.

    • Las agrupaciones de elementos de una expresión regular se representan enmarcando entre paréntesis dichos elementos. A un grupo de elementos se lo considera como un elemento más y, en cuanto tal, susceptible de recibir las especificaciones que valen para elementos simples.

    • Nota: en la implementación de grep creada por GNU, que es la que incluyen las distribuciones basadas en GNU/Linux, el signo '{' como representante de sí mismo (como literal) debe enmarcarse entre corchetes cuando la expresión regular es una expresión regular extendida.

  • Diseñar una expresión regular es un trabajo creativo y, como tal, susceptible de diferentes aproximaciones y soluciones.

  • La simplicidad y la belleza son aspectos fundamentales a la hora de valorar y construir la solución de un problema.

No hay comentarios:

Publicar un comentario en la entrada