Tuve la impresión de que grep y awk usaban una máquina de expresiones regulares NFA (no determinista).
La imagen a mitad de esta página sobreLa coincidencia de expresiones regulares puede ser simple y rápidaconfirmar que ese es el caso.
Se sabe que la implementación de una NFA podría detenerse cuando se iguale la primera alternancia. Por ejemplo, esta máquina NFA del artículo vinculadoPor ejemplo, considere la NFA para abab|abbb:
Las que corresponden a la expresión regular abab|abbbalcanzarán el estado de coincidencia a la derecha con la cadena ababbbbcuando coincidan con la primera abab. En ese punto se detendrá cuando llegó al final, hasta un estado coincidente (S10). No es necesario probar más entradas, incluso si abbbes posible otra coincidencia.
Es decir, en este código:
echo 'catfish' | grep -Eo 'cat|catfish'
El resultado debería serlo catpero lo es catfish. No importa si se intercambia la alternancia, el resultado es el mismo.
¿Qué hace que el motor grep regex siempre encuentre la coincidencia más larga?
Y, ¿es posible cambiar ese valor predeterminado?
Respuesta1
No creo que haya una manera de hacer esto con un compatible con POSIX grepo awk, porque el estándar requiere la coincidencia más larga (consulte, por ejemplo, la regex(7)página de manual).
Con awkpuede obtener el resultado deseado modificando el awkprograma y la expresión regular, por ejemplo
echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }
En esta situación, recurriría a pcregrep(parte de la biblioteca de expresiones regulares compatible con Perl pcre), que le permite especificar un subgrupo numerado con -o:
echo SetValue | pcregrep -o1 '(Set)(Value)?'
o, debido a que pcre tiene sintaxis para coincidencias no codiciosas,
echo SetValue | pcregrep -o0 'Set(Value)??'
Respuesta2
Hasta donde pude entender esto, resulta que, de hecho, haydos máquinas NFA:
Motor NFA tradicional
Una máquina NFA que retrocede y para la cualla coincidencia más larga situada más a la izquierda no siempre se podía respetar.Motor POSIX NFA
Un motor NFA sin seguimiento que procesa todos los estados en paralelo y puede elegir cualquier coincidencia en la cadena de entrada. La selección de la coincidencia más larga y situada más a la izquierda es un requisito POSIX.
Sin embargo, una máquina de seguimiento de datos DFA (Perl) que puedeexplotar exponencialmente (2^n)está controlado por el texto (no la expresión regular) y podría seleccionar el primero de una alternancia (o no).
También se dice que unDFA reconoce todas las coincidencias posibles en paralelo.
Y, según el autor del artículo vinculado en la pregunta, elLa implementación de re2 define la alternancia como: x|y ==> x o y (prefiero x), es decir: preferir el primero de una alternancia.
Entonces, en conclusión, no hay manera de relacionar realmente los NFA o DFA con qué parte de una alternancia se seleccionará, eso depende de la implementación específica.
Y no, no he encontrado una manera de decirle a una implementación específica que cambie su valor predeterminado.
Relacionado: