Reemplazar múltiples cadenas en una sola pasada

11

Estoy buscando una forma de reemplazar las cadenas de marcador de posición en un archivo de plantilla con valores concretos, con herramientas comunes de Unix (bash, sed, awk, quizás perl). Es importante que el reemplazo se realice en una sola pasada, es decir, lo que ya está escaneado / reemplazado no debe considerarse para otro reemplazo. Por ejemplo, estos dos intentos fallan:

echo "AB" | awk '{gsub("A","B");gsub("B","A");print}'
>> AA

echo "AB" | sed 's/A/B/g;s/B/A/g'
>> AA

El resultado correcto en este caso es, por supuesto, BA.

En general, la solución debería ser equivalente a escanear la entrada de izquierda a derecha para una coincidencia más larga con una de las cadenas de reemplazo dadas, y para cada coincidencia, realizar un reemplazo y continuar desde ese punto en adelante en la entrada (ninguna de las la entrada ya leída ni los reemplazos realizados deben considerarse para las coincidencias). En realidad, los detalles no importan, solo que los resultados del reemplazo nunca se consideran para otro reemplazo, en su totalidad o en parte.

NOTA Solo estoy buscando soluciones genéricas correctas. No proponga soluciones que fallen para ciertas entradas (archivos de entrada, búsqueda y reemplazo de pares), por improbables que puedan parecer.

Ambroz Bizjak
fuente
¿Asumo que son más largos que un personaje? Para esto podrías usar tr AB BA.
Kevin
3
Y, francamente, no me sorprendería si alguien considerara su nota un poco grosera.
Peter
1
¿Cómo espera "obtener solo las soluciones correctas" cuando no ha proporcionado una entrada o salida de muestra?
jasonwryan
1
Me temo que tendrá que hacerlo exactamente como lo describe, analizar desde el principio y reemplazar a medida que avanza, es decir, no con expresiones regulares.
Peter
2
Esta es una pregunta justa, pero la respuesta es que necesita un analizador de máquina de estados , que es lo que proporciona la respuesta de Rici (creo que en un verdadero estilo de hacker). En otras palabras, está subestimando la complejidad de la tarea, por ejemplo, "Quiero analizar genéricamente (HT | X) ML con expresiones regulares" -> La respuesta es NO. No puedes (solo) usar sed. No puedes (solo) usar awk. AFAIK no existe ninguna herramienta que lo haga fuera de la caja. Explotación de Sans rici, tendrías que escribir algo de código.
Ricitos

Respuestas:

10

OK, una solución general. La siguiente función bash requiere 2kargumentos; cada par consta de un marcador de posición y un reemplazo. Depende de usted citar las cadenas apropiadamente para pasarlas a la función. Si el número de argumentos es impar, se agregará un argumento vacío implícito, que eliminará efectivamente las ocurrencias del último marcador de posición.

Ni los marcadores de posición ni los reemplazos pueden contener caracteres NUL, pero puede usar \paisajes C estándar , como \0si necesita NULs (y, en consecuencia, debe escribir \\si desea a \).

Requiere las herramientas de compilación estándar que deben estar presentes en un sistema tipo posix (lex y cc).

replaceholder() {
  local dir=$(mktemp -d)
  ( cd "$dir"
    { printf %s\\n "%option 8bit noyywrap nounput" "%%"
      printf '"%s" {fputs("%s", yyout);}\n' "${@//\"/\\\"}"
      printf %s\\n "%%" "int main(int argc, char** argv) { return yylex(); }"
    } | lex && cc lex.yy.c
  ) && "$dir"/a.out
  rm -fR "$dir"
}

Suponemos que \ya se ha escapado si es necesario en los argumentos, pero debemos escapar de las comillas dobles, si están presentes. Eso es lo que hace el segundo argumento al segundo printf. Como la lexacción predeterminada es ECHO, no debemos preocuparnos por eso.

Ejemplo de ejecución (con tiempos para los escépticos; es solo una computadora portátil barata):

$ time echo AB | replaceholder A B B A
BA

real    0m0.128s
user    0m0.106s
sys     0m0.042s
$ time printf %s\\n AB{0000..9999} | replaceholder A B B A > /dev/null

real    0m0.118s
user    0m0.117s
sys     0m0.043s

Para entradas más grandes, podría ser útil proporcionar un indicador de optimización ccy, para la compatibilidad actual de Posix, sería mejor usarlo c99. Una implementación aún más ambiciosa podría intentar almacenar en caché los ejecutables generados en lugar de generarlos cada vez, pero no son exactamente costosos de generar.

Editar

Si tiene tcc , puede evitar la molestia de crear un directorio temporal y disfrutar del tiempo de compilación más rápido que ayudará en las entradas de tamaño normal:

treplaceholder () { 
  tcc -run <(
  {
    printf %s\\n "%option 8bit noyywrap nounput" "%%"
    printf '"%s" {fputs("%s", yyout);}\n' "${@//\"/\\\"}"
    printf %s\\n "%%" "int main(int argc, char** argv) { return yylex(); }"
  } | lex -t)
}

$ time printf %s\\n AB{0000..9999} | treplaceholder A B B A > /dev/null

real    0m0.039s
user    0m0.041s
sys     0m0.031s
rici
fuente
No estoy seguro de si esto es una broma o no;)
Ambroz Bizjak
3
@ambrozbizjak: Funciona, es rápido para entradas grandes y aceptablemente rápido para entradas pequeñas. Puede que no use las herramientas en las que estaba pensando, pero son herramientas estándar. ¿Por qué sería una broma?
rici 18/06
44
+1 ¡Por no ser una broma! : D
Ricitos
Eso sería POSIX portátil como fn() { tcc ; } <<CODE\n$(gen code)\nCODE\n. Sin embargo, ¿puedo preguntar, esta es una respuesta increíble y la voté tan pronto como la leí, pero no entiendo lo que está sucediendo con la matriz de shell? ¿Qué hace "${@//\"/\\\"}"esto?
mikeserv
@mikeserv: «Para cada argumento como un valor entrecomillado (" $ @ "), reemplace todas las (//) apariciones de una cita (\") con (/) una barra invertida (\\) seguida de una cita (\ ") ». Consulte Expansión de parámetros en el manual de bash.
rici
1
printf 'STRING1STRING1\n\nSTRING2STRING1\nSTRING2\n' |
od -A n -t c -v -w1 |
sed 's/ \{1,3\}//;s/\\$/&&/;H;s/.*//;x
     /\nS\nT\nR\nI\nN\nG\n1/s//STRING2/
     /\nS\nT\nR\nI\nN\nG\n2/s//STRING1/
     /\\n/!{x;d};s/\n//g;s/./\\&/g' |
     xargs printf %b

###OUTPUT###

STRING2STRING2

STRING1STRING2
STRING1

Algo como esto siempre reemplazará cada aparición de sus cadenas de destino solo una vez, ya que ocurren en sedlas secuencias en una mordida por línea. Esta es la forma más rápida que puedo imaginar que lo harías. Por otra parte, yo no escribo C. Pero esto lo hace ocupe de forma fiable delimitadores nulos si lo desea. Vea esta respuesta para ver cómo funciona. Esto no tiene problemas con ningún carácter de shell especial contenido o similar, pero es específico de la ubicación ASCII o, en otras palabras, odno generará caracteres de varios bytes en la misma línea y solo hará uno por cada. Si esto es un problema, querrás agregarlo iconv.

mikeserv
fuente
+1 ¿Por qué dice que solo reemplaza "la aparición más temprana de sus cadenas objetivo"? En la salida parece que los reemplaza a todos. No estoy pidiendo verlo, pero ¿podría hacerse de esta manera sin codificar los valores?
Ricitos
@goldilocks - Sí, pero solo tan pronto como ocurran. Tal vez debería reformular eso. Y sí, podría agregar un medio sedy guardar hasta un valor nulo o algo y luego sedescribir el guión de este; o ponerlo en una función de shell y darle valores a un mordisco por línea como "/$1/"... "/$2/"- tal vez yo también escriba esas funciones ...
mikeserv
Esto no parece funcionar en el caso donde están los marcadores de posición PLACE1, PLACE2y PLA. PLAsiempre gana. OP dice: "equivalente a escanear la entrada de izquierda a derecha para una coincidencia más larga con una de las cadenas de reemplazo dadas" (énfasis agregado)
rici
@rici - gracias. Entonces tendré que hacer los delimitadores nulos. De vuelta en un instante.
mikeserv
@rici: estaba a punto de publicar otra versión, que se encargará de lo que describas, pero mirándolo nuevamente y no creo que deba hacerlo. Dice el más largo para una de las cadenas de reemplazo dadas. Esto hace eso. No hay indicios de que una cadena sea un subconjunto de otra, solo que el valor reemplazado puede serlo. Tampoco creo que iterar sobre una lista sea una forma válida de resolver el problema. Dado el problema tal como lo entiendo, esta es una solución que funciona.
mikeserv
1

Una perlsolución Incluso si algunos declararon que no es posible, encontré uno, pero en general una simple coincidencia y reemplazo no es posible e incluso empeora debido al retroceso de un NFA, el resultado puede ser inesperado.

En general, y esto debe decirse, el problema arroja resultados diferentes que dependen del orden y la longitud de las tuplas de reemplazo. es decir:

A B
AA CC

y la entrada AAAda como resultado BBBo CCB.

Aquí el código:

#!/usr/bin/perl

$v='if (0) {} ';
while (($a,$b)=split /\s+/, <DATA>) {
  $k.=$a.'|';
  $v.='elsif ($& eq \''.$a.'\') {print \''.$b.'\'} ';
}
$k.='.';
$v.='else {print $&;}';

eval "
while (<>) {
  \$_ =~ s/($k)/{$v}/geco;
}";  
print "\n";


__DATA__
A    B
B    A
abba baab
baab abbc
abbc aaba

Checkerbunny:

$ echo 'ABBabbaBBbaabAAabbc'|perl script
$ BAAbaabAAabbcBBaaba

fuente