Saltar al contenido

regex: expresión regular para coincidir con una línea que no contiene una palabra

septiembre 24, 2021
apple touch icon@2

Dado que nadie más ha dado una respuesta directa a la pregunta que fue preguntado, Lo haré.

La respuesta es que con POSIX grep, es imposible satisfacer literalmente esta solicitud:

grep "<Regex for 'doesn't contain hede'>" input

La razón es que POSIX grep solo se requiere para trabajar con Expresiones regulares básicas, que simplemente no son lo suficientemente potentes para realizar esa tarea (no son capaces de analizar todos los lenguajes regulares debido a la falta de alternancia).

Sin embargo, GNU grep implementa extensiones que lo permiten. En particular, | es el operador de alternancia en la implementación de BRE de GNU. Si su motor de expresión regular admite alternancia, paréntesis y la estrella de Kleene, y puede anclar al principio y al final de la cadena, eso es todo lo que necesita para este enfoque. Sin embargo, tenga en cuenta que los conjuntos negativos [^ ... ] son muy convenientes además de esos, porque de lo contrario, debe reemplazarlos con una expresión de la forma (a|b|c| ... ) que enumera todos los caracteres que no están en el conjunto, lo cual es extremadamente tedioso y demasiado largo, incluso más si todo el conjunto de caracteres es Unicode.

Gracias a la teoría del lenguaje formal, podemos ver cómo se ve esa expresión. Con GNU grep, la respuesta sería algo como:

grep "^([^h]|h(h|eh|edh)*([^eh]|e[^dh]|ed[^eh]))*(|h(h|eh|edh)*(|e|ed))$" input

(encontrado con Grial y algunas optimizaciones adicionales hechas a mano).

También puede utilizar una herramienta que implemente Expresiones regulares extendidas, igual que egrep, para deshacerse de las barras invertidas:

egrep "^([^h]|h(h|eh|edh)*([^eh]|e[^dh]|ed[^eh]))*(|h(h|eh|edh)*(|e|ed))$" input

Aquí hay un script para probarlo (tenga en cuenta que genera un archivo testinput.txt en el directorio actual). Varias de las expresiones presentadas fallan en esta prueba.

#!/bin/bash
REGEX="^([^h]|h(h|eh|edh)*([^eh]|e[^dh]|ed[^eh]))*(|h(h|eh|edh)*(|e|ed))$"

# First four lines as in OP's testcase.
cat > testinput.txt <<EOF
hoho
hihi
haha
hede

h
he
ah
head
ahead
ahed
aheda
ahede
hhede
hehede
hedhede
hehehehehehedehehe
hedecidedthat
EOF
diff -s -u <(grep -v hede testinput.txt) <(grep "$REGEX" testinput.txt)

En mi sistema imprime:

Files /dev/fd/63 and /dev/fd/62 are identical

como se esperaba.

Para aquellos interesados ​​en los detalles, la técnica empleada es convertir la expresión regular que coincide con la palabra en un autómata finito, luego invertir el autómata cambiando cada estado de aceptación a no aceptación y viceversa, y luego convertir el FA resultante de nuevo en una expresión regular.

Como todos han notado, si su motor de expresiones regulares admite una búsqueda anticipada negativa, la expresión regular es mucho más simple. Por ejemplo, con GNU grep:

grep -P '^((?!hede).)*$' input

Sin embargo, este enfoque tiene la desventaja de que requiere un motor de expresión regular de retroceso. Esto lo hace inadecuado en instalaciones que utilizan motores de expresión regular seguros como RE2, que es una de las razones para preferir el enfoque generado en algunas circunstancias.

Usando el excelente de Kendall Hopkins Teoría formal biblioteca, escrita en PHP, que proporciona una funcionalidad similar a Grail, y un simplificador escrito por mí mismo, he podido escribir un generador en línea de expresiones regulares negativas dada una frase de entrada (solo se admiten caracteres alfanuméricos y de espacio actualmente): http://www.formauri.es/personal/pgimeno/misc/non-match-regex/

Para hede produce:

^([^h]|h(h|e(h|dh))*([^eh]|e([^dh]|d[^eh])))*(h(h|e(h|dh))*(ed?)?)?$

que es equivalente a lo anterior.

close