Ich hatte den Eindruck, dass grep und awk eine NFA (Non-Deterministic) Regex-Maschine verwendeten.
Das Bild in der Mitte dieser Seite überDas Abgleichen regulärer Ausdrücke kann einfach und schnell seinBestätigen Sie, dass dies der Fall ist.
Es ist bekannt, dass eine NFA-Implementierung angehalten werden kann, wenn die erste Alternierung übereinstimmt. Beispielsweise diese NFA-Maschine aus dem verlinkten ArtikelBetrachten Sie beispielsweise den NFA für abab|abbb:
Welche dem regulären Ausdruck entsprechen, abab|abbberreicht den Übereinstimmungsstatus rechts mit der Zeichenfolge, ababbbbwenn die erste übereinstimmt abab. An diesem Punkt wird es angehalten, da es das Ende erreicht hat, in einem Übereinstimmungsstatus (S10). Es ist nicht erforderlich, weitere Eingaben zu testen, selbst wenn eine weitere Übereinstimmung abbbmöglich ist.
Das heißt, in diesem Code:
echo 'catfish' | grep -Eo 'cat|catfish'
Das Ergebnis sollte sein, catist es aber catfish. Unabhängig davon, ob die Alternierung vertauscht wird, ist das Ergebnis dasselbe.
Warum findet die Grep-Regex-Engine immer die längste Übereinstimmung?
Und ist es möglich, diese Vorgabe zu ändern?
Antwort1
Ich glaube nicht, dass es eine Möglichkeit gibt, dies mit einem POSIX-kompatiblen grepoder zu tun awk, da der Standard tatsächlich die längste Übereinstimmung erfordert (siehe beispielsweise die regex(7)Manpage).
Mit awkkönnen Sie die gewünschte Ausgabe erhalten, indem Sie das awkProgramm und den regulären Ausdruck ändern, zum Beispiel
echo 'SetValue' | awk '{ if (match($0, /Set(Value)?/)) { print substr($0, RSTART, 3); }
In dieser Situation würde ich auf pcregrep(Teil der mit Perl kompatiblen pcre-Bibliothek für reguläre Ausdrücke) zurückgreifen, mit dem Sie eine nummerierte Untergruppe mit Folgendem angeben können -o:
echo SetValue | pcregrep -o1 '(Set)(Value)?'
oder, weil pcre eine Syntax für nicht gieriges Matching hat,
echo SetValue | pcregrep -o0 'Set(Value)??'
Antwort2
Soweit ich das nachvollziehen konnte, stellt sich heraus, dass es tatsächlichzwei NFA-Maschinen:
Traditionelle NFA-Maschine
Eine NFA-Maschine, die zurückverfolgt und für diedie längste Übereinstimmung ganz links konnte nicht immer beachtet werden.POSIX NFA-Engine
Eine nicht rückverfolgende NFA-Engine, die alle Zustände parallel verarbeitet und jede Übereinstimmung in der Eingabezeichenfolge auswählen kann. Die Auswahl der am weitesten links stehenden, längsten Übereinstimmung ist eine POSIX-Anforderung.
Allerdings gibt es eine DFA Backtracking-Maschine (Perl), dieexponentiell explodieren (2^n)wird durch den Text (nicht durch den regulären Ausdruck) gesteuert und könnte das erste einer Alternative auswählen (oder nicht).
Es wird auch gesagt, dass einDFA erkennt alle möglichen Übereinstimmungen parallel.
Und vom Autor des in der Frage verlinkten Artikels:Die re2-Implementierung definiert den Wechsel wie folgt: x|y ==> x oder y (vorzugsweise x), das heißt: den ersten einer Abwechslung vorziehen.
Zusammenfassend lässt sich also sagen, dass es keine Möglichkeit gibt, NFAs oder DFAs tatsächlich darauf zu beziehen, welcher Teil einer Alternative ausgewählt wird, da dies von der spezifischen Implementierung abhängt.
Und nein, ich habe keine Möglichkeit gefunden, einer bestimmten Implementierung mitzuteilen, dass sie ihre Standardeinstellung ändern soll.
Verwandt: